分散式系統中唯一 ID 的生成方法

本文主要介紹在一個分散式系統中, 怎麼樣生成全局唯一的 ID

一, 問題描述

在分散式系統存在多個 Shard 的場景中, 同時在各個 Shard 插入數據時, 怎麼給這些數據生成全局的 unique ID?

在單機系統中 (例如一個 MySQL 實例), unique ID 的生成是非常簡單的, 直接利用 MySQL 自帶的自增 ID 功能就可以實現.

但在一個存在多個 Shards 的分散式系統 (例如多個 MySQL 實例組成一個集群, 在這個集群中插入數據), 這個問題會變得複雜, 所生成的全局的 unique ID 要滿足以下需求:

保證生成的 ID 全局唯一

今後數據在多個 Shards 之間遷移不會受到 ID 生成方式的限制

生成的 ID 中最好能帶上時間信息, 例如 ID 的前 k 位是 Timestamp, 這樣能夠直接通過對 ID 的前 k 位的排序來對數據按時間排序

生成的 ID 最好不大於 64 bits

生成 ID 的速度有要求. 例如, 在一個高吞吐量的場景中, 需要每秒生成幾萬個 ID (Twitter 最新的峰值到達了 143,199 Tweets/s, 也就是 10萬+/秒)

整個服務最好沒有單點

如果沒有上面這些限制, 問題會相對簡單, 例如:

直接利用 UUID.randomUUID() 介面來生成 unique ID

