1、引言

很多人一想到IM應用開發，第一印象就是“長連接”、“socket”、“保活”、“協議”這些關鍵詞，沒錯，這些確實是IM開發中肯定會涉及的技術范疇。

但，當你真正開始編寫第一行代碼時，最現實的問題實際上是“聊天消息ID該怎么生成？”這個看似微不足道的小事情。說它看似微不足道，是因為在IM里它太平常了，處處可見它的身影。不過，雖然看似微不足道，但實際卻很重要，因為它的生成算法和生成策略的優劣在某種意義上來說，決定了你的IM應用層某些功能實現的難易度。

有簽于此，即時通訊網專門整理了“IM消息ID技術專題”系列文章，希望能帶給你對這個看似微小但卻很重要的技術點有更深刻的理解和最佳實踐思路。

本文是專題系列文章的第5篇，專門介紹百度開源的分布式消息ID生成器UidGenerator的算法邏輯、實現思路、重點源碼解讀等，或許能帶給你更多的啟發。

學習交流：

- 即時通訊/推送技術開發交流5群：215477170 [推薦]

- 移動端IM開發入門文章：《新手入門一篇就夠：從零開發移動端IM》

（本文同步發布于：http://www.52im.net/thread-2953-1-1.html）

2、專題目錄

本文是“IM消息ID技術專題”系列文章的第5篇，專題總目錄如下：

《IM消息ID技術專題(一)：微信的海量IM聊天消息序列號生成實踐（算法原理篇）》

《IM消息ID技術專題(二)：微信的海量IM聊天消息序列號生成實踐（容災方案篇）》

《IM消息ID技術專題(三)：解密融云IM產品的聊天消息ID生成策略》

《IM消息ID技術專題(四)：深度解密美團的分布式ID生成算法》

《IM消息ID技術專題(五)：百度開源分布式ID生成器UidGenerator介紹》（* 本文）

3、基本介紹

全局ID（常見的比如：IM聊天系統中的消息ID、電商系統中的訂單號、外賣應用中的訂單號等）服務是分布式服務中的基礎服務，需要保持全局唯一、高效、高可靠性。有些時候還可能要求保持單調，但也并非一定要嚴格遞增或者遞減。

全局ID也可以通過數據庫的自增主鍵來獲取，但是如果要求QPS很高顯然是不現實的。

UidGenerator（備用地址）工程是百度開源的基于Snowflake算法的唯一ID生成器（百度對Snowflake算法進行了改進），引入了高性能隊列高性能隊列disruptor中RingBuffer思想，進一步提升了效率。

UidGenerator是Java語言實現的，它以組件形式工作在應用項目中，支持自定義workerId位數和初始化策略,，從而適用于docker等虛擬化環境下實例自動重啟、漂移等場景。 

在技術實現上，UidGenerator有以下關鍵特性：

1）UidGenerator通過借用未來時間來解決sequence天然存在的并發限制；

2）采用RingBuffer來緩存已生成的UID, 并行化UID的生產和消費；

3）同時對CacheLine補齊，避免了由RingBuffer帶來的硬件級「偽共享」問題。

基于以上技術特性，UidGenerator的單機壓力測試數據顯示，其QPS可高達600萬。

依賴的環境：

1）Java8及以上版本（代碼中使用了函數式編程語句等新特性，請見：uid-generator源碼在線版）；

2）MySQL（內置WorkerID分配器, 啟動階段通過DB進行分配; 如自定義實現, 則DB非必選依賴）。

以下是UidGenerator工程的相關資源：

1）完整源碼地址：https://github.com/baidu/uid-generator

2）備用源碼地址：https://github.com/52im/uid-generator

3）源碼在線閱讀：http://docs.52im.net/extend/docs/src/uid-generator/（推薦）

4、什么是Snowflake算法？

4.1 SnowFlake算法原理

友情提示：本節文字內容摘選自《IM消息ID技術專題(四)：深度解密美團的分布式ID生成算法》一文，如果您想了解美團對于SnowFlake算法的理解和應用情況，可詳細閱讀之。

SnowFlake 算法，是 Twitter 開源的分布式 ID 生成算法。其核心思想就是：使用一個 64 bit 的 long 型的數字作為全局唯一 ID。

這 64 個 bit 中，其中 1 個 bit 是不用的，然后用其中的 41 bit 作為毫秒數，用 10 bit 作為工作機器 ID，12 bit 作為序列號。

