设计一个分布式 ID 生成器
问题
Snowflake 的时钟回拨问题怎么解决？美团 Leaf 的改进方案是什么？百亿级 ID 怎么设计？
分布式 ID 的核心要求
分布式 ID 生成器不在面试题里新奇，但它几乎出现在所有后端系统里——订单号、消息 ID、用户 ID、日志 ID，每个都需要一个全局唯一的 ID。三个核心要求：
- 全局唯一：不能重复，没有任何商量余地
- 趋势递增：MySQL B+ 树索引对有序插入最友好，无序 ID 会导致页分裂，写入性能骤降
- 高可用、低延迟：ID 生成往往是业务写入的第一道关卡，如果生成器挂了，整个写入链路都卡住
Snowflake 算法：最经典的方案
Snowflake 的结构很简单，64 位长整型，分成四段：
0 | 0000000000 0000000000 0000000000 0000000000 0 | 00000 | 00000 | 000000000000
↑ 符号位(1) ↑ 时间戳(41 bit) ↑ 机器ID(10) ↑ 序列号(12)- 1 bit 符号位：固定 0，保证 ID 为正数
- 41 bit 时间戳：毫秒级，从某个起始时间算起，能用约 69 年
- 10 bit 机器 ID：5 位数据中心 + 5 位机器，支持 32 × 32 = 1024 个节点
- 12 bit 序列号：同一毫秒内递增，每毫秒最多 4096 个 ID
单机 QPS 约 409 万/秒（1000 × 4096），一般来说够用。
一个简单实现
public class SnowflakeIdWorker {
private final long datacenterId;
private final long workerId;
private long sequence = 0L;
private long lastTimestamp = -1L;
private static final long TWEPOCH = 1609459200000L; // 2021-01-01
private static final long WORKER_ID_BITS = 5L;
private static final long DATACENTER_ID_BITS = 5L;
private static final long SEQUENCE_BITS = 12L;
public synchronized long nextId() {
long timestamp = System.currentTimeMillis();
// 时钟回拨检测
if (timestamp < lastTimestamp) {
throw new RuntimeException("时钟回拨，拒绝生成 ID");
}
if (timestamp == lastTimestamp) {
sequence = (sequence + 1) & 0xFFF;
// 同一毫秒用完 4096 个，等下一毫秒
if (sequence == 0) {
timestamp = waitNextMillis(lastTimestamp);
}
} else {
sequence = 0L;
}
lastTimestamp = timestamp;
return ((timestamp - TWEPOCH) << 22)
| (datacenterId << 17)
| (workerId << 12)
| sequence;
}
}这个实现有个明显的问题：时钟回拨时直接抛异常。生产环境不能这么干。
时钟回拨：Snowflake 最大的坑
服务器 NTP 同步导致时间倒退几毫秒甚至几百毫秒，是常见情况。如果时钟回拨后直接用旧时间戳，就可能生成重复 ID。
真实案例：2021 年某电商大促期间，因运维批量调整 NTP 服务器导致 200+ 台机器同时回拨 50ms，Snowflake ID 生成器大面积抛异常，订单创建链路中断 3 分钟，直接损失预估 200 万+ GMV。事后复盘发现：回拨量其实只有 50ms，但代码里直接 throw RuntimeException，没有任何治理策略。
业界常见的三种解法：
方案一：等待追回
记录上次生成 ID 的时间戳，检测到回拨后阻塞等待，直到系统时间追上。回拨量小（几毫秒）时可行，但回拨超过 1 秒就不可接受了。
// 等待追回实现
private long tilNextMillis(long lastTimestamp) {
long timestamp = System.currentTimeMillis();
while (timestamp < lastTimestamp) {
// 回拨多少等多久，最多等 1 秒
long wait = lastTimestamp - timestamp;
if (wait > 1000) {
// 回拨超过 1 秒，走备用方案，不再死等
throw new ClockBackwardsException("回拨超过 1s: " + wait + "ms");
}
LockSupport.parkNanos(TimeUnit.MILLISECONDS.toNanos(wait));
timestamp = System.currentTimeMillis();
}
return timestamp;
}适用边界：回拨小于 10ms 时，等待时间几乎无感知；回拨 200ms 时，该线程阻塞 200ms，高并发场景下可能引发线程池堆积。
方案二：备用序列号段
回拨时切换机器 ID 或数据中心 ID，沿用旧时间戳但用不同的机器标识，确保 ID 不会重复。本质上是用机器 ID 的冗余来覆盖时钟回拨。
// 回拨时用备用 workerId
private long nextIdWithBackup() {
long timestamp = System.currentTimeMillis();
if (timestamp < lastTimestamp) {
// 切换到备用机器 ID 段
long backupWorkerId = workerId + 1024; // 偏移到备用段
return ((lastTimestamp - TWEPOCH) << 22)
| (backupWorkerId << 12)
| sequence.incrementAndGet();
}
// 正常走主逻辑
...
}注意：备用段的范围有限，极端情况下（频繁回拨）备用 ID 也会耗尽。
方案三：用号段替代时间戳
这是最彻底的方案——抛弃时间戳，改用预先分配的号段。美团 Leaf 就是这么做的。
美团 Leaf：不用时间戳，用号段
Leaf 的核心思路：在 DB 中维护一个 biz_tag 表，每次取一段 ID，进程内缓存，用完再取。
CREATE TABLE `leaf_alloc` (
`biz_tag` varchar(128) NOT NULL,
`max_id` bigint(20) NOT NULL DEFAULT '1',
`step` int(11) NOT NULL DEFAULT '1000',
`description` varchar(256) DEFAULT NULL,
`update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
PRIMARY KEY (`biz_tag`)
);
-- 插入业务线
INSERT INTO leaf_alloc(biz_tag, max_id, step, description)
VALUES('order', '1', '1000', '订单 ID');
INSERT INTO leaf_alloc(biz_tag, max_id, step, description)
VALUES('user_id', '100000000', '2000', '用户 ID');取号段过程：
// 伪代码：取号段（乐观锁方式）
public Segment getNextSegment(String tag) {
// 乐观锁：CAS 更新 max_id
String sql = "UPDATE leaf_alloc SET max_id = max_id + step WHERE biz_tag = ?";
int updated = jdbcTemplate.update(sql, tag);
if (updated == 0) {
throw new RuntimeException("biz_tag 不存在");
}
// 读取更新后的 max_id
long maxId = queryMaxId(tag);
long minId = maxId - step;
return new Segment(minId, maxId);
}客户端拿到号段后，在内存中分配 ID，用完才去 DB 取下一个号段。
优点：
- 完全避免时钟回拨问题（不依赖时间）
- QPS 可达 1 万+/秒，且大部分时间 0 DB 写入
- 每个
biz_tag独立，业务隔离
缺点：
- 依赖 DB 的可用性（DB 挂了号段取不到）
- 趋势递增，但不同 tag 之间不保证全局单调递增——注意：面试常问，"不同业务线 ID 谁大谁小没有意义，不能用来做跨业务排序"
- 进程重启后号段缓存丢失，浪费一个号段
双 Buffer 优化
Leaf 还有一个重要的优化：双 Buffer 预加载。当当前号段消耗到 10% 时，后台异步加载下一个号段，避免号段耗尽时同步等待 DB 的毛刺。
时序图 —— 双 Buffer 号段分配流程：
Client SegmentBuffer DB
| | |
|--- nextId() ------------------->| |
| |--- 从 current 取 ID ----->|
|<-- 返回 ID ---------------------| |
| | |
|--- nextId() (号段消耗 > 90%) --->| |
| |--- 异步加载 next ---------|
| | |--- UPDATE leaf_alloc
| | |--- SELECT max_id
| |<-- next 号段 + 1 已就绪 --|
|<-- 返回 ID ---------------------| |
| | |
|--- current 耗尽 -----------------| |
| |--- 切换 current = next ---|
| |--- 触发下一轮预加载 -------|public class SegmentBuffer {
private AtomicBoolean switching = new AtomicBoolean(false);
private volatile Segment current;
private volatile Segment next;
private volatile boolean ready; // 下一个号段是否已加载
private volatile boolean initOk;
public long nextId() {
long id = current.nextId();
// 当前号段消耗超过 90%，触发预加载
if (current.usedPercent() > 90 && !ready) {
asyncLoadNext();
}
return id;
}
private void asyncLoadNext() {
if (switching.compareAndSet(false, true)) {
executor.submit(() -> {
try {
Segment nextSegment = idGen.loadNextSegment(tag);
next = nextSegment;
ready = true;
} finally {
switching.set(false);
}
});
}
}
}实测效果：美团内部数据显示，双 Buffer 优化后，Leaf 客户端 99.9% 的 ID 获取在 1ms 内完成，DB 写入频率从每千次 1 次降低到每万次 1 次。
百度 UidGenerator：另一种思路
百度的方案在 Snowflake 框架上做了改进：
- 时间戳用秒级（减少位数到 28 bit，可用 8 年）
- 序列号用 RingBuffer 预生成（提升吞吐）
- 机器 ID 通过 DB 自动分配（不用手动配置）
核心改进是序列号预生成：用 RingBuffer 预先在内存中生成一批序列号，分配时从 RingBuffer 取，避免锁竞争。
// RingBuffer 序列号预生成（简化版）
public class BufferedUidProvider {
private final RingBuffer ringBuffer;
private final int bufferSize;
public BufferedUidProvider(int bufferSize) {
this.bufferSize = BufferPaddingStrategy.powerOfTwo(bufferSize);
this.ringBuffer = new RingBuffer(this.bufferSize);
// 预热：一次性生成一批 UID 放入 RingBuffer
preLoad();
}
public long nextId() {
// 无锁从 RingBuffer 取，CAS 移动 tail
return ringBuffer.take();
}
}对比 Snowflake 原始实现：BufferedUidProvider 的吞吐量在同配置下比原生 Snowflake 高 30%-50%，原因是减少了 synchronized 锁竞争。
各方案性能对比
| 维度 | Snowflake 原生 | 美团 Leaf-segment | 百度 UidGenerator |
|---|---|---|---|
| 单机 QPS | 约 400 万 | 约 5 万（受限于号段内存分配速度） | 约 600 万 |
| 依赖 | 无（本地生成） | 依赖 DB | 依赖 DB（机器 ID 注册）+ Spring |
| 时钟回拨 | 需要自己处理 | 不依赖时间，零影响 | 需要自己处理 |
| ID 趋势递增 | 是 | 是（单 tag 内） | 是 |
| 集群扩展性 | 1024 节点 | 理论无限（增加 step） | 依赖 DB 机器 ID 分配 |
| 运维复杂度 | 低（手动配 workerId） | 中（维护 DB 高可用） | 高（Spring 依赖，DB 注册） |
| 典型问题 | 时钟回拨抛异常 | DB 单点故障 | 机器 ID 注册冲突 |
高性能设计：号段 vs 预生成 vs 本地生成
三种路线各有优劣，选型时看三个约束：
- 你能容忍的最大 ID 生成延迟：Leaf 有 DB 交互，极端情况 50ms+；Snowflake 纯本地，微秒级
- 你的集群规模：1024 节点以内 Snowflake 够用，超过就用 Leaf
- 你的时间同步精度：NTP 配置差（回拨 > 1s 常见）就别用 Snowflake
性能和安全性
ID 可逆性问题
Snowflake 和 Leaf 生成的 ID 是趋势递增的，爬虫可以通过递增 ID 遍历全量数据，这在现实场景中是真实攻击向量。
真实案例：某社交平台使用 Snowflake 作为帖子 ID，竞品通过自动化脚本按 ID 递增抓取全量内容，日抓取量 100 万+，持续 3 个月未被发现。事后溯源发现：ID 生成器没有混淆，递增规则太明显，连 offset 都不需要猜。
解法：Base62 编码 + XOR 混淆。
public long obfuscate(long rawId, long mask) {
// XOR 混淆：简单但有效
return rawId ^ mask;
}
public String encode(long id) {
// 混淆后转 Base62
return base62(obfuscate(id, MASK));
}混淆后 ID 看起来随机，但实际可逆——提供给前端的是编码后的字符串，后端解码后还原真实 ID。
混淆多段对比：
| 混淆方式 | 安全性 | 性能损耗 | 实现复杂度 |
|---|---|---|---|
| XOR mask | 低（知道 mask 即可还原） | 纳秒级 | 简单 |
| Base62 编码 | 中（编码后长度变化） | 微秒级 | 简单 |
| AES 加密 | 高 | 毫秒级 | 需要密钥管理 |
| Hash 不可逆 | 极高（但需要额外映射表查原始 ID） | 微秒级 | 需要额外存储 |
高可用设计
ID 生成器的高可用不是单机能搞定的：
- Leaf 的 DB 高可用：主从 + 分库，一个 DB 挂了不影响其他 tag。美团 Leaf 实际部署时每个 biz_tag 至少配 2 个 DB 源，故障时自动切换
- Snowflake 的机器 ID 分配：通过 ZK/Redis 动态分配机器 ID，避免手动配置。ZK 挂了不影响已有节点，但新节点加入会失败
- 多活部署：ID 生成器多节点部署，每个节点接不同的机器 ID 段。跨机房部署时注意：不同机房的 NTP 时间偏移可能不同
面试追问清单
这道题面试官喜欢连环追问，提前准备：
"Snowflake 的 41 位时间戳能用到哪一年？"
答：取决于起始时间 TWEPOCH。如果 TWEPOCH = 2021-01-01，41 位毫秒 ≈ 69 年，到 2090 年。如果现在部署，建议 TWEPOCH 设成当前时间附近，最大化可用年限。"Leaf 的 DB 挂了怎么办？"
答：如果号段缓存未耗尽，客户端仍能正常分配。如果缓存已耗尽，降级为等待或报错。美团的做法是：配置多 DB 源，主库挂了自动切换备库。"百亿级数据量，Leaf 的 step 设多大？"
答：QPS 越高，step 越大。美团 Leaf 的 order 业务 step 设置 10000，用户 ID 设置 5000。step 太大浪费号段（重启丢失多），太小导致频繁 DB 写入。经验值：按 QPS × 期望 DB 间隔秒数计算——比如 1000 QPS，希望 10 秒一次 DB 请求，step = 10000。"ID 生成器怎么做单元测试？"
答：Mock 时钟，手动回拨验证回拨策略；对 Leaf 用内嵌 H2 替代 MySQL；验证连续 10 万次 ID 不重复。
选型建议
大多数场景 Leaf 就够用了。如果公司内部有稳定的 ZK/etcd 集群，用 Leaf 的双 Buffer 模式，结合分库保证高可用。如果业务量级在亿级以下，Snowflake + 时钟回拨容忍策略（等待追回或备用机器 ID）也能满足需求。
如果做面试准备，把 Snowflake 的位运算推导、时钟回拨三种解法、Leaf 双 Buffer 时序流程讲清楚，基本能覆盖大多数面试官的追问范围。
参考：美团 Leaf 设计文档、百度 UidGenerator、Snowflake 原版论文