雪花演算法詳解

語言: CN / TW / HK

政採雲技術團隊.png

無涯.png 雪花演算法是 Twitter 內部使用的分散式全域性唯一 ID 生成演算法,並將其開源。本文介紹演算法原理、及其一些實際使用中的問題和解法。

演算法原理

雪花演算法生成的是一個 Long 型別的 ID,Long 佔用 64 個 bit 位,該演算法將 bit 位分為以下部分:

| | 符號位 | 時間戳 | 機器 id | sequence | | ---- | ------ | ------ | ------ | -------- | | 佔用 | 1 bit | 41 bit | 10 bit | 12 bit |

符號位:通常為 0,代表正數

時間戳:毫秒數,不是直接從 1970 年開始的時間戳,而是代表可使用時間(當前時間減去開始使用時間),大約可使用 2^41 毫秒約 69 年。

機器 id:高 5 位為資料中心 id,低 5 位為機器 id

sequence:在同一毫秒內從 0 開始的計數器,最大 2^12 為 4096 個,當超過 4096 時,則阻塞等待下一毫秒。既每秒單機可支援併發約為 400 萬。

演算法實現相對簡單,本文就不貼程式碼了。重點是 需要保障機器 id 唯一,可通過配置、資料庫、redis、zk 等實現

問題與解法

原始的演算法在實際使用場景中,可能會碰到以下問題:

時鐘回撥

時鐘回撥會導致生成重複的 ID,可通過以下方式解決: 1. 與最後生成時間做對比 2. 回撥時間較短時,可阻塞等待 3. 否則,可以重新獲取新的機器 id

此方案可能會導致機器 id 消耗太快,可對時間戳、sequence 佔用 bit 進行調整。不過不必太過擔心,機器 id 也是可以重複使用的,只要不是使用中的重複就好。

前端 JS 精度

JS 內建有 32 位整數,而 number 型別的安全整數是 53 位。如果超過 53 位,則精度會丟失。當碰見雪花演算法時,為了正確表示,則只能使用 2^31 毫秒約 24 天。

解決方案:調整時間戳為秒:則能使用 2^31 秒約 68 年。此時,單機併發則為 4096。如果不夠,可以適當調小機器 id bit 位數,調大 sequence 位數,使併發增加。

分庫分表

分庫分表通常採用取模演算法,當路由欄位使用了雪花演算法時,會有什麼問題呢?

資料分佈不均勻

在同一時間內,sequence 自增永遠從 0 開始。當分庫分表採用取模演算法時,會導致生成的 ID 一直落在前面的庫、表裡,造成資料傾斜,影響效能。此種現象在單位時間(毫秒、秒)併發低、或分表較多的場景下尤為突出。

解決方案:sequence 從一個隨機數開始。

隨機範圍選擇,需要在以下幾點取一個平衡: 1. 隨機範圍太大:將會造成 sequence 浪費,併發降低

可通過調大 sequence 佔用 bit 解決

  1. 太小:將會導致後續分庫分表擴容後,資料又傾斜了

建議:取一個未來可能的最大分表數。

控制路由目標表

當分庫分表資料已經發生傾斜不均勻了,該如何解決呢?

假設共有 4 個例項、分庫為 16、分表數為 128,資料傾斜將造成第一個例項資料過多、效能降低。需要將後續資料落在其它例項上既不落在 0-31 表上,以降低第一個例項壓力,待資料分佈均勻後,再使用前面的演算法

基於 sequence 隨機開始,有以下方案:

方案一

將 sequence 隨機開始,遞增後的值,執行一下路由演算法,當其落在其它例項上時,才返回;否則繼續遞增。

優點:簡單 缺點:id 生成器通常為中介軟體團隊的服務,並且後續需要恢復之前的演算法,修改麻煩

方案二

我們知道新的 sequence 要求: 1. 與老 sequence 一一對映不會重複 2. 與老 sequence 一樣,單調遞增 3. 路由後落在指定的表裡

為了講解方便,我們假設分了 8 張表:0-7。需要使新的 sequence 落在 表 3-6 上。假設 x 軸為從 ID 伺服器得到原始 sequence,則 y 可能的值分佈如圖所示:x、y 都從 0 開始

image-20220529201359797

可以找到規律:y 為從0開始,第 x+1 個有效的值。

當路由運算後落在表3-6上,即為有效

在實現時,注意以下幾點:

  1. 正確解析出原始 sequence,並用新 sequence 組裝新的 ID
  2. 新 sequence 的最大值,不能大於其佔用 bit 所位能代表的最大值

    當超過時,可等待後取下一個時間的 sequence

  3. 由於新老 sequence 是一一對映,所以可以提前快取結果,避免 cpu 消耗

以上兩種方案都有一個影響:會浪費更多的 sequence,使最大併發降低,使用時請結合實際情況。

總結

本文介紹了雪花演算法原理及其在使用過程中可能出現的問題和解法。如果你在使用中有碰到其它問題或者有更好的解法,請評論留言吧!

推薦閱讀

基於流量域的資料全鏈路治理

一次介面響應時間過長的效能分析及排查過程

MySQL 之 innodb 自增鎖原理實現

基於父子關係的高效去重演算法

招賢納士

政採雲技術團隊(Zero),一個富有激情、創造力和執行力的團隊,Base 在風景如畫的杭州。團隊現有300多名研發小夥伴,既有來自阿里、華為、網易的“老”兵,也有來自浙大、中科大、杭電等校的新人。團隊在日常業務開發之外,還分別在雲原生、區塊鏈、人工智慧、低程式碼平臺、中介軟體、大資料、物料體系、工程平臺、效能體驗、視覺化等領域進行技術探索和實踐,推動並落地了一系列的內部技術產品,持續探索技術的新邊界。此外,團隊還紛紛投身社群建設,目前已經是 google flutter、scikit-learn、Apache Dubbo、Apache Rocketmq、Apache Pulsar、CNCF Dapr、Apache DolphinScheduler、alibaba Seata 等眾多優秀開源社群的貢獻者。如果你想改變一直被事折騰,希望開始折騰事;如果你想改變一直被告誡需要多些想法,卻無從破局;如果你想改變你有能力去做成那個結果,卻不需要你;如果你想改變你想做成的事需要一個團隊去支撐,但沒你帶人的位置;如果你想改變本來悟性不錯,但總是有那一層窗戶紙的模糊……如果你相信相信的力量,相信平凡人能成就非凡事,相信能遇到更好的自己。如果你希望參與到隨著業務騰飛的過程,親手推動一個有著深入的業務理解、完善的技術體系、技術創造價值、影響力外溢的技術團隊的成長過程,我覺得我們該聊聊。任何時間,等著你寫點什麼,發給 [email protected]

微信公眾號

文章同步釋出,政採雲技術團隊公眾號,歡迎關注

政採雲技術團隊.png