介绍
snowflake 雪花算法可以在不依赖数据库的情况下，生成全局唯一的ID。雪花算法生成的ID是一个64位的整数，它由以下4部分组成:
- 时间戳：占用41位，精确到毫秒级，用于记录时间戳，差值形式可以使用69年。
- 数据中心ID：占5位，可以部署32个数据中心。
- 机器ID：占5位，每个数据中心可以有32台机器。
- 序列号：占用12位，每个节点每毫秒最多可以生成4096个ID。
组成 [1][41][5][5][12] ，其中第一位是符号位默认值为0。
工作原理：
- 使用配置文件或环境变量确保不同数据中心和机器节点拥有唯一ID。
- 设置时钟回拨处理策略，使用NTP服务同步时钟。
- 当一个节点在同一毫秒内请求多个ID时，会通过增加序列号的方式来保证ID的唯一性。
下面将使用 GO 语言简单实现雪花算法。
实现
纪元
因为雪花算法中时间戳是根据当前时间戳与纪元时间戳做差得出的，所以我们得先设定一个纪元时间戳。
Go 语言中 UnixMill 可以将当前时间转化为精确到毫秒的时间戳，所以我们打算使用 UnixMill 将当前时间转换为时间戳作为纪元时间戳。
package main
import (
"fmt"
"time"
)
func main () {
// 获取当前时间
now := time.Now()
// 获取时间戳
timestamp := now.UnixMilli()
fmt.Println(timestamp)
// 人类可读形式
humanReadable := now.Format("2006-01-02 15:04:05")
fmt.Println(humanReadable)
}
最大值
为了方便接口设计，我们去掉了数据中心，只剩下时间戳、机器ID和序列号。为了方便边界判断，我们需要设定常量记录它们的最大值。为了方便拼接将时间戳、机器ID和序列号拼接成最终结果，我们还需要记录它们的偏移量，具体实现如下：
const (
epoch int64 = 1719562568879 // 设置起始时间戳，例如2021-01-01 00:00:00 UTC
timeBitLength uint8 = 41 // 时间戳占用的位数
workerIDBitLength uint8 = 5 // 工作机器ID占用的位数
sequenceBitLength uint8 = 12 // 序列号占用的位数
maxWorkerID int64 = -1 ^ (-1 << workerIDBitLength) // 工作机器ID的最大值
maxSequence int64 = -1 ^ (-1 << sequenceBitLength) // 序列号的最大值
timeShift uint8 = workerIDBitLength + sequenceBitLength
workerIDShift uint8 = sequenceBitLength
twepoch int64 = epoch
)
Snowflake 结构体
snowflake 结构体包括一把互斥锁，以及组成唯一ID的三部分，具体实现如下：
type Snowflake struct {
mu sync.Mutex
timestamp int64
workerID int64
sequence int64
}
初始化结构体
同一台机应该使用唯一的 Snowflake 对象，初始化时赋予其合法且唯一的 workerID。
func NewSnowflake(workerID int64) (*Snowflake, error) {
if workerID < 0 || workerID > maxWorkerID {
return nil, errors.New("worker ID out of range")
}
return &Snowflake{
timestamp: 0,
workerID: workerID,
sequence: 0,
}, nil
}
生成ID
- 在同一台机器上为避免生成重复的ID，我们应该在生成ID之前，先获取互斥锁。
- 拿到锁之后，利用当前时间戳与纪元时间戳做差得到 timestamp 的值。
- 比较当前timestamp 与结构体中的 timestamp。
- 如果当前值更小，说明发生了时钟回拨，抛出异常拒绝生成ID。
- 如果 timestamp 值相等，那么说明是同一毫秒内生成不同序列号
- 如果可用序列号没有用完则递增生成序列号
- 如果序列号用完，循环回0，则等待下一毫秒的到来。
- 如果 timestamp 值不同，那么说明时新值，将序列号置零。
- 组合时间戳、机器ID和序列号得到唯一ID。
func (s *Snowflake) Generate() (int64, error) {
s.mu.Lock()
defer s.mu.Unlock()
now := time.Now().UnixMilli() - twepoch
if now < s.timestamp {
return 0, errors.New("clock is moving backwards")
}
if now == s.timestamp {
s.sequence = (s.sequence + 1) & maxSequence
if s.sequence == 0 {
for now <= s.timestamp {
now = time.Now().UnixMilli() - twepoch
}
}
} else {
s.sequence = 0
}
s.timestamp = now
id := ((now << timeShift) | (s.workerID << workerIDShift) | (s.sequence))
return id, nil
}
使用
上面内容完成后，只要先创建 Snowflake 对象，然后再调用 Generate 函数便可以生成唯一ID。
func main() {
sf, _ := NewSnowflake(1) // Assuming workerID 1 is valid
for i := 0; i < 1000; i++ {
id, err := sf.Generate()
fmt.Println(id)
}
}
特点
1.高性能：ID生成过程完全在内存中完成，高效且延迟低。
2.高可用：ID的生成在本地完成，不会因为单点故障而影响其他节点ID的生成。
3.无中心化：不依赖于外部系统，如数据库，避免复杂的依赖和潜在的性能瓶颈。
4.可排序：由于ID的前部是基于时间的，所以生成的ID自然是按时间顺序增加的。
注意事项
使用时应注意统一所有节点时钟，并且设计好时钟回拨时的处理方案。