SnowFlake的ID構成：

（本圖引用自《IM消息ID技術專題(四)：深度解密美團的分布式ID生成算法》）

SnowFlake的ID樣本：

（本圖引用自《IM消息ID技術專題(四)：深度解密美團的分布式ID生成算法》）

給大家舉個例子吧，如上圖所示，比如下面那個 64 bit 的 long 型數字：

1）第一個部分，是 1 個 bit：0，這個是無意義的；

2）第二個部分，是 41 個 bit：表示的是時間戳；

3）第三個部分，是 5 個 bit：表示的是機房 ID，10001；

4）第四個部分，是 5 個 bit：表示的是機器 ID，1 1001；

5）第五個部分，是 12 個 bit：表示的序號，就是某個機房某臺機器上這一毫秒內同時生成的 ID 的序號，0000 00000000。

① 1 bit：是不用的，為啥呢？

因為二進制里第一個 bit 為如果是 1，那么都是負數，但是我們生成的 ID 都是正數，所以第一個 bit 統一都是 0。

② 41 bit：表示的是時間戳，單位是毫秒。

41 bit 可以表示的數字多達 2^41 - 1，也就是可以標識 2 ^ 41 - 1 個毫秒值，換算成年就是表示 69 年的時間。

③ 10 bit：記錄工作機器 ID，代表的是這個服務最多可以部署在 2^10 臺機器上，也就是 1024 臺機器。

但是 10 bit 里 5 個 bit 代表機房 id，5 個 bit 代表機器 ID。意思就是最多代表 2 ^ 5 個機房（32 個機房），每個機房里可以代表 2 ^ 5 個機器（32 臺機器）。

④12 bit：這個是用來記錄同一個毫秒內產生的不同 ID。

12 bit 可以代表的最大正整數是 2 ^ 12 - 1 = 4096，也就是說可以用這個 12 bit 代表的數字來區分同一個毫秒內的 4096 個不同的 ID。理論上snowflake方案的QPS約為409.6w/s，這種分配方式可以保證在任何一個IDC的任何一臺機器在任意毫秒內生成的ID都是不同的。

簡單來說，你的某個服務假設要生成一個全局唯一 ID，那么就可以發送一個請求給部署了 SnowFlake 算法的系統，由這個 SnowFlake 算法系統來生成唯一 ID。

• 1）這個 SnowFlake 算法系統首先肯定是知道自己所在的機房和機器的，比如機房 ID = 17，機器 ID = 12；
• 2）接著 SnowFlake 算法系統接收到這個請求之后，首先就會用二進制位運算的方式生成一個 64 bit 的 long 型 ID，64 個 bit 中的第一個 bit 是無意義的；
• 3）接著 41 個 bit，就可以用當前時間戳（單位到毫秒），然后接著 5 個 bit 設置上這個機房 id，還有 5 個 bit 設置上機器 ID；
• 4）最后再判斷一下，當前這臺機房的這臺機器上這一毫秒內，這是第幾個請求，給這次生成 ID 的請求累加一個序號，作為最后的 12 個 bit。

最終一個 64 個 bit 的 ID 就出來了，類似于： 

（本圖引用自《IM消息ID技術專題(四)：深度解密美團的分布式ID生成算法》）

這個算法可以保證說，一個機房的一臺機器上，在同一毫秒內，生成了一個唯一的 ID。可能一個毫秒內會生成多個 ID，但是有最后 12 個 bit 的序號來區分開來。

下面我們簡單看看這個 SnowFlake 算法的一個代碼實現，這就是個示例，大家如果理解了這個意思之后，以后可以自己嘗試改造這個算法。

總之就是用一個 64 bit 的數字中各個 bit 位來設置不同的標志位，區分每一個 ID。

4.2 SnowFlake算法的代碼實現

SnowFlake 算法的一個典型Java實現代碼，可以參見文章中的第“6.5 方案四：SnowFlake 算法的思想分析”節：《通俗易懂：如何設計能支撐百萬并發的數據庫架構？》，是Jack Jiang曾在某項目中實際使用過的代碼。

4.3 SnowFlake算法的優缺點

對于份布式的業務系統來說，SnowFlake算法的優缺點如下。

► 優點：

1）毫秒數在高位，自增序列在低位，整個ID都是趨勢遞增的；

