UidGenerator是百度開源的Java語言實現，
基於Snowflake算法的唯一ID生成器。而且，它非常適合虛擬環境，比如：Docker。另外，它通過消費未來時間克服了雪花算法的併發限制。UidGenerator提前生成ID並緩存在RingBuffer中。 壓測結果顯示，單個實例的QPS能超過6000,000。依賴環境：
- JDK8+
- MySQL（用於分配WorkerId）
snowflake
由下圖可知，雪花算法的幾個核心組成部分：
- 1位sign標識位；
- 41位時間戳；
- 10位workId（數據中心+工作機器，可以其他組成方式）；
- 12位自增序列；
但是百度對這些組成部分稍微調整了一下：
由上圖可知，UidGenerator的時間部分只有28位，這就意味著UidGenerator默認只能承受8.5年（2^28-1/86400/365）。當然，根據你業務的需求，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的話，需要創建一個表：
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，一定要根據你的業務的情況和特點，調整各個字段佔用的位數：
<code><property>
<property>
<property>
<property>/<code>
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的狀態要麼是CANPUT，要麼是CANTAKE。以某個slot的值為例，初始值為0，即CANPUT。接下來會初始化填滿這個RingBuffer，這時候這個slot的值就是1，即CANTAKE。等獲取分佈式ID時取到這個slot的值後，這個slot的值又變為0，以此類推。
RingBuffer Of UID
保存唯一ID的RingBuffer有兩個指針，Tail指針和Cursor指針。
- Tail指針表示最後一個生成的唯一ID。如果這個指針追上了Cursor指針，意味著RingBuffer已經滿了。這時候，不允許再繼續生成ID了。用戶可以通過屬性rejectedPutBufferHandler指定處理這種情況的策略。
- Cursor指針表示最後一個已經給消費的唯一ID。如果Cursor指針追上了Tail指針，意味著RingBuffer已經空了。這時候，不允許再繼續獲取ID了。用戶可以通過屬性rejectedTakeBufferHandler指定處理這種異常情況的策略。
另外，如果你想增強RingBuffer提升它的吞吐能力，那麼需要配置一個更大的boostPower值：
- <property>
CachedUidGenerator的理論講完後，接下來就是它具體是如何實現的了，我們首先看它的申明，它是實現了DefaultUidGenerator，所以，它事實上就是對DefaultUidGenerator的增強：
<code>public class CachedUidGenerator extends DefaultUidGenerator
implements DisposableBean {
......
}/<code>
worker id
CachedUidGenerator的workerId實現繼承自它的父類DefaultUidGenerator，即實例啟動時往表WORKER_NODE插入數據後得到的自增ID值。
接下來深入解讀CachedUidGenerator的核心操作，即對RingBuffer的操作，包括初始化、取分佈式唯一ID、填充分佈式唯一ID等。
初始化
CachedUidGenerator在初始化時除了給workerId賦值，還會初始化RingBuffer。這個過程主要工作有：
- 根據boostPower 的值確定RingBuffer的size；
- 構造RingBuffer，默認paddingFactor為50。這個值的意思是當RingBuffer中剩餘可用ID數量少於50%的時候，就會觸發一個異步線程往RingBuffer中填充新的唯一ID（調用BufferPaddingExecutor中的paddingBuffer()方法，這個線程中會有一個標誌位running控制併發問題），直到填滿為止；
- 判斷是否配置了屬性scheduleInterval，這是另外一種RingBuffer填充機制, 在Schedule線程中, 週期性檢查填充。默認:不配置, 即不使用Schedule線程. 如需使用, 請指定Schedule線程時間間隔, 單位:秒；
- 初始化Put操作拒絕策略，對應屬性rejectedPutBufferHandler。即當RingBuffer已滿, 無法繼續填充時的操作策略。默認無需指定, 將丟棄Put操作, 僅日誌記錄. 如有特殊需求, 請實現RejectedPutBufferHandler接口(支持Lambda表達式)；
- 初始化Take操作拒絕策略，對應屬性rejectedTakeBufferHandler。即當環已空, 無法繼續獲取時的操作策略。默認無需指定, 將記錄日誌, 並拋出UidGenerateException異常. 如有特殊需求, 請實現RejectedTakeBufferHandler接口；
- 初始化填滿RingBuffer中所有slot（即塞滿唯一ID，這一步和第2步驟一樣都是調用BufferPaddingExecutor中的paddingBuffer()方法）；
- 開啟buffer補丁線程（前提是配置了屬性scheduleInterval），原理就是利用ScheduledExecutorService的scheduleWithFixedDelay()方法。
說明：第二步的異步線程實現非常重要，也是UidGenerator解決時鐘回撥的關鍵：在滿足填充新的唯一ID條件時，通過時間值遞增得到新的時間值（lastSecond.incrementAndGet()），而不是System.currentTimeMillis()這種方式，而lastSecond是AtomicLong類型，所以能保證線程安全問題。
取值
RingBuffer初始化有值後，接下來的取值就簡單了。不過，由於分佈式ID都保存在RingBuffer中，取值過程中就會有一些邏輯判斷：
- 如果剩餘可用ID百分比低於paddingFactor參數指定值，就會異步生成若干個ID集合，直到將RingBuffer填滿。
- 如果獲取值的位置追上了tail指針，就會執行Task操作的拒絕策略。
- 獲取slot中的分佈式ID。
- 將這個slot的標誌位只為CANPUTFLAG。
總結
通過上面對UidGenerator的分析可知，CachedUidGenerator方式主要通過採取如下一些措施和方案規避了時鐘回撥問題和增強唯一性：
專注於技術熱點大數據，人工智能，JAVA、Python、 C 、GO、Javascript等語言最新前言技術，及業務痛點問題分析，請關注【編程我最懂】共同交流學習。
閱讀更多 編程我最懂 的文章
