本文來自融云技術團隊原創分享，原文發布于“融云全球互聯網通信云”公眾號，原題《如何實現分布式場景下唯一 ID 生成？》，即時通訊網收錄時有部分改動。
1、引言
對于IM應用來說，消息ID（或稱序列號）是個看似不起眼，但非常重要的東西之一。
消息ID的使用貫穿了IM技術邏輯的方方面面，比如：
1）聊天消息的順序保證；
2）聊天消息QoS送達保證機制時的去重；
3）特定聊天消息的精確查找和匹配；
4）聊天消息的已讀未讀處理；
5）聊天消息的送達回執；
6）群聊消息的擴散讀拉取標記；
7）... ...
但，IM系統高度個性化的特性（設計上沒有統一的標準和思路），包括聊天消息ID的生成算法在內，每個產品都有自已的思路和考量。
常見的消息ID生成策略有：
1）UUID：這種方法簡單直觀，可以很好的保證唯一性，但對于技術潔癖的人來說ID長度會有點長；
2）使用時間戳長整數：這個最偷懶，用在吞吐量不大的場景下，湊活也能用，但存在重復的風險，也無法保證分布式下的唯一性；
3）使用twitter開源的snowflake算法：在分布式高并發的情況下，這也是個不錯的選擇；
4）按用戶使用獨立的ID生成空間生成順序的ID：比如微信的消息序列號生成策略就很不錯。
從某種意義上來講，消息ID的生成策略決定了IM應用層某些功能實現的難易度，好的消息ID生成策略會讓IM產品的開發越做越順，反之越做越別扭。
本文要分享的是融云即時通訊云產品中的聊天消息ID生成算法和策略，一個19字節的ID就能包含：時間戳、消息類型、會話ID、序列號，小ID、大用途，值得借鑒！
免責申明：本文來自融云官方技術團隊的分享，僅用于技術交流學習和研究目的，請勿用于非法用途，文中如涉及商業秘密，請告之我處理！
特別說明：僅出于技術研究和學習目的來分享此文，并未收取任何好處，所以此文不是廣告，我也不是托。如有不妥，請告之！
學習交流：
- 即時通訊/推送技術開發交流5群：215477170[推薦]
- 移動端IM開發入門文章：《新手入門一篇就夠：從零開發移動端IM》
（本文同步發布于：http://www.52im.net/thread-2747-1-1.html）
2、相關文章
3、技術背景
對于一套分布式部署的 IM 系統，要求每條消息的 ID 要保證在集群中全局唯一且按生成時間有序排列。如何快速高效的生成消息數據的唯一 ID ，是影響系統吞吐量的關鍵因素。
那么，融云是如何做到生成全局唯一消息 ID 的呢？
首先需要明確下 ID 生成的核心需求：
1）全局唯一；
2）有序。
4、設計思路
融云消息數據的唯一 ID 長度采用 80 Bit。
每 5 個 Bit ，進行一次 32 進制編碼，轉換為一個字符，字符取值范圍是：數字 “2 ~ 9 ”和字母“A ~ B”。其中，已經去掉容易造成肉眼混淆的，數字 0 和 1 （余下可用的數字是8個），及字母 O 和 I（余下可用的字母是24個），總可用字符就是32個（剛好可按32進制進行編碼）。
這樣，80 Bit 可以轉換為 16 個字符，再加上 3 個分隔符（ - ），將 16 個字符分為 4 組，最終得到一個 19 字符的唯一 ID ，形如：“ BD8U-FCOJ-LDC5-L789 ”。 這樣設計，即可以保證生成的 ID 是有序的，也能方便閱讀。
如上圖所示，80 Bit 被分為 4 段。
1）第一段 42 Bit：用于存放時間戳，最長可表示到 2109 年，足夠開發者當前使用了。時間戳數據放在高位，可以保證生成的唯一 ID 是按時間有序的，這個是消息 ID 必須要滿足的條件。
2）第二段 12 Bit：用于存放自旋轉 ID 。我們知道，時間戳的精度是到毫秒的，對于一套億級 IM 系統來說，同一毫秒內產生多條消息太正常不過了，這個自旋 ID 就是在給落到同一毫秒內的消息進行自增編號。12 Bit 則意味著，同一毫秒內，單臺主機中最多可以標識 4096（ 2 的 12 次方）條消息。
3）第三段 4 Bit：用于標識會話類型。4 Bit ，最多可以標識 16 中會話，足夠涵蓋單聊、群聊、系統消息、聊天室、客服及公眾號等常用會話類型。
4）第四段 22 Bit：會話 ID 。如群聊中的群 ID ，聊天室中的聊天室 ID 等。與第三段會話類型組合在一起，可以唯一標識一個會話。其他的一些 ID 生成算法，會預留兩段，分別用來標識數據中心編號和主機編號（如 SnowFlake 算法），我們并沒有這樣做，而是將這兩段用來標識會話。這樣，ID 生成可以直接融入到業務服務中，且不必關心服務所在的主機，做到無狀態擴縮容。
5、代碼實現
消息 ID 共占 80 Bit ，計算時我們分為兩部分，高 64 Bit （記為 highBits）和低 16 Bit （記為 lowBits）。
具體的代碼實現過程，大致如下。
1）獲取當前系統的時間戳，并賦值給消息 ID 的高 64 Bit ：
2）獲取一個自旋 ID ， highBits 左移 12 位，并將自旋 ID 拼接到低 12 位中：
其中，自旋 ID 是一個從 0 到 4095 范圍內，順序遞增的數，生成規則如下：
3）上步的 highBits 左移 4 位，將會話類型拼接到低 4 位：
4）取會話 ID 哈希值的低 22 位，記為 sessionIdInt：
5）highBits 左移 6 位，并將 sessionIdInt 的高 6 位拼接到 highBits 的低 6 位中：
6）取會話 ID 的低 16 位作為 lowBits：
7）highBits 與 lowBits 拼接得到 80 Bit 的消息 ID，對其進行 32 進制編碼，即可得到唯一消息 ID：
編碼規則：從左至右，每 5 個 Bit 轉換為一個整數，以這個整數作為下標，即可在下表中找到對應的字符。
6、實際應用
PS：如果感覺上面兩節介紹的算法思路和代碼實現有點抽象，可以直接去看融云的IM產品中的實際消息ID生成情況。
比如，從融云的Demo產品中取出的同一個用戶相近時間內的3條單聊消息ID樣本：
BD8U-DG1U-5UI5-L789
BD8U-DU6D-2205-L789
BD8U-FCOJ-LDC5-L789
比如，可以直接登陸融云的Web產品 http://web.sealtalk.im，在瀏覽器端研究學習它的消息ID生成情況：
特別說明：僅僅出于技術研究和學習目的來分享此文，并沒有收到融云的任何好處，所以此文不是廣告，我也不是托。如有不妥，請告之！
7、注意事項
融云所使用的這種 ID 生成的方式，需要注意：
1）注意保證自旋 ID 的生成是線程安全的；
2）避免在并發情況下，生成出同樣的 ID ；
3）此 ID 生成算法，強烈依賴系統時間，如果系統時間被改小，也可能造成 ID 生成重復。
附錄：更多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的圖片傳輸速度和成功率》
《如約而至：微信自用的移動端IM網絡層跨平臺組件庫Mars已正式開源》
《基于社交網絡的Yelp是如何實現海量用戶圖片的無損壓縮的？》
《騰訊技術分享：騰訊是如何大幅降低帶寬和網絡流量的(圖片壓縮篇)》
《騰訊技術分享：騰訊是如何大幅降低帶寬和網絡流量的(音視頻技術篇)》
《字符編碼那點事：快速理解ASCII、Unicode、GBK和UTF-8》
《全面掌握移動端主流圖片格式的特點、性能、調優等》
《子彈短信光鮮的背后：網易云信首席架構師分享億級IM平臺的技術實踐》
《IM開發基礎知識補課(五)：通俗易懂，正確理解并用好MQ消息隊列》
《微信技術分享：微信的海量IM聊天消息序列號生成實踐（算法原理篇）》
《自已開發IM有那么難嗎？手把手教你自擼一個Andriod版簡易IM (有源碼)》
《融云技術分享：解密融云IM產品的聊天消息ID生成策略》
>> 更多同類文章 ……
（本文同步發布于：http://www.52im.net/thread-2747-1-1.html）