2）不依賴數據庫等第三方系統，以服務的方式部署，穩定性更高，生成ID的性能也是非常高的；

3）可以根據自身業務特性分配bit位，非常靈活。

► 缺點：

強依賴機器時鐘，如果機器上時鐘回撥，會導致發號重復或者服務會處于不可用狀態。

5、UidGenerator改進后的SnowFlake算法

通過上節，我們知道了原版SnowFlake算法的基本構成。

具體是，原版SnowFlake算法核心組成：

原版SnowFlake算法各字段的具體意義是：

1）1位sign標識位；

2）41位時間戳；

3）10位workId（即5位數據中心id+5位工作機器id）；

4）12位自增序列。

而UidGenerator改進后的SnowFlake算法核心組成如下圖：

簡單來說，UidGenerator能保證“指定機器 & 同一時刻 & 某一并發序列”，是唯一，并據此生成一個64 bits的唯一ID（long），且默認采用上圖字節分配方式。

與原版的snowflake算法不同，UidGenerator還支持自定義時間戳、工作機器id和序列號等各部分的位數，以應用于不同場景（詳見源碼實現）。

如上圖所示，UidGenerator默認ID中各數據位的含義如下：

• 1）sign(1bit)：固定1bit符號標識，即生成的UID為正數。
• 2）delta seconds (28 bits)：當前時間，相對于時間基點"2016-05-20"的增量值，單位：秒，最多可支持約8.7年（注意：(a)這里的單位是秒，而不是毫秒！ (b)注意這里的用詞，是“最多”可支持8.7年，為什么是“最多”，后面會講）。
• 3）worker id (22 bits)：機器id，最多可支持約420w次機器啟動。內置實現為在啟動時由數據庫分配，默認分配策略為用后即棄，后續可提供復用策略。
• 4）sequence (13 bits)：每秒下的并發序列，13 bits可支持每秒8192個并發（注意下這個地方，默認支持qps最大為8192個）。

6、UidGenerator的具體代碼實現分析

通過閱讀UidGenerator的源碼可知，UidGenerator的具體實現有兩種選擇，即 DefaultUidGenerator 和 CachedUidGenerator。我們分別來看看這兩個具體代碼實現的精妙之處。

6.1 DefaultUidGenerator

DefaultUidGenerator 的源碼很清楚的說明了幾個生成ID的關鍵位的實現邏輯。

1）delta seconds（28 bits）：

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

2）worker id（22bits）：

接下來說一下DefaultUidGenerator是如何給worker id賦值的，搭建DefaultUidGenerator的話，需要創建一個表：

DROP DATABASE IF EXISTS `xxxx`;

CREATE DATABASE `xxxx` ;

use `xxxx`;

DROP TABLE IF EXISTS WORKER_NODE;

CREATE TABLE WORKER_NODE

(

    ID BIGINT NOT NULL AUTO_INCREMENT COMMENT 'auto increment id',

    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 TIMESTAMP NOT NULL COMMENT 'modified time',

    CREATED TIMESTAMP NOT NULL COMMENT 'created time',

    PRIMARY KEY(ID)

)

COMMENT='DB WorkerID Assigner for UID Generator', ENGINE = INNODB;

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

3）sequence（13bits）：

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

a. synchronized保證線程安全；

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

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

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

 

（上述源碼節選自：DefaultUidGenerator 類中的 nextId() 方法）

4）小結：

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

<!-- Specified bits & epoch as your demand. No specified the default value will be used -->

    <property name="timeBits" value="29"/>

    <property name="workerBits" value="21"/>

    <property name="seqBits" value="13"/>

    <property name="epochStr" value="2016-09-20"/>

6.2 CachedUidGenerator

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

以下是CachedUidGenerator中的RingBuffer原理示意圖：

擴展知識：什么是RingBuffer？

Ring Buffer的概念，其實來自于Linux內核（Maybe），是為解決某些特殊情況下的競爭問題提供了一種免鎖的方法。這種特殊的情況就是當生產者和消費者都只有一個，而在其它情況下使用它也是必須要加鎖的。

環形緩沖區通常有一個讀指針和一個寫指針。讀指針指向環形緩沖區中可讀的數據，寫指針指向環形緩沖區中可寫的緩沖區。通過移動讀指針和寫指針就可以實現緩沖區的數據讀取和寫入。在通常情況下，環形緩沖區的讀用戶僅僅會影響讀指針，而寫用戶僅僅會影響寫指針。如果僅僅有一個讀用戶和一個寫用戶，那么不需要添加互斥保護機制就可以保證數據的正確性。如果有多個讀寫用戶訪問環形緩沖區，那么必須添加互斥保護機制來確保多個用戶互斥訪問環形緩沖區。

