本文主要介紹在一個(gè)分布式系統(tǒng)中, 怎么樣生成全局唯一的 ID
一, 問題描述
在分布式系統(tǒng)存在多個(gè) Shard 的場(chǎng)景中, 同時(shí)在各個(gè) Shard 插入數(shù)據(jù)時(shí), 怎么給這些數(shù)據(jù)生成全局的 unique ID?
在單機(jī)系統(tǒng)中 (例如一個(gè) MySQL 實(shí)例), unique ID 的生成是非常簡(jiǎn)單的, 直接利用 MySQL 自帶的自增 ID 功能就可以實(shí)現(xiàn).
但在一個(gè)存在多個(gè) Shards 的分布式系統(tǒng) (例如多個(gè) MySQL 實(shí)例組成一個(gè)集群, 在這個(gè)集群中插入數(shù)據(jù)), 這個(gè)問題會(huì)變得復(fù)雜, 所生成的全局的 unique ID 要滿足以下需求:
保證生成的 ID 全局唯一
今后數(shù)據(jù)在多個(gè) Shards 之間遷移不會(huì)受到 ID 生成方式的限制
生成的 ID 中最好能帶上時(shí)間信息, 例如 ID 的前 k 位是 Timestamp, 這樣能夠直接通過對(duì) ID 的前 k 位的排序來對(duì)數(shù)據(jù)按時(shí)間排序
生成的 ID 最好不大于 64 bits
生成 ID 的速度有要求. 例如, 在一個(gè)高吞吐量的場(chǎng)景中, 需要每秒生成幾萬(wàn)個(gè) ID (Twitter 最新的峰值到達(dá)了 143,199 Tweets/s, 也就是 10萬(wàn)+/秒)
整個(gè)服務(wù)最好沒有單點(diǎn)
如果沒有上面這些限制, 問題會(huì)相對(duì)簡(jiǎn)單, 例如:
直接利用 UUID.randomUUID() 接口來生成 unique ID (http://www.ietf.org/rfc/rfc4122.txt). 但這個(gè)方案生成的 ID 有 128 bits, 另外, 生成的 ID 中也沒有帶 Timestamp
利用一個(gè)中心服務(wù)器來統(tǒng)一生成 unique ID. 但這種方案可能存在單點(diǎn)問題; 另外, 要支持高吞吐率的系統(tǒng), 這個(gè)方案還要做很多改進(jìn)工作 (例如, 每次從中心服務(wù)器批量獲取一批 IDs, 提升 ID 產(chǎn)生的吞吐率)
Flickr 的做法 (http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/). 但他這個(gè)方案 ID 中沒有帶 Timestamp, 生成的 ID 不能按時(shí)間排序
在要滿足前面 6 點(diǎn)要求的場(chǎng)景中, 怎么來生成全局 unique ID 呢?
Twitter 的 Snowflake 是一種比較好的做法. 下面主要介紹 Twitter Snowflake, 以及它的變種
二, Twitter Snowflake
https://github.com/twitter/snowflake
Snowflake 生成的 unique ID 的組成 (由高位到低位):
41 bits: Timestamp (毫秒級(jí))
10 bits: 節(jié)點(diǎn) ID (datacenter ID 5 bits + worker ID 5 bits)
12 bits: sequence number
一共 63 bits (最高位是 0)
unique ID 生成過程:
10 bits 的機(jī)器號(hào), 在 ID 分配 Worker 啟動(dòng)的時(shí)候, 從一個(gè) Zookeeper 集群獲取 (保證所有的 Worker 不會(huì)有重復(fù)的機(jī)器號(hào))
41 bits 的 Timestamp: 每次要生成一個(gè)新 ID 的時(shí)候, 都會(huì)獲取一下當(dāng)前的 Timestamp, 然后分兩種情況生成 sequence number:
如果當(dāng)前的 Timestamp 和前一個(gè)已生成 ID 的 Timestamp 相同 (在同一毫秒中), 就用前一個(gè) ID 的 sequence number + 1 作為新的 sequence number (12 bits); 如果本毫秒內(nèi)的所有 ID 用完, 等到下一毫秒繼續(xù) (這個(gè)等待過程中, 不能分配出新的 ID)
如果當(dāng)前的 Timestamp 比前一個(gè) ID 的 Timestamp 大, 隨機(jī)生成一個(gè)初始 sequence number (12 bits) 作為本毫秒內(nèi)的第一個(gè) sequence number
整個(gè)過程中, 只是在 Worker 啟動(dòng)的時(shí)候會(huì)對(duì)外部有依賴 (需要從 Zookeeper 獲取 Worker 號(hào)), 之后就可以獨(dú)立工作了, 做到了去中心化.
異常情況討論:
在獲取當(dāng)前 Timestamp 時(shí), 如果獲取到的時(shí)間戳比前一個(gè)已生成 ID 的 Timestamp 還要小怎么辦? Snowflake 的做法是繼續(xù)獲取當(dāng)前機(jī)器的時(shí)間, 直到獲取到更大的 Timestamp 才能繼續(xù)工作 (在這個(gè)等待過程中, 不能分配出新的 ID)
從這個(gè)異常情況可以看出, 如果 Snowflake 所運(yùn)行的那些機(jī)器時(shí)鐘有大的偏差時(shí), 整個(gè) Snowflake 系統(tǒng)不能正常工作 (偏差得越多, 分配新 ID 時(shí)等待的時(shí)間越久)
從 Snowflake 的官方文檔 (https://github.com/twitter/snowflake/#system-clock-dependency) 中也可以看到, 它明確要求 "You should use NTP to keep your system clock accurate". 而且最好把 NTP 配置成不會(huì)向后調(diào)整的模式. 也就是說, NTP 糾正時(shí)間時(shí), 不會(huì)向后回?fù)軝C(jī)器時(shí)鐘.
三, Snowflake 的其他變種
Snowflake 有一些變種, 各個(gè)應(yīng)用結(jié)合自己的實(shí)際場(chǎng)景對(duì) Snowflake 做了一些改動(dòng). 這里主要介紹 3 種.
- Boundary flake
http://boundary.com/blog/2012/01/12/flake-a-decentralized-k-ordered-unique-id-generator-in-erlang/
變化:
ID 長(zhǎng)度擴(kuò)展到 128 bits:
最高 64 bits 時(shí)間戳;
然后是 48 bits 的 Worker 號(hào) (和 Mac 地址一樣長(zhǎng));
最后是 16 bits 的 Seq Number
由于它用 48 bits 作為 Worker ID, 和 Mac 地址的長(zhǎng)度一樣, 這樣啟動(dòng)時(shí)不需要和 Zookeeper 通訊獲取 Worker ID. 做到了完全的去中心化
基于 Erlang
它這樣做的目的是用更多的 bits 實(shí)現(xiàn)更小的沖突概率, 這樣就支持更多的 Worker 同時(shí)工作. 同時(shí), 每毫秒能分配出更多的 ID
- Simpleflake
http://engineering.custommade.com/simpleflake-distributed-id-generation-for-the-lazy/
Simpleflake 的思路是取消 Worker 號(hào), 保留 41 bits 的 Timestamp, 同時(shí)把 sequence number 擴(kuò)展到 22 bits;
Simpleflake 的特點(diǎn):
sequence number 完全靠隨機(jī)產(chǎn)生 (這樣也導(dǎo)致了生成的 ID 可能出現(xiàn)重復(fù))
沒有 Worker 號(hào), 也就不需要和 Zookeeper 通訊, 實(shí)現(xiàn)了完全去中心化
Timestamp 保持和 Snowflake 一致, 今后可以無(wú)縫升級(jí)到 Snowflake
Simpleflake 的問題就是 sequence number 完全隨機(jī)生成, 會(huì)導(dǎo)致生成的 ID 重復(fù)的可能. 這個(gè)生成 ID 重復(fù)的概率隨著每秒生成的 ID 數(shù)的增長(zhǎng)而增長(zhǎng).
所以, Simpleflake 的限制就是每秒生成的 ID 不能太多 (最好小于 100次/秒, 如果大于 100次/秒的場(chǎng)景, Simpleflake 就不適用了, 建議切換回 Snowflake).
- instagram 的做法
先簡(jiǎn)單介紹一下 instagram 的分布式存儲(chǔ)方案:
先把每個(gè) Table 劃分為多個(gè)邏輯分片 (logic Shard), 邏輯分片的數(shù)量可以很大, 例如 2000 個(gè)邏輯分片
然后制定一個(gè)規(guī)則, 規(guī)定每個(gè)邏輯分片被存儲(chǔ)到哪個(gè)數(shù)據(jù)庫(kù)實(shí)例上面; 數(shù)據(jù)庫(kù)實(shí)例不需要很多. 例如, 對(duì)有 2 個(gè) PostgreSQL 實(shí)例的系統(tǒng) (instagram 使用 PostgreSQL); 可以使用奇數(shù)邏輯分片存放到第一個(gè)數(shù)據(jù)庫(kù)實(shí)例, 偶數(shù)邏輯分片存放到第二個(gè)數(shù)據(jù)庫(kù)實(shí)例的規(guī)則
每個(gè) Table 指定一個(gè)字段作為分片字段 (例如, 對(duì)用戶表, 可以指定 uid 作為分片字段)
插入一個(gè)新的數(shù)據(jù)時(shí), 先根據(jù)分片字段的值, 決定數(shù)據(jù)被分配到哪個(gè)邏輯分片 (logic Shard)
然后再根據(jù) logic Shard 和 PostgreSQL 實(shí)例的對(duì)應(yīng)關(guān)系, 確定這條數(shù)據(jù)應(yīng)該被存放到哪臺(tái) PostgreSQL 實(shí)例上
instagram unique ID 的組成:
41 bits: Timestamp (毫秒)
13 bits: 每個(gè) logic Shard 的代號(hào) (最大支持 8 x 1024 個(gè) logic Shards)
10 bits: sequence number; 每個(gè) Shard 每毫秒最多可以生成 1024 個(gè) ID
生成 unique ID 時(shí), 41 bits 的 Timestamp 和 Snowflake 類似, 這里就不細(xì)說了.
主要介紹一下 13 bits 的 logic Shard 代號(hào) 和 10 bits 的 sequence number 怎么生成.
logic Shard 代號(hào):
假設(shè)插入一條新的用戶記錄, 插入時(shí), 根據(jù) uid 來判斷這條記錄應(yīng)該被插入到哪個(gè) logic Shard 中.
假設(shè)當(dāng)前要插入的記錄會(huì)被插入到第 1341 號(hào) logic Shard 中 (假設(shè)當(dāng)前的這個(gè) Table 一共有 2000 個(gè) logic Shard)
新生成 ID 的 13 bits 段要填的就是 1341 這個(gè)數(shù)字
sequence number 利用 PostgreSQL 每個(gè) Table 上的 auto-increment sequence 來生成:
如果當(dāng)前表上已經(jīng)有 5000 條記錄, 那么這個(gè)表的下一個(gè) auto-increment sequence 就是 5001 (直接調(diào)用 PL/PGSQL 提供的方法可以獲取到)
然后把 這個(gè) 5001 對(duì) 1024 取模就得到了 10 bits 的 sequence number
instagram 這個(gè)方案的優(yōu)勢(shì)在于:
利用 logic Shard 號(hào)來替換 Snowflake 使用的 Worker 號(hào), 就不需要到中心節(jié)點(diǎn)獲取 Worker 號(hào)了. 做到了完全去中心化
另外一個(gè)附帶的好處就是, 可以通過 ID 直接知道這條記錄被存放在哪個(gè) logic Shard 上
同時(shí), 今后做數(shù)據(jù)遷移的時(shí)候, 也是按 logic Shard 為單位做數(shù)據(jù)遷移的, 所以這種做法也不會(huì)影響到今后的數(shù)據(jù)遷移
