是什么驾凶？
snowflake ID 算法是 twitter 使用的唯一 ID 生成算法灾螃，為了滿足 Twitter 每秒上萬條消息的請求地回，使每條消息有唯一浙宜、有一定順序的 ID ，且支持分布式生成酬荞。
主要解決了高并發(fā)時 ID 生成不重復的問題
結構
snowflake ID 的結構是一個 64 bit 的 int 型數據搓劫。
如圖所示 :
1 bit：不使用，可以是 1 或 0
41 bit：記錄時間戳 (當前時間戳減去用戶設置的初始時間混巧，毫秒表示)枪向，可記錄最多 69 年的時間戳數據
10 bit：用來記錄分布式節(jié)點 ID，一般每臺機器一個唯一 ID咧党，也可以多進程每個進程一個唯一 ID秘蛔，最大可部署 1024 個節(jié)點
12 bit：序列號，用來記錄不同 ID 同一毫秒時的序列號傍衡，最多可生成 4096 個序列號
時間戳深员、節(jié)點 ID 和序列號的位數可以根據業(yè)務自由浮動調整
唯一 ID 原理
假設在一個節(jié)點 (機器) 上，節(jié)點 ID 唯一蛙埂，并發(fā)時有多個線程去生成 ID辨液。
滿足以上條件時，如果多個線程在同一毫秒內生成 ID箱残，那么序列號步進 (加一)，這里要保證序列號的操作并發(fā)安全，使同一毫秒內生成的 ID 擁有不同序列號被辑。如果序列號達到上限燎悍，則等待這一毫秒結束，在新的毫秒繼續(xù)步進盼理。
這樣保證了：
所有生成的 ID 按時間趨勢遞增 （有序）
整個分布式系統(tǒng)內不會產生重復 ID （唯一）
用 go 實現的思路
why go ?
go 有封裝好的協(xié)程 goroutine谈山，可以很好的處理并發(fā)，可以加鎖保證數據的同步安全宏怔，有很好的性能奏路。當然其它語言如 Java、Scala 也是完全可以的臊诊。
思路
1鸽粉、確定唯一的節(jié)點 ID
2、設置一個初始時間戳 (毫秒表示)
3抓艳、處理并發(fā)時序列號步進和并發(fā)安全問題
4触机、組裝各個 bits ，生成最終的 64 bit ID
編碼實現
首先我們要引入基礎的模塊
import (
"fmt" // 測試玷或、打印
"time" // 獲取時間
"errors" // 生成錯誤
"sync" // 使用互斥鎖
)
基礎常量定義
這里求最大值使用了位運算儡首，-1 的二進制表示為 1 的補碼，感興趣的同學可以自己算算試試 -1 ^ (-1 << nodeBits) 這里是不是等于 1023
const (
nodeBits uint8 = 10 // 節(jié)點 ID 的位數
stepBits uint8 = 12 // 序列號的位數
nodeMax int64 = -1 ^ (-1 << nodeBits) // 節(jié)點 ID 的最大值偏友，用于檢測溢出
stepMax int64 = -1 ^ (-1 << stepBits) // 序列號的最大值蔬胯，用于檢測溢出
timeShift uint8 = nodeBits + stepBits // 時間戳向左的偏移量
nodeShift uint8 = stepBits // 節(jié)點 ID 向左的偏移量
)
設置初始時間的時間戳 (毫秒表示)，我這里使用 twitter 設置的一個時間位他，這個可以隨意設置 氛濒，比現在的時間靠前即可。
var Epoch int64 = 1288834974657 // timestamp 2006-03-21:20:50:14 GMT
ID 結構和 Node 結構的實現
這里我們申明一個 int64 的 ID 類型 （這樣可以為此類型定義方法棱诱，比直接使用 int64 變量更靈活）
type ID int64
Node 結構用來存儲一個節(jié)點 (機器) 上的基礎數據
type Node struct {
mu sync.Mutex // 添加互斥鎖泼橘，保證并發(fā)安全
timestamp int64 // 時間戳部分
node int64 // 節(jié)點 ID 部分
step int64 // 序列號 ID 部分
}
獲取 Node 類型實例的函數，用于獲得當前節(jié)點的 Node 實例
func NewNode(node int64) (*Node, error) {
// 如果超出節(jié)點的最大范圍迈勋，產生一個 error
if node < 0 || node > nodeMax {
return nil, errors.New("Node number must be between 0 and 1023")
}
// 生成并返回節(jié)點實例的指針
return &Node{
timestamp: 0,
node: node,
step: 0,
}, nil
}
最后一步炬灭，生成 ID 的方法
func (n *Node) Generate() ID {
n.mu.Lock() // 保證并發(fā)安全, 加鎖
defer n.mu.Unlock() // 方法運行完畢后解鎖
// 獲取當前時間的時間戳 (毫秒數顯示)
now := time.Now().UnixNano() / 1e6
if n.timestamp == now {
// step 步進 1
n.step ++
// 當前 step 用完
if n.step > stepMax {
// 等待本毫秒結束
for now <= n.timestamp {
now = time.Now().UnixNano() / 1e6
}
}
} else {
// 本毫秒內 step 用完
n.step = 0
}
n.timestamp = now
// 移位運算，生產最終 ID
result := ID((now - Epoch) << timeShift | (n.node << nodeShift) | (n.step))
return result
}
測試
我們使用循環(huán)去開啟多個 goroutine 去并發(fā)生成 ID靡菇，然后使用 map 以 ID 作為鍵存儲重归，來判斷是否生成了唯一的 ID
main 函數代碼
func main() {
// 測試腳本
// 生成節(jié)點實例
node, err := NewNode(1)
if err != nil {
fmt.Println(err)
return
}
ch := make(chan ID)
count := 10000
// 并發(fā) count 個 goroutine 進行 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 有重復
_, 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")
}
完整的程序實例 ：點我查看
上線使用
你可以用 go 的 net/http 包處理并發(fā)請求，生成 ID 并且返回 http 響應結果厦凤。
Just do it
