idGenerator是百度開源的Java語言實(shí)現(xiàn)，基于Snowflake算法的唯一ID生成器。而且，它非常適合虛擬環(huán)境，比如：Docker。另外，它通過消費(fèi)未來時間克服了雪花算法的并發(fā)限制。UidGenerator提前生成ID并緩存在RingBuffer中。 壓測結(jié)果顯示，單個實(shí)例的QPS能超過6000,000。依賴環(huán)境：

1、JDK8+

2、MySQL（用于分配WorkerId）

snowflake

由下圖可知，雪花算法的幾個核心組成部分：

1、1位sign標(biāo)識位；

2、41位時間戳；

3、10位workId（數(shù)據(jù)中心+工作機(jī)器，可以其他組成方式）；

4、12位自增序列；

但是百度對這些組成部分稍微調(diào)整了一下：

由上圖可知，UidGenerator的時間部分只有28位，這就意味著UidGenerator默認(rèn)只能承受8.5年（2^28-1/86400/365）。當(dāng)然，根據(jù)你業(yè)務(wù)的需求，UidGenerator可以適當(dāng)調(diào)整delta seconds、worker node id和sequence占用位數(shù)。

接下來分析百度UidGenerator的實(shí)現(xiàn)。需要說明的是UidGenerator有兩種方式提供：和DefaultUidGenerator和CachedUidGenerator。我們先分析比較容易理解的DefaultUidGenerator。

DefaultUidGenerator

delta seconds

這個值是指當(dāng)前時間與epoch時間的時間差，且單位為秒。epoch時間就是指集成UidGenerator生成分布式ID服務(wù)第一次上線的時間，可配置，也一定要根據(jù)你的上線時間進(jìn)行配置，因?yàn)槟J(rèn)的epoch時間可是2016-09-20，不配置的話，會浪費(fèi)好幾年的可用時間。

worker id

接下來說一下UidGenerator是如何給worker id賦值的，搭建UidGenerator的話，需要創(chuàng)建一個表：

DROP TABLE IF EXISTS WORKER_NODE; CREATE TABLE WORKER_NODE(ID BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY ,HOST_NAME VARCHAR(64) NOT NULL COMMENT 'host name',PORT VARCHAR(64) NOT NULL COMMENT 'port',TYPE INT NOT NULL COMMENT 'node type: ACTUAL or CONTAINER',LAUNCH_DATE DATE NOT NULL COMMENT 'launch date',MODIFIED DATETIME NOT NULL COMMENT 'modified time',CREATED DATEIMTE NOT NULL COMMENT 'created time' )COMMENT='DB WorkerID Assigner for UID Generator',ENGINE = INNODB;

UidGenerator會在集成用它生成分布式ID的實(shí)例啟動的時候，往這個表中插入一行數(shù)據(jù)，得到的id值就是準(zhǔn)備賦給workerId的值。由于workerId默認(rèn)22位，那么，集成UidGenerator生成分布式ID的所有實(shí)例重啟次數(shù)是不允許超過4194303次（即2^22-1），否則會拋出異常。

這段邏輯的核心代碼來自DisposableWorkerIdAssigner.java中，當(dāng)然，你也可以實(shí)現(xiàn)WorkerIdAssigner.java接口，自定義生成workerId。

sequence

核心代碼如下，幾個實(shí)現(xiàn)的關(guān)鍵點(diǎn)：

synchronized保證線程安全；

如果時間有任何的回?fù)?#xff0c;那么直接拋出異常；

如果當(dāng)前時間和上一次是同一秒時間，那么sequence自增。如果同一秒內(nèi)自增值超過2^13-1，那么就會自旋等待下一秒（getNextSecond）；

如果是新的一秒，那么sequence重新從0開始；

protected synchronized long nextId() {long currentSecond = getCurrentSecond();if (currentSecond < lastSecond) {long refusedSeconds = lastSecond - currentSecond;throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);}if (currentSecond == lastSecond) {sequence = (sequence + 1) & bitsAllocator.getMaxSequence();if (sequence == 0) {currentSecond = getNextSecond(lastSecond);}} else {sequence = 0L;}lastSecond = currentSecond;return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence); }

