雪花算法：64 bit 的分布式 ID 设计

一句话结论（30s）

雪花算法用「41bit 时间戳 + 10bit 机器ID + 12bit 序列号」生成全局唯一且趋势递增的 ID——因为 InnoDB 聚簇索引按主键物理排序，UUID 的随机性会导致大量页分裂拖慢插入，而趋势递增的 ID 总是追加到最右叶节点、几乎不分裂；它唯一的短板是时钟回拨，用等待/拒绝/扩展序列号三种策略兜底。

核心原理（2min）

64bit 结构：1bit 保留（恒 0 保正数）+ 41bit 毫秒时间戳（可支撑 69 年）+ 10bit 机器/数据中心 ID（1024 节点）+ 12bit 同毫秒序列号（每毫秒 4096 个）。
为什么快：趋势递增 → InnoDB B+ 树插入总是追加到最右叶节点 → 几乎无页分裂 → 插入性能远优于随机 UUID。
时钟回拨三解法：回拨 ≤5ms 则 sleep 等待；回拨过大则拒绝并告警；临时兜底用扩展序列号（超 4096 会冲突）。
替代方案：美团 Leaf 用 ZooKeeper 持久化递增 segment 号，完全不依赖时间戳。

底层深入（5-10min）

为什么不用 UUID？

UUID 是随机的——每次 INSERT 的 ID 随机分布在 B+ 树的各处。InnoDB 的聚簇索引按主键物理排序，随机主键导致大量页分裂（一个页满了要在中间插入新行 → 分裂为两页 → 磁盘碎片 → 查询变慢）。

思考：随机主键为什么必然引发页分裂？ 因为 B+ 树的叶子节点是按键值顺序物理排列的固定大小页（默认 16KB）。如果新主键落在两个已满页的中间，这一页就得拆成两页、把一半数据搬移出去，这个分裂动作既慢又产生磁盘碎片。而递增主键永远追加到最右页——页没满就往里塞，满了就开新页，从不往中间插，这就是”趋势递增”能避免页分裂的根本原因。

Snowflake 的 64 bit 结构

1 bit (保留) | 41 bit (毫秒时间戳) | 10 bit (机器ID) | 12 bit (序列号)

1 bit:  保留，恒为 0（保证正数）
41 bit: 从自定义起始时间的毫秒数，可支撑 69 年
10 bit: 机器/数据中心 ID，支持 1024 个节点
12 bit: 同一毫秒内的递增序列号，每毫秒支持 4096 个 ID

趋势递增：按时间排序，同一台机器上的 ID 趋势递增 → InnoDB 的 B+ 树插入时总是追加到最右叶节点 → 几乎没有页分裂 → 插入性能远优于 UUID。

思考：为什么偏偏是 41 + 10 + 12 这个组合？ 三个字段都是在 64 bit 预算内做的权衡。41 bit 时间戳是主导——2^41 毫秒约 69 年，相比 UUID 完全无时间语义，这是最大价值；10 bit 机器 ID 决定横向扩容上限（2^10 = 1024 个节点）；12 bit 序列号决定单机单毫秒吞吐（2^12 = 4096）。注意 1 + 41 + 10 + 12 = 64，恰好用满。如果 QPS 更高，可以让出几位机器 ID 换更多序列号位——本质是”用字段宽度换边界容量”的静态分配，没有绝对最优，只有符合自身规模的配比。

时钟回拨问题

如果 NTP 校正导致机器时钟回拨了 100ms → 接下来 100ms 内可能生成与之前重复的 ID。

三种解法：

等待：检测到回拨 <= 5ms 则 sleep 等时钟追上来
拒绝：回拨过大 → 拒绝生成 ID → 上游告警
扩展序列号：用之前毫秒的序列号继续递增（超过 4096 会冲突，是临时兜底）

思考：时钟回拨为什么是雪花算法唯一的硬伤？ 因为它的唯一性完全建立在”时间戳单调递增”这个假设上。机器 ID 固定、序列号每毫秒归零，一旦时间戳倒退，同一毫秒内用相同机器 ID + 相同序列号就能重新生成完全一样的 ID——这个假设被 NTP 校正破坏时，唯一性就崩溃了。而 UUID 不依赖时间、数据库自增由 DB 统一分配，都不存在这个风险，这正是雪花算法为”去中心化 + 高性能”付出的代价。

