别着急,坐和放宽
使用社交账号登录
雪花算法(Snowflake)是Twitter开源的分布式ID生成算法,于2010年推出。在分布式系统中,我们经常需要生成全局唯一的ID,传统的数据库自增ID在分布式环境下会遇到性能瓶颈和单点故障问题。雪花算法应运而生,它能够在分布式环境下高效地生成趋势递增、全局唯一的64位长整型ID。
雪花算法生成的ID是一个64位的长整型数字,由以下四部分组成:
| 组成部分 | 位数 | 说明 |
|---|---|---|
| 符号位 | 1 bit | 固定为0,保证生成的ID为正数 |
| 时间戳 | 41 bits | 毫秒级时间戳(当前时间 - 起始时间) |
| 机器ID | 10 bits | 数据中心ID(5 bits) + 工作机器ID(5 bits) |
| 序列号 | 12 bits | 同一毫秒内的序列号,支持单机每毫秒生成4096个ID |
(2^41 - 1) / (1000 * 60 * 60 * 24 * 365) ≈ 69年2^10 = 1024 台机器2^12 = 4096 个ID4096 * 1000 = 409万/秒package main
import (
"fmt"
"log"
)
func main() {
// 创建Snowflake实例:数据中心ID=1, 机器ID=1
sf, err := NewSnowflake(1, 1)
if err != nil {
log.Fatal(err)
}
// 生成10个ID
for i := 0; i < 10; i++ {
id, err := sf.NextID()
if err != nil {
log.Fatal(err)
}
fmt.Printf("ID: %d\n", id)
// 解析ID
parts := ParseID(id)
fmt.Printf(" 时间: %v\n", GetTimestamp(id))
fmt.Printf(" 数据中心: %d, 机器: %d, 序列号: %d\n\n",
parts["datacenterID"], parts["workerID"], parts["sequence"])
}
}
分布式数据库主键
订单号生成
消息队列
分布式追踪
业务对象ID
| 注意事项 | 说明 | 解决方案 |
|---|---|---|
| 时钟回拨 | 服务器时间被人为修改或NTP同步导致时间倒退 | 1. 检测到回拨时抛出异常 2. 等待时钟追上 3. 使用时钟回拨容忍方案 |
| 机器ID分配 | 需要确保每台机器的datacenterID+workerID唯一 | 1. 配置文件管理 2. 使用ZooKeeper分配 3. 使用Redis自动分配 |
| 起始时间选择 | epoch时间戳决定算法可用年限 | 选择接近项目开始时间的时间点 |
| 并发控制 | 高并发下需要保证线程安全 | 使用互斥锁或CAS操作 |
1. 时钟回拨容忍
// 容忍小范围(如5ms)的时钟回拨
if now < s.timestamp {
offset := s.timestamp - now
if offset <= 5 {
time.Sleep(time.Duration(offset) * time.Millisecond)
now = time.Now().UnixMilli()
} else {
return 0, errors.New("clock moved backwards")
}
}
2. 机器ID自动分配
| 方案 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 数据库自增 | 简单,强一致性 | 性能瓶颈,不适合分布式 | 单体应用 |
| UUID | 真正全局唯一,无需协调 | 无序,占用空间大(128位) | 不关注性能的场景 |
| Snowflake | 趋势递增,高性能,信息量大 | 依赖系统时钟,需分配机器ID | 分布式系统(推荐) |
| 数据库号段 | 性能较好,数据库实现简单 | 需要访问数据库 | 中等并发场景 |
雪花算法是一个简单高效的分布式ID生成方案,在保证全局唯一性的同时,还具有趋势递增、高性能、高可用等特点。通过合理的位分配,在一个64位长整型中巧妙地编码了时间、机器和序列信息。
在实际应用中,需要注意时钟回拨、机器ID分配等问题,并根据具体业务场景进行优化调整。对于大多数分布式系统来说,雪花算法都是一个值得推荐的ID生成方案。
参考资料
package snowflake
import (
"errors"
"sync"
"time"
)
const (
// 起始时间戳 (2024-01-01 00:00:00 UTC)
epoch int64 = 1704067200000
// 各部分位数
timestampBits = 41 // 时间戳占用位数
datacenterBits = 5 // 数据中心ID占用位数
workerBits = 5 // 工作机器ID占用位数
sequenceBits = 12 // 序列号占用位数
// 最大值
maxDatacenterID = -1 ^ (-1 << datacenterBits) // 31
maxWorkerID = -1 ^ (-1 << workerBits) // 31
maxSequence = -1 ^ (-1 << sequenceBits) // 4095
// 位移量
workerShift = sequenceBits // 12
datacenterShift = sequenceBits + workerBits // 17
timestampShift = sequenceBits + workerBits + datacenterBits // 22
)
// Snowflake ID生成器
type Snowflake struct {
mu sync.Mutex // 互斥锁,保证并发安全
timestamp int64 // 上次生成ID的时间戳
datacenterID int64 // 数据中心ID
workerID int64 // 工作机器ID
sequence int64 // 序列号
}
// 创建一个新的Snowflake实例
func NewSnowflake(datacenterID, workerID int64) (*Snowflake, error) {
// 参数校验
if datacenterID < 0 || datacenterID > maxDatacenterID {
return nil, errors.New("datacenterID must be between 0 and 31")
}
if workerID < 0 || workerID > maxWorkerID {
return nil, errors.New("workerID must be between 0 and 31")
}
return &Snowflake{
timestamp: 0,
datacenterID: datacenterID,
workerID: workerID,
sequence: 0,
}, nil
}
// 生成下一个ID
func (s *Snowflake) NextID() (int64, error) {
s.mu.Lock()
defer s.mu.Unlock()
// 获取当前时间戳(毫秒)
now := time.Now().UnixMilli()
// 如果当前时间小于上次生成ID的时间戳,说明发生了时钟回拨
if now < s.timestamp {
return 0, errors.New("clock moved backwards")
}
// 如果是同一毫秒内生成的ID
if now == s.timestamp {
// 序列号自增
s.sequence = (s.sequence + 1) & maxSequence
// 如果序列号溢出(超过4095)
if s.sequence == 0 {
// 阻塞到下一毫秒
now = s.waitNextMillis(s.timestamp)
}
} else {
// 不同毫秒,序列号重置为0
s.sequence = 0
}
// 更新时间戳
s.timestamp = now
// 组装64位ID:
// (时间戳 << 22) | (数据中心ID << 17) | (机器ID << 12) | 序列号
id := ((now - epoch) << timestampShift) |
(s.datacenterID << datacenterShift) |
(s.workerID << workerShift) |
s.sequence
return id, nil
}
// 阻塞等待到下一毫秒
func (s *Snowflake) waitNextMillis(lastTimestamp int64) int64 {
timestamp := time.Now().UnixMilli()
for timestamp <= lastTimestamp {
timestamp = time.Now().UnixMilli()
}
return timestamp
}
// 从ID中解析出各个组成部分
func ParseID(id int64) map[string]int64 {
return map[string]int64{
"timestamp": ((id >> timestampShift) + epoch),
"datacenterID": (id >> datacenterShift) & maxDatacenterID,
"workerID": (id >> workerShift) & maxWorkerID,
"sequence": id & maxSequence,
}
}
// 从ID中提取生成时间
func GetTimestamp(id int64) time.Time {
timestamp := (id >> timestampShift) + epoch
return time.UnixMilli(timestamp)
}
// 使用Redis自动分配机器ID
func AutoAssignWorkerID(redis *redis.Client, datacenterID int64) (int64, error) {
key := fmt.Sprintf("snowflake:datacenter:%d:workers", datacenterID)
workerID, err := redis.Incr(ctx, key).Result()
if err != nil {
return 0, err
}
if workerID > maxWorkerID {
return 0, errors.New("no available worker ID")
}
return workerID, nil
}