• 總結(jié)

通過DefaultUidGenerator的實(shí)現(xiàn)可知，它對時鐘回?fù)艿奶幚肀容^簡單粗暴。另外如果使用UidGenerator的DefaultUidGenerator方式生成分布式ID，一定要根據(jù)你的業(yè)務(wù)的情況和特點(diǎn)，調(diào)整各個字段占用的位數(shù)：

<property name="timeBits" value="28"/> <property name="workerBits" value="22"/> <property name="seqBits" value="13"/> <property name="epochStr" value="2016-09-20"/>

CachedUidGenerator

CachedUidGenerator是UidGenerator的重要改進(jìn)實(shí)現(xiàn)。它的核心利用了RingBuffer，如下圖所示，它本質(zhì)上是一個數(shù)組，數(shù)組中每個項(xiàng)被稱為slot。UidGenerator設(shè)計(jì)了兩個RingBuffer，一個保存唯一ID，一個保存flag。RingBuffer的尺寸是2^n，n必須是正整數(shù)：

• RingBuffer Of Flag

其中，保存flag這個RingBuffer的每個slot的值都是0或者1，0是CAN_PUT_FLAG的標(biāo)志位，1是CAN_TAKE_FLAG的標(biāo)識位。每個slot的狀態(tài)要么是CAN_PUT，要么是CAN_TAKE。以某個slot的值為例，初始值為0，即CAN_PUT。接下來會初始化填滿這個RingBuffer，這時候這個slot的值就是1，即CAN_TAKE。等獲取分布式ID時取到這個slot的值后，這個slot的值又變?yōu)?，以此類推。

RingBuffer Of UID

保存唯一ID的RingBuffer有兩個指針，Tail指針和Cursor指針。

1、Tail指針表示最后一個生成的唯一ID。如果這個指針追上了Cursor指針，意味著RingBuffer已經(jīng)滿了。這時候，不允許再繼續(xù)生成ID了。用戶可以通過屬性rejectedPutBufferHandler指定處理這種情況的策略。

2、Cursor指針表示最后一個已經(jīng)給消費(fèi)的唯一ID。如果Cursor指針追上了Tail指針，意味著RingBuffer已經(jīng)空了。這時候，不允許再繼續(xù)獲取ID了。用戶可以通過屬性rejectedTakeBufferHandler指定處理這種異常情況的策略。

另外，如果你想增強(qiáng)RingBuffer提升它的吞吐能力，那么需要配置一個更大的boostPower值：

<!-- RingBuffer size擴(kuò)容參數(shù), 可提高UID生成能力.即每秒產(chǎn)生ID數(shù)上限能力 --> <!-- 默認(rèn):3，原bufferSize=2^13, 擴(kuò)容后bufferSize = 2^13 << 3 = 65536 --> <property name="boostPower" value="3"/>

CachedUidGenerator的理論講完后，接下來就是它具體是如何實(shí)現(xiàn)的了，我們首先看它的申明，它是實(shí)現(xiàn)了DefaultUidGenerator，所以，它事實(shí)上就是對DefaultUidGenerator的增強(qiáng)：

public class CachedUidGenerator extends DefaultUidGenerator implements DisposableBean {... ... }

• worker id

CachedUidGenerator的workerId實(shí)現(xiàn)繼承自它的父類DefaultUidGenerator，即實(shí)例啟動時往表WORKER_NODE插入數(shù)據(jù)后得到的自增ID值。

接下來深入解讀CachedUidGenerator的核心操作，即對RingBuffer的操作，包括初始化、取分布式唯一ID、填充分布式唯一ID等。

• 初始化

CachedUidGenerator在初始化時除了給workerId賦值，還會初始化RingBuffer。這個過程主要工作有：

1、根據(jù)boostPower的值確定RingBuffer的size；

2、構(gòu)造RingBuffer，默認(rèn)paddingFactor為50。這個值的意思是當(dāng)RingBuffer中剩余可用ID數(shù)量少于50%的時候，就會觸發(fā)一個異步線程往RingBuffer中填充新的唯一ID（調(diào)用BufferPaddingExecutor中的paddingBuffer()方法，這個線程中會有一個標(biāo)志位running控制并發(fā)問題），直到填滿為止；

