分布式ID生成算法｜雪花算法 Snowflake

寫在前面

在分布式領域中，不可避免的需要生成一個全局唯一ID。而在近幾年的發展中有許多分布式ID生成算法，比較經典的就是 Twitter 的雪花算法(Snowflake Algorithm)。當然國內也有美團的基于snowflake改進的Leaf算法。那么今天我們就來介紹一下雪花算法。

雪花算法

算法來源： 世界上沒有完全相同的兩片雪花 。所以！雪崩的時候，沒有任何一片雪花是相同的！

雪花算法的本質是生成一個64位的 long int 類型的id，可以拆分成一下幾個部分：

最高位固定位0。因為第一位為符號位，如果是1那么就是負數了。
接下來的 41 位存儲毫秒級時間戳，2^41 大概可以使用69年。
再接來就是10位存儲機器碼，包括 5 位dataCenterId 和 5 位 workerId。最多可以部署2^10=1024臺機器。
最后12位存儲序列號。統一毫秒時間戳時，通過這個遞增的序列號來區分。即對于同一臺機器而言，同一毫秒時間戳下可以生成 2^12=4096 個不重復id。

在這里插入圖片描述

雪花算法其實是強依賴于時間戳的，因為我們看上面生成的幾個數字，我們唯一不可控的就是時間，如果發生了時鐘回撥有可能會發生id生成一樣了。

所以雪花算法適合那些與時間有強關聯的業務 ，比如訂單，交易之類的，需要有時間強相關的業務。

生成 ID 流程圖

在這里插入圖片描述
下面會結合代碼講述詳細講述這張圖

代碼實現

前置工作

既然是由上述的幾個部分組成，那么我們可以先定義幾個常量

// 時間戳的 占用位數
timestampBits = 41
// dataCenterId 的占用位數
dataCenterIdBits = 5
// workerId 的占用位數
workerIdBits = 5
// sequence 的占用位數
seqBits = 12

并且定義各個字段的最大值，防止越界

// timestamp 最大值, 相當于 2^41-1 = 2199023255551
timestampMaxValue = -1 ^ (-1 << timestampBits)
// dataCenterId 最大值, 相當于 2^5-1 = 31
dataCenterIdMaxValue = -1 ^ (-1 << dataCenterIdBits)
// workId 最大值, 相當于 2^5-1 = 31
workerIdMaxValue = -1 ^ (-1 << workerIdBits)
// sequence 最大值, 相當于 2^12-1 = 4095
seqMaxValue = -1 ^ (-1 << seqBits)

移動位數

// workId 向左移動12位（seqBits占用位數）因為這12位是sequence占的
workIdShift = 12
// dataCenterId 向左移動17位 (seqBits占用位數 + workId占用位數)
dataCenterIdShift = 17
// timestamp 向左移動22位 (seqBits占用位數 + workId占用位數 + dataCenterId占用位數)
timestampShift = 22

定義雪花生成器的對象，定義上面我們介紹的幾個字段即可

type SnowflakeSeqGenerator struct {mu           *sync.Mutextimestamp    int64dataCenterId int64workerId     int64sequence     int64
}

func NewSnowflakeSeqGenerator(dataCenterId, workId int64) (r *SnowflakeSeqGenerator, err error) {if dataCenterId < 0 || dataCenterId > dataCenterIdMaxValue {err = fmt.Errorf("dataCenterId should between 0 and %d", dataCenterIdMaxValue-1)return}if workId < 0 || workId > workerIdMaxValue {err = fmt.Errorf("workId should between 0 and %d", dataCenterIdMaxValue-1)return}return &SnowflakeSeqGenerator{mu:           new(sync.Mutex),timestamp:    defaultInitValue - 1,dataCenterId: dataCenterId,workerId:     workId,sequence:     defaultInitValue,}, nil
}

具體算法

timestamp存儲的是上一次的計算時間，如果當前的時間比上一次的時間還要小，那么說明發生了時鐘回撥，那么此時我們不進行生產id，并且記錄錯誤日志。

now := time.Now().UnixMilli()
if S.timestamp > now { // Clock callbacklog.Errorf("Clock moved backwards. Refusing to generate ID, last timestamp is %d, now is %d", S.timestamp, now)return ""
}

如果時間相等的話，那就說明這是在 同一毫秒時間戳內生成的 ，那么就進行seq的自旋，在這同一毫秒內最多生成 4095 個。如果超過4095的話，就等下一毫秒。

if S.timestamp == now {
// generate multiple IDs in the same millisecond, incrementing the sequence number to prevent conflictsS.sequence = (S.sequence + 1) & seqMaxValueif S.sequence == 0 {// sequence overflow, waiting for next millisecondfor now <= S.timestamp {now = time.Now().UnixMilli()}}
}

那么如果是不在同一毫秒內的話，seq直接用初始值就好了

