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

jopen 9年前發布 | 12K 次閱讀分布式分布式/云計算/大數據

一, 問題描述

在分布式系統存在多個 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 (推ter 最新的峰值到達了 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 呢?

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

二, 推ter Snowflake

https://github.com/推ter/snowflake

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

41 bits: Timestamp (毫秒級)

10 bits: 節點 ID (datacenter ID 5 bits + worker ID 5 bits)

12 bits: sequence number

一共 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/推ter/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 為單位做數據遷移的, 所以這種做法也不會影響到今后的數據遷移

http://darktea.github.io/notes/2013/12/08/Unique-ID

本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1450337879188.html

分布式分布式/云計算/大數據