1 介紹
雪花算法（Snowflake）是一種生成分布式全局唯一ID的算法，生成的ID稱為Snowflake IDs或snowflakes。這種算法由Twitter創(chuàng)建，并用于推文的ID。目前倉儲平臺生成ID是用的雪花算法修改后的版本。
雪花算法幾個特性
-
生成的ID分布式唯一和按照時間遞增有序，毫秒數(shù)在高位，自增序列在低位，整個ID都是趨勢遞增的。
-
不依賴數(shù)據(jù)庫等三方系統(tǒng)，穩(wěn)定性更高，性能非常高的。
-
可以根據(jù)自身業(yè)務(wù)特性分配bit位，非常靈活。
2 其他分布式唯一ID生成方案
2.1 數(shù)據(jù)庫生成
以MySQL為例，單庫單表，給字段設(shè)置auto_increment來生成全局唯一ID
優(yōu)點(diǎn):
-
非常簡單，維護(hù)成本比較低
-
ID唯一，單調(diào)遞增，可以設(shè)置固定步長
缺點(diǎn):
- 可用性難以保證，每次生成ID都需要訪問數(shù)據(jù)庫，瓶頸在于單臺MySQL讀寫性能上，如果數(shù)據(jù)庫掛掉會造成服務(wù)不可用，這是一個致命的問題
2.2 UUID
UUID是由一組32位數(shù)的16進(jìn)制數(shù)字所構(gòu)成，故UUID理論上的總數(shù)為1632=2128，約等于3.4 x 10^38。也就是說若每納秒產(chǎn)生1兆個UUID，要花100億年才會將所有UUID用完。UUID的標(biāo)準(zhǔn)型式包含32個16進(jìn)制數(shù)字，以連字號分為五段，形式為8-4-4-4-12的32個字符。示例：550e8400-e29b-41d4-a716-446655440000
優(yōu)點(diǎn):
-
本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，沒有網(wǎng)絡(luò)耗時
-
基本沒有性能上限
缺點(diǎn):
-
可讀性差
-
長度過長，16字節(jié)128位，生成的UUID通常是36位(包含-)，有些場景可能不適用。如果用作數(shù)據(jù)庫主鍵，在MySQL的InnoDB引擎下長度過長，二級索引(非主鍵索引)會占用很大的空間。
-
無法保證趨勢遞增，在MySQL的InnoDB引擎下，新插入數(shù)據(jù)會根據(jù)主鍵來尋找合適位置，會導(dǎo)致頻繁的移動、分頁增加了很多開銷。
3 snowflake算法實(shí)現(xiàn)細(xì)節(jié)
3.1拆解64bit位
snowflake生成的id通常是一個64bit數(shù)字，java中用long類型。
圖1：snowflake算法中的64-bit劃分方式
-
1-bit不用于生成ID(符號位) long 范圍[-2^(64-1), 2^(64-1) ] , (64-1)中的1代表的就是符號位
-
41-bit時間戳(毫秒)可以表示1 x 2^41 / (1000 x 3600 x 24 x 365) = 69年的時間
-
10-bit可以分別表示1 x 2^10 = 1024臺機(jī)器,范圍[0,1023]
-
12-bit表示1ms內(nèi)自動遞增的序列號，1 x 2^12 = 4096個 范圍[0,4095]。單機(jī)1ms可以生成4096個不重復(fù)的ID
通過上述方式進(jìn)行生成ID，可以保證1024臺機(jī)器在任意69年的時間段里不會出現(xiàn)重復(fù)的ID，而且單臺機(jī)器支持一秒能夠生成409.6萬個ID。
這種方式可以支撐大部分業(yè)務(wù)，如果不滿足，可以根據(jù)自身業(yè)務(wù)特點(diǎn)來調(diào)整不同命名空間占用的bit數(shù)。如果我們有劃分IDC的需求，可以將10-bit分5-bit給IDC，分5-bit給工作機(jī)器。這樣就可以表示32個IDC，每個IDC下可以有32臺機(jī)器。如果我們的機(jī)器位比較特殊，數(shù)值相對較大，但是對并發(fā)要求不高，還可以將時間位調(diào)整為秒級，時間位節(jié)省出10-bit留給機(jī)器位。
-
1-bit符號位
-
31-bit時間戳(秒)1 x 2^31/ (3600 x 24 x 365) = 68年
-
22-bit機(jī)器位 運(yùn)維平臺給提供的數(shù)值 范圍 [0,2^22-1]
-
10-bit序列號 范圍[0, 2^10 - 1]共1024個
通過上述方式進(jìn)行生成ID，可以保證4194303臺機(jī)器在任意68年的時間段里不會出現(xiàn)重復(fù)的ID，而且單臺機(jī)器支持一秒能夠生成1024個ID。
3.2 Java實(shí)現(xiàn)
public class IdGenerator {
// 起始時間
private final long from = 1422720000000L;
// 機(jī)器位所占bit位數(shù)
private final long instanceIdBits = 10L;
// 序列號所占bit位數(shù)
private final long sequenceBits = 12L;
// 機(jī)器位左移長度
private final long instanceIdShift = sequenceBits;
// 時間位左移長度
private final long timestampLeftShift = sequenceBits + instanceIdBits;
// 序號1: 最大機(jī)器ID
private final long maxInstanceId = -1L ^ (-1L << instanceIdBits);
// 最大序列號
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
private long instanceId;
private long sequence = 0L;
private long lastTimestamp = -1L;
public IdGenerator(long instanceId) {
if (instanceId > maxInstanceId || instanceId < 0) {
throw new IllegalArgumentException(String.format("instance Id can't be greater than %d or less than 0", maxInstanceId));
}
this.instanceId = instanceId;
}
// 序號2:
public synchronized long nextId() {
long timestamp = timeGen();
// 序號3:
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
// 序號4:
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
timestamp = tilNextSecs(lastTimestamp);
}
} else {
sequence = 0L;
}
lastTimestamp = timestamp;
// 序號5:
return ((timestamp - from) << timestampLeftShift) // (當(dāng)前時間 - 起始時間) 向左移位
| (instanceId << instanceIdShift) // 機(jī)器位 向左移位
| sequence; // 序列位
}
private long tilNextSecs(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
}
3.3一些疑問
3.3.1 為什么bit位置只利用了63位？
因為long在java中占8字節(jié)，每字節(jié)8bit，一共64bit，其中有1個bit位是符號位不能用做生成ID，如果符號位也用來做ID中的1個bit為會導(dǎo)致ID出現(xiàn)負(fù)數(shù)，影響趨勢遞增特性。
3.3.2 計算最大機(jī)器ID
見代碼中注釋 序號1
maxInstanceId = -1L ^ (-1L<<instanceIdBits)
等價于 maxInstanceId = -1 ^( -1<<10)
① -1二進(jìn)制
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
② -1左移10位 -1<<10 二進(jìn)制
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1100 0000 0000
①與②進(jìn)行異或運(yùn)算 異或運(yùn)算:同為假，異為真,所以最終結(jié)果應(yīng)該為
0000 0000 0000 0000 0000 0000 0000 00000000 0000 0000 0000 0000 0011 1111 1111
最后:maxInstanceId = 2^10 - 1 = 1023
sequenceMask 計算方法相同，結(jié)果為2^12 - 1 = 4095
3.3.3 計算序列號位
見代碼中注釋 序號4
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
timestamp = tilNextSecs(lastTimestamp);
}
} else {
sequence = 0L;
}
其中這段代碼的是計算序列號的代碼主要邏輯是，如果上個生成ID的時間位與當(dāng)前ID的時間位沖突，則會生成一個序列號進(jìn)行區(qū)分，如果序列號用盡，則等待下一個時間點(diǎn)再生成。如果上個生成ID的時間位與當(dāng)前ID的時間位不沖突，則將序列號設(shè)置成0。
sequence = (sequence + 1) & sequenceMask，序列號最大值sequenceMask為4095，等價于如下這種寫法。
sequence = (sequence + 1);
if(sequence == 4095){
sequence = 0;
}
其實(shí)這兩種寫法的結(jié)果是一致的，就是對(sequence + 1)進(jìn)行取余。
這里有個位運(yùn)算知識點(diǎn) k % m = k & (m - 1),m需要滿足 m = 2^n,sequenceMask = 2^12 - 1。所以剛好可以用與運(yùn)算進(jìn)行取余操作，效率杠杠滴。
3.3.4 生成ID
見代碼中注釋 序號5:
此時我們拿到了時間位(timestamp - from)、機(jī)器位(instanceId )、序列號位(sequence),所以就可以計算最終的ID了。
((timestamp - from) << timestampLeftShift) // (當(dāng)前時間 - 起始時間) 向左移位
| (instanceId << instanceIdShift) // 機(jī)器位 向左移位
| sequence; // 序列位
①((timestamp - from) << timestampLeftShift) 計算時間位
from是固定的1422720000000, timestampLeftShift = 12 + 10.我們假設(shè)timestamp = 1422720000001。也就是from剛剛過去1毫秒。1毫秒也是我們時間位倒數(shù)第二小的值，因為0是最小值。時間位取值范圍[0, 2^41 - 1],從這也可以看出上邊描述時間位時為什么把時間段特意標(biāo)注了，因為時間位存的不是具體時間，而是以from為起始來算的過去了多少時間。
來看下 1<<22 結(jié)果
圖2: 時間位移位結(jié)果
圖2可以看出，時間位向左移位22，位置正好到第一個時間位。
②(instanceId << instanceIdShift) 計算機(jī)器位
為了方便計算，這里我們假設(shè)instanceId 等于1,機(jī)器位取值范圍[0,-1]。
那么機(jī)器位就是 1 << 12
圖3: 機(jī)器位移位結(jié)果
圖3可以看出，機(jī)器位左移12位，位置正好到第一個機(jī)器位。
③按照 ① | ② | sequence 進(jìn)行或運(yùn)算進(jìn)行生成ID
現(xiàn)在我們有了時間位的值，機(jī)器位的值，就只差序列號位的值，序列號是上面3描述代碼生成的，范圍是[0, 2^12-1]。為了方便計算，我們假設(shè)sequence = 1
那么 ID = ① | ② | 1。進(jìn)行或運(yùn)算
圖4: ID = ① | ② | 1
下圖是按照上面邏輯生成的ID
圖5: 程序生成結(jié)果
3.3.5 注意:雪花算法需要用單例方式生成ID
因為雪花算法會依賴上一次生成的ID的時間來判斷是否需要對序列號進(jìn)行增加的操作，如果不是單例，兩個業(yè)務(wù)用兩個對象同時獲取ID，則可能會生成相同的ID
4 關(guān)于雪花算法的一些思考
機(jī)器位怎么取值
-
主機(jī)唯一標(biāo)識 如果運(yùn)維平臺有機(jī)器唯一標(biāo)識，可以在運(yùn)維平臺取。不過需要考慮機(jī)器位能否容納下唯一標(biāo)識，可能會過長，也需要考慮運(yùn)維平臺的唯一標(biāo)識未來變化。
-
可根據(jù)ip進(jìn)行計算 如果能保證不同機(jī)房的機(jī)器ip不重復(fù)，可以利用ip來計算機(jī)器位，IP最大 255.255.255.255。而（255+255+255+255) < 1024，因此采用IP段數(shù)值相加即可生成機(jī)器位，不受IP位限制。不過這種方式也不是絕對ok，要根據(jù)自身情況在選擇，比如10.0.5.2 與 10.0.2.5 計算出來也是相同的。使用這種IP生成機(jī)器位的方法,必須保證IP段相加不能重復(fù)
-
通過數(shù)據(jù)庫/redis/zk等進(jìn)行協(xié)調(diào)，在應(yīng)用啟動的時候給每個機(jī)器分配不會重復(fù)的機(jī)器位id。
時鐘回?fù)軉栴}
雪花算法強(qiáng)依賴時間，如果時間發(fā)生回?fù)?，有可能會生成重?fù)的ID，在我們上面的nextId中我們用當(dāng)前時間和上一次的時間進(jìn)行判斷，如果當(dāng)前時間小于上一次的時間那么肯定是發(fā)生了回?fù)?，雪花算法的做法是簡單的拋出了一個異常。
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
如果業(yè)務(wù)的異常容忍度低，這里我們可以對其進(jìn)行優(yōu)化,如果時間回?fù)軙r間較短，比如配置5ms以內(nèi)，那么可以直接等待一定的時間，讓機(jī)器的時間追上來。也可以利用擴(kuò)展位，將64-bit的機(jī)器位或者序列號位預(yù)留出2-bit的防止時鐘回滾的擴(kuò)展位。
5 ID逆運(yùn)算
如果線上出現(xiàn)ID重復(fù)，如何進(jìn)行問題定位？對ID進(jìn)行逆運(yùn)算拿到ID的時間位、機(jī)器位、序號位。就可以進(jìn)行下一步分析了。以上述生成的4198401為例
5.1 時間
時間位 = ID / 2^(機(jī)器位 + 序列號位) + from
時間位 = 4198401 / 2^(12 + 10) + 1422720000000 = 1422720000001
與上述生成ID時用時間位相符
注意:ID / 2^(機(jī)器位 + 序列號位) 是整數(shù)
5.2 機(jī)器
機(jī)器位 = (ID / 2^序列號位 ) % 2^(機(jī)器位)
機(jī)器位 = (4198401 / 2^12) % 2^10= (1025) % 1024 = 1
與上述生成ID時用機(jī)器位數(shù)值相符
5.3 序列號
ID % 2^序列號位
序列號 = 4198401 % = 4198401 % 1024 = 1
與上述生成ID時用的序列號數(shù)值相符
6 資料
開源代碼scala版本：https://github.com/twitter-archive/snowflake
作者：京東物流 馬紅巖文章來源：http://www.zghlxwxcb.cn/news/detail-601930.html
來源：京東云開發(fā)者社區(qū) 自猿其說Tech文章來源地址http://www.zghlxwxcb.cn/news/detail-601930.html
到了這里，關(guān)于拆解雪花算法生成規(guī)則的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
