分散式 ID 生成策略
作者 | 小牛
Java 工程師,關注服務端技術
對於系統中的一組資料而言,必不可少地對應有唯一標識。簡單的單體應用可以使用資料庫的自增 ID 作為唯一標識。而在複雜的分散式系統中,就需要一些特定的策略去生成對應的分散式 ID。
常見的專案中 ID 會有以下兩個特點:
-
全域性唯一性。
-
趨勢遞增(對於使用 MySQL 的專案而言)。
-
因為一般 ID 會作為資料庫的主鍵儲存,而在 MySQL InnoDB 中使用的是聚簇索引,使用有序的 ID 可以保證寫入效能。
一般在分散式系統中,會有一個單獨的服務來生成 ID。而這個服務則需要保證高可用性、高QPS 與安全性。另外生成的 ID 是不應該對外暴露的,如果非要對外展示,最好是無規則、不規律的編碼。
常見的生成策略如下:
UUID
UUID (Universally Unique Identifier) 生成的是一個長度為 32 的 16 進位制格式的字串。UUID 有多個版本,各版本演算法不同。但核心思想是一致的,基本上都是結合機器的網絡卡、當前時間、一個隨機數來生成特定長度的字串。
優點:
效能好、高可擴充套件性:本地生成,無網路消耗,不需要考慮效能瓶頸。
缺點:
-
無法保證趨勢遞增。
-
UUID 過長,如果需要在資料庫儲存,作為主鍵建立索引效率低。
適用場景:不需要考慮空間佔用,不需要生成有遞增趨勢,且不在 MySQL 中儲存。
Snowflake
snowflake 是 Twitter 開源的一個 ID 生成演算法。
-
首位符號位:因為 ID 一般為正數,該值為 0。
-
41 位時間戳(毫秒級):
-
時間戳不是當前時間的時間戳,而是儲存時間戳的差值(當前時間戳 - 起始時間戳(起始時間戳需要程式指定))理論上可以最多使用
(1 << 41) / (1000x60x60x24x365) = 69年
。 -
10 位資料機器位:包括 5 位資料標識位和 5 位機器標識位,也就是說最多可以部署節點數為:
1 << 10 = 1024
。 -
12 位毫秒內的序列:同一節點、同一時刻最多生成 ID 數
1 << 12 = 4096
。
最後生成結果為 64 位 Long 型數值。
優點
-
趨勢遞增,且按照時間有序。
-
效能高、穩定性高、不依賴資料庫等第三方系統。
-
可以按照自身業務特性靈活分配 bit 位。
缺點
-
依賴於機器時鐘,時鐘回撥會造成暫不可用或重複發號。
在分散式系統中,每臺機器上的時鐘不可能完全同步。在同步各個伺服器的時間時,有一定機率發生時鐘回撥。
適用場景:要求高效能,可以不連續,資料型別為 long 型。
Flicker
Flicker 方案主要思路是設計單獨的庫表,利用資料庫的自增 ID 來生成全域性 ID。
CREATE TABLE ticket_center ( id bigint(20) unsigned NOT NULL auto_increment, stub char(1) NOT NULL default '', PRIMARY KEY (id), UNIQUE KEY unq_stub (stub) )ENGINE=MyISAM;
-
stub: 票根,對應需要生成 Id 的業務方編碼,可以是專案名、表名甚至是伺服器 IP 地址。
-
MyISAM:預設表型別,基於傳統的 ISAM 型別。ISAM是 Indexed Sequential Access Method (有索引的順序訪問方法) 的縮寫,它是儲存記錄和檔案的標準方法。不是事務安全的,而且不支援外來鍵。如果執行大量的 select,MySql 儲存引擎選用 MyISAM 比較適合。
可以使用下面的SQL 獲取 ID:
REPLACE INTO ticket_center (stub) VALUES ('test'); SELECT LAST_INSERT_ID();
Replace into
先嚐試插入資料到表中,如果發現表中已經有此行資料(根據主鍵或者唯一索引判斷)則先刪除此行資料,然後插入新的資料, 否則直接插入新資料
為了解決單點故障問題:Flicker 方案啟用了兩臺資料庫伺服器來生成 ID,通過區分 auto_increment 的起始值和步長來生成奇偶數的 ID。(也可以根據情況部署多臺伺服器)
優點
-
充分利用了資料庫自增 ID 機制,生成的 ID 有序遞增。
缺點
-
依賴於資料庫,可用性低
-
水平擴充套件困難:定義好了起始值、步長和機器臺數之後,如果要新增機器就比較麻煩了。
適用場景:資料量不多,併發量不大。
Redis
因為 Redis 中的所有命令都是單執行緒的,可以利用 Incrby
命令來模擬 ID 的遞增。並且可以通過使用叢集來提升吞吐量。我們可以為不同的 Redis 節點設定不同的初始值並統一步長,這樣就能利用 Redis 生成唯一且趨勢遞增的 ID 了。例如有 3 個 Redis 節點,分別設定初始值為 1、2、3 ,這時步長就應該定為 3 。這樣每個節點不會生成重複的 ID。
Incrby :將 key 中儲存的數字加上指定的增量值。這是一個 "INCR AND GET” 的原子操作, 業務方可以定義一個自己的 key 值,通過 INCR 命令來獲取對應的 ID。
優點:
-
不依賴資料庫,且效能優於依賴資料庫的 Flicker 方案。
缺點:
-
擴充套件性低,Redis 叢集需要設定好初始值與步長。
-
Reids 宕機可能會生成重複的Id。
適用場景:Redis 叢集高可用,併發量高。
Leaf
上面提到的這些常見的 ID 生成策略,有時並不能完全滿足實際生產中的需求,在實際專案中會對其做一些改造和優化。
美團的 Leaf 分散式 ID 生成系統 ,在 Flicker 策略 與 Snowflake 演算法的基礎上做了兩套優化的方案。下文會簡單介紹一下 Leaf 方案做的一些優化,並不會深入分析。詳細方案大家可以檢視這裡:《Leaf 分散式 ID 生成系統 》
Leaf-segment 資料庫方案
相比於 Flicker 方案每次都需要讀取資料庫,Leaf-segment 改為了利用 proxy server 批量獲取,且做了雙 buffer 的優化。設計圖如下:
雙 buffer:ID 分號段載入,且當號段消費到某個點時就非同步的把下一個號段載入到記憶體中。而不需要等到號段用盡的時候才去更新號段。
Leaf-snowflake 方案
主要是針對時鐘回撥問題做了特殊處理。 若發生時鐘回撥則拒絕發號,並進行告警。
適用場景:服務規模較大,呼叫頻繁。
總結
關於分散式 ID 的生成策略暫且介紹到這裡。其實還有一些優秀的解決方案,比如百度的 uid-generator,微信的 SEQSVR。基本上都是都上面一些方案的優化,這裡就不做詳細介紹了。在實際使用中,需要根據自身業務場景來選取合適的方案,也並非大而全的方案就是好的方案。
參考文章:
-
Leaf——美團點評分散式ID生成系統
-
電商高併發、高流量下分散式 ID 的解決方案
全文完
以下文章您可能也會感興趣:
我們正在招聘 Java 工程師,歡迎有興趣的同學投遞簡歷到 [email protected] 。
杏仁技術站
長按左側二維碼關注我們,這裡有一群熱血青年期待著與您相會。