更多具體的 CachedUidGenerator 的代碼實現，有興趣可以仔細讀一讀，也可以前往百度uid-generator工程的說明頁看看具體的算法原理，這里就不再贅述。

簡要的小結一下，CachedUidGenerator方式主要通過采取如下一些措施和方案規避了時鐘回撥問題和增強唯一性：

• 1）自增列：CachedUidGenerator的workerId在實例每次重啟時初始化，且就是數據庫的自增ID，從而完美的實現每個實例獲取到的workerId不會有任何沖突；
• 2）RingBuffer：CachedUidGenerator不再在每次取ID時都實時計算分布式ID，而是利用RingBuffer數據結構預先生成若干個分布式ID并保存；
• 3）時間遞增：傳統的SnowFlake算法實現都是通過System.currentTimeMillis()來獲取時間并與上一次時間進行比較，這樣的實現嚴重依賴服務器的時間。而CachedUidGenerator的時間類型是AtomicLong，且通過incrementAndGet()方法獲取下一次的時間，從而脫離了對服務器時間的依賴，也就不會有時鐘回撥的問題（這種做法也有一個小問題，即分布式ID中的時間信息可能并不是這個ID真正產生的時間點，例如：獲取的某分布式ID的值為3200169789968523265，它的反解析結果為{"timestamp":"2019-05-02 23:26:39","workerId":"21","sequence":"1"}，但是這個ID可能并不是在"2019-05-02 23:26:39"這個時間產生的）。

6.3 小結一下

CachedUidGenerator通過緩存的方式預先生成一批唯一ID列表，可以解決唯一ID獲取時候的耗時。但這種方式也有不好點，一方面需要耗費內存來緩存這部分數據，另外如果訪問量不大的情況下，提前生成的UID中的時間戳可能是很早之前的。而對于大部分的場景來說，DefaultUidGenerator 就可以滿足相關的需求了，沒必要來湊CachedUidGenerator這個熱鬧。

另外，關于UidGenerator比特位分配的建議：

對于并發數要求不高、期望長期使用的應用, 可增加timeBits位數, 減少seqBits位數. 例如節點采取用完即棄的WorkerIdAssigner策略, 重啟頻率為12次/天, 那么配置成{"workerBits":23,"timeBits":31,"seqBits":9}時, 可支持28個節點以整體并發量14400 UID/s的速度持續運行68年.

對于節點重啟頻率頻繁、期望長期使用的應用, 可增加workerBits和timeBits位數, 減少seqBits位數. 例如節點采取用完即棄的WorkerIdAssigner策略, 重啟頻率為24*12次/天, 那么配置成{"workerBits":27,"timeBits":30,"seqBits":6}時, 可支持37個節點以整體并發量2400 UID/s的速度持續運行34年.

7、UidGenerator的吞吐量壓力測試

UidGenerator的測試數據顯示，在MacBook Pro（2.7GHz Intel Core i5, 8G DDR3）上進行的CachedUidGenerator（單實例）的UID吞吐量測試情況如下。

首先：固定住workerBits為任選一個值(如20), 分別統計timeBits變化時(如從25至32, 總時長分別對應1年和136年)的吞吐量, 測試結果如下圖所示： 

再固定住timeBits為任選一個值(如31), 分別統計workerBits變化時(如從20至29, 總重啟次數分別對應1百萬和500百萬)的吞吐量, 測試結果如下圖所示：

由此可見：不管如何配置, CachedUidGenerator總能提供600萬/s的穩定吞吐量，只是使用年限會有所減少，這真的是太棒了！

最后：固定住workerBits和timeBits位數(如23和31), 分別統計不同數目(如1至8,本機CPU核數為4)的UID使用者情況下的吞吐量，測試結果如下圖所示：

8、參考資料

[1] 改進版Snowflake全局ID生成器-uid-generator

[2] UidGenerator

[3] 百度開源分布式id生成器uid-generator源碼剖析

附錄：更多IM開發熱門技術文章

《新手入門一篇就夠：從零開發移動端IM》