3、判斷是否配置了屬性scheduleInterval，這是另外一種RingBuffer填充機(jī)制, 在Schedule線程中, 周期性檢查填充。默認(rèn):不配置, 即不使用Schedule線程. 如需使用, 請指定Schedule線程時間間隔, 單位:秒；

4、初始化Put操作拒絕策略，對應(yīng)屬性rejectedPutBufferHandler。即當(dāng)RingBuffer已滿, 無法繼續(xù)填充時的操作策略。默認(rèn)無需指定, 將丟棄Put操作, 僅日志記錄. 如有特殊需求, 請實(shí)現(xiàn)RejectedPutBufferHandler接口(支持Lambda表達(dá)式)；

5、初始化Take操作拒絕策略，對應(yīng)屬性rejectedTakeBufferHandler。即當(dāng)環(huán)已空, 無法繼續(xù)獲取時的操作策略。默認(rèn)無需指定, 將記錄日志, 并拋出UidGenerateException異常. 如有特殊需求, 請實(shí)現(xiàn)RejectedTakeBufferHandler接口；

6、初始化填滿RingBuffer中所有slot（即塞滿唯一ID，這一步和第2步驟一樣都是調(diào)用BufferPaddingExecutor中的paddingBuffer()方法）；

7、開啟buffer補(bǔ)丁線程（前提是配置了屬性scheduleInterval），原理就是利用ScheduledExecutorService的scheduleWithFixedDelay()方法。

說明：第二步的異步線程實(shí)現(xiàn)非常重要，也是UidGenerator解決時鐘回?fù)艿年P(guān)鍵：在滿足填充新的唯一ID條件時，通過時間值遞增得到新的時間值（lastSecond.incrementAndGet()），而不是System.currentTimeMillis()這種方式，而lastSecond是AtomicLong類型，所以能保證線程安全問題。

取值

RingBuffer初始化有值后，接下來的取值就簡單了。不過，由于分布式ID都保存在RingBuffer中，取值過程中就會有一些邏輯判斷：

1、如果剩余可用ID百分比低于paddingFactor參數(shù)指定值，就會異步生成若干個ID集合，直到將RingBuffer填滿。

2、如果獲取值的位置追上了tail指針，就會執(zhí)行Task操作的拒絕策略。

3、獲取slot中的分布式ID。

4、將這個slot的標(biāo)志位只為CAN_PUT_FLAG。

---

總結(jié)

通過上面對UidGenerator的分析可知，CachedUidGenerator方式主要通過采取如下一些措施和方案規(guī)避了時鐘回?fù)軉栴}和增強(qiáng)唯一性：

自增列：UidGenerator的workerId在實(shí)例每次重啟時初始化，且就是數(shù)據(jù)庫的自增ID，從而完美的實(shí)現(xiàn)每個實(shí)例獲取到的workerId不會有任何沖突。

RingBuffer：UidGenerator不再在每次取ID時都實(shí)時計(jì)算分布式ID，而是利用RingBuffer數(shù)據(jù)結(jié)構(gòu)預(yù)先生成若干個分布式ID并保存。

時間遞增：傳統(tǒng)的雪花算法實(shí)現(xiàn)都是通過System.currentTimeMillis()來獲取時間并與上一次時間進(jìn)行比較，這樣的實(shí)現(xiàn)嚴(yán)重依賴服務(wù)器的時間。而UidGenerator的時間類型是AtomicLong，且通過incrementAndGet()方法獲取下一次的時間，從而脫離了對服務(wù)器時間的依賴，也就不會有時鐘回?fù)艿膯栴}（這種做法也有一個小問題，即分布式ID中的時間信息可能并不是這個ID真正產(chǎn)生的時間點(diǎn)，例如：獲取的某分布式ID的值為3200169789968523265，它的反解析結(jié)果為{"timestamp":"2019-05-02 23:26:39","workerId":"21","sequence":"1"}，但是這個ID可能并不是在"2019-05-02 23:26:39"這個時間產(chǎn)生的）。

總結(jié)

以上是生活随笔為你收集整理的UidGenerator：百度开源的分布式ID服务（解决了时钟回拨问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。