分布式全局唯一ID: snowflake 算法
站长
· 阅读数 3
在分布式系统中，经常需要生成全局唯一ID。雪花算法是由Twitter开源的一种生成全局唯一ID的算法,在业中广泛应用。本文将介绍雪花算法，以及Go如何使用雪花算法来生成全局唯一ID。
snowflake
雪花算法的核心思想是将一个64bit的整数分成多个部分,包括: 时间戳、机器ID、序列号等, 不依赖mysql、redis、内存等，通过服务器时间、定义的工作机器ID和序号来保证全局唯一性，同时具体一定的有序性。生成的值大概是这样的：
1765396306500521984
1765757491058053120
1765758879200710656
组成部分
| 最高位 | 中位 | 中下位 | 末位 |
+--------------------------------------------------------------------------+
| 1 Bit Unused | 41 Bit Timestamp | 10 Bit NodeID | 12 Bit Sequence ID |
+--------------------------------------------------------------------------+
- 最高位占1 bit，值固定为 0
- 中位占 41 bit，值为毫秒级时间戳,总共可以容纳约70年左右的时间
- 中下位占 10 bit，值为工作机器的 ID，值的上限为 1024
- 末位占 12 bit，值为当前毫秒内 0开始不断累加，值的上限为 4096
所以，SnowFlake一毫秒内最多可以生成全局唯一ID的数量为:1024 X 4096 = 4194304
Go实现snowflake
参考[4]中的Example, 看看Go如何实现snowflake
package main
import (
"errors"
"sync"
"time"
)
// 定义常量
const (
epoch = 1704038400000 // 2024-01-01的时间戳
workerIDBits = 5 // 机器ID所占的位数
sequenceBits = 8 // 序列号所占的位数
maxWorkerID = -1 ^ (-1 << workerIDBits)
maxSequence = -1 ^ (-1 << sequenceBits)
workerIDShift = sequenceBits
timestampShift = workerIDBits + sequenceBits
)
// 定义结构体
type Snowflake struct {
mu sync.Mutex
workerID int64
lastTimestamp int64
sequence int64
}
// 创建Snowflake实例
func NewSnowflake(workerID int64) (*Snowflake, error) {
if workerID < 0 || workerID > maxWorkerID {
return nil, errors.New("invalid worker ID")
}
return &Snowflake{
workerID: workerID,
}, nil
}
// 生成ID的方法
func (s *Snowflake) GenerateID() int64 {
s.mu.Lock()
defer s.mu.Unlock()
timestamp := time.Now().UnixNano() / 1000000
if timestamp < s.lastTimestamp {
panic("clock moved backwards")
}
if timestamp == s.lastTimestamp {
s.sequence = (s.sequence + 1) & maxSequence
if s.sequence == 0 {
// 当前毫秒的序列号已经用完，等待下一毫秒
for timestamp <= s.lastTimestamp {
timestamp = time.Now().UnixNano() / 1000000
}
}
} else {
s.sequence = 0
}
s.lastTimestamp = timestamp
id := ((timestamp - epoch) << timestampShift) | (s.workerID << workerIDShift) | s.sequence
return id
}
// 使用示例
func main() {
snowflake, err := NewSnowflake(1)
if err != nil {
panic(err)
}
id := snowflake.GenerateID()
println(id)
}
可以看到，实现的代码简练，不过短短的数十行。通过传入node值，调用NewSnowflake生成一个ID生成器，执行函数GenerateID生成唯一id。让我们写一下基准测试，看看性能如何。
func BenchmarkGenerate(b *testing.B) {
node, err := NewNode(1)
if err != nil {
b.Fatal(err)
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
_ = node.Generate()
}
}
输出：
BenchmarkGenerate
BenchmarkGenerate-4 64616 28031 ns/op
当然，snowflake的缺点也是比较明显的:
- 服务器的时间发生了错乱或者回拨， 有很大 概率生成重复的 ID
- 中位是 41 bit 的毫秒级时间戳，也就是从当前起始到41 bit 耗尽， 只够用70 年左右
bwmarrin/snowflake
bwmarrin/snowflake 是一个非常简单的、稳定且完整的Twitter 第三方雪花生成器。它提供了:
- 解析现有雪花 ID 的方法。
- 将雪花 ID 转换为多种其他数据类型并返回的方法。
- JSON Marshal/Unmarshal 函数可在 JSON API 中轻松使用雪花 ID。
- 单调时钟计算可防止时钟漂移。
go get github.com/bwmarrin/snowflake
一个入门级的例子
package main
import (
"fmt"
"github.com/bwmarrin/snowflake"
)
func main() {
// Create a new Node with a Node number of 1
node, err := snowflake.NewNode(1)
if err != nil {
fmt.Println(err)
return
}
// Generate a snowflake ID.
id := node.Generate()
// Print out the ID in a few different ways.
fmt.Printf("Int64 ID: %d\n", id)
fmt.Printf("String ID: %s\n", id)
fmt.Printf("Base2 ID: %s\n", id.Base2())
fmt.Printf("Base64 ID: %s\n", id.Base64())
// Print out the ID's timestamp
fmt.Printf("ID Time : %d\n", id.Time())
// Print out the ID's node number
fmt.Printf("ID Node : %d\n", id.Node())
// Print out the ID's sequence number
fmt.Printf("ID Step : %d\n", id.Step())
// Generate and print, all in one.
fmt.Printf("ID : %d\n", node.Generate().Int64())
}
输出
Int64 ID: 1765396306500521984
String ID: 1765396306500521984
Base2 ID: 1100001111111111100101001011001011000110000000001000000000000
Base64 ID: MTc2NTM5NjMwNjUwMDUyMTk4NA==
ID Time : 1709738253604
ID Node : 1
ID Step : 0
ID : 1765396306500521985
为了和上例进行对比，这里我们做了基准测试，仅供参考:
func BenchmarkGenerate(b *testing.B) {
node, err := snowflake.NewNode(1)
if err != nil {
fmt.Println(err)
return
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
_ = node.Generate()
}
}
BenchmarkGenerate
BenchmarkGenerate-4 1000000 1119 ns/op
更多的snowflake算法实现可以参考：链接【3】【4】
总结
本文简要介绍了雪花算法, 核心是使用时间戳、机器ID、序列号等生成一个64bit整数的全局唯一ID。文中还介绍了Go语言是如何实践的，并介绍了使用snowflake的几个第三方库bwmarrin/snowflake、sonyflake等，并对比了几个基准测试结果，简单且高效。