前言

最近想自己嘗試從頭做一個(gè)短域名系統(tǒng)堂飞，短域名系統(tǒng)中比較關(guān)鍵一環(huán)的技術(shù)就是一個(gè)較長的網(wǎng)址會(huì)有一到多個(gè)唯一ID去標(biāo)識悔叽，最終達(dá)到短域名的效果。

如果是以實(shí)際情況來說周蹭，流量不大的話這個(gè)很容易實(shí)現(xiàn)效果趋艘，無論是數(shù)據(jù)庫的自增ID還是利用Redis這種單機(jī)的發(fā)號疲恢，都可以解決問題。但是如果自己玩還這樣做的話瓷胧，那就很沒意思了显拳，所以，我會(huì)意淫一個(gè)較大的流量場景搓萧，然后不斷調(diào)整方案解決思路直到達(dá)到滿足假設(shè)流量場景的要求為止(意味著解決思路如果被打臉后還會(huì)回來更新這篇博客杂数，hhhhhhhh)。

常見的ID生成

一般來說瘸洛，數(shù)據(jù)庫的自增ID是我們最常用的揍移，又或者是使用Redis的incr去自增得到一個(gè)遞增的唯一序號。在一般情況下這都是夠用的反肋。但如果有一天那伐，訪問的量級超出了單機(jī)的承受范圍，我們需要擴(kuò)容時(shí)石蔗，這些單機(jī)的自增ID基本上是沒辦法很好的水平擴(kuò)容罕邀。

針對這種情況，在之前在美團(tuán)技術(shù)團(tuán)隊(duì)分享的一篇文章中看到過一種方式抓督，Redis同樣也可以應(yīng)用該思路燃少，比如分布式下的MySQL自增ID，通過調(diào)整每臺MySQL的增長步長來解決铃在，其中增長步長和MySQL的機(jī)器數(shù)量相等阵具，比如有兩臺MySQL機(jī)器，那么設(shè)置第一臺MySQL的初始值為1定铜，接下來的自增結(jié)果是:1阳液，3，5揣炕，7帘皿，9...，第二臺MySQL機(jī)器的初始值設(shè)置為2畸陡，接下來的自增結(jié)果是:2鹰溜，4，6丁恭，8曹动，10...。

這樣雖然能很好的解決多臺MySQL的ID自增問題牲览，但是水平擴(kuò)容卻很麻煩墓陈，當(dāng)你往里面新增一臺機(jī)器的時(shí)候，新機(jī)器的初始值設(shè)置會(huì)變得很困難，需要很多額外的處理贡必。比如最開始只有一臺機(jī)器兔港，按照上面的邏輯來說，會(huì)得到:1仔拟，2衫樊，3，4理逊，5...這樣往后的遞增橡伞。但當(dāng)新添一個(gè)機(jī)器時(shí)，機(jī)器總數(shù)變了晋被，步長也會(huì)改變，所以如果沒有任何處理直接添加第二臺機(jī)器刚盈，就會(huì)得到:2羡洛，4，6藕漱，8欲侮，10...往后的遞增，是不是發(fā)現(xiàn)其中序號4在沒加機(jī)器前已經(jīng)生成過了肋联，這樣會(huì)導(dǎo)很多致重復(fù)威蕉。

我的思路

我的這個(gè)思路不一定正確，只是我自己思考的一個(gè)嘗試橄仍，所以韧涨，如果解決思路有問題請用力打我的臉。

一個(gè)理想的ID生成服務(wù)侮繁，每個(gè)服務(wù)都是無狀態(tài)虑粥，互相沒有依賴和通信，并且每個(gè)節(jié)點(diǎn)都可以生成全局唯一的ID宪哩，這樣一來擴(kuò)容起來就只需要考慮堆機(jī)器娩贷，而不用考慮任何其它因素。

而對于全局唯一的ID生成锁孟，則可以考慮snowflake的方案彬祖，該方案利用系統(tǒng)時(shí)間去遞增ID，不依賴任何存儲(chǔ)系統(tǒng)品抽，該ID的結(jié)構(gòu)如下:

這個(gè)唯一ID的構(gòu)成不依賴其它任何系統(tǒng)如MySQL储笑、Redis等，只依賴系統(tǒng)的時(shí)間桑包，可以說天然無狀態(tài)南蓬。除了ID是順序遞增外(對有些業(yè)務(wù)來說，順序遞增的ID不太友好)，對于我想要構(gòu)建的無狀態(tài)ID生成服務(wù)赘方，是很好的選擇烧颖。

但是如果依賴時(shí)間去構(gòu)造ID，就還需要解決一個(gè)問題窄陡，就是系統(tǒng)時(shí)間的回退炕淮。比如在系統(tǒng)NTP同步時(shí)間的時(shí)候，系統(tǒng)時(shí)間就可能會(huì)出現(xiàn)短暫的回退跳夭，這對于依賴系統(tǒng)時(shí)間生成ID的服務(wù)來說涂圆，就意味著生成的ID可能會(huì)重復(fù)，這是不能接受的币叹。

而對于時(shí)間回退的解決方式润歉，網(wǎng)上的解決方案非常多，但是實(shí)現(xiàn)起來都比較復(fù)雜颈抚，所以我選擇改動(dòng)一下snowflake的結(jié)構(gòu)踩衩，換種方式解決一下，我的結(jié)構(gòu)如下:

其中贩汉，時(shí)間戳部分改為由程序自己在內(nèi)存中維護(hù)的自增值驱富，并且最后10bit留給機(jī)器作為編號來確保ID的唯一。而如何確保這部分自增序號不回退匹舞，就可以沿用一下微信團(tuán)隊(duì)分享的一個(gè)簡單的處理思路褐鸥。

如果我們能夠接受序號不是連續(xù)遞增的，回退這個(gè)問題就很好解決赐稽，比如現(xiàn)在生成的ID是1叫榕、2、3又憨，可能后面就會(huì)變成4翠霍、10、11蠢莺、12這樣寒匙。而具體實(shí)現(xiàn)的邏輯則是，內(nèi)存中維護(hù)一個(gè)自增序號和一個(gè)自增序號的上限(max seq)躏将，獲取自增序號時(shí)先檢查當(dāng)前序號+1是否>=自增序號上限锄弱，如果>=自增序號上限，則將這個(gè)自增序號上限擴(kuò)大:自增序號上限(max seq)+=擴(kuò)大步長(step)祸憋，然后持久化這個(gè)值到磁盤文件中会宪，下次重新啟動(dòng)時(shí)則從該文件中獲取到該自增序號上限并同時(shí)賦值給當(dāng)前程序維護(hù)的自增序號。

參考

Leaf——美團(tuán)點(diǎn)評分布式ID生成系統(tǒng)
萬億級調(diào)用系統(tǒng)：微信序列號生成器架構(gòu)設(shè)計(jì)及演變