雪花算法

雪花算法是 Twitter 开源的分布式 ID 生成算法，它具有这些特点：

• 高性能高可用，生成不依赖于数据库，可以分布式部署，完全在内存内生成
• 基于时间戳，生成的 ID 是相对来说有序递增的（
• 高吞吐，允许百万级 QPS

雪花算法原理

雪花算法通常使用一个 64 位长整型来存储一个 ID，这 64 位中包含了时间戳、机器 ID 和序列号三部分：

二进制下形似这样（使用空格分割便于阅读）：

0 11001010011010101011001110100010011111110 0000000001 000000000001
↑                        ↑                       ↑           ↑
1                        2                       3           4

1. 1位 不使用的符号位，始终为 0（二进制数最高位符号位为 1 代表负数）
2. 41位 毫秒级时间戳，最多表示大约 69 年
3. 10位 机器 ID（通常来说拆分为 5 位机器 ID 和 5 位服务 ID 这样的组合形式），最多可以表示 1024 台机器
4. 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 唯一。

Java 基础实现

参见 Demo GitHub Repository。