简介
snowflake(雪花算法)是一个开源的分布式ID生成算法，结果是一个long型的ID。snowflake算法将64bit划分为多段，分开来标识机器、时间等信息，具体组成结构如下图所示：
| 位置（从右到左） | 大小 | 作用 |
|---|---|---|
| 0～11bit | 12bits | 序列号，用来对同一个毫秒之内产生不同的ID，可记录4095个 |
| 12～21bit | 10bits | 10bit用来记录机器ID，总共可以记录1024台机器 |
| 22～62bit | 41bits | 用来记录时间戳，这里可以记录69年 |
| 63bit | 1bit | 符号位，不做处理 |
特点
它有以下几个特点：
- 能满足高并发分布式系统环境下ID不重复；
- 基于时间戳，可以保证基本有序递增；
- 不依赖于第三方的库或者中间件；
- 不支持时间回拨；
代码实现
- 定义SnowFlake结构体
// SnowFlake 雪花分布式ID结构体
type SnowFlake struct {
epoch int64 // 起始时间戳
timestamp int64 // 当前时间戳，毫秒
centerId int64 // 数据中心机房ID
workerId int64 // 机器ID
sequence int64 // 毫秒内序列号
timestampBits int64 // 时间戳占用位数
centerIdBits int64 // 数据中心id所占位数
workerIdBits int64 // 机器id所占位数
sequenceBits int64 // 序列所占的位数
lastTimestamp int64 // 上一次生成ID的时间戳
sequenceMask int64 // 生成序列的掩码最大值
workerIdShift int64 // 机器id左移偏移量
centerIdShift int64 // 数据中心机房id左移偏移量
timestampShift int64 // 时间戳左移偏移量
maxTimeStamp int64 // 最大支持的时间
lock sync.Mutex // 锁
}
- 初始化Snowflake
由于 -1 在二进制上表示是：
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
所以想要求得 41bits 的 timestamp 最大值可以将 -1 向左位移 41 位，得到：
11111111 11111111 11111110 00000000 00000000 00000000 00000000 00000000
那么再和 -1 进行 ^异或运算：
00000000 00000000 00000001 11111111 11111111 11111111 11111111 11111111
这就可以表示 41bits 的 timestamp 最大值，maxWorkerId和maxCenterId同理。
// Init 初始化
func (s *SnowFlake) Init(centerId, workerId int64) error {
s.epoch = int64(1622476800000) //设置起始时间戳：2022-01-01 00:00:00
s.centerId = centerId
s.workerId = workerId
s.centerIdBits = 4 // 支持的最大机房ID占位数，最大是15
s.workerIdBits = 6 // 支持的最大机器ID占位数，最大是63
s.timestampBits = 41 // 时间戳占用位数
s.maxTimeStamp = -1 ^ (-1 << s.timestampBits)
maxWorkerId := -1 ^ (-1 << s.workerIdBits)
maxCenterId := -1 ^ (-1 << s.centerIdBits)
// 参数校验
if int(centerId) > maxCenterId || centerId < 0 {
return errors.New(fmt.Sprintf("Center ID can't be greater than %d or less than 0", maxCenterId))
}
if int(workerId) > maxWorkerId || workerId < 0 {
return errors.New(fmt.Sprintf("Worker ID can't be greater than %d or less than 0", maxWorkerId))
}
s.sequenceBits = 12 // 序列在ID中占的位数,最大为4095
s.sequence = -1
s.lastTimestamp = -1 // 上次生成 ID 的时间戳
s.sequenceMask = -1 ^ (-1 << s.sequenceBits) // 计算毫秒内，最大的序列号
s.workerIdShift = s.sequenceBits // 机器ID向左移12位
s.centerIdShift = s.sequenceBits + s.workerIdBits // 机房ID向左移18位
s.timestampShift = s.sequenceBits + s.workerIdBits + s.centerIdBits // 时间截向左移22位
return nil
}
- 生成下一个ID
// NextId 生成下一个ID
func (s *SnowFlake) NextId() (int64, error) {
s.lock.Lock() //设置锁，保证线程安全
defer s.lock.Unlock()
now := time.Now().UnixNano() / 1000000 // 获取当前时间戳，转毫秒
if now < s.lastTimestamp { // 如果当前时间小于上一次 ID 生成的时间戳，说明发生时钟回拨
return 0, errors.New(fmt.Sprintf("Clock moved backwards. Refusing to generate id for %d milliseconds", s.lastTimestamp-now))
}
t := now - s.epoch
if t > s.maxTimeStamp {
return 0, errors.New(fmt.Sprintf("epoch must be between 0 and %d", s.maxTimeStamp-1))
}
// 同一时间生成的，则序号+1
if s.lastTimestamp == now {
s.sequence = (s.sequence + 1) & s.sequenceMask
// 毫秒内序列溢出：超过最大值; 阻塞到下一个毫秒，获得新的时间戳
if s.sequence == 0 {
for now <= s.lastTimestamp {
now = time.Now().UnixNano() / 1000000
}
}
} else {
s.sequence = 0 // 时间戳改变，序列重置
}
// 保存本次的时间戳
s.lastTimestamp = now
// 根据偏移量，向左位移达到
return (t << s.timestampShift) | (s.centerId << s.centerIdShift) | (s.workerId << s.workerIdShift) | s.sequence, nil
}
- 调用示例
func main() {
snowFlake := &SnowFlake{}
_ = snowFlake.Init(1, 5)
for i := 0; i < 10; i++ {
fmt.Println(snowFlake.NextId())
}
}
结果输出：
72644832480481280 <nil>
72644832480481281 <nil>
72644832480481282 <nil>
72644832480481283 <nil>
72644832480481284 <nil>
72644832480481285 <nil>
72644832480481286 <nil>
72644832480481287 <nil>
72644832480481288 <nil>
72644832480481289 <nil>
评论区