百度開源的分布式唯一ID生成器UidGenerator，解決了時鐘回撥問題

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

依賴環(huán)境：

• JDK8+

• MySQL（用于分配WorkerId）

snowflake

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

• 1位sign標識位；

• 41位時間戳；

• 10位workId（數據中心+工作機器，可以其他組成方式）；

• 12位自增序列；

cdn.xitu.io/2019/5/11/16aa5ac6ebba5511?imageView2/0/w/1280/h/960/format/webp/ignore-error/1">

但是百度對這些組成部分稍微調整了一下：

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

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

DefaultUidGenerator

delta seconds

這個值是指當前時間與epoch時間的時間差，且單位為秒。epoch時間就是指集成UidGenerator生成分布式ID服務第一次上線的時間，可配置，也一定要根據你的上線時間進行配置，因為默認的epoch時間可是2016-09-20，不配置的話，會浪費好幾年的可用時間。

worker id

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

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

這段邏輯的核心代碼來自DisposableWorkerIdAssigner.java中，當然，你也可以實現WorkerIdAssigner.java接口，自定義生成workerId。

sequence

核心代碼如下，幾個實現的關鍵點：

• synchronized保證線程安全；

• 如果時間有任何的回撥，那么直接拋出異常；

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

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

總結

通過DefaultUidGenerator的實現可知，它對時鐘回撥的處理比較簡單粗暴。另外如果使用UidGenerator的DefaultUidGenerator方式生成分布式ID，一定要根據你的業(yè)務的情況和特點，調整各個字段占用的位數：

CachedUidGenerator

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

RingBuffer Of Flag

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

RingBuffer Of UID

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

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

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

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

CachedUidGenerator的理論講完后，接下來就是它具體是如何實現的了，我們首先看它的申明，它是實現了DefaultUidGenerator，所以，它事實上就是對DefaultUidGenerator的增強：

worker id

CachedUidGenerator的workerId實現繼承自它的父類DefaultUidGenerator，即實例啟動時往表WORKER_NODE插入數據后得到的自增ID值。

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

初始化

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

1. 根據boostPower的值確定RingBuffer的size；

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

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

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

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

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

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

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

取值

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

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

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

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

4. 將這個slot的標志位只為CANPUTFLAG。

總結

通過上面對UidGenerator的分析可知，CachedUidGenerator方式主要通過采取如下一些措施和方案規(guī)避了時鐘回撥問題和增強唯一性：

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

• RingBuffer：UidGenerator不再在每次取ID時都實時計算分布式ID，而是利用RingBuffer數據結構預先生成若干個分布式ID并保存。

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