ID生成策略——SnowFlake

一、遇到問題

某個項目采用了數據庫（MySQL）自增ID作為主要業務數據的主鍵。數據庫自增ID使用簡單，自動編號，速度快，而且是增量增長，按順序存放，對于檢索非常有利。

單庫環境下，數據庫自增ID問題不大。但在分布式環境或分庫分表環境下，數據庫自增ID逐漸暴露出一些問題。例如，分庫分表的情況下保證ID唯一變得困難；訂單號等業務數據如果用數據庫自增ID，競對很容易算出大概的業務量。

二、常見的ID生成策略

1、數據庫自增ID（前面提到了）

2、UUID

算法的核心思想是結合機器的網卡、當地時間、一個隨記數來生成UUID。

優點：本地生成，生成簡單，性能好，沒有高可用風險

缺點：長度過長，存儲冗余，且無序不可讀，查詢效率低

3、Redis生成ID

Redis生成ID可以看做數據庫自增ID的升級版。Redis的所有命令操作都是單線程的，本身提供像 incr 和 increby 這樣的自增原子命令，所以能保證生成的 ID 肯定是唯一有序的。

優點：不依賴于數據庫，靈活方便，且性能優于數據庫；數字ID天然排序，對分頁或者需要排序的結果很有幫助。

缺點：如果系統中沒有Redis，還需要引入新的組件，增加系統復雜度；需要編碼和配置的工作量比較大。

考慮到單節點的性能瓶頸，可以使用 Redis 集群來獲取更高的吞吐量。假如一個集群中有5臺 Redis。可以初始化每臺 Redis 的值分別是1, 2, 3, 4, 5，然后步長都是 5。各個 Redis 生成的 ID 為

4、Twitter的snowflake算法。

三、snowflake算法

snowflake算法，采用64位二進制整數。二進制具體位數含義如下圖。

1位，不用。二進制中最高位為1的都是負數，但是我們生成的id都使用正數，所以這個最高位固定是0

41位，用來記錄時間戳（毫秒）。

如果只用來表示正整數（計算機中正數包含0），可以表示的數值范圍是：0 至 241?1，減1是因為可表示的數值范圍是從0開始算的，而不是1。

也就是說41位可以表示241?1個毫秒的值，轉化成單位年則是(241?1)/(1000?60?60?24?365)=69年

10位，用來記錄工作機器id。

可以部署在1024個節點，包括5位datacenterId和5位workerId

12位，序列號，用來記錄同毫秒內產生的不同id。

12位（bit）可以表示的最大正整數是4095，即可以用0、1、2、3、....4095這4096個數字，來表示同一機器同一時間截（毫秒)內產生的4096個ID序號

大多數人都知道這個算法，但Twitter 利用 zookeeper 還做了很多工程上的實現，感興趣可以看https://github.com/twitter/snowflake

截取git上該工程的主要文件目錄， 

git工程README.md文件中有這么一段話

We have retired the initial release of Snowflake and working on open sourcing the next version based on Twitter-server, in a form that can run anywhere without requiring Twitter's own infrastructure services.

Twitter幾年前就停止了對這個項目的維護，新的版本也沒見著放出來。好在現有版本的核心算法已經能夠滿足常規的需求。

當然，snowflake有眾多優點的同時也是有缺點的。

優點：

毫秒數在高位，自增序列在低位，整個ID都是趨勢遞增的。

不依賴數據庫等第三方系統，以服務的方式部署，穩定性更高，生成ID的性能也是非常高的。

可以根據自身業務特性分配bit位，非常靈活。

缺點：

強依賴機器時鐘，如果機器上時鐘回撥，會導致發號重復或者服務會處于不可用狀態。

強依賴時鐘在有些情況下很致命，我個人就遇到過服務器剛重啟的短時間內時間沒有同步，造成生成ID出問題的情況！

四、一些改進策略

1、美團Leaf比較完美的方案

美團Leaf比較好的解決了這些問題，參看《Leaf——來自美團點評的分布式ID生成系統》

美團Leaf的方案核心有兩點

（1）依靠zookeeper實現workerId的自動化租用

（2）通過算法解決了時鐘回撥問題

美團Leaf目前是開源軟件，可以在https://github.com/weizhenyi/leaf-snowflake下載

2、一個候選人不嚴謹但成本很低的實現

我在面試中，一個候選人提出的方法也比較有意思（盡管這個方法不嚴謹）。

在redis中設置一個整數變量workerNum，初始值為0，snowflake id生成客戶端每次啟動時讀取redis中的變量，用workerNum%1024作為worker的值，然后把redis中的workerNum+1。

在idworker數量不多的情況下，這個方案一般不會出現workerId重復（因為隨著業務的迭代，一般情況下idworker過一段時間都會因為業務部署而重啟）。如果研發資源特別有限，又想使用snowflake可以考慮一下這個辦法。 

3、個人項目中hash分庫的解決辦法

實際使用中，有時候ID需要支持分庫分表，snowflake的默認實現對這塊支持得不夠。在業務量不大的情況下，snowflake生成的id序列號部分大多都是0，轉換為十進制會是偶數。用這個id通過取模hash分庫，顯然不平均。

萬一有這樣的需求怎么辦呢？可以考慮借助ID時間戳部分實現均勻分布

（1）分庫分表邏輯使用ID中時間戳部分做取模。這個方法需要把10進制ID轉成2進制，然后移位，再進行計算。比較麻煩

（2）生成ID的時候把序列號部分尾數用時間戳對應的位置覆蓋。截段代碼，這段代碼的取值能保證ID除以128的余數均勻分布。