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