snowflake 是什麼
snowflake 單詞原意為雪花，是 twitter 開源的一種分佈式 ID 生成算法。該算法可以保證在不借助第三方服務或者說工具的情況下，在多臺機器上持續生成保證唯一性的 64 位整型 ID。
snowflake ID 的組成
snowflake 將 ID 的 64 位劃分為四塊區域，分別填入的是當前服務實例的數據中心 ID，節點 ID，時間戳，以及相同時間戳下的遞增序號。
以下是 snowflake 原始算法中，各字段的順序以及所佔的位數：
ID組成圖
小提示，在生產環境，使用 snowflake 的思想生成分佈式 ID 時，這些字段所佔的位數可以根據自身業務靈活調整。本文如無特殊說明，都是針對 snowflake 原始算法進行講解。
數據中心 ID 和節點 ID
不同的服務實例間，使用不同的數據中心 ID 和節點 ID，可以保證生成的 ID 不重複。
從該算法使用數據中心 ID 加節點 ID（而不是單個服務實例 ID）的方式決定服務實例的唯一性，也可以看出，該算法設計之初是一個非常面向具體業務場景的算法。
數據中心 ID 和節點 ID 分別佔 5 位。即整個系統最多可以有 32 個數據中心，每個數據中心最多可以有 32 個節點。為什麼數據中心 ID 和節點 ID 是 5 位？額，應該也是 twitter 根據當時的業務拍腦袋拍的。
那麼數據中心 ID 和節點 ID 怎麼生成呢？這點不由 snowflake 負責，也即這兩個 ID 在多個服務實例之間不重複是由 snowflake 的調用方保證的。比如一種簡單的方式是直接使用靜態配置，這種方式適用於節點數量比較少且相對固定的情況下。
時間戳
如前文圖中展示，snowflake 使用 42 位存儲時間戳。
我們平時所說的 UNIX 時間戳，指的是從 1970 年 1 月 1 號 0 點到現在所經過的時間。如果單位是毫秒，需要使用 64 位整型存儲。
由於在 snowflake 算法中，只需要保證時間戳隨時間遞增即可，所以 snowflake 中的時間戳是使用 UNIX 時間戳減去一個基準時間，這個基準時間在原版代碼中是 1288834974657，也即2010/11/4 9:42:54.657。你也可以換種方式理解，即從 2010 年 11 月 4 號 xxx 這個基準時間點到現在所經過的時間。
減去自定義的基準時間後，時間戳比 UNIX 時間戳小了很多，snowflake 使用得到的時間戳的低 42 位作為 ID 的一部分（即 ID 的高 42 位）。如下圖所示：
時間戳取值圖
時間戳可能存在的問題
首先，時間戳隨著系統時間增長，當時間戳的第 42 位增長到 1 時，ID 的最高位也將變為 1。由於 snowflake 默認使用有符號 64 位整型，最高位為符號位，這將導致生成的 ID 變為負數。
通過如下公式(1<<41) / 1000 / 60 / 60 / 24 / 365計算，可知道在基準時間上（snowflake 默認的基準時間是 2010/11/4）再過 69.7 年，將出現 ID 為負數的情況。
這裡展開說明下，如果想要生成的 ID 永遠不為負數，可以保持 ID 的最高位始終為 0，其他的字段減少 1 位，比如說時間戳只使用 41 位。這樣時間戳出現翻轉歸零的時長縮短 1 倍，大概為 35 年，基本上是可接受的。你可能會說，69.7 年已經足夠長啦，到出現負數的時候我早退休了，哪管它洪水滔天。但是假設你要設計一個 32 位的分佈式 ID 生成器呢？此時你必然需要考慮哪些字段可以縮短，時間戳多久出現翻轉（也即 ID 可能翻轉）不影響業務。
第二，假如單臺機器上，獲取當前時間的方法出現時間回退，那麼可能出現 ID 重複的情況。
第三，假如服務重啟，重啟後時間戳沒變（即 1 毫秒內重啟成功），那麼此時 snowflake 丟失了重啟前當前時間戳的遞增序號，遞增序號重新從 0 開始，也可能出現和重啟前生成的 ID 重複的情況。
最後一點值得注意的是，一個服務上線後，基準時間點不應該隨意修改。避免造成時間戳回退。
遞增序號
如前文圖中展示，snowflake 使用 12 位存儲遞增序號。
為什麼在時間戳的基礎之上，還需要遞增序號？因為即使是在單個服務實例中，我們也可能需要在 1 毫秒內生成多個 ID，這種情況下，同 1 毫秒下的 seq 會從 0 開始順序遞增。12 位的 seq 範圍為[0, 4095]，如果 1 毫秒內生成的 ID 數量超過 4096 怎麼辦呢，snowflake 會阻塞直到時間戳更新後，再生成可用的 ID 返回給調用方。相關代碼如下：
<code>now = time.Now().UnixNano() / 1e6// 時間戳回退，返回錯誤if now < n.lastTs {return -1, ErrGen}// 時間戳相同時，使用遞增序號解決衝突if now == n.lastTs {n.seq = (n.seq + 1) & n.seqMask// 遞增序號翻轉為 0，表示該時間戳下的序號已經全部用完，阻塞等待系統時間增長if n.seq == 0 {for now <= n.lastTs {now = time.Now().UnixNano() / 1e6}}} else {n.seq = 0}n.lastTs = now/<code>完整代碼見：https://github.com/q191201771/naza/blob/master/pkg/snowflake/snowflake.go
snowflake 1 毫秒可產生多少 ID？
32（5位數據中心ID） * 32（5位節點ID） * 4096（遞增序號） = 4194304
所生成 ID 的特點
單個服務實例生成的 ID 是遞增的；多個服務實例生成的 ID，受限於系統時間不一致，或者是節點 ID 的大小，可能出現整體 ID 不遞增的情況。
總結
好了，至此，snowflake 算法就基本介紹完畢了。算法的實現部分十分簡單，不到 100 行代碼，基本上就是一些位操作。
感興趣的可以看看我寫的一份 Go 語言實現：snowflake.go[1]，在 twitter 原始 scala 實現版本的基礎上，額外支持配置所有的字段所佔的位數（比如支持將數據中心 ID 所佔位數設置為 0，從而只使用節點 ID），支持配置基準時間，支持配置是否永遠不返回負數 ID，支持併發調用。
twitter 放在 github 上的原始版本，master 分支的代碼已經刪了，只能在 release 下載老版本的源碼壓縮包。
最後，感謝閱讀，如果覺得文章還不錯，可以給我的 github 項目naza[2]來個 star 哈。該項目是我學習 Go 時寫的一些輪子代碼集合，後續我還會寫一些文章逐個介紹裡面的輪子以及一些寫 Go 代碼的技巧。
naza 項目地址：https://github.com/q191201771/naza
naza 的其他的文章：
- Go 創建對象時，如何優雅的傳遞初始化參數[3]
- 給 Go 程序加入編譯版本時間等信息[4]
[1]
snowflake.go: https://github.com/q191201771/naza/blob/master/pkg/snowflake/snowflake.go
[2]
naza: https://github.com/q191201771/naza
[3]
Go創建對象時，如何優雅的傳遞初始化參數: http://127.0.0.1:4000/p/60015/
[4]
給Go程序加入編譯版本時間等信息: https://pengrl.com/p/37397/
閱讀更多 Go語言中文網 的文章
