域名預(yù)訂/競(jìng)價(jià)，好“米”不錯(cuò)過(guò)
?背景 ?
對(duì)于一套分布式部署的 IM 系統(tǒng)，要求每條消息的 ID 要保證在集群中全局*且按生成時(shí)間有序排列。如何快速高效的生成消息數(shù)據(jù)的* ID ，是影響系統(tǒng)吞吐量的關(guān)鍵因素。那么，融云是如何做到生成全局*消息 ID 的呢？
首先需要明確下 ID 生成的核心需求：
1. 全局*
2. 有序
?設(shè)計(jì) ?
融云消息數(shù)據(jù)的* ID 長(zhǎng)度采用 80 Bit 。每 5 個(gè) Bit ，進(jìn)行一次 32 進(jìn)制編碼，轉(zhuǎn)換為一個(gè)字符，字符取值范圍是，( 2 ~ 9 ) 和 ( A ~ B )，其中，已經(jīng)去掉容易造成肉眼混淆的，數(shù)字 0 和 1 ，及字母 O 和 I 。這樣，80 Bit 可以轉(zhuǎn)換為 16 個(gè)字符，再加上 3 個(gè)分隔符（ - ），將 16 個(gè)字符分為 4 組，*終得到一個(gè) 19 字符的* ID 。 這樣設(shè)計(jì)，即可以保證生成的 ID 是有序的，也能方便閱讀。
如上圖所示，80 Bit 被分為 4 段：
1. *段 42 Bit ，用于存放時(shí)間戳，*長(zhǎng)可表示到 2109 年，足夠*當(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ò)縮容。
?實(shí)現(xiàn)過(guò)程 ?
消息 ID 共占 80 Bit ，計(jì)算時(shí)我們分為兩部分，高 64 Bit （記為 highBits ）和低 16 Bit （記為 lowBits ）。
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)的字符。
總結(jié)：
這種 ID 生成的方式，需要注意保證自旋 ID 的生成是線程安全的。避免在并發(fā)情況下，生成出同樣的 ID 。另外，此 ID 生成算法，強(qiáng)烈依賴系統(tǒng)時(shí)間，如果系統(tǒng)時(shí)間被改小，也可能造成 ID 生成重復(fù)。
申請(qǐng)創(chuàng)業(yè)報(bào)道，分享創(chuàng)業(yè)好點(diǎn)子。點(diǎn)擊此處，共同探討創(chuàng)業(yè)新機(jī)遇！
