百度开源分布式id生成器uid-generator源码剖析
百度uid-generator源碼
https://github.com/baidu/uid-generator
snowflake算法
uid-generator是基于Twitter開源的snowflake算法實現的。
snowflake將long的64位分為了3部分，時間戳、工作機器id和序列號，位數分配如下。
其中，時間戳部分的時間單位一般為毫秒。也就是說1臺工作機器1毫秒可產生4096個id（2的12次方）。
源碼實現分析
與原始的snowflake算法不同，uid-generator支持自定義時間戳、工作機器id和序列號等各部分的位數，以應用于不同場景。默認分配方式如下。
-
sign(1bit)
固定1bit符號標識，即生成的UID為正數。 -
delta seconds (28 bits)
當前時間，相對于時間基點"2016-05-20"的增量值，單位：秒，最多可支持約8.7年（注意：1. 這里的單位是秒，而不是毫秒！ 2.注意這里的用詞，是“最多”可支持8.7年，為什么是“最多”，后面會講） -
worker id (22 bits)
機器id，最多可支持約420w次機器啟動。內置實現為在啟動時由數據庫分配，默認分配策略為用后即棄，后續可提供復用策略。 -
sequence (13 bits)
每秒下的并發序列，13 bits可支持每秒8192個并發。（注意下這個地方，默認支持qps最大為8192個）
DefaultUidGenerator
DefaultUidGenerator的產生id的方法與基本上就是常見的snowflake算法實現，僅有一些不同，如以秒為為單位而不是毫秒。
DefaultUidGenerator的產生id的方法如下。
protected synchronized long nextId() {long currentSecond = getCurrentSecond();// Clock moved backwards, refuse to generate uidif (currentSecond < lastSecond) {long refusedSeconds = lastSecond - currentSecond;throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);}// At the same second, increase sequenceif (currentSecond == lastSecond) {sequence = (sequence + 1) & bitsAllocator.getMaxSequence();// Exceed the max sequence, we wait the next second to generate uidif (sequence == 0) {currentSecond = getNextSecond(lastSecond);}// At the different second, sequence restart from zero} else {sequence = 0L;}lastSecond = currentSecond;// Allocate bits for UIDreturn bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);}CachedUidGenerator
CachedUidGenerator支持緩存生成的id。
基本實現原理
關于CachedUidGenerator，文檔上是這樣介紹的。
在實現上, UidGenerator通過借用未來時間來解決sequence天然存在的并發限制; 采用RingBuffer來緩存已生成的UID, 并行化UID的生產和消費, 同時對CacheLine補齊，避免了由RingBuffer帶來的硬件級「偽共享」問題. 最終單機QPS可達600萬。
【采用RingBuffer來緩存已生成的UID, 并行化UID的生產和消費】
使用RingBuffer緩存生成的id。RingBuffer是個環形數組，默認大小為8192個，里面緩存著生成的id。
獲取id
會從ringbuffer中拿一個id，支持并發獲取
填充id
RingBuffer填充時機
-
程序啟動時，將RingBuffer填充滿，緩存著8192個id
-
在調用getUID()獲取id時，檢測到RingBuffer中的剩余id個數小于總個數的50%，將RingBuffer填充滿，使其緩存8192個id
-
定時填充（可配置是否使用以及定時任務的周期）
【UidGenerator通過借用未來時間來解決sequence天然存在的并發限制】
因為delta seconds部分是以秒為單位的，所以1個worker 1秒內最多生成的id書為8192個（2的13次方）。
從上可知，支持的最大qps為8192，所以通過緩存id來提高吞吐量。
為什么叫借助未來時間？
因為每秒最多生成8192個id，當1秒獲取id數多于8192時，RingBuffer中的id很快消耗完畢，在填充RingBuffer時，生成的id的delta seconds 部分只能使用未來的時間。
（因為使用了未來的時間來生成id，所以上面說的是，【最多】可支持約8.7年）
源碼剖析
獲取id
@Overridepublic long getUID() {try {return ringBuffer.take();} catch (Exception e) {LOGGER.error("Generate unique id exception. ", e);throw new UidGenerateException(e);}}RingBuffer緩存已生成的id
（注意：這里的RingBuffer不是Disruptor框架中的RingBuffer，但是借助了很多Disruptor中RingBuffer的設計思想，比如使用緩存行填充解決偽共享問題）
RingBuffer為環形數組，默認容量為sequence可容納的最大值（8192個），可以通過boostPower參數設置大小。
tail指針、Cursor指針用于環形數組上讀寫slot：
-
Tail指針
表示Producer生產的最大序號(此序號從0開始，持續遞增)。Tail不能超過Cursor，即生產者不能覆蓋未消費的slot。當Tail已趕上curosr，此時可通過rejectedPutBufferHandler指定PutRejectPolicy -
Cursor指針
表示Consumer消費到的最小序號(序號序列與Producer序列相同)。Cursor不能超過Tail，即不能消費未生產的slot。當Cursor已趕上tail，此時可通過rejectedTakeBufferHandler指定TakeRejectPolicy
CachedUidGenerator采用了雙RingBuffer，Uid-RingBuffer用于存儲Uid、Flag-RingBuffer用于存儲Uid狀態(是否可填充、是否可消費)
由于數組元素在內存中是連續分配的，可最大程度利用CPU cache以提升性能。但同時會帶來「偽共享」FalseSharing問題，為此在Tail、Cursor指針、Flag-RingBuffer中采用了CacheLine 補齊方式。
public class RingBuffer {private static final Logger LOGGER = LoggerFactory.getLogger(RingBuffer.class);/** Constants */private static final int START_POINT = -1; private static final long CAN_PUT_FLAG = 0L; //用于標記當前slot的狀態，表示可以put一個id進去private static final long CAN_TAKE_FLAG = 1L; //用于標記當前slot的狀態，表示可以take一個idpublic static final int DEFAULT_PADDING_PERCENT = 50; //用于控制何時填充slots的默認閾值：當剩余的可用的slot的個數，小于bufferSize的50%時，需要生成id將slots填滿/** The size of RingBuffer's slots, each slot hold a UID */private final int bufferSize; //slots的大小，默認為sequence可容量的最大值，即8192個private final long indexMask; private final long[] slots; //slots用于緩存已經生成的idprivate final PaddedAtomicLong[] flags; //flags用于存儲id的狀態(是否可填充、是否可消費)/** Tail: last position sequence to produce *///Tail指針//表示Producer生產的最大序號(此序號從0開始，持續遞增)。Tail不能超過Cursor，即生產者不能覆蓋未消費的slot。當Tail已趕上curosr，此時可通過rejectedPutBufferHandler指定PutRejectPolicyprivate final AtomicLong tail = new PaddedAtomicLong(START_POINT); ///** Cursor: current position sequence to consume *///表示Consumer消費到的最小序號(序號序列與Producer序列相同)。Cursor不能超過Tail，即不能消費未生產的slot。當Cursor已趕上tail，此時可通過rejectedTakeBufferHandler指定TakeRejectPolicyprivate final AtomicLong cursor = new PaddedAtomicLong(START_POINT);/** Threshold for trigger padding buffer*/private final int paddingThreshold; //用于控制何時填充slots的閾值/** Reject put/take buffer handle policy *///當slots滿了，無法繼續put時的處理策略。默認實現：無法進行put，僅記錄日志private RejectedPutBufferHandler rejectedPutHandler = this::discardPutBuffer;//當slots空了，無法繼續take時的處理策略。默認實現：僅拋出異常private RejectedTakeBufferHandler rejectedTakeHandler = this::exceptionRejectedTakeBuffer; /** Executor of padding buffer *///用于運行【生成id將slots填滿】任務private BufferPaddingExecutor bufferPaddingExecutor;RingBuffer填充時機
-
程序啟動時，將RingBuffer填充滿，緩存著8192個id
-
在調用getUID()獲取id時，檢測到RingBuffer中的剩余id個數小于總個數的50%，將RingBuffer填充滿，使其緩存8192個id
-
定時填充（可配置是否使用以及定時任務的周期）
填充RingBuffer
/*** Padding buffer fill the slots until to catch the cursor*/public void paddingBuffer() {LOGGER.info("Ready to padding buffer lastSecond:{}. {}", lastSecond.get(), ringBuffer);// is still runningif (!running.compareAndSet(false, true)) {LOGGER.info("Padding buffer is still running. {}", ringBuffer);return;}// fill the rest slots until to catch the cursorboolean isFullRingBuffer = false;while (!isFullRingBuffer) {//獲取生成的id，放到RingBuffer中。List<Long> uidList = uidProvider.provide(lastSecond.incrementAndGet());for (Long uid : uidList) {isFullRingBuffer = !ringBuffer.put(uid);if (isFullRingBuffer) {break;}}}// not running nowrunning.compareAndSet(true, false);LOGGER.info("End to padding buffer lastSecond:{}. {}", lastSecond.get(), ringBuffer);}生成id（上面代碼中的uidProvider.provide調用的就是這個方法）
/*** Get the UIDs in the same specified second under the max sequence* * @param currentSecond* @return UID list, size of {@link BitsAllocator#getMaxSequence()} + 1*/protected List<Long> nextIdsForOneSecond(long currentSecond) {// Initialize result list size of (max sequence + 1)int listSize = (int) bitsAllocator.getMaxSequence() + 1;List<Long> uidList = new ArrayList<>(listSize);// Allocate the first sequence of the second, the others can be calculated with the offset//這里的實現很取巧//因為1秒內生成的id是連續的，所以利用第1個id來生成后面的id，而不用頻繁調用snowflake算法long firstSeqUid = bitsAllocator.allocate(currentSecond - epochSeconds, workerId, 0L);for (int offset = 0; offset < listSize; offset++) {uidList.add(firstSeqUid + offset);}return uidList;}?填充緩存行解決“偽共享”
關于偽共享，可以參考這篇文章《偽共享（false sharing），并發編程無聲的性能殺手》
//數組在物理上是連續存儲的，flags數組用來保存id的狀態（是否可消費、是否可填充），在填入id和消費id時，會被頻繁的修改。//如果不進行緩存行填充，會導致頻繁的緩存行失效，直接從內存中讀數據。private final PaddedAtomicLong[] flags;//tail和cursor都使用緩存行填充，是為了避免tail和cursor落到同一個緩存行上。/** Tail: last position sequence to produce */private final AtomicLong tail = new PaddedAtomicLong(START_POINT);/** Cursor: current position sequence to consume */private final AtomicLong cursor = new PaddedAtomicLong(START_POINT) /*** Represents a padded {@link AtomicLong} to prevent the FalseSharing problem<p>* * The CPU cache line commonly be 64 bytes, here is a sample of cache line after padding:<br>* 64 bytes = 8 bytes (object reference) + 6 * 8 bytes (padded long) + 8 bytes (a long value)* @author yutianbao*/ public class PaddedAtomicLong extends AtomicLong {private static final long serialVersionUID = -3415778863941386253L;/** Padded 6 long (48 bytes) */public volatile long p1, p2, p3, p4, p5, p6 = 7L;/*** Constructors from {@link AtomicLong}*/public PaddedAtomicLong() {super();}public PaddedAtomicLong(long initialValue) {super(initialValue);}/*** To prevent GC optimizations for cleaning unused padded references*/public long sumPaddingToPreventOptimization() {return p1 + p2 + p3 + p4 + p5 + p6;}}PaddedAtomicLong為什么要這么設計？
可以參考下面文章
一個Java對象到底占用多大內存？https://www.cnblogs.com/magialmoon/p/3757767.html
寫Java也得了解CPU--偽共享?https://www.cnblogs.com/techyc/p/3625701.html
總結
以上是生活随笔為你收集整理的百度开源分布式id生成器uid-generator源码剖析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： UidGenerator
- 下一篇： 操作系统的极简教程（一）