Charles Shao
Go back

分布式 ID 深挖 · 雪花算法及其变体

–views

单机时代，一个 AUTO_INCREMENT 主键就把「唯一 ID」这件事解决了。可一旦把库拆成几十个分片、把服务铺到上百台机器，问题就变了：没有一个中心能替所有机器发号，每台机器又必须独立造出不会撞车的 ID。广告系统尤其如此——每台竞价机每秒生成几万个曝光 ID、请求 ID，还要求这些 ID 能落进分库分表、能被下游去重、能按时间排序。这就是分布式 ID 生成要解的题，而**雪花算法（Snowflake）**是这道题流传最广的答案。

本文是分布式系统系列的第 5 篇（收尾）。 前四篇从共识打到事务，这一篇收在最贴近业务的一环：怎么在无中心协调下，让每台机器都能高速造出全局唯一的号。

  1. 分布式共识（开篇）· Paxos 与 Raft 图解
  2. ZooKeeper 与 etcd 深挖 · ZAB、Raft、Watch 与租约
  3. 分布式锁深挖 · Redis Redlock vs ZooKeeper/etcd
  4. 分布式事务深挖 · 2PC、TCC、Saga 与 Outbox
  5. 分布式 ID 深挖 · 雪花算法及其变体（本篇）

一句话定位：分布式 ID = 在没有中心协调的前提下，让每台机器都能独立、快速地造出「全局唯一 + 趋势递增」的号。 雪花算法的精髓，就是把这个答案压进一个 64 位整数里，用几次位运算发出来。

TL;DR

Table of contents

Open Table of contents

1. 为什么需要分布式 ID：五个需求维度

在拆库拆服务之前，唯一 ID 根本不是问题——单库一个自增主键就够了。真正的难题出现在「多台机器同时发号、且没有中心裁判」时。而且业务对这个 ID 的期望远不止「不重复」这一条，通常要同时满足下面五维，且它们互相拉扯：

  1. 全局唯一（硬指标）：任何两台机器、任何时刻发出的 ID 都不能撞车。这是底线，撞了就是数据事故（撞了就会引发下游连锁故障）。
  2. 趋势递增 / 单调（软指标）：ID 大体上随时间增大。这不是为了好看——用它做 MySQL 主键时，递增值让 B+ 树总在末尾追加、几乎不页分裂，而无序值会到处插入、频繁分裂页、拉低写入吞吐（这条在 §2 展开，也是分库分表里反复强调的）。「趋势递增」是全局大致有序，「严格单调」是后一个一定比前一个大——后者更贵。
  3. 高性能：发号在很多请求的最前面（一次广告曝光要先拿曝光 ID 才能往下走），必须低延迟、高吞吐，最好本地就能生成，别每次都走网络。
  4. 高可用：发号服务挂了，整条业务链路就断了。它必须比它服务的业务更可用——去中心化（本地生成）是达到高可用最直接的路。
  5. 信息安全（不可猜测）：如果订单 ID 严格连续，竞争对手今天下一单、明天下一单，两个 ID 一减就知道你一天的订单量。对外暴露的 ID 有时故意要不连续 / 不可猜测——这和「单调」直接冲突。

这五维几乎不可能全占满：本地生成（高性能高可用）就很难保证严格单调；严格连续（好排序）就泄露业务量（不安全）。所以没有「最好的方案」，只有「最贴合你这维取舍的方案」。雪花算法之所以流行，是因为它在「唯一 + 趋势递增 + 本地高性能」这个最常见的组合上做得足够好。

2. 先看看非雪花的方案：UUID、DB 自增、Redis INCR

理解雪花为什么长成那样，最好先看看它的「竞品」各自卡在哪一维。

方案全局唯一有序性性能可用性短板
UUID✅ 本地生成❌ 完全无序✅ 极快✅ 无依赖128 位、字符串、做主键伤索引
DB 自增✅✅ 严格单调❌ 每次 IO❌ 单点扩展差、依赖 DB
号段模式✅✅ 趋势递增✅ 内存发号⚠️ 依赖 DB（可缓冲）重启丢一段、仍依赖 DB
Redis INCR✅✅ 单调✅⚠️ 依赖 Redis引入外部依赖、持久化风险
Snowflake✅ 本地生成✅ 趋势递增✅ 位运算✅ 去中心依赖时钟、怕回拨