美团的 Leaf 方案用 ZooKeeper 持久化一个递增的 segment 号，完全不依赖时间戳。

代码实现（Java）

标准雪花算法实现（含时钟回拨等待 + 拒绝两种兜底）：

public class SnowflakeIdWorker {
    // 起始时间戳（2020-01-01 00:00:00），用相对时间避免 41bit 容量浪费
    private final long twepoch = 1577836800000L;

    private final long workerIdBits = 5L;      // 机器 ID 5 位
    private final long datacenterIdBits = 5L;  // 数据中心 ID 5 位（合起来 10 位）
    private final long maxWorkerId = ~(-1L << workerIdBits);
    private final long maxDatacenterId = ~(-1L << datacenterIdBits);
    private final long sequenceBits = 12L;     // 序列号 12 位

    private final long workerIdShift = sequenceBits;
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private final long sequenceMask = ~(-1L << sequenceBits);

    private final long workerId;
    private final long datacenterId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("workerId 越界");
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId 越界");
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();

        // 时钟回拨：本应单调递增的时间戳变小时触发
        if (timestamp < lastTimestamp) {
            long offset = lastTimestamp - timestamp;
            if (offset <= 5) {
                // 策略一：小回拨等待时钟追上来
                try {
                    Thread.sleep(offset);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
                timestamp = System.currentTimeMillis();
                if (timestamp < lastTimestamp) {
                    throw new RuntimeException("时钟回拨，拒绝生成 ID");
                }
            } else {
                // 策略二：大回拨直接拒绝
                throw new RuntimeException("时钟回拨 " + offset + "ms，拒绝生成 ID");
            }
        }

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;  // 同毫秒内序列号 +1
            if (sequence == 0) {
                // 同毫秒序列号耗尽（4096 用满），自旋到下一毫秒
                while (timestamp <= lastTimestamp) {
                    timestamp = System.currentTimeMillis();
                }
            }
        } else {
            sequence = 0L;  // 新毫秒，序列号归零
        }

        lastTimestamp = timestamp;

        // 三段分别左移后按位或，拼成完整 64 bit ID
        return ((timestamp - twepoch) << timestampLeftShift)
             | (datacenterId << datacenterIdShift)
             | (workerId << workerIdShift)
             | sequence;
    }
}

思考：为什么最后用三个左移加 |，而不是加法？ 因为三个字段占用的是互不重叠的位段（序列号低 12 位、机器 ID 中 10 位、时间戳高 41 位），各自左移后正好落到自己的区间，| 把它们”拼”成完整 64 bit。用加法数值上一样，但 | 在语义上更明确表达”拼接位段”的意图，也避免读者误以为字段之间有进位关系。

章末提问

Q1：雪花算法生成的 ID 是全局唯一吗？为什么？ 结论先行：是，在”单机时钟不回拨 + 节点 ID 不重复”两个前提下全局唯一。因为 ID 由（时间戳，机器 ID，序列号）三元组构成，只要同一毫秒内同一台机器的序列号不超 4096，这个三元组就唯一；跨机器由机器 ID 区分，跨毫秒由时间戳区分。一旦时钟回拨或机器 ID 配重了，唯一性立即失效。

Q2：为什么 ID 要趋势递增，直接用数据库自增不就行了吗？ 结论先行：趋势递增是为了 B+ 树插入性能，数据库自增则死在”单点 + 分库分表会撞号”上。因为自增 ID 依赖单一主库串行分配，无法横向扩展，分库分表后多个库各增各的必然撞 ID；而雪花算法把”发号”下放到每个节点本地计算，无网络往返、天然适配分布式。它同时补上了 UUID 的短板——UUID 无时间语义导致页分裂，自增有单点瓶颈，雪花算法取两者之长。

Q3：时钟回拨时，三种兜底策略分别有什么副作用？ 结论先行：等待会阻塞请求、拒绝会牺牲可用性、扩展序列号可能产生冲突。因为等待本质是用延迟换正确性，回拨多久就卡多久；拒绝是直接失败，把”唯一性”排在”可用性”之上；扩展序列号在回拨超过 4096 毫秒（或序列号本身已耗尽）时必然重出 ID，所以只能当临时兜底，不能长期依赖。

雪花算法——分布式全局唯一ID的64bit设计