《移動端IM開發者必讀(一)：通俗易懂，理解移動網絡的“弱”和“慢”》

《移動端IM開發者必讀(二)：史上最全移動弱網絡優化方法總結》

《從客戶端的角度來談談移動端IM的消息可靠性和送達機制》

《現代移動端網絡短連接的優化手段總結：請求速度、弱網適應、安全保障》

《騰訊技術分享：社交網絡圖片的帶寬壓縮技術演進之路》

《小白必讀：閑話HTTP短連接中的Session和Token》

《IM開發基礎知識補課：正確理解前置HTTP SSO單點登錄接口的原理》

《移動端IM中大規模群消息的推送如何保證效率、實時性？》

《移動端IM開發需要面對的技術問題》

《開發IM是自己設計協議用字節流好還是字符流好？》

《請問有人知道語音留言聊天的主流實現方式嗎？》

《IM消息送達保證機制實現(一)：保證在線實時消息的可靠投遞》

《IM消息送達保證機制實現(二)：保證離線消息的可靠投遞》

《如何保證IM實時消息的“時序性”與“一致性”？》

《一個低成本確保IM消息時序的方法探討》

《IM單聊和群聊中的在線狀態同步應該用“推”還是“拉”？》

《IM群聊消息如此復雜，如何保證不丟不重？》

《談談移動端 IM 開發中登錄請求的優化》

《移動端IM登錄時拉取數據如何作到省流量？》

《淺談移動端IM的多點登錄和消息漫游原理》

《完全自已開發的IM該如何設計“失敗重試”機制？》

《通俗易懂：基于集群的移動端IM接入層負載均衡方案分享》

《微信對網絡影響的技術試驗及分析（論文全文）》

《即時通訊系統的原理、技術和應用（技術論文）》

《開源IM工程“蘑菇街TeamTalk”的現狀：一場有始無終的開源秀》

《QQ音樂團隊分享：Android中的圖片壓縮技術詳解（上篇）》

《QQ音樂團隊分享：Android中的圖片壓縮技術詳解（下篇）》

《騰訊原創分享(一)：如何大幅提升移動網絡下手機QQ的圖片傳輸速度和成功率》

《騰訊原創分享(二)：如何大幅壓縮移動網絡下APP的流量消耗（上篇）》

《騰訊原創分享(三)：如何大幅壓縮移動網絡下APP的流量消耗（下篇）》

《如約而至：微信自用的移動端IM網絡層跨平臺組件庫Mars已正式開源》

《基于社交網絡的Yelp是如何實現海量用戶圖片的無損壓縮的？》

《騰訊技術分享：騰訊是如何大幅降低帶寬和網絡流量的(圖片壓縮篇)》

《騰訊技術分享：騰訊是如何大幅降低帶寬和網絡流量的(音視頻技術篇)》

《字符編碼那點事：快速理解ASCII、Unicode、GBK和UTF-8》

《全面掌握移動端主流圖片格式的特點、性能、調優等》

《子彈短信光鮮的背后：網易云信首席架構師分享億級IM平臺的技術實踐》

《IM開發基礎知識補課(五)：通俗易懂，正確理解并用好MQ消息隊列》

《微信技術分享：微信的海量IM聊天消息序列號生成實踐（算法原理篇）》

《自已開發IM有那么難嗎？手把手教你自擼一個Andriod版簡易IM (有源碼)》

《融云技術分享：解密融云IM產品的聊天消息ID生成策略》

《IM開發基礎知識補課(六)：數據庫用NoSQL還是SQL？讀這篇就夠了！》

《適合新手：從零開發一個IM服務端（基于Netty，有完整源碼）》

《拿起鍵盤就是干：跟我一起徒手開發一套分布式IM系統》

《IM里“附近的人”功能實現原理是什么？如何高效率地實現它？》

《IM開發基礎知識補課(七)：主流移動端賬號登錄方式的原理及設計思路》

《IM開發基礎知識補課(八)：史上最通俗，徹底搞懂字符亂碼問題的本質》

《IM“掃一掃”功能很好做？看看微信“掃一掃識物”的完整技術實現》

《IM的掃碼登錄功能如何實現？一文搞懂主流應用的掃碼登錄技術原理》

《IM要做手機掃碼登錄？先看看微信的掃碼登錄功能技術原理》

>> 更多同類文章 ……

（本文同步發布于：http://www.52im.net/thread-2953-1-1.html）