(http://www.ietf.org/rfc/rfc4122.txt). 但這個方案生成的 ID 有 128 bits, 另外, 生成的 ID 中也沒有帶 Timestamp

利用一個中心伺服器來統一生成 unique ID. 但這種方案可能存在單點問題; 另外, 要支持高吞吐率的系統, 這個方案還要做很多改進工作 (例如, 每次從中心伺服器批量獲取一批 IDs, 提升 ID 產生的吞吐率)

Flickr 的做法 (http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/). 但他這個方案 ID 中沒有帶 Timestamp, 生成的 ID 不能按時間排序

在要滿足前面 6 點要求的場景中, 怎麼來生成全局 unique ID 呢?

Twitter 的 Snowflake 是一種比較好的做法. 下面主要介紹 Twitter Snowflake, 以及它的變種

二, Twitter Snowflake

https://github.com/twitter/snowflake

Snowflake 生成的 unique ID 的組成 (由高位到低位):

一共 63 bits (最高位是 0)

unique ID 生成過程:

10 bits 的機器號, 在 ID 分配 Worker 啟動的時候, 從一個 Zookeeper 集群獲取 (保證所有的 Worker 不會有重複的機器號)

41 bits 的 Timestamp: 每次要生成一個新 ID 的時候, 都會獲取一下當前的 Timestamp, 然後分兩種情況生成 sequence number:

如果當前的 Timestamp 和前一個已生成 ID 的 Timestamp 相同 (在同一毫秒中), 就用前一個 ID 的 sequence number + 1 作為新的 sequence number (12 bits); 如果本毫秒內的所有 ID 用完, 等到下一毫秒繼續 (這個等待過程中, 不能分配出新的 ID)

如果當前的 Timestamp 比前一個 ID 的 Timestamp 大, 隨機生成一個初始 sequence number (12 bits) 作為本毫秒內的第一個 sequence number

整個過程中, 只是在 Worker 啟動的時候會對外部有依賴 (需要從 Zookeeper 獲取 Worker 號), 之後就可以獨立工作了, 做到了去中心化.

異常情況討論:

在獲取當前 Timestamp 時, 如果獲取到的時間戳比前一個已生成 ID 的 Timestamp 還要小怎麼辦? Snowflake 的做法是繼續獲取當前機器的時間, 直到獲取到更大的 Timestamp 才能繼續工作 (在這個等待過程中, 不能分配出新的 ID)

從這個異常情況可以看出, 如果 Snowflake 所運行的那些機器時鐘有大的偏差時, 整個 Snowflake 系統不能正常工作 (偏差得越多, 分配新 ID 時等待的時間越久)

從 Snowflake 的官方文檔 (https://github.com/twitter/snowflake/#system-clock-dependency) 中也可以看到, 它明確要求 「You should use NTP to keep your system clock accurate」. 而且最好把 NTP 配置成不會向後調整的模式. 也就是說, NTP 糾正時間時, 不會向後回撥機器時鐘.

三, Snowflake 的其他變種

Snowflake 有一些變種, 各個應用結合自己的實際場景對 Snowflake 做了一些改動. 這裡主要介紹 3 種.

1. Boundary flake

http://boundary.com/blog/2012/01/12/flake-a-decentralized-k-ordered-unique-id-generator-in-erlang/

變化:

ID 長度擴展到 128 bits:

最高 64 bits 時間戳;

然後是 48 bits 的 Worker 號 (和 Mac 地址一樣長);

最後是 16 bits 的 Seq Number

由於它用 48 bits 作為 Worker ID, 和 Mac 地址的長度一樣, 這樣啟動時不需要

和 Zookeeper 通訊獲取 Worker ID. 做到了完全的去中心化

基於 Erlang

它這樣做的目的是用更多的 bits 實現更小的衝突概率, 這樣就支持更多的 Worker 同時工作. 同時, 每毫秒能分配出更多的 ID

2. Simpleflake

http://engineering.custommade.com/simpleflake-distributed-id-generation-for-the-lazy/

Simpleflake 的思路是取消 Worker 號, 保留 41 bits 的 Timestamp, 同時把 sequence number 擴展到 22 bits;

Simpleflake 的特點:

sequence number 完全靠隨機產生 (這樣也導致了生成的 ID 可能出現重複)

沒有 Worker 號, 也就不需要和 Zookeeper 通訊, 實現了完全去中心化

Timestamp 保持和 Snowflake 一致, 今後可以無縫升級到 Snowflake

Simpleflake 的問題就是 sequence number 完全隨機生成, 會導致生成的 ID 重複的可能. 這個生成 ID 重複的概率隨著每秒生成的 ID 數的增長而增長.

所以, Simpleflake 的限制就是每秒生成的 ID 不能太多 (最好小於 100次/秒, 如果大於 100次/秒的場景, Simpleflake 就不適用了, 建議切換回 Snowflake).

3. instagram 的做法

先簡單介紹一下 instagram 的分散式存儲方案:

先把每個 Table 劃分為多個邏輯分片 (logic Shard), 邏輯分片的數量可以很大, 例如 2000 個邏輯分片

然後制定一個規則, 規定每個邏輯分片被存儲到哪個資料庫實例上面; 資料庫實例不需要很多. 例如, 對有 2 個 PostgreSQL 實例的系統 (instagram 使用 PostgreSQL); 可以使用奇數邏輯分片存放到第一個資料庫實例, 偶數邏輯分片存放到第二個資料庫實例的規則

每個 Table 指定一個欄位作為分片欄位 (例如, 對用戶表, 可以指定 uid 作為分片欄位)

插入一個新的數據時, 先根據分片欄位的值, 決定數據被分配到哪個邏輯分片 (logic Shard)

然後再根據 logic Shard 和 PostgreSQL 實例的對應關係, 確定這條數據應該被存放到哪台 PostgreSQL 實例上

instagram unique ID 的組成:

41 bits: Timestamp (毫秒)

13 bits: 每個 logic Shard 的代號 (最大支持 8 x 1024 個 logic Shards)

10 bits: sequence number; 每個 Shard 每毫秒最多可以生成 1024 個 ID

生成 unique ID 時, 41 bits 的 Timestamp 和 Snowflake 類似, 這裡就不細說了.

主要介紹一下 13 bits 的 logic Shard 代號 和 10 bits 的 sequence number 怎麼生成.

logic Shard 代號:

假設插入一條新的用戶記錄, 插入時, 根據 uid 來判斷這條記錄應該被插入到哪個 logic Shard 中.

假設當前要插入的記錄會被插入到第 1341 號 logic Shard 中 (假設當前的這個 Table 一共有 2000 個 logic Shard)

新生成 ID 的 13 bits 段要填的就是 1341 這個數字

sequence number 利用 PostgreSQL 每個 Table 上的 auto-increment sequence 來生成:

如果當前表上已經有 5000 條記錄, 那麼這個表的下一個 auto-increment sequence 就是 5001 (直接調用 PL/PGSQL 提供的方法可以獲取到)

然後把 這個 5001 對 1024 取模就得到了 10 bits 的 sequence number

instagram 這個方案的優勢在於:

利用 logic Shard 號來替換 Snowflake 使用的 Worker 號, 就不需要到中心節點獲取 Worker 號了. 做到了完全去中心化

另外一個附帶的好處就是, 可以通過 ID 直接知道這條記錄被存放在哪個 logic Shard 上

同時, 今後做數據遷移的時候, 也是按 logic Shard 為單位做數據遷移的, 所以這種做法也不會影響到今後的數據遷移

編輯 | 碼哥

圖片源於網路，版權歸原作者所有

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！

請您繼續閱讀更多來自 程序員之家 的精彩文章: