ID生成策略——SnowFlake

一、遇到問(wèn)題

某個(gè)項(xiàng)目采用了數(shù)據(jù)庫(kù)（MySQL）自增ID作為主要業(yè)務(wù)數(shù)據(jù)的主鍵。數(shù)據(jù)庫(kù)自增ID使用簡(jiǎn)單，自動(dòng)編號(hào)，速度快，而且是增量增長(zhǎng)，按順序存放，對(duì)于檢索非常有利。

單庫(kù)環(huán)境下，數(shù)據(jù)庫(kù)自增ID問(wèn)題不大。但在分布式環(huán)境或分庫(kù)分表環(huán)境下，數(shù)據(jù)庫(kù)自增ID逐漸暴露出一些問(wèn)題。例如，分庫(kù)分表的情況下保證ID唯一變得困難；訂單號(hào)等業(yè)務(wù)數(shù)據(jù)如果用數(shù)據(jù)庫(kù)自增ID，競(jìng)對(duì)很容易算出大概的業(yè)務(wù)量。

二、常見(jiàn)的ID生成策略

1、數(shù)據(jù)庫(kù)自增ID（前面提到了）

2、UUID

算法的核心思想是結(jié)合機(jī)器的網(wǎng)卡、當(dāng)?shù)貢r(shí)間、一個(gè)隨記數(shù)來(lái)生成UUID。

優(yōu)點(diǎn)：本地生成，生成簡(jiǎn)單，性能好，沒(méi)有高可用風(fēng)險(xiǎn)

缺點(diǎn)：長(zhǎng)度過(guò)長(zhǎng)，存儲(chǔ)冗余，且無(wú)序不可讀，查詢效率低

3、Redis生成ID

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

優(yōu)點(diǎn)：不依賴于數(shù)據(jù)庫(kù)，靈活方便，且性能優(yōu)于數(shù)據(jù)庫(kù)；數(shù)字ID天然排序，對(duì)分頁(yè)或者需要排序的結(jié)果很有幫助。

缺點(diǎn)：如果系統(tǒng)中沒(méi)有Redis，還需要引入新的組件，增加系統(tǒng)復(fù)雜度；需要編碼和配置的工作量比較大。

考慮到單節(jié)點(diǎn)的性能瓶頸，可以使用 Redis 集群來(lái)獲取更高的吞吐量。假如一個(gè)集群中有5臺(tái) Redis?？梢猿跏蓟颗_(tái) Redis 的值分別是1, 2, 3, 4, 5，然后步長(zhǎng)都是 5。各個(gè) Redis 生成的 ID 為

4、Twitter的snowflake算法。

三、snowflake算法

snowflake算法，采用64位二進(jìn)制整數(shù)。二進(jìn)制具體位數(shù)含義如下圖。

1位，不用。二進(jìn)制中最高位為1的都是負(fù)數(shù)，但是我們生成的id都使用正數(shù)，所以這個(gè)最高位固定是0

41位，用來(lái)記錄時(shí)間戳（毫秒）。

如果只用來(lái)表示正整數(shù)（計(jì)算機(jī)中正數(shù)包含0），可以表示的數(shù)值范圍是：0 至 241?1，減1是因?yàn)榭杀硎镜臄?shù)值范圍是從0開(kāi)始算的，而不是1。

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

10位，用來(lái)記錄工作機(jī)器id。

可以部署在1024個(gè)節(jié)點(diǎn)，包括5位datacenterId和5位workerId

12位，序列號(hào)，用來(lái)記錄同毫秒內(nèi)產(chǎn)生的不同id。

12位（bit）可以表示的最大正整數(shù)是4095，即可以用0、1、2、3、....4095這4096個(gè)數(shù)字，來(lái)表示同一機(jī)器同一時(shí)間截（毫秒)內(nèi)產(chǎn)生的4096個(gè)ID序號(hào)

大多數(shù)人都知道這個(gè)算法，但Twitter 利用 zookeeper 還做了很多工程上的實(shí)現(xiàn)，感興趣可以看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幾年前就停止了對(duì)這個(gè)項(xiàng)目的維護(hù)，新的版本也沒(méi)見(jiàn)著放出來(lái)。好在現(xiàn)有版本的核心算法已經(jīng)能夠滿足常規(guī)的需求。

當(dāng)然，snowflake有眾多優(yōu)點(diǎn)的同時(shí)也是有缺點(diǎn)的。

優(yōu)點(diǎn)：

毫秒數(shù)在高位，自增序列在低位，整個(gè)ID都是趨勢(shì)遞增的。

不依賴數(shù)據(jù)庫(kù)等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的。

可以根據(jù)自身業(yè)務(wù)特性分配bit位，非常靈活。

缺點(diǎn)：

強(qiáng)依賴機(jī)器時(shí)鐘，如果機(jī)器上時(shí)鐘回?fù)埽瑫?huì)導(dǎo)致發(fā)號(hào)重復(fù)或者服務(wù)會(huì)處于不可用狀態(tài)。

強(qiáng)依賴時(shí)鐘在有些情況下很致命，我個(gè)人就遇到過(guò)服務(wù)器剛重啟的短時(shí)間內(nèi)時(shí)間沒(méi)有同步，造成生成ID出問(wèn)題的情況！

四、一些改進(jìn)策略

1、美團(tuán)Leaf比較完美的方案

美團(tuán)Leaf比較好的解決了這些問(wèn)題，參看《Leaf——來(lái)自美團(tuán)點(diǎn)評(píng)的分布式ID生成系統(tǒng)》

美團(tuán)Leaf的方案核心有兩點(diǎn)

（1）依靠zookeeper實(shí)現(xiàn)workerId的自動(dòng)化租用

（2）通過(guò)算法解決了時(shí)鐘回?fù)軉?wèn)題

美團(tuán)Leaf目前是開(kāi)源軟件，可以在https://github.com/weizhenyi/leaf-snowflake下載

2、一個(gè)候選人不嚴(yán)謹(jǐn)?shù)杀竞艿偷膶?shí)現(xiàn)

我在面試中，一個(gè)候選人提出的方法也比較有意思（盡管這個(gè)方法不嚴(yán)謹(jǐn)）。

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

在idworker數(shù)量不多的情況下，這個(gè)方案一般不會(huì)出現(xiàn)workerId重復(fù)（因?yàn)殡S著業(yè)務(wù)的迭代，一般情況下idworker過(guò)一段時(shí)間都會(huì)因?yàn)闃I(yè)務(wù)部署而重啟）。如果研發(fā)資源特別有限，又想使用snowflake可以考慮一下這個(gè)辦法。 

3、個(gè)人項(xiàng)目中hash分庫(kù)的解決辦法

實(shí)際使用中，有時(shí)候ID需要支持分庫(kù)分表，snowflake的默認(rèn)實(shí)現(xiàn)對(duì)這塊支持得不夠。在業(yè)務(wù)量不大的情況下，snowflake生成的id序列號(hào)部分大多都是0，轉(zhuǎn)換為十進(jìn)制會(huì)是偶數(shù)。用這個(gè)id通過(guò)取模hash分庫(kù)，顯然不平均。

萬(wàn)一有這樣的需求怎么辦呢？可以考慮借助ID時(shí)間戳部分實(shí)現(xiàn)均勻分布

（1）分庫(kù)分表邏輯使用ID中時(shí)間戳部分做取模。這個(gè)方法需要把10進(jìn)制ID轉(zhuǎn)成2進(jìn)制，然后移位，再進(jìn)行計(jì)算。比較麻煩

（2）生成ID的時(shí)候把序列號(hào)部分尾數(shù)用時(shí)間戳對(duì)應(yīng)的位置覆蓋。截段代碼，這段代碼的取值能保證ID除以128的余數(shù)均勻分布。