最近在看sharding-jdbc相關(guān)的資料暖途，此篇文章是對其中涉及的分布式ID生成算法做一個總結(jié)讹俊。
先拋開sharding-jdbc的實(shí)現(xiàn)策略厕氨，我們來介紹一下幾種常見的分布式ID生成算法枕稀。
UUID
這個是最簡單的生成算法杀赢。
優(yōu)點(diǎn)：本地生成辨萍，無網(wǎng)絡(luò)消耗棋恼，性能很高，基本不會有瓶頸锈玉。
缺點(diǎn)：因?yàn)閁UID太長爪飘，所以不利于存儲。在MySQL的InnoDB引擎中拉背，主鍵會做聚集索引师崎，會加重?cái)?shù)據(jù)庫的負(fù)擔(dān)。生成的ID無序椅棺，沒有趨勢遞增性犁罩。其次是安全問題：基于MAC地址生成UUID的算法可能會造成MAC地址泄露。
數(shù)據(jù)庫生成
利用MySQL數(shù)據(jù)庫進(jìn)行ID生成两疚。每次需要生成ID的時候床估，去訪問一次MySQL數(shù)據(jù)庫，取得上次的ID值再加1即可诱渤。
上面這種方案可能會遇到瓶頸問題顷窒，每次生成ID都要訪問數(shù)據(jù)庫。我們可以改進(jìn)為每次訪問數(shù)據(jù)庫不只取一條數(shù)據(jù)，而取出一批數(shù)據(jù)鞋吉，數(shù)據(jù)庫只記錄一次最大ID鸦做，等服務(wù)將這批ID分發(fā)完之后再從數(shù)據(jù)庫重新取出一批ID進(jìn)行分發(fā)。這樣可以降低訪問數(shù)據(jù)庫的次數(shù)谓着。
即使優(yōu)化過得方案MySQL也是單點(diǎn)泼诱，會有高可用問題，假如MySQL掛掉的話整個ID生成服務(wù)就不可用赊锚。解決方案是使用數(shù)據(jù)庫集群治筒，然后每個數(shù)據(jù)庫實(shí)例設(shè)置固定步長，例如DB0從1開始步長為5舷蒲，則生成的ID為1,6,11耸袜，DB1從2開始步長為5，生成的ID為2,7,12牲平。
Twitter snowflake
這種方案是一種以劃分命名空間來生成ID的一種算法堤框，把64-bit分別劃分成多段，分開來標(biāo)示機(jī)器纵柿、時間等蜈抓，在snowflake中的64-bit分別表示如下圖所示：
前41位表示時間，中間10位表示機(jī)器序號昂儒，序列號用來記錄同毫秒內(nèi)產(chǎn)生的不同id沟使。12位（bit）可以表示的最大正整數(shù)是2^{12}-1 = 4095，即可以用0渊跋、1腊嗡、2、3拾酝、....4094這4095個數(shù)字燕少，來表示同一機(jī)器同一時間截（毫秒)內(nèi)產(chǎn)生的4095個ID序號。
Java中64bit的整數(shù)是long類型微宝，所以在Java中SnowFlake算法生成的id是用long來存儲的棺亭。
優(yōu)點(diǎn)：
毫秒數(shù)在高位，自增序列在低位蟋软，整個ID都是趨勢遞增的镶摘。
不依賴數(shù)據(jù)庫等第三方系統(tǒng)。
可以根據(jù)自身業(yè)務(wù)特性分配bit位岳守，非常靈活凄敢。
缺點(diǎn)：
依賴機(jī)器時鐘，如果機(jī)器上時鐘回?fù)苁。瑫?dǎo)致ID重復(fù)或者服務(wù)會處于不可用狀態(tài)涝缝。
Leaf：美團(tuán)分布式ID生成服務(wù)
Leaf是美團(tuán)自主研發(fā)的分布式ID生成算法扑庞，目前已開源。
Leaf有兩種模式
第一種是預(yù)分發(fā)模式：
該模式使用數(shù)據(jù)庫生成ID拒逮，可以看做是上面提到的數(shù)據(jù)庫方案的升級版罐氨，它可以在DB之上掛N個Server，每個Server啟動時滩援，都會去DB拿固定長度的ID List栅隐。因?yàn)镮D是由內(nèi)存分發(fā)，所以也可以做到很高效玩徊。Leaf每次去DB拿固定長度的ID List租悄，然后把最大的ID持久化下來。該模式使用的表結(jié)構(gòu)如下恩袱。
biz_tag用來區(qū)分業(yè)務(wù)泣棋，max_id表示該biz_tag目前所被分配的ID號段的最大值，step表示每次分配的號段長度畔塔。原來獲取ID每次都需要寫數(shù)據(jù)庫潭辈，現(xiàn)在只需要把step設(shè)置得足夠大，比如1000俩檬。那么只有當(dāng)1000個號被消耗完了之后才會去重新讀寫一次數(shù)據(jù)庫萎胰。僅僅存儲一批ID中最大的那一個碾盟，讀寫數(shù)據(jù)庫的頻率從1減小到了1/step棚辽。假設(shè)有,2個Leaf實(shí)例連接同一個數(shù)據(jù)庫時，步長設(shè)為1000冰肴，
Leaf Server 1：從DB加載號段[1屈藐，1000]。
Leaf Server 2：從DB加載號段[1001熙尉，2000]联逻。
某一個Client獲取到的ID序列可能是：1，1001检痰，2001包归，2，1002铅歼，2002……也可能是：1公壤，2，1001椎椰，2001厦幅，2002，2003慨飘，3确憨，4……
該方案有兩個問題：1.在更新DB的時候會出現(xiàn)耗時尖刺，系統(tǒng)最大耗時取決于更新DB號段的時間。2.當(dāng)更新DB號段的時候休弃，如果DB宕機(jī)或者發(fā)生主從切換吞歼，會導(dǎo)致一段時間的服務(wù)不可用。
為了解決這兩個問題塔猾，Leaf進(jìn)行了優(yōu)化浆熔。
雙Buffer優(yōu)化
采用了異步更新的策略，同時通過雙Buffer的方式桥帆，保證無論何時DB出現(xiàn)問題医增，都能有一個Buffer的號段可以正常對外提供服務(wù)，只要DB在一個Buffer的下發(fā)的周期內(nèi)恢復(fù)老虫，就不會影響整個Leaf的可用性叶骨。原理是Leaf服務(wù)內(nèi)部有兩個號段緩存區(qū)segment。當(dāng)前號段已下發(fā)10%時祈匙，如果下一個號段未更新忽刽，則另啟一個更新線程去更新下一個號段。當(dāng)前號段全部下發(fā)完后夺欲，如果下個號段準(zhǔn)備好了則切換到下個號段為當(dāng)前segment接著下發(fā)跪帝，循環(huán)往復(fù)。
該方案可以生成趨勢遞增的ID些阅，同時ID號是可計(jì)算的伞剑，不適用于訂單ID生成場景，比如在兩天中午12點(diǎn)分別下單市埋，通過訂單id號相減就能大致計(jì)算出公司一天的訂單量黎泣。
第二種模式Leaf-snowflake
類snowflake方案，使用zookeeper進(jìn)行snowflake中機(jī)器編號bit位的分配缤谎。
Leaf-snowflake是按照下面幾個步驟啟動的：1.啟動Leaf-snowflake服務(wù)抒倚，連接Zookeeper，在leaf_forever父節(jié)點(diǎn)下檢查自己是否已經(jīng)注冊過（是否有該順序子節(jié)點(diǎn)）坷澡。2.如果有注冊過直接取回自己的workerID（zk順序節(jié)點(diǎn)生成的int類型ID號）托呕，啟動服務(wù)。3.如果沒有注冊過频敛，就在該父節(jié)點(diǎn)下面創(chuàng)建一個持久順序節(jié)點(diǎn)项郊，創(chuàng)建成功后取回順序號當(dāng)做自己的workerID號，啟動服務(wù)姻政。同時對Zookeeper生成機(jī)器號做了弱依賴處理呆抑，即使Zookeeper有問題，也不會影響服務(wù)汁展。Leaf在第一次從Zookeeper拿取workerID后鹊碍，會在本機(jī)文件系統(tǒng)上緩存一個workerID文件厌殉。即使ZooKeeper出現(xiàn)問題，同時恰好機(jī)器也在重啟侈咕，也能保證服務(wù)的正常運(yùn)行公罕。
Leaf也解決了時鐘回?fù)芸赡軐?dǎo)致ID重復(fù)的問題。采用的是重試（開啟了NTP同步的機(jī)器）加報(bào)警的方案耀销。對于如何判斷時間是否發(fā)生回?fù)苈ゾ欤捎玫氖蔷C合對比其余Leaf節(jié)點(diǎn)的系統(tǒng)時間來判斷自身系統(tǒng)時間是否準(zhǔn)確。具體做法是服務(wù)啟動時首先檢查自己是否寫過ZooKeeper leaf_forever節(jié)點(diǎn)：若寫過熊尉，則用自身系統(tǒng)時間與leaf_forever/${self}節(jié)點(diǎn)記錄時間做比較罐柳，若小于leaf_forever/${self}時間則認(rèn)為機(jī)器時間發(fā)生了大步長回?fù)埽?wù)啟動失敗并報(bào)警狰住。若未寫過张吉，證明是新服務(wù)節(jié)點(diǎn)，直接創(chuàng)建持久節(jié)點(diǎn)leaf_forever/${self}并寫入自身系統(tǒng)時間催植，接下來綜合對比其余Leaf節(jié)點(diǎn)的系統(tǒng)時間來判斷自身系統(tǒng)時間是否準(zhǔn)確肮蛹，具體做法是取leaf_temporary下的所有臨時節(jié)點(diǎn)(所有運(yùn)行中的Leaf-snowflake節(jié)點(diǎn))的服務(wù)IP：Port，然后通過RPC請求得到所有節(jié)點(diǎn)的系統(tǒng)時間创南，計(jì)算sum(time)/nodeSize伦忠。若abs( 系統(tǒng)時間-sum(time)/nodeSize ) < 閾值，認(rèn)為當(dāng)前系統(tǒng)時間準(zhǔn)確稿辙，正常啟動服務(wù)昆码，同時寫臨時節(jié)點(diǎn)leaf_temporary/${self} 維持租約。否則認(rèn)為本機(jī)系統(tǒng)時間發(fā)生大步長偏移邓深，啟動失敗并報(bào)警未桥。每隔一段時間(3s)上報(bào)自身系統(tǒng)時間寫入leaf_forever/${self}笔刹。
百度UidGenerator
百度開源的類SnowFlake算法芥备。同Leaf一樣，也提供兩種模式舌菜。
第一種就是標(biāo)準(zhǔn)的snowflake算法的實(shí)現(xiàn)萌壳。
第二種是帶緩存的snowflake。主要通過RingBuffer來實(shí)現(xiàn)日月。最初接觸RingBuffer是在Distruptor中袱瓮，前者是該框架的核心，說起來比較復(fù)雜爱咬，以后會專門寫一下Distruptor中的RingBuffer尺借。這里就暫時留個坑，等寫好RingBuffer后再來補(bǔ)上精拟。
滴滴Tinyid
這個是滴滴開源的分布式ID解決方案燎斩，基于數(shù)據(jù)庫號段算法實(shí)現(xiàn)虱歪，同美團(tuán)Leaf的Segment方式幾乎相同，這里就不詳細(xì)說了栅表，放一個滴滴github地址好了笋鄙，里面的內(nèi)容也比較簡單，有興趣可以去看下
