分散式 ID 生成方案探討
我們用個業務場景的例子來說明:
如果一個業務的資料使用 MySQL 儲存,基於使用者ID進行分庫分表,每一條資料都需要分配一個在這個業務中的全域性唯一ID,如何實現全域性唯一 ID ?本文探討一些方案。
探討方案前,先討論下面兩個點:
一、用數字,還是用字串?
下面的方案中既有用數字當全域性唯一ID,也有用字串作為全域性唯一ID的。數字儲存空間小,效能相對較高,但是取值範圍有限,也很難有語義化的值。字串與之相反。具體使用哪種,根據場景決策。
二、如果這個ID是對外暴露的,比如是使用者訂單號,要考慮下面兩點後再選擇方案:
- 不能暴露敏感資訊,比如不能把使用者ID放到訂單號裡;
- 不能讓別人猜到你的資料量。比如用的步長為1進行遞增的全域性ID,競爭對手早上下單一次,晚上下單一次,就知道當天的下單量了。
方案1:使用者ID + 自增主鍵
一個簡單的方案是,全域性唯一 ID 用字串型別,由 使用者ID 和 自增主鍵的值組成。例如有一條記錄,使用者ID為1234,自增主鍵值是32,那麼全域性唯一ID便是 1234-12
。
為什麼這個方案裡全域性唯一ID不用數字型別?很簡單,使用者1234有一條記錄的自增主鍵是56,那麼全域性唯一ID就是123456;使用者123有一條記錄的自增主鍵是456,那麼全域性唯一ID也會是123456,這就有問題了。
所以用字串。
但這個方案是有問題的。因為和自增主鍵產生了耦合。為什麼呢?
原因1:需要兩步才能把全域性唯一ID放進去,第一步是插入不包含全域性ID的資料,並得到主鍵ID;第二步是組裝全域性ID,並update到記錄中。(這隻能說是個小問題)
原因2:後續遷移資料很麻煩。比如原先用 32 張分表儲存資料,後來發現不夠用,改用 128 張分表。這種情況下需要將 原先的 32張分表資料不斷的向新的 128張分表遷移,但新的128張分表有有自己的自增主鍵。這會導致遷移很麻煩,比如:
- 在新表中全域性ID保持不變,但是主鍵ID要和舊錶ID保持一致嗎?如果保持一致,新表中會浪費一些自增主鍵,能接受嗎?
- 如果遷移過程中必須保證業務可用,新增加的資料在新的分表和舊的分表中的自增主鍵和全域性唯一ID如何保持一致?
遷移資料是個很大的話題,這裡只丟擲問題,不做討論。
方案2:UUID
用 UUID 的話,全域性唯一ID必須是字串型別。
持保留意見,因為對我來說是個黑盒,我不知道在一個較長時間內會不會出現重複,出現時間回撥等異常的情況下會不會出現重複。
方案3:單點全域性唯一ID
例如,新建一個帶MySQL表(就叫 global_id吧),表裡面只有一條記錄,記錄著當前的全域性唯一id,初始值為0。每當業務方需要一個全域性唯一ID時,按照下面邏輯生成:
- 進入資料庫事務
- 通過update對global_id表中的資料加1。(這一步會對資料加上排他鎖,事務結束後才釋放)
- 讀取當前全域性id值
- 提交事務
- 返回全域性唯一id
在 Leaf——美團點評分散式ID生成系統 中給出了一個用資料庫自增主鍵的方案,但思路是相同的:
- 進入事務
- 用replace覆蓋掉當前資料
- 獲取自增主鍵值作為全域性唯一ID
- 提交事務
- 返回全域性唯一ID
以上,可以封裝成一個 IDService 服務。
zookeeper 有個順序節點功能,也可以實現。
問題是:單點,效能差,可用性低。
方案4:snowflake
Snowflake 演算法用於生成單調遞增的long數字型別ID。
long型別數字,8位元組,64位元,被拆成多個段:
位元數 | 段名 | 說明 |
---|---|---|
1 | 符號位 | 保持為0。 |
41 | 毫秒級時間戳 | 2^41 = 2199023255552,可以標識從0到2199023255551,2199023255551對應的時間是2039-09-07 23:47:35。也就是從 2019 年算,還能用20 年。但這個時間戳是相對1970年的,我們可以優化成相對2019年,這樣就可以用接近70年。 |
5 | 資料中心ID | 2^5=32,支援32個數據中心。但是一般沒有這麼多資料中心,可以不用或者用2位元。多出的位元位送給下面的workId。 |
5 | workerID | 2^5=32,可以認為用來標識同一個服務的多個程序例項。在現在的微服務背景下,一個服務32個例項可能不夠用,所以可以向上面的 資料中心ID 要幾個位元位。注意, 資料中心ID + workerId 千萬不能重複使用,否則做不到全域性唯一。 |
12 | 毫秒級流水號 | 2^12=4096。這個是自增的部分。 |
這個演算法可以內嵌到業務方程式碼中,也可以單獨做出來一個服務供業務方呼叫。
資料中心ID
和 workerID
如何指定 ?
資料中心ID
+ workerID
不能重複,否則做不到全域性唯一,那麼怎麼給一個服務例項指定呢?資料中心ID這個是可以提前確定的,作為環境變數傳給服務即可。所以我們主要看workerID如何指定。有這樣幾個方案:
一、服務啟動時手動指定。
二、引入zookeeper順序節點,服務啟動時從zookeeper拿到順序ID作為workerID,並持久化到本地。(有個問題,如果該服務例項被摘除,如何回收workerID?)
三、用更多bit存workerID,用完即走。例如 uid-generator 用了 22 bit ,這樣可以支援 2^22 = 4194304 個workerID。從0開始分配workerID,不停遞增,最新的workerID記錄在資料庫中。服務例項啟動時獲取workerID,服務重啟,則重新獲取workerID。(同樣的,沒解決回收的問題。用更多bit存workerID,意味著其他段變短, uid-generator 用 28bit存秒級時間戳,22位元存workerID,13位元存秒級流水號)
四、用機器ip去算一個workerID。這是個很不明智的選擇,因為早晚會遇到衝突的情況,比如 從一次 Snowflake 異常說起 。
另外一點要注意的是,workerID限制了服務例項的數量。
說了這麼多,snowflake 演算法長什麼樣?
可以看下 SnowFlake.java 的實現,很簡單。還有很多同學造過這個輪子:
注意演算法中一個很重要的點:當前毫秒時間戳內的流水號使用完後,若仍需要馬上生成新的全域性ID,要等到下一毫秒,再繼續從0開始生成流水號。這個等到下一毫秒,不需要用sleep,之間勇哥死迴圈不定獲取當前時間就行。
還有一個點,如果服務執行過程中,發現時間回撥,建議返回失敗,並告警。
時鐘回撥,影響很大!
在服務執行過程中發生時間回撥,我們可以返回失敗。但是若服務重啟後發生時間回撥了呢?舉個例子,服務在每一秒都會向業務方生成全域性唯一ID,在伺服器時間是 2019-01-26 22:40:29
服務因異常而重啟,重新提供服務時伺服器時間是 2019-01-26 22:40:28
,竟然在 2019-01-26 22:40:29
之前!這種時間的不合理變化(至少對於snowflake不合理)可能是因為:
- NTP 同步時間
- 人工修改時間
把上面兩件事情禁止掉就能解決。
還有一個解決方案是,將當前時間(秒級)持久化到硬碟。服務異常重啟時,用當前時間和硬碟上存的時間作比較,若小於等於硬碟上時間,則等到下一秒,等到當前時間大於硬碟記錄的時間,再提供服務。
方案5:預取
這個方案對應 Leaf——美團點評分散式ID生成系統 中的 Leaf 方案,可以看做本文中方案3的優化。
我們將提供ID的服務稱作 IDService ,當業務方請求 IDservice 提供一個全域性ID時,IDservice不再像方案3那樣讓資料庫生成一個新ID,而是從服務例項中儲存的資料庫預先生成的一堆ID中取出一個返回給業務方。
假設MySQL表(還叫 global_id吧),表裡面只有一條記錄,記錄著當前的全域性唯一id,初始值為0,預取的步長是1000 ,IDservice 可以這樣設計:
-
IDservice 服務啟動時,將 global_id 表中全域性id加1000,並將0~999這1000個數字放在記憶體中(例如 Java中的queue,可以順序放,也可以打亂順序再放進去)。此時資料庫中記錄的全域性 ID 是 1000。
-
業務方向 IDservice 請求全域性唯一ID時,若IDservice例項中還有ID,則取出,返回給業務方;若沒有,則將 global_id 表中全域性id加1000,並將1000~1999這1000個數字放在記憶體中。此時資料庫中記錄的全域性 ID 是 2000。
這個方案中,資料庫更新時,IDservice 會變慢,所以 Leaf 用了雙 buffer 進行優化。原先用一個 Java Queue 儲存預取的1000個ID,現在改成用兩個 Java Queue ,都存1000個預取的ID。我們將兩個 Java Queue 分別命名為Q1、Q2。
雙buffer方案:
- IDservice 服務啟動時,將 global_id 表中全域性id加1000,並將0~999這1000個數字填充到Q1中;將 global_id 表中全域性id加1000,並將1000~1999這1000個數字填充到Q2中;(例如 Java中的queue,可以順序放,也可以打亂順序再放進去)。此時資料庫中記錄的全域性 ID 是 2000。兩個佇列,預設從 Q1 取ID。
- 業務方向IDservice請求全域性唯一ID時,發現現在設定為從Q1中取ID,於是嘗試從 Q1 中取 ID。若有則取出,返回給業務方;若Q1中沒有ID了,則切換為預設從 Q2 取ID,返回給業務方。同時,異步向Q1中填充ID:將 global_id 表中全域性id加1000,並將2000~2999這1000個數字填充到Q1中。此時資料庫中記錄的全域性 ID 是 3000。
- 類似的,若Q2中沒有ID了,則切換為預設從Q1取ID,並異步向Q1中填充ID。
雙 buffer 方案也可以用在下面幾個基於預取的方案中。
該方案中仍使用了一個數據庫,是單點,如何提升可用性?Leaf 方案中給了兩個方案:
- 可以用主從架構部署資料庫,主庫出問題後切換到從庫。但是極端情況下主從同步會導致問題。
- 選擇使用“類Paxos演算法”實現的強一致MySQL方案。
方案6:snakeflake + 預取
這個方案對應 Leaf——美團點評分散式ID生成系統 中的 Leaf+segments 方案。
在這個方案中,去除對資料庫的依賴,使用 snowflake 生成ID,但不是一個一個的生成,而是像方案5那樣預取,這樣可以進一步提升效能。
那麼如何解決異常重啟後時間回撥的問題?
Leaf+segments 方案給出的解決辦法是,每3秒將機器時間持久化,服務啟動時將當前時間和之前持久化的時間比較,若小於,則等待或者直接啟動失敗。
這裡也有一個問題,就是一定要保證時間戳不能出現極大波動,例如,千萬不要出現運維事務,導致機器時間變成100年以後。其他方案,也應該評估下該風險。
方案7:基於多資料庫的高可用方案1
方案5中只用了一個數據庫,可用性不高,可以用多個數據庫提升可用性。舉個例子:
我們用2個數據庫,資料庫1只能取奇數,資料庫2只能取偶數。
- 預取ID時,可以隨機選一個數據庫,也可以用輪詢選擇資料庫。
- IDservice 發現一個數據庫不可用時,可以臨時摘除掉。
如果要更多資料庫,比如3個數據庫,那麼數資料庫1只能生成1,4,7,10等ID,資料庫2只能生成2、5、8、11等ID,資料庫3只能生成3、6、9、12 等ID。
這套方案來自 Flickr 。
方案8:基於多資料庫的高可用方案2
假如用字串做 ID,ID全部由數字組成 ,我們這樣設計ID:
字元數 | 段名 | 描述 |
---|---|---|
10 | 時間(年的後兩位+月+日+時+分) | 例如,2019年01月27日09:48,對應 1901270947 |
2 | 資料庫編號 | 支援00~99 |
10 | 流水號 | 從0000000000到9999999999 |
我們用100個數據庫來生成ID,每個資料庫中一張表,每一分鐘對應一條記錄。例如我們在編號為12的資料庫建立表:
CREATE TABLE `id_info` ( `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT, `db_index` CHAR(2) NOT NULL DEFAULT '12', -- 資料庫編號 `current_minute` CHAR(10) NOT NULL , -- 當前時間,分鐘級,如1901270947 `sequence` intNOT NULL DEFAULT 0,-- 流水號 PRIMARY KEY (`id`) ) ENGINE = InnoDB CHARACTER SET = utf8mb4
當 IDservice 用步長1000 從資料庫預取 ID:
- 選擇一個數據庫,例如選擇了編號12的資料庫
- 找到當前時間(分鐘級,例如是 1901270947 )對應的記錄,無則建立。
- 對 sequence 增加1000,IDservice 將1901270947120000000000到1901270947120000000999存到記憶體。
如何保證高可用呢?
- 一個分庫在一分鐘內生成10000000000 個ID,正常業務是用不完的。
- 若有資料庫出現問題,IDService 將其臨時摘除即可。
對於上面的第1點,如果這一分鐘的真用完了怎麼辦?兩個策略:
- 丟擲錯誤,等待下一分鐘到來再重新獲取ID
- 借用下一分鐘的ID。
資料量分析:
如果資料庫每分鐘生成一條記錄,一天有24*60=1440條記錄,一年會產生525600條記錄。可以定期刪除較舊資料。
為什麼說 如果資料庫每分鐘生成一條記錄
?如果ID消費很慢,會導致有些分鐘被跳過。
如果刪除資料後出現時間跨度的時間回撥怎麼辦?那就把允許使用的時間最小值記錄下來,每次刪除資料,更新下這個最小值即可。
方案9:基於多資料庫的高可用方案3
這裡我們假定要做一個long型別的全域性ID。我們知道:
秒級時間戳目前只用了10個數字,例如 1548563250 (對應時間是 2019-01-27 12:27:30) 。
63 bit位元能表示的最大數字是 9223372036854775807
,由19個數字組成。
基於上面兩點,我們可以這樣組裝一個long型別全域性ID:
十進位制數字數 | 段名 | 描述 |
---|---|---|
10 | 秒級時間戳 | 例如,1548563250 對應 2019-01-27 12:27:30 。 最大值是 9223372036 ,對應 2262年 |
2 | 資料庫編號 | 支援從 00 到 99 |
7 | 流水號 | 支援從 0000000 到 9999999 |
我們用100個數據庫來生成ID,每個資料庫中一張表,每一分鐘對應一條記錄。例如我們在編號為12的資料庫建立表:
CREATE TABLE `id_info` ( `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT, `db_index` int NOT NULL DEFAULT 12, -- 資料庫編號 `current_timestamp` int NOT NULL DEFAULT 0, -- 當前秒級時間戳,最大值是 9223372036 `sequence` intNOT NULL DEFAULT 0,-- 流水號,最大值是 9999999 PRIMARY KEY (`id`) ) ENGINE = InnoDB CHARACTER SET = utf8mb4
在這個方案裡,每張表只有一條資料。
設定步長為1000,IDservice 用以下方案預取全域性ID:
- 對於 T 遠大於 M 的情況,有兩種可能的原因,一個是ID消費的很慢,一個是系統時間出現異常(這種情況要告警)。為了消除ID 消費太慢的情況,IDservice 可以每5分鐘檢測下當前存的ID對應的時間,若是5分鐘之前,則強制重新預取 ID。
- 當T<=M,流水號又已經分配完時,向前借1秒。
- 為了降低DB操作,也可以一次預取更多的全域性ID,比如一次取 100000 個全域性ID。