分布式高性能 ID 生成算法——Snowflake ID。

維基百科 Snowflake ID 格式Untitled

來源：https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake[2]

雪花算法(Snowflake ID) 是時下應(yīng)用相當(dāng)廣的一個分布式全序 ID 生成算法，這篇 Twitter 官方博客 2010 年的文章，宣告了雪花算法的誕生，概略的介紹了 Twitter 當(dāng)時對分布式 ID 生產(chǎn)算法需求的背景(context)、可選項和最終方案。理解了其產(chǎn)生時的需求，也就理解了算法的一半，推薦一讀。

問題背景。Twitter 的數(shù)據(jù)庫經(jīng)歷了一個從小到大、從單機到分布式的增長過程。但無論在分布式數(shù)據(jù)庫 Cassandra[3] 中，還是使用 gizzard[4] 方案水平擴容的多機 MySQL 中，都沒有一個滿足 Twitter 當(dāng)時需求的全局 ID 生成方案。那 Twitter 當(dāng)時對全局 ID 的要求是什么呢?

• 每秒產(chǎn)生數(shù)萬個 ID。這就限制了不能使用依賴多機溝通來產(chǎn)生 ID。畢竟一次網(wǎng)絡(luò)通信延遲都會有 1ms+，自然難以實現(xiàn)超過 1k 的 qps。
• 所有 ID 滿足全序(roughly sortable)關(guān)系。即任意兩個 id 都是可比的，畢竟 Feed 流中所有 Tweet 的排序都依賴此 ID。
• 長度不超過 64 bit 。Twitter 以前經(jīng)歷過隨著系統(tǒng)體量的增大而痛苦的增加 ID bit 數(shù)的過程，這次希望一步到位，但同時又不太長。

可選項?；?MySQL 的自增 id，類似于 flickr[5]的方案。但不通過多機同步，難以提供全序保證。

一些現(xiàn)成的 UUID 算法，但其生成的 ID 都是 128 bit。

基于 Zookeeper 的全局自增 id 。自然，由于 Zab 等共識算法，其能保證全序，卻不能滿足 Twitter 的性能需求。

最終方案。通過組合時間戳、進程編號、自增序號，Twitter 找到了一種分布式高性能全序 ID 生成算法。基本思想是，大體保證機器間的時鐘同步，并利用機器時鐘生成時間戳作為自增 ID，如果兩個進程產(chǎn)生了相同時間戳，則通過進程編號進一步確認(rèn)其大小。由于一般時間戳?xí)_到毫秒，為了滿足 QPS 需求，會留幾位給自增 id，使得 1ms 內(nèi)產(chǎn)生 10+ 個 id。

最終格式如上圖，1 bit 的符號位，固定為0，以保證在有符號數(shù)體系下 ID 也為正數(shù)。41 bit 的時間戳，單位 ms，時間戳本身是個相對值，其起始點可以自行設(shè)置。10 bit 的進程編號，最終可支持含有 1024 個進程的單機或者集群，但一般來說，每個機器一個進程。12 bit 的自增序號，每毫秒最多允許產(chǎn)生 4k+ 個 ID。

在實際使用時，可以在保證總 bit 數(shù)的情況下，按需調(diào)整三個字段的 bit 數(shù)。比如進程數(shù)確定不會超過 100 個，則可以將對應(yīng)字段縮短為 7 bit。進程序號可以在初始時通過一個全局發(fā)號器來分配，比如 Zookeeper。在之后的運行或者重啟時，無需再改。

開源代碼在此[6]，其優(yōu)點如下：

• 高性能(Performance)。單進程 10k+ 的 QPS，平均 2ms 的延遲。
• 無需溝通(Uncoordinated)。產(chǎn)生 ID 的這組進程，可以分布在多個數(shù)據(jù)中心的多個機器，而在產(chǎn)生數(shù)據(jù)時無需進行互相溝通(除了 NTP 時間戳同步)。
• 大致按時間有序(Roughly Time Ordered)?？梢詮?ID 中解析出時間戳。
• 可直接排序(Directly Sortable)。無需解析即可直接排序。
• 緊湊(Compact)。不要 128 bit 就要 64 bit。
• 高可用(Highly Available)。將進程分布在多數(shù)據(jù)中心的多臺機器上，只要有一臺機器活著，就仍能提供服務(wù)。

一些問題。雪花算法會隱式的依賴機器時鐘，雖然并不嚴(yán)格。但使用者需要保證產(chǎn)生 ID 的所有機器通過 NTP 保持大致的時間同步。snowflake 算法可以處理由于 NTP 時鐘同步帶來的時鐘回退問題。但解決方法很粗暴，即發(fā)現(xiàn)時鐘回退了就死等到時鐘超過上一次 ID 產(chǎn)生的對應(yīng)時間點。也正因如此，需要維持所有機器時鐘大致同步。

參考資料

[1]任何想法都?xì)g迎來提 issue: https://github.com/DistSysCorp/ArticleListWeekly/issues

[2]Announcing Snowflake: https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake

[3]Cassandra: Open Source NoSQL Database: http://cassandra.apache.org/

[4]gizzard: http://github.com/twitter/gizzard

[5]Ticket Servers: Distributed Unique Primary Keys on the Cheap: https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

[6]snowflake 2010: https://github.com/twitter-archive/snowflake/tree/snowflake-2010