前言
最近工作上遇到一個(gè)雪花算法生成Id重復(fù)導(dǎo)致數(shù)據(jù)庫(kù)中表主鍵沖突，導(dǎo)致入庫(kù)失敗的問(wèn)題苍匆，所以順便學(xué)習(xí)了一下雪花算法顾孽，下面是學(xué)習(xí)的筆記以及討論如果解決雪花算法在分布式部署中生成重復(fù)Id的問(wèn)題。
基礎(chǔ)概念
snowflake中文的意思是雪花窖杀，所以常被稱(chēng)為雪花算法
它是twitter用scala語(yǔ)言編寫(xiě)的一個(gè)用于簡(jiǎn)單規(guī)則運(yùn)算就能高效生成唯一ID的算法蝴猪，下面是源碼地址：
網(wǎng)上還有各種其他語(yǔ)言的版本调衰，思路基本上都是參考上述源碼
特性
生成的ID不重復(fù)
生成性能高
基于時(shí)間戳膊爪，可以基本保證有序遞增
設(shè)計(jì)原理
準(zhǔn)備工作
bit與byte
bit(位)：電腦中存儲(chǔ)的最小單位，可以存儲(chǔ)二進(jìn)制中的0或1
byte(字節(jié))：一個(gè)byte由8個(gè)bit組成
如圖：
而在java中嚎莉，每個(gè)數(shù)據(jù)類(lèi)型存儲(chǔ)所占的字節(jié)數(shù)不一樣米酬，常用的如下：
int：4 個(gè)字節(jié)。
short：2 個(gè)字節(jié)趋箩。
long：8 個(gè)字節(jié)赃额。
byte：1 個(gè)字節(jié)。
float：4 個(gè)字節(jié)叫确。
double：8 個(gè)字節(jié)跳芳。
char：2 個(gè)字節(jié)。
而雪花算法生成的數(shù)字竹勉，我們定義為long飞盆，所以就是8個(gè)byte，64bit
假設(shè)我們定義 long a = 1L次乓；則在計(jì)算機(jī)中的存儲(chǔ)如下：
也就是可表示的范圍為：-9223372036854775808（-2的63次方） ~ 9223372036854775807（2的63次方-1）吓歇，考慮到生成的唯一值用于數(shù)據(jù)庫(kù)主鍵，所以理論值為0~9223372036854775807（2的63次方-1）票腰，容量上肯定能滿(mǎn)足業(yè)務(wù)方了
組成原理
雪花算法生成的Id由：1bit 不用 + 41bit時(shí)間戳+10bit工作機(jī)器id+12bit序列號(hào)城看，如下圖：
不用：1bit，因?yàn)樽罡呶皇欠?hào)位杏慰，0表示正析命，1表示負(fù)，所以這里固定為0
時(shí)間戳：41bit逃默，服務(wù)上線的時(shí)間毫秒級(jí)的時(shí)間戳（為當(dāng)前時(shí)間-服務(wù)第一次上線時(shí)間），這里為（2^41-1）/1000/60/60/24/365 = 49.7年
工作機(jī)器id：10bit簇搅，表示工作機(jī)器id完域，用于處理分布式部署id不重復(fù)問(wèn)題，可支持2^10 = 1024個(gè)節(jié)點(diǎn)
序列號(hào)：12bit瘩将，用于離散同一機(jī)器同一毫秒級(jí)別生成多條Id時(shí)吟税，可允許同一毫秒生成2^12 = 4096個(gè)Id，則一秒就可生成4096*1000 = 400w個(gè)Id
說(shuō)明：上面總體是64位姿现，具體位數(shù)可自行配置肠仪，如想運(yùn)行更久，需要增加時(shí)間戳位數(shù)备典；如想支持更多節(jié)點(diǎn)异旧，可增加工作機(jī)器id位數(shù)；如想支持更高并發(fā)提佣，增加序列號(hào)位數(shù)
Java版本的具體實(shí)現(xiàn)
public class SnowflakeIdWorker {
/** 開(kāi)始時(shí)間截 (建議用服務(wù)第一次上線的時(shí)間吮蛹，到毫秒級(jí)的時(shí)間戳) */
private final long twepoch = 687888001020L;
/** 機(jī)器id所占的位數(shù) */
private final long workerIdBits = 10L;
/** 支持的最大機(jī)器id荤崇，結(jié)果是1023 (這個(gè)移位算法可以很快的計(jì)算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù)) */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/** 序列在id中占的位數(shù) */
private final long sequenceBits = 12L;
/** 機(jī)器ID向左移12位 */
private final long workerIdShift = sequenceBits;
/** 時(shí)間截向左移22位(10+12) */
private final long timestampLeftShift = sequenceBits + workerIdBits;
/** 生成序列的掩碼，這里為4095 (0b111111111111=0xfff=4095)
* <<為左移潮针，每左移動(dòng)1位术荤，則擴(kuò)大1倍
* */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
/** 工作機(jī)器ID(0~1024) */
private long workerId;
/** 毫秒內(nèi)序列(0~4095) */
private long sequence = 0L;
/** 上次生成ID的時(shí)間截 */
private long lastTimestamp = -1L;
//==============================Constructors=====================================
/**
* 構(gòu)造函數(shù)
* @param workerId 工作ID (0~1023)
*/
public SnowflakeIdWorker(long workerId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("workerId can't be greater than %d or less than 0", maxWorkerId));
}
this.workerId = workerId;
}
// ==============================Methods==========================================
/**
* 獲得下一個(gè)ID (該方法是線程安全的)
* @return SnowflakeId
*/
public synchronized long nextId() {
long timestamp = timeGen();
//如果當(dāng)前時(shí)間小于上一次ID生成的時(shí)間戳，說(shuō)明系統(tǒng)時(shí)鐘回退過(guò)這個(gè)時(shí)候應(yīng)當(dāng)拋出異常
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
//如果是同一時(shí)間生成的每篷，則進(jìn)行毫秒內(nèi)序列
if (lastTimestamp == timestamp) {
//如果毫秒相同瓣戚，則從0遞增生成序列號(hào)
sequence = (sequence + 1) & sequenceMask;
//毫秒內(nèi)序列溢出
if (sequence == 0) {
//阻塞到下一個(gè)毫秒,獲得新的時(shí)間戳
timestamp = tilNextMillis(lastTimestamp);
}
}
//時(shí)間戳改變，毫秒內(nèi)序列重置
else {
sequence = 0L;
}
//上次生成ID的時(shí)間截
lastTimestamp = timestamp;
//移位并通過(guò)或運(yùn)算拼到一起組成64位的ID
return ((timestamp - twepoch) << timestampLeftShift) //
| (workerId << workerIdShift) //
| sequence;
}
/**
* 阻塞到下一個(gè)毫秒焦读，直到獲得新的時(shí)間戳
* @param lastTimestamp 上次生成ID的時(shí)間截
* @return 當(dāng)前時(shí)間戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以毫秒為單位的當(dāng)前時(shí)間子库，從1970-01-01 08:00:00算起
* @return 當(dāng)前時(shí)間(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
}
上述代碼中，有涉及到位運(yùn)算吨灭，這里對(duì)雪花算法中需要用到的挑出來(lái)介紹一下：
原碼刚照、反碼、補(bǔ)碼
我們?yōu)槭裁匆肋@三個(gè)概念呢喧兄？首先要知道无畔，計(jì)算機(jī)中的運(yùn)算都是以補(bǔ)碼的形式進(jìn)行運(yùn)算的
原碼就是二進(jìn)制的形式，反碼和補(bǔ)碼跟本身的正負(fù)有關(guān)吠冤，定義如下：
| 類(lèi)型 | 原碼 | 反碼 | 補(bǔ)碼 |
|---|---|---|---|
| 正數(shù) | 二進(jìn)制 | 就是原碼 | 就是原碼 |
| 負(fù)數(shù) | 二進(jìn)制 | 符號(hào)位不變浑彰，其他位取反 | 反碼的基礎(chǔ)上加1 |
我們先來(lái)看原碼，數(shù)字轉(zhuǎn)換成二進(jìn)制就是這個(gè)數(shù)字的原碼拯辙，比如之前提到的long a = 1L郭变；如下：
要注意的是最高位是符號(hào)位，1標(biāo)識(shí)負(fù)涯保，0表示正诉濒，則long a = -1L的原碼，如下：
long a = 1L夕春，反碼和補(bǔ)碼是跟原碼一致未荒，我們主要來(lái)看-1L的情況：
左移<<
a << b片排， 表示a的二進(jìn)制數(shù)值整體向左移動(dòng)b位，符號(hào)位不變速侈，低位空出來(lái)的補(bǔ)0率寡，相當(dāng)于a * (2^b)
比如-1L << 12， 表示-1L的二進(jìn)制往左移動(dòng)12位倚搬，剛才提了負(fù)數(shù)的二進(jìn)制是以補(bǔ)碼的形式存在冶共，則運(yùn)算過(guò)程如下：
異或^
規(guī)則 兩個(gè)操作數(shù)進(jìn)行異或時(shí)，對(duì)于同一位上，如果數(shù)值相同則為 0比默，數(shù)值不同則為 1幻捏。
1 ^ 0 = 1,
1 ^ 1 = 0,
0 ^ 0 = 0;
比如，-1L ^(-1L << 12),也就是-1L ^-4096命咐，運(yùn)算過(guò)程如下：
或 |
規(guī)則 或運(yùn)算時(shí)篡九，進(jìn)行運(yùn)算的兩個(gè)數(shù)，從最低位到最高位醋奠，一一對(duì)應(yīng)榛臼。如果某 bit 的兩個(gè)數(shù)值對(duì)應(yīng)的值只要 1 個(gè)為 1，則結(jié)果值相應(yīng)的 bit 就是 1窜司，否則為 0沛善。
0 | 0 = 0,
0 | 1 = 1,
1 | 1 = 1
比如：3 | 5
如下圖：
如果想了解得更詳細(xì)，可以看：位運(yùn)算
雪花算法的細(xì)節(jié)
1. 線程安全
/**
* 獲得下一個(gè)ID (該方法是線程安全的)
* @return SnowflakeId
*/
public synchronized long nextId() {
可以看到塞祈，生成ID的方法是加了synchronized 關(guān)鍵詞金刁，確保了線程安全，否則在并發(fā)情況下议薪，生成的Id就有可能重復(fù)了
2. 同一毫秒,生成多個(gè)Id時(shí)
根據(jù)雪花算法的組成尤蛮，可以看出，如果同一臺(tái)機(jī)器同一毫秒需要生成多個(gè)Id斯议，因?yàn)楹撩氲臅r(shí)間戳产捞、機(jī)器工作id一樣，則前52位一致哼御，所以需要靠后12位的序列號(hào)來(lái)區(qū)分
具體關(guān)鍵性代碼如下:
//如果是同一時(shí)間生成的坯临，則進(jìn)行毫秒內(nèi)序列
if (lastTimestamp == timestamp) {
//如果毫秒相同，則從0遞增生成序列號(hào)
sequence = (sequence + 1) & sequenceMask;
//毫秒內(nèi)序列溢出
if (sequence == 0) {
//阻塞到下一個(gè)毫秒,獲得新的時(shí)間戳
timestamp = tilNextMillis(lastTimestamp);
}
}
lastTimestamp 記錄了上一次生成Id的毫秒級(jí)的時(shí)間戳恋昼；timestamp為當(dāng)前生成Id時(shí)毫秒級(jí)的時(shí)間戳看靠，如果同一毫秒生成多個(gè)id，則兩者相等
然后通過(guò)下面的代碼來(lái)生成序列
//如果毫秒相同液肌，則從0遞增生成序列號(hào)
sequence = (sequence + 1) & sequenceMask;
sequence開(kāi)始為0衷笋，sequenceMask為生成序列號(hào)的掩碼，定義如下：
/** 生成序列的掩碼矩屁，這里為4095 (0b111111111111=0xfff=4095)
* <<為左移，每左移動(dòng)1位爵赵，則擴(kuò)大1倍
* */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
上述的sequenceBits為序列號(hào)吝秕，這里定義的為12，則要運(yùn)算下面代碼
-1L ^(-1L << 12)
我們?cè)谏厦娈惢虻倪\(yùn)算中空幻，有算過(guò)這個(gè)值烁峭，為4095，不記得的可以看上面 異或部分，也就是同一毫秒约郁，可以逐步生成0~4095序列號(hào)
如果sequence遞增到4095重新回到0時(shí)缩挑，證明當(dāng)前毫秒已經(jīng)產(chǎn)生了4096個(gè)序列號(hào)，則使用tilNextMillis(lastTimestamp)方法阻塞到下一毫秒并賦值給timestamp鬓梅，此時(shí)sequence=0供置，我們看看tilNextMillis(lastTimestamp)是怎么阻塞到下一毫秒的
/**
* 阻塞到下一個(gè)毫秒，直到獲得新的時(shí)間戳
* @param lastTimestamp 上次生成ID的時(shí)間截
* @return 當(dāng)前時(shí)間戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
可以看到绽快，直接就是不斷獲取當(dāng)前時(shí)間和最近生成Id的時(shí)間戳進(jìn)行判斷芥丧，如果還在當(dāng)前毫秒級(jí)別，則空轉(zhuǎn)坊罢，直到下一毫秒
3.移位并通過(guò)或運(yùn)算拼到一起組成64位的ID
//移位并通過(guò)或運(yùn)算拼到一起組成64位的ID
return ((timestamp - twepoch) << timestampLeftShift) //
| (workerId << workerIdShift) //
| sequence;
我們?cè)倩仡櫹?4位的Id是怎么組成的
那我們?cè)趺赐ㄟ^(guò)時(shí)間戳续担、工作機(jī)器id、序列號(hào)來(lái)完成拼接呢活孩？其實(shí)就是通過(guò)移位并或運(yùn)算來(lái)完成的物遇，我們先看下上述代碼中的含義：
timestamp ：當(dāng)前時(shí)間毫秒級(jí)別的時(shí)間戳
twepoch：開(kāi)始時(shí)間毫秒級(jí)別的時(shí)間截
timestampLeftShift：時(shí)間需要左移位數(shù)，這里為sequenceBits + workerIdBits憾儒，這里為序列號(hào)位數(shù)+工作機(jī)器id位數(shù)询兴，即12+10 = 22
workerId ：工作機(jī)器id，用于解決分布式Id重復(fù)的問(wèn)題航夺，這里為外部傳入的參數(shù)
workerIdShift：工作機(jī)器id左移位數(shù)蕉朵，這里為sequenceBits，即12
sequence：序列阳掐，這里為0~4095中的一個(gè)數(shù)值
我們舉個(gè)例子始衅，假設(shè)twepoch為當(dāng)前時(shí)間，timestamp為twepoch之后1000ms缭保，即（timestamp - twepoch）=1000汛闸；工作機(jī)器id為1，即workerId = 1艺骂；當(dāng)前毫秒值第一次生成诸老，即sequence = 0，則ID為：
((1000) << 22)
| (1 << 12)
| 0
即生成的Id：4194308096
我們先看1000钳恕、1别伏、0的二進(jìn)制，以及進(jìn)行位移并或運(yùn)算之后的結(jié)果
假設(shè)同一毫秒值忧额，又生成了一次id厘肮，則：
((1000) << 22)
| (1 << 12)
| 1
即生成的Id：4194308097，所以同一臺(tái)機(jī)器人上基本保證了遞增
雪花算法生成Id重復(fù)問(wèn)題
我們之前提到睦番，同一機(jī)器同一毫秒級(jí)类茂，我們能生成4096個(gè)不同序列耍属，即不同Id，但是如果我們使用的是微服務(wù)架構(gòu)巩检，那不同機(jī)器人是否會(huì)可能生成相同Id呢厚骗？
其實(shí)我們之前有提到工作機(jī)器Id的作用，就是用于解決分布式Id重復(fù)的問(wèn)題兢哭，這個(gè)workerId是通過(guò)構(gòu)造方法傳入的领舰，如果我們用10位來(lái)存儲(chǔ)這個(gè)值，那就是最多支持1024個(gè)節(jié)點(diǎn)
/**
* 構(gòu)造函數(shù)
* @param workerId 工作ID (0~1023)
*/
public SnowflakeIdWorker(long workerId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("workerId can't be greater than %d or less than 0", maxWorkerId));
}
this.workerId = workerId;
}
那么關(guān)鍵問(wèn)題就回歸到如何去把我們的服務(wù)器和workerId對(duì)應(yīng)起來(lái)厦瓢？如果不是容器化部署提揍，部署是固定的機(jī)器，我們用機(jī)器的唯一名來(lái)做key煮仇，那我們可以對(duì)這些機(jī)器名和workerId建立一個(gè)對(duì)應(yīng)關(guān)系劳跃，如果存在就用之前的workerId，不存在就往上累加比如我們用計(jì)算機(jī)名做key：
這樣機(jī)器如果不斷累加浙垫，最多支持1024臺(tái)服務(wù)器
但是如果是容器化部署刨仑，需要支持動(dòng)態(tài)增加節(jié)點(diǎn)，并且每次部署的機(jī)器不一定一樣時(shí)夹姥，就會(huì)有問(wèn)題杉武，如果發(fā)現(xiàn)不同，就往上累加辙售，經(jīng)過(guò)多次發(fā)版轻抱，就可能會(huì)超過(guò)1023，這個(gè)時(shí)候生成雪花Id時(shí)旦部，工作機(jī)器id左移12位后肺然，當(dāng)進(jìn)行或運(yùn)算時(shí)罐旗，時(shí)間戳的位置就會(huì)被影響捞奕，比如workerId=1024琅拌，我們拿之前的舉例第1000ms，那它和第1001ms婚度、workerId=0配置蘸秘，可能生成重復(fù)的Id，如下圖所示：
先來(lái)看看我司之前生成workerId的規(guī)則：
private static void Init()
{
if (worker == null)
{
//初始化為1
long workerId = 1;
//得到服務(wù)器機(jī)器名稱(chēng)
string hostName = System.Net.Dns.GetHostName();
if (RedisHelper.Exists(hostName))
{
// 如果redis中存在改服務(wù)器名稱(chēng)蝗茁，則直接取得workerId
workerId =long.Parse(RedisHelper.Get(hostName));
}
else
{
//如果redis不存在醋虏，則用hashcode對(duì)32取模
var code = hostName.GetHashCode();
var Id = code % 32;
//如果取模以后的Id，大于15哮翘，則從0~15中隨機(jī)一個(gè)數(shù)字灰粮，也就是把16~31中轉(zhuǎn)換到0~15，并存入redis
//原因是忍坷，我司只給了4個(gè)bit存儲(chǔ)workerId，所以只能支持0~15
if (Id>15||Id<0)
{
Id = new Random().Next(0, 15);
}
workerId = (long)Id;
RedisHelper.Set(hostName, workerId);
}
//把workerId傳入構(gòu)造方法
worker = new IdWorker(workerId);
}
}
上述代碼有2個(gè)問(wèn)題：
- hashcode對(duì)32取模，本身就可能會(huì)重復(fù)佩研，比如460141958和3164804對(duì)32取模都是4柑肴，那生成的workerId就重復(fù)了
- 如果hashcode>15,隨機(jī)取一個(gè)，那每次都有1/16的概率重復(fù)
我司考慮的優(yōu)化方案為：
- 在redis中存儲(chǔ)一個(gè)當(dāng)前workerId的最大值
- 每次生成workerId時(shí)旬薯，從redis中獲取到當(dāng)前workerId最大值晰骑，并+1作為當(dāng)前workerId，并存入redis
- 如果workerId為1023绊序，自增為1024硕舆，則重置0，作為當(dāng)前workerId骤公，并存入redis
上述邏輯抚官，其實(shí)可以參考序列號(hào)的位運(yùn)算，簡(jiǎn)化為：
workerId= (workerId+ 1) & (-1L ^ (-1L << workerIdBits))
其中：workerIdBits為機(jī)器人Id所占的位數(shù)
如果workerIdBits = 10阶捆，則為0增長(zhǎng)到1023后凌节，繼續(xù)從0開(kāi)始自增
上述方案確保了，任何時(shí)間點(diǎn)不同服務(wù)器的workerId一定不一致洒试，假設(shè)我們有6個(gè)pod倍奢，多輪啟動(dòng)的情況如下：
上述方案是否一定沒(méi)問(wèn)題呢？其實(shí)是有的垒棋，如果自增1新分配的workerId還沒(méi)釋放掉卒煞，這個(gè)時(shí)候就會(huì)沖突了
比如我們第一個(gè)pod(workerId=0)一直沒(méi)有重啟過(guò)，但是第二個(gè)pod一直在重啟叼架，達(dá)到1024時(shí)回到0畔裕，則同時(shí)會(huì)有兩個(gè)pod的workerId為0, 這兩臺(tái)pod上程序生成的Id就有可能重復(fù)。
我們算極端情況下碉碉，workerIdBits=10柴钻，即1024個(gè)節(jié)點(diǎn)的情況下，可以支持到兩次發(fā)版中間第一個(gè)pod一直不重啟垢粮，其余5個(gè)pod一直重啟的極端情況下贴届，也能支持204次。但是只要發(fā)一次版本蜡吧，所有pod都會(huì)到最近redis中記錄的最大workerId毫蚓，像我們一周一個(gè)版本的情況，不會(huì)存在這個(gè)問(wèn)題昔善。
我們主要是關(guān)注pod個(gè)數(shù)和workerId運(yùn)行的最大值元潘，如果想支持兩次發(fā)版間更多次非所有pod的重啟，我們可以擴(kuò)充workerIdBits君仆，比如workerIdBits=10翩概，支持workerId最大為1023牲距，但如果workerIdBits=12，則支持workerId最大為4095
幾個(gè)注意的點(diǎn)
- twepoch為開(kāi)始的時(shí)間戳钥庇，建議為服務(wù)第一次上線的時(shí)間牍鞠，雖然我們41bit的時(shí)間戳支持49.7年，但是其實(shí)是說(shuō)的距離twepoch的時(shí)間评姨，如果兩者差值超過(guò)了49.7年难述，左右左移22位，就會(huì)導(dǎo)致部分有效數(shù)據(jù)丟失吐句，生成的Id數(shù)據(jù)不能保證大致是遞增的
- 雪花算法生成的id的組成位數(shù)胁后，可以根據(jù)自己的實(shí)際需求可調(diào)整，如果需要支持更長(zhǎng)嗦枢，增加時(shí)間戳所占位數(shù)攀芯；如果想支持更多服務(wù)器或者更多次重啟，增加工作機(jī)器人id所占位數(shù)净宵；如果想支持同一時(shí)間更多并發(fā)敲才，增加序列號(hào)所占位數(shù)
- 生成雪花算法的類(lèi)，需要使用單例模式择葡，并且需要保證線程安全
