是什么？
snowflake ID 算法是 twitter 使用的唯一 ID 生成算法，為了滿足 Twitter 每秒上萬條消息的請求，使每條消息有唯一、有一定順序的 ID ，且支持分布式生成。
主要解決了高并發(fā)時 ID 生成不重復(fù)的問題
結(jié)構(gòu)
snowflake ID 的結(jié)構(gòu)是一個 64 bit 的 int 型數(shù)據(jù)。
如圖所示 :
1 bit：不使用，可以是 1 或 0
41 bit：記錄時間戳 (當(dāng)前時間戳減去用戶設(shè)置的初始時間，毫秒表示)，可記錄最多 69 年的時間戳數(shù)據(jù)
10 bit：用來記錄分布式節(jié)點(diǎn) ID，一般每臺機(jī)器一個唯一 ID，也可以多進(jìn)程每個進(jìn)程一個唯一 ID，最大可部署 1024 個節(jié)點(diǎn)
12 bit：序列號，用來記錄不同 ID 同一毫秒時的序列號，最多可生成 4096 個序列號
時間戳、節(jié)點(diǎn) ID 和序列號的位數(shù)可以根據(jù)業(yè)務(wù)自由浮動調(diào)整
唯一 ID 原理
假設(shè)在一個節(jié)點(diǎn) (機(jī)器) 上，節(jié)點(diǎn) ID 唯一，并發(fā)時有多個線程去生成 ID。
滿足以上條件時，如果多個線程在同一毫秒內(nèi)生成 ID，那么序列號步進(jìn) (加一)，這里要保證序列號的操作并發(fā)安全，使同一毫秒內(nèi)生成的 ID 擁有不同序列號。如果序列號達(dá)到上限，則等待這一毫秒結(jié)束，在新的毫秒繼續(xù)步進(jìn)。
這樣保證了：
所有生成的 ID 按時間趨勢遞增 （有序）
整個分布式系統(tǒng)內(nèi)不會產(chǎn)生重復(fù) ID （唯一）
用 go 實(shí)現(xiàn)的思路
why go ?
go 有封裝好的協(xié)程 goroutine，可以很好的處理并發(fā)，可以加鎖保證數(shù)據(jù)的同步安全，有很好的性能。當(dāng)然其它語言如 Java、Scala 也是完全可以的。
思路
1、確定唯一的節(jié)點(diǎn) ID
2、設(shè)置一個初始時間戳 (毫秒表示)
3、處理并發(fā)時序列號步進(jìn)和并發(fā)安全問題
4、組裝各個 bits ，生成最終的 64 bit ID
編碼實(shí)現(xiàn)
首先我們要引入基礎(chǔ)的模塊
import (
"fmt" // 測試、打印
"time" // 獲取時間
"errors" // 生成錯誤
"sync" // 使用互斥鎖
)
基礎(chǔ)常量定義
這里求最大值使用了位運(yùn)算，-1 的二進(jìn)制表示為 1 的補(bǔ)碼，感興趣的同學(xué)可以自己算算試試 -1 ^ (-1 << nodeBits) 這里是不是等于 1023
const (
nodeBits uint8 = 10 // 節(jié)點(diǎn) ID 的位數(shù)
stepBits uint8 = 12 // 序列號的位數(shù)
nodeMax int64 = -1 ^ (-1 << nodeBits) // 節(jié)點(diǎn) ID 的最大值，用于檢測溢出
stepMax int64 = -1 ^ (-1 << stepBits) // 序列號的最大值，用于檢測溢出
timeShift uint8 = nodeBits + stepBits // 時間戳向左的偏移量
nodeShift uint8 = stepBits // 節(jié)點(diǎn) ID 向左的偏移量
)
設(shè)置初始時間的時間戳 (毫秒表示)，我這里使用 twitter 設(shè)置的一個時間，這個可以隨意設(shè)置 ，比現(xiàn)在的時間靠前即可。
var Epoch int64 = 1288834974657 // timestamp 2006-03-21:20:50:14 GMT
ID 結(jié)構(gòu)和 Node 結(jié)構(gòu)的實(shí)現(xiàn)
這里我們申明一個 int64 的 ID 類型 （這樣可以為此類型定義方法，比直接使用 int64 變量更靈活）
type ID int64
Node 結(jié)構(gòu)用來存儲一個節(jié)點(diǎn) (機(jī)器) 上的基礎(chǔ)數(shù)據(jù)
type Node struct {
mu sync.Mutex // 添加互斥鎖，保證并發(fā)安全
timestamp int64 // 時間戳部分
node int64 // 節(jié)點(diǎn) ID 部分
step int64 // 序列號 ID 部分
}
獲取 Node 類型實(shí)例的函數(shù)，用于獲得當(dāng)前節(jié)點(diǎn)的 Node 實(shí)例
func NewNode(node int64) (*Node, error) {
// 如果超出節(jié)點(diǎn)的最大范圍，產(chǎn)生一個 error
if node < 0 || node > nodeMax {
return nil, errors.New("Node number must be between 0 and 1023")
}
// 生成并返回節(jié)點(diǎn)實(shí)例的指針
return &Node{
timestamp: 0,
node: node,
step: 0,
}, nil
}
最后一步，生成 ID 的方法
func (n *Node) Generate() ID {
n.mu.Lock() // 保證并發(fā)安全, 加鎖
defer n.mu.Unlock() // 方法運(yùn)行完畢后解鎖
// 獲取當(dāng)前時間的時間戳 (毫秒數(shù)顯示)
now := time.Now().UnixNano() / 1e6
if n.timestamp == now {
// step 步進(jìn) 1
n.step ++
// 當(dāng)前 step 用完
if n.step > stepMax {
// 等待本毫秒結(jié)束
for now <= n.timestamp {
now = time.Now().UnixNano() / 1e6
}
}
} else {
// 本毫秒內(nèi) step 用完
n.step = 0
}
n.timestamp = now
// 移位運(yùn)算，生產(chǎn)最終 ID
result := ID((now - Epoch) << timeShift | (n.node << nodeShift) | (n.step))
return result
}
測試
我們使用循環(huán)去開啟多個 goroutine 去并發(fā)生成 ID，然后使用 map 以 ID 作為鍵存儲，來判斷是否生成了唯一的 ID
main 函數(shù)代碼
func main() {
// 測試腳本
// 生成節(jié)點(diǎn)實(shí)例
node, err := NewNode(1)
if err != nil {
fmt.Println(err)
return
}
ch := make(chan ID)
count := 10000
// 并發(fā) count 個 goroutine 進(jìn)行 snowflake ID 生成
for i := 0; i < count; i++ {
go func() {
id := node.Generate()
ch <- id
}()
}
defer close(ch)
m := make(map[ID]int)
for i := 0; i < count; i++ {
id := <- ch
// 如果 map 中存在為 id 的 key, 說明生成的 snowflake ID 有重復(fù)
_, ok := m[id]
if ok {
fmt.Printf("ID is not unique!\n")
return
}
// 將 id 作為 key 存入 map
m[id] = i
}
// 成功生成 snowflake ID
fmt.Println("All ", count, " snowflake ID generate successed!\n")
}
完整的程序?qū)嵗?：點(diǎn)我查看
上線使用
你可以用 go 的 net/http 包處理并發(fā)請求，生成 ID 并且返回 http 響應(yīng)結(jié)果。
Just do it