else {// initialized sequences are used directly at different millisecond timestampsS.sequence = defaultInitValue
}

如果超過了69年，也就是時間戳超過了69年，也不能再繼續生成了

tmp := now - epoch
if tmp > timestampMaxValue {log.Errorf("epoch should between 0 and %d", timestampMaxValue-1)return ""
}

記錄這一次的計算時間，這樣就可以和下一次的生成的時間做對比了。

S.timestamp = now

將 timestamp + dataCenterId + workId + sequence 拼湊一起，注意一點是我們最好用字符串輸出，因為前端js中的number類型超過53位會溢出的。

// combine the parts to generate the final ID and convert the 64-bit binary to decimal digits.
r := (tmp)<<timestampShift |(S.dataCenterId << dataCenterIdShift) |(S.workerId << workIdShift) |(S.sequence)return fmt.Sprintf("%d", r)

完整代碼 & 測試文件

package sequenceimport ("fmt""sync""time""github.com/seata/seata-go/pkg/util/log"
)// SnowflakeSeqGenerator snowflake gen ids
// ref: https://en.wikipedia.org/wiki/Snowflake_IDvar (// set the beginning timeepoch = time.Date(2024, time.January, 01, 00, 00, 00, 00, time.UTC).UnixMilli()
)const (// timestamp occupancy bitstimestampBits = 41// dataCenterId occupancy bitsdataCenterIdBits = 5// workerId occupancy bitsworkerIdBits = 5// sequence occupancy bitsseqBits = 12// timestamp max value, just like 2^41-1 = 2199023255551timestampMaxValue = -1 ^ (-1 << timestampBits)// dataCenterId max value, just like 2^5-1 = 31dataCenterIdMaxValue = -1 ^ (-1 << dataCenterIdBits)// workId max value, just like 2^5-1 = 31workerIdMaxValue = -1 ^ (-1 << workerIdBits)// sequence max value, just like 2^12-1 = 4095seqMaxValue = -1 ^ (-1 << seqBits)// number of workId offsets (seqBits)workIdShift = 12// number of dataCenterId offsets (seqBits + workerIdBits)dataCenterIdShift = 17// number of timestamp offsets (seqBits + workerIdBits + dataCenterIdBits)timestampShift = 22defaultInitValue = 0
)type SnowflakeSeqGenerator struct {mu           *sync.Mutextimestamp    int64dataCenterId int64workerId     int64sequence     int64
}// NewSnowflakeSeqGenerator initiates the snowflake generator
func NewSnowflakeSeqGenerator(dataCenterId, workId int64) (r *SnowflakeSeqGenerator, err error) {if dataCenterId < 0 || dataCenterId > dataCenterIdMaxValue {err = fmt.Errorf("dataCenterId should between 0 and %d", dataCenterIdMaxValue-1)return}if workId < 0 || workId > workerIdMaxValue {err = fmt.Errorf("workId should between 0 and %d", dataCenterIdMaxValue-1)return}return &SnowflakeSeqGenerator{mu:           new(sync.Mutex),timestamp:    defaultInitValue - 1,dataCenterId: dataCenterId,workerId:     workId,sequence:     defaultInitValue,}, nil
}// GenerateId timestamp + dataCenterId + workId + sequence
func (S *SnowflakeSeqGenerator) GenerateId(entity string, ruleName string) string {S.mu.Lock()defer S.mu.Unlock()now := time.Now().UnixMilli()if S.timestamp > now { // Clock callbacklog.Errorf("Clock moved backwards. Refusing to generate ID, last timestamp is %d, now is %d", S.timestamp, now)return ""}if S.timestamp == now {// generate multiple IDs in the same millisecond, incrementing the sequence number to prevent conflictsS.sequence = (S.sequence + 1) & seqMaxValueif S.sequence == 0 {// sequence overflow, waiting for next millisecondfor now <= S.timestamp {now = time.Now().UnixMilli()}}} else {// initialized sequences are used directly at different millisecond timestampsS.sequence = defaultInitValue}tmp := now - epochif tmp > timestampMaxValue {log.Errorf("epoch should between 0 and %d", timestampMaxValue-1)return ""}S.timestamp = now// combine the parts to generate the final ID and convert the 64-bit binary to decimal digits.r := (tmp)<<timestampShift |(S.dataCenterId << dataCenterIdShift) |(S.workerId << workIdShift) |(S.sequence)return fmt.Sprintf("%d", r)
}

測試文件

func TestSnowflakeSeqGenerator_GenerateId(t *testing.T) {var dataCenterId, workId int64 = 1, 1generator, err := NewSnowflakeSeqGenerator(dataCenterId, workId)if err != nil {t.Error(err)return}var x, y stringfor i := 0; i < 100; i++ {y = generator.GenerateId("", "")if x == y {t.Errorf("x(%s) & y(%s) are the same", x, y)}x = y}
}