雪花算法
2025年2月5日大约 2 分钟
雪花算法是 Twitter 开源的分布式 ID 生成算法,它具有这些特点:
- 高性能高可用,生成不依赖于数据库,可以分布式部署,完全在内存内生成
- 基于时间戳,生成的 ID 是相对来说有序递增的(
- 高吞吐,允许百万级 QPS
雪花算法原理
雪花算法通常使用一个 64 位长整型来存储一个 ID,这 64 位中包含了时间戳、机器 ID 和序列号三部分:
二进制下形似这样(使用空格分割便于阅读):
0 11001010011010101011001110100010011111110 0000000001 000000000001
↑ ↑ ↑ ↑
1 2 3 4
1位
不使用的符号位,始终为 0(二进制数最高位符号位为 1 代表负数)41位
毫秒级时间戳,最多表示大约 69 年10位
机器 ID(通常来说拆分为 5 位机器 ID 和 5 位服务 ID 这样的组合形式),最多可以表示 1024 台机器12位
序列号,每毫秒最多生成 4096 个 ID
上面这个 ID 转换为十进制存储就是 7292833926844780545
。代表的时间是 2025-02-05 17:18:22.462
,机器 ID 是 1
,序列号是 1
。
雪花算法实现
伪代码
// 如果 WorkerID 用数据库自增分配等从 1 开始的方式
// 要注意此时机器最多是 1023 台(0~1023),因为 0 未分配
var workerId = 1;
var lastTimestamp;
// sequence 0~4095
var sequence = 0;
// 这个方法需要是线程安全的
synchronized nextId()
{
var timestamp = now();
if (timestamp < lastTimestamp) {
// 回拨处理,可以拒绝也可以尝试等待
throw new Exception("发生时钟回拨拒绝生成 ID");
}
if (timestamp == lastTimestamp) {
if (++sequence > 4095) {
// 同一毫秒内序列号用完,等待下一毫秒
timestamp = waitToNextMillis();
sequence = 0;
}
} else {
// 新的毫秒,序列号从 0 开始
sequence = 0;
}
lastTimestamp = timestamp;
return ((timestamp - TWEPOCH) << 22) | (workerId << 12) | sequence;
}
waitToNextMillis()
{
sleep(1);
}
三部分(时间戳、机器 ID、序列号)的位数可以根据实际情况调整,但是总和必须是 64 位。分别生成最后左移所需位数,然后三部分进行或运算得到最终 ID。
实现时要注意时钟回拨的处理和机器 ID 唯一。