2.1 UUID：本地生成的代价是「无序」

UUID（如 v4）最大的好处是纯本地生成、零协调、绝不会撞车。但它有两个致命短板，让它几乎不适合做数据库主键：

UUID 适合「只要唯一、不在乎顺序、也不做聚簇主键」的场景（如日志 traceId、幂等去重键）。真要用它做主键，至少上 UUID v7（时间戳前缀、有序）来缓解页分裂。

2.2 DB 自增与号段模式：从「每次 IO」到「一次一批」

数据库自增（AUTO_INCREMENT）严格单调、简单可靠，但每发一个 ID 都要一次写 DB，且单点——单库自增撑不起分布式吞吐。改进思路是号段模式（segment）：不再一个一个取，而是一次性从 DB 取一段（比如 [1001, 2000]）缓存到应用内存里，之后在内存里自增着发，一整段发完再去 DB 取下一段。

这样 DB 的访问频率被摊薄了 step（段长）倍——发 1000 个 ID 只碰一次 DB。代价是：应用重启会丢掉当前段没发完的号（ID 出现跳跃，但不影响唯一性）。号段模式是美团 Leaf 的两大方案之一，§6 会讲它的双 buffer 优化。

2.3 Redis INCR：用单线程换原子有序

Redis 的 INCR / INCRBY 天生适合发号：Redis 单线程模型让 INCR 无需加锁就是原子的，多客户端并发自增也不会错乱，且严格单调。可以像号段一样用 INCRBY key 1000 一次批量取一段，进一步降 RTT。

代价是引入了对 Redis 的强依赖：Redis 挂了就发不出号；而且要小心持久化——如果 INCR 的结果没落盘就宕机、又从旧快照恢复，计数器可能回退造成重复。生产上用它发号，通常要配合 AOF always 或主从 + 哨兵，把可用性和持久化都补上。

3. Snowflake：64 位怎么切，位运算怎么发

雪花算法（Twitter 2010 年开源）的核心洞察是：把生成唯一 ID 需要的三样东西——时间、机器、序列——按位段塞进一个 64 位整数。这样每台机器只靠本地时钟 + 本地计数就能发号，彻底去掉了中心协调。

Snowflake 64 位布局图：一个 64 位 long 从高位到低位被切成四段——第 63 位是符号位恒为 0（保证 ID 为正数）；第 62 到 22 位是 41 位毫秒级时间戳（存当前时间减去自定义纪元 epoch 的差值，约可用 69 年）；第 21 到 12 位是 10 位机器 ID（最多 1024 个节点，常拆成 5 位数据中心 + 5 位 worker）；第 11 到 0 位是 12 位序列号（同一毫秒内自增 0 到 4095，每毫秒最多 4096 个）。底部标注：单节点理论上限每毫秒 4096 个即约 409.6 万 ID 每秒，发满则自旋等到下一毫秒；整体随时间戳趋势递增、高位是时间所以天然按时间有序、适合做 DB 主键（顺序写、B+ 树尾部追加、几乎不页分裂）；位宽可按需重分，机器多就多给 workerId、单机 QPS 高就多给序列号，三段总和为 63 即可。

Snowflake 的 64 位布局：高位放时间（保证趋势递增），中间放机器（保证跨机不撞），低位放序列（保证同毫秒内不撞）——三段拼起来就是一个全局唯一、趋势递增的 long。

3.1 四段各自的职责

3.2 QPS 上限：一台机器每秒 409.6 万

把序列号的容量乘上毫秒数就是单机上限：4096 个/毫秒 × 1000 毫秒/秒 ≈ 409.6 万 ID/秒。对绝大多数业务，单机四百万的发号能力绰绰有余；真不够，就从别的段「借位」给序列号。这也说明雪花的位宽不是铁板一块——机器多就多给 workerId，单机 QPS 高就多给序列号，只要三段加起来是 63 位即可。

3.3 位运算实现：掩码、移位、拼接

雪花的发号逻辑几乎全是位运算，这也是它快的原因。下面是一个能讲清每一步位操作的 Java 实现：

public class SnowflakeIdGenerator {
    // 自定义纪元：2024-01-01 00:00:00 UTC（毫秒）。从这天起算，41 位可用约 69 年
    private static final long EPOCH = 1704067200000L;

    private static final long WORKER_ID_BITS = 10L;
    private static final long SEQUENCE_BITS  = 12L;

    // ~(-1L << n) 得到 n 个 1 的掩码：workerId 上限 1023，序列号上限 4095
    private static final long MAX_WORKER_ID  = ~(-1L << WORKER_ID_BITS);   // 1023
    private static final long SEQUENCE_MASK  = ~(-1L << SEQUENCE_BITS);    // 4095

    // 各段在 64 位里的左移量
    private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;                    // 12
    private static final long TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;   // 22

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

    public SnowflakeIdGenerator(long workerId) {
        if (workerId < 0 || workerId > MAX_WORKER_ID) {
            throw new IllegalArgumentException("workerId 超出范围 [0, " + MAX_WORKER_ID + "]");
        }
        this.workerId = workerId;
    }

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

        if (now < lastTimestamp) {
            // 时钟回拨！朴素实现直接抛异常，生产要更细致，见 §4
            throw new IllegalStateException("时钟回拨 " + (lastTimestamp - now) + "ms，拒绝发号");
        }

        if (now == lastTimestamp) {
            // 同一毫秒内：序列号自增，& 掩码让它到 4095 后回绕为 0
            sequence = (sequence + 1) & SEQUENCE_MASK;
            if (sequence == 0) {
                // 4096 个用完了，自旋等到下一毫秒
                now = tilNextMillis(lastTimestamp);
            }
        } else {
            // 进入新的一毫秒，序列号归零
            sequence = 0L;
        }

        lastTimestamp = now;

        // 三段左移到各自的位置，再用 | 拼成一个 long
        return ((now - EPOCH) << TIMESTAMP_SHIFT)
             | (workerId      << WORKER_ID_SHIFT)
             |  sequence;
    }

    private long tilNextMillis(long last) {
        long ts = System.currentTimeMillis();
        while (ts <= last) {
            ts = System.currentTimeMillis();
        }
        return ts;
    }
}

几个位运算细节值得咂摸：

4. 时钟回拨：雪花算法的阿喀琉斯之踵

雪花把物理时钟当成 ID 的高位，这也埋下了它最大的隐患：只要时钟往回走，ID 就可能重复。

时钟为什么会回拨？最常见的是 NTP 校准——机器时钟会漂移，NTP 会周期性把它「拨准」，如果本地时钟走快了，校准就会把它往回拨几毫秒到几百毫秒；此外闰秒、虚拟机时钟同步、人为改时间都可能造成回拨。

时钟回拨导致重复 ID 及处理策略图，分左右两栏。左栏「问题：NTP 校准把时钟拨回过去」自上而下四步：t=1810ms 发出 ID₁（ts=1810, seq=0，唯一）；NTP 校准把时钟从 1810 回拨到 1808（倒退 2 毫秒）；t=1808ms 朴素实现未察觉回拨照常发号（ts=1808, seq=0）；结果这个 ID 与历史上 t=1808 时发出的某个 ID 完全相同，产生重复，导致下游去重误判、分片路由错乱。右栏「处理策略：检测 now < lastTimestamp」列三种：① 小幅回拨则等待，自旋直到当前时间大于等于 lastTimestamp 再发号，适用于回拨在几毫秒内、阻塞可接受；② 大幅回拨则拒绝加告警，超过阈值直接抛异常停止发号，宁可短暂不可用也不发重复 ID；③ 用逻辑时钟或备用 workerId，用单调递增的逻辑时钟替代物理时钟，或切换一个备用机器位绕开撞车。底部说明：根因是雪花高位是物理时钟，一旦回拨（时间戳、workerId、序列）的组合就可能和过去某个 ID 重复，而 workerId 分配冲突会把问题放大成跨机器重复；生产做法是记录 lastTimestamp、每次发号先比对，回拨在阈值内就等待、超阈值就拒绝并告警，同时用 ZK/etcd 保证 workerId 唯一，双管齐下。

时钟回拨的本质：(时间戳, workerId, 序列) 三元组一旦因时钟倒退而与历史重合，就撞出重复 ID。处理三招——小幅等待、大幅拒绝、或干脆用逻辑时钟绕开物理时钟。

4.1 三种处理策略

关键是检测：每次发号前比较 now 与 lastTimestamp，now < lastTimestamp 就说明发生了回拨。检测到之后有三条路：

public synchronized long nextId() {
    long now = System.currentTimeMillis();
    long offset = lastTimestamp - now;

    if (offset > 0) {                       // 检测到时钟回拨
        if (offset <= MAX_BACKWARD_MS) {    // ① 小幅回拨：等它追上来
            try {
                wait(offset << 1);          // 等待约 2 倍偏移
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
            now = System.currentTimeMillis();
            if (now < lastTimestamp) {       // 等完还没追上，只能拒绝
                throw new ClockBackwardsException(lastTimestamp - now);
            }
        } else {                            // ② 大幅回拨：拒绝并告警
            metrics.markClockBackwards(offset);
            alert("时钟回拨 " + offset + "ms 超阈值，停止发号");
            throw new ClockBackwardsException(offset);
        }
    }
    // ...（同 §3.3 的正常发号逻辑）
}
  1. 小幅回拨 → 等待：如果回拨只有几毫秒（offset <= 阈值），就自旋 / 等待到 now >= lastTimestamp 再发号。代价是这段时间发号被短暂阻塞，但阈值内可接受，且不会产生重复 ID。
  2. 大幅回拨 → 拒绝 + 告警：如果回拨超过阈值（比如几百毫秒、几秒），等待就不现实了（等几秒等于服务不可用）。这时宁可拒绝发号、抛异常、拉响告警，也绝不能冒着发重复 ID 的风险硬发——这台机器暂时退出发号，把流量切给别的机器。
  3. 逻辑时钟 / 备用位 → 绕开物理时钟：更进一步的方案是不完全信任物理时钟。比如用一个单调递增的逻辑时钟（回拨时逻辑时钟继续往前，不倒退）替代 System.currentTimeMillis()；或者预留备用 workerId 位，检测到回拨就切一个没用过的 workerId，从而绕开「时间戳 + workerId」的重合。百度 UidGenerator 的「借用未来时间」（§6.3）本质上也是这一思路。

生产上的标准姿势是 ①+② 组合再加监控：小幅等待、大幅拒绝、全程埋点告警。绝不要用只 throw 或只无限等待的极端实现——前者遇到常规 NTP 校准就频繁报错，后者遇到大回拨就把服务拖死。

5. workerId 从哪来：配置、ZK、etcd 注册

雪花「不同机器不撞车」的全部保证，压在 workerId 全局唯一这一个前提上。一旦两台机器拿到相同的 workerId，它们在同一毫秒发的号就会完全一样——这是比时钟回拨更隐蔽、也更常见的重复 ID 来源（两者都可能撞上）。workerId 怎么分配，有三档做法：

关键原则：workerId 的唯一性必须由一个「有共识能力的中心」来保证，而不是靠人不出错。 手工配置在小规模下能跑，但它把「唯一性」建立在运维纪律上——而运维纪律迟早会破。用 ZK/etcd 把这件事自动化、可回收、可审计，是雪花上规模的必修课。

6. 号段模式与工业级变体：Leaf 与 UidGenerator

原生雪花之外，工业界打磨出了几个更完备的方案，最有代表性的是美团 Leaf 的两条路线和百度 UidGenerator。

6.1 Leaf-segment：号段模式与双 buffer 预取

§2.2 提过号段模式的雏形：一次从 DB 取一段 ID 缓存到内存里发。但朴素号段有个毛病——当前段一发完，那一刻的请求必须同步等一次「查 DB 取下一段」，于是每隔一段就出现一次延迟毛刺。Leaf 的解法是双 buffer 预取：

Leaf-segment 双 buffer 预取图。左侧是一张 DB 表 leaf_alloc（biz_tag = ad_imp，max_id = 4000，step = 1000），是全局唯一自增源，每次原子地把 max_id 加上 step。中间偏右有两个号段 buffer：Segment Buffer0 是当前段，区间 [2001, 3000]，已发到 2900，在内存里自增无需访问 DB；Segment Buffer1 是备用段，区间 [3001, 4000]，已预取就绪，当前段一耗尽即无缝切换。图中标注：当 Buffer0 用量超过 90% 时，后台线程异步向 DB 请求下一段（执行 UPDATE max_id = max_id + step），把取回的新区间填入备用 Buffer1；当前段耗尽后直接切换到备用段。底部说明：朴素号段是段耗尽才同步查 DB，那一刻请求要等一次 DB 往返、出现周期性毛刺；双 buffer 则在用到阈值时提前把下一段取好放进备用 buffer，当前段一耗尽立刻无缝切换，把取号的 DB 访问从关键路径挪走。对比雪花：号段是趋势递增、对 DB 依赖强但不怕时钟回拨；Leaf-snowflake 用 ZK 托管 workerId 并做时钟回拨校验。

双 buffer 的关键：不等段耗尽才取号，而是「用到 90% 就后台预取下一段」。当前段一发完立刻切到已备好的备用段——把「取号」的 DB 往返从发号关键路径上彻底挪走。

内存里同时维护两个号段 buffer：一个正在发（current），一个备用（next）。当 current 段消费到某个阈值（如 90%）时，就用后台线程异步去 DB 取下一段填进 next buffer；等 current 段发完，直接无缝切换到 next，同时再触发下一次预取。这样「取号」的 DB 访问永远发生在后台，请求路径上再也不用同步等 DB。

DB 侧的号段分配就是一条原子更新：

-- 取一段：把 max_id 往前推 step，返回新区间 [old_max_id + 1, new_max_id]
UPDATE leaf_alloc
   SET max_id = max_id + step
 WHERE biz_tag = 'ad_imp';

SELECT max_id, step FROM leaf_alloc WHERE biz_tag = 'ad_imp';

号段模式的好处是对 DB 依赖弱（N 倍摊薄）、趋势递增、且完全不怕时钟回拨（它压根不用时钟）；代价是重启会丢弃当前段没发完的号（ID 出现跳段，但不影响唯一），以及 ID 是趋势递增而非严格连续。

6.2 Leaf-snowflake：给雪花配上 ZK 托管的 workerId

Leaf 的另一条线就是把原生雪花做扎实：用 ZooKeeper 自动分配并持久化 workerId（§5），机器重启后能拿回原来的 workerId；同时内置时钟回拨检测——启动时和运行时都校验本机时钟，回拨超阈值就拒绝启动 / 拒绝发号并告警。它解决的正是原生雪花最容易翻车的两点：workerId 冲突和时钟回拨。

6.3 百度 UidGenerator：借用未来时间 + RingBuffer

百度的 UidGenerator 是雪花的另一种工程化，两个亮点：

三者定位：Leaf-segment 要「不依赖时钟、能接受跳段」；Leaf-snowflake / 原生雪花 要「本地生成、趋势递增、能接受时钟约束」；UidGenerator 要「高吞吐、想尽量抹平时钟回拨的抖动」。它们不是替代关系，而是同一道题在不同约束下的不同解。

7. 选型：有序 vs 分片友好 vs 严格单调

回到最开始的五维需求，落到实际选型，通常先问自己几个问题：

没有银弹。「趋势递增 + 本地高性能 + 去中心高可用」的最大公约数就是雪花，所以它成了默认选择；而当你在「分片均匀」「严格单调」「不可猜测」某一维上有更强诉求时，就得为那一维单独加设计（解耦分片键、引入单点、混随机位）——这正是 §1 说的「五维互相拉扯，选型即取舍」。

参考

–views
Share this post on:
Share this post via WhatsApp Share this post on Facebook Share this post on X Share this post via Telegram Share this post on Pinterest Share this post via email
Previous Post
RPC 框架（开篇）· 原理与 gRPC/Thrift/Dubbo
Next Post
分布式事务深挖 · 2PC、TCC、Saga 与 Outbox