當(dāng)前位置:首頁 >  站長 >  編程技術(shù) >  正文

【融云分析】如何實(shí)現(xiàn)分布式場景下唯一ID生成?

 2019-03-25 17:31  來源: 互聯(lián)網(wǎng)   我來投稿 撤稿糾錯(cuò)

  域名預(yù)訂/競價(jià),好“米”不錯(cuò)過

?背景 ?

對于一套分布式部署的 IM 系統(tǒng),要求每條消息的 ID 要保證在集群中全局*且按生成時(shí)間有序排列。如何快速高效的生成消息數(shù)據(jù)的* ID ,是影響系統(tǒng)吞吐量的關(guān)鍵因素。那么,融云是如何做到生成全局*消息 ID 的呢?

首先需要明確下 ID 生成的核心需求:

1. 全局*

2. 有序

?設(shè)計(jì) ?

融云消息數(shù)據(jù)的* ID 長度采用 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í)間戳,*長可表示到 2109 年,足夠*當(dāng)前使用了。時(shí)間戳數(shù)據(jù)放在高位,可以保證生成的* ID 是按時(shí)間有序的,這個(gè)是消息 ID 必須要滿足的條件。

2. 第二段 12 Bit ,用于存放自旋轉(zhuǎn) ID 。我們知道,時(shí)間戳的精度是到毫秒的,對于一套億級 IM 系統(tǒng)來說,同一毫秒內(nèi)產(chǎn)生多條消息太正常不過了,這個(gè)自旋 ID 就是在給落到同一毫秒內(nèi)的消息進(jìn)行自增編號。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)消息、聊天室、客服及公眾號等常用會(huì)話類型。

4. 第四段 22 Bit ,會(huì)話 ID 。如群聊中的群 ID ,聊天室中的聊天室 ID 等。與第三段會(huì)話類型組合在一起,可以*標(biāo)識(shí)一個(gè)會(huì)話。其他的一些 ID 生成算法,會(huì)預(yù)留兩段,分別用來標(biāo)識(shí)數(shù)據(jù)中心編號和主機(jī)編號(如 SnowFlake 算法),我們并沒有這樣做,而是將這兩段用來標(biāo)識(shí)會(huì)話。這樣,ID 生成可以直接融入到業(yè)務(wù)服務(wù)中,且不必關(guān)心服務(wù)所在的主機(jī),做到無狀態(tài)擴(kuò)縮容。

?實(shí)現(xiàn)過程 ?

消息 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 。對其進(jìn)行 32 進(jìn)制編碼,即可得到*消息 ID 。編碼規(guī)則如下:從左至右,每 5 個(gè) Bit 轉(zhuǎn)換為一個(gè)整數(shù),以這個(gè)整數(shù)作為下標(biāo),即可在下表中找到對應(yīng)的字符。

總結(jié):

這種 ID 生成的方式,需要注意保證自旋 ID 的生成是線程安全的。避免在并發(fā)情況下,生成出同樣的 ID 。另外,此 ID 生成算法,強(qiáng)烈依賴系統(tǒng)時(shí)間,如果系統(tǒng)時(shí)間被改小,也可能造成 ID 生成重復(fù)。

申請創(chuàng)業(yè)報(bào)道,分享創(chuàng)業(yè)好點(diǎn)子。點(diǎn)擊此處,共同探討創(chuàng)業(yè)新機(jī)遇!

相關(guān)標(biāo)簽
分布式系統(tǒng)

相關(guān)文章

熱門排行

信息推薦