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

維基百科 Snowflake ID 格式Untitled

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

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

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

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

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

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

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

最終方案。通過(guò)組合時(shí)間戳、進(jìn)程編號(hào)、自增序號(hào)，Twitter 找到了一種分布式高性能全序 ID 生成算法?；舅枷胧牵篌w保證機(jī)器間的時(shí)鐘同步，并利用機(jī)器時(shí)鐘生成時(shí)間戳作為自增 ID，如果兩個(gè)進(jìn)程產(chǎn)生了相同時(shí)間戳，則通過(guò)進(jìn)程編號(hào)進(jìn)一步確認(rèn)其大小。由于一般時(shí)間戳?xí)_到毫秒，為了滿足 QPS 需求，會(huì)留幾位給自增 id，使得 1ms 內(nèi)產(chǎn)生 10+ 個(gè) id。

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

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

開(kāi)源代碼在此[6]，其優(yōu)點(diǎn)如下：

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

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

參考資料

[1]任何想法都?xì)g迎來(lái)提 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