设计分布式 ID 生成器
问题
如何在分布式系统中生成全局唯一、有序的 ID？
答案
一、为什么需要分布式 ID
单库时可以用数据库自增 ID。但在分库分表、微服务场景下：
- 多个库的自增 ID 会重复
- 需要在插入前就获得 ID（异步消息、前端预览等）
- 自增 ID 暴露业务量（如订单量），有安全隐患
二、方案对比
| 方案 | 有序性 | 性能 | 依赖 | 长度 |
|---|---|---|---|---|
| UUID | ❌ 无序 | ⭐⭐⭐⭐⭐ | 无 | 36 字符 |
| 雪花算法 | ✅ 趋势递增 | ⭐⭐⭐⭐⭐ | 时钟 | 64 bit |
| 号段模式 | ✅ 递增 | ⭐⭐⭐⭐ | 数据库 | 可变 |
| Redis INCR | ✅ 递增 | ⭐⭐⭐⭐ | Redis | 可变 |
| 数据库自增 | ✅ 递增 | ⭐⭐ | 数据库 | 可变 |
三、UUID
import { randomUUID } from 'crypto';
const id = randomUUID();
// 'f47ac10b-58cc-4372-a567-0d02b2c3d479'
优点：无依赖、高性能、全球唯一。
缺点：
- 36 字符太长，索引效率低
- 无序：B+ 树索引频繁分裂，写入性能差
- 不可读，无法排序
UUID v7（推荐）
UUID v7 在前 48 bit 嵌入时间戳，保持趋势递增，解决了 B+ 树分裂问题：
// uuid v7（需要 uuid 库 v9+）
import { v7 as uuidv7 } from 'uuid';
const id = uuidv7();
// '018f3e4a-1b2c-7d4e-8a9b-1c2d3e4f5a6b'
// ^^^^^^^^ 时间戳部分，保证递增
四、雪花算法（Snowflake）
Twitter 提出的 64 bit ID 生成算法：
┌─ 1 bit ─┬──────── 41 bit ─────────┬── 10 bit ──┬── 12 bit ──┐
│ 符号位 0 │ 时间戳（毫秒级） │ 机器 ID │ 序列号 │
└──────────┴─────────────────────────┴────────────┴────────────┘
时间戳：41 bit 可用 69 年
机器 ID：10 bit 支持 1024 个节点（5 bit 数据中心 + 5 bit 机器）
序列号：12 bit 每毫秒 4096 个 ID
理论上限：409.6 万 ID/秒
class Snowflake {
private sequence = 0n;
private lastTimestamp = -1n;
// 起始时间（2024-01-01）
private readonly EPOCH = 1704067200000n;
private readonly MACHINE_ID_BITS = 10n;
private readonly SEQUENCE_BITS = 12n;
private readonly machineId: bigint;
private readonly maxSequence = (1n << this.SEQUENCE_BITS) - 1n;
constructor(machineId: number) {
this.machineId = BigInt(machineId);
}
nextId(): bigint {
let timestamp = BigInt(Date.now());
if (timestamp === this.lastTimestamp) {
// 同毫秒，序列号递增
this.sequence = (this.sequence + 1n) & this.maxSequence;
if (this.sequence === 0n) {
// 序列号溢出，等待下一毫秒
timestamp = this.waitNextMillis(this.lastTimestamp);
}
} else {
this.sequence = 0n;
}
this.lastTimestamp = timestamp;
return (
((timestamp - this.EPOCH) << (this.MACHINE_ID_BITS + this.SEQUENCE_BITS)) |
(this.machineId << this.SEQUENCE_BITS) |
this.sequence
);
}
private waitNextMillis(last: bigint): bigint {
let ts = BigInt(Date.now());
while (ts <= last) {
ts = BigInt(Date.now());
}
return ts;
}
}
const snowflake = new Snowflake(1);
const id = snowflake.nextId();
// 例如：7169537123456789012n
时钟回拨问题
服务器时钟回拨会导致 ID 重复。解决方案：
- 拒绝生成：检测到回拨直接抛异常
- 等待追上：回拨小于阈值（如 5ms）则等待
- 预留位：用 2~3 bit 做时钟序列号，回拨时递增
五、号段模式
-- 号段分配表
CREATE TABLE id_generator (
biz_tag VARCHAR(64) PRIMARY KEY, -- 业务标识
max_id BIGINT NOT NULL, -- 当前已分配的最大 ID
step INT NOT NULL DEFAULT 1000, -- 每次获取的号段长度
updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);
-- 初始化
INSERT INTO id_generator (biz_tag, max_id, step) VALUES ('order', 0, 1000);
-- 获取号段（原子操作）
UPDATE id_generator SET max_id = max_id + step WHERE biz_tag = 'order';
-- 返回 [old_max_id + 1, old_max_id + step]
class SegmentIdGenerator {
private currentId: number;
private maxId: number;
async nextId(bizTag: string): Promise<number> {
if (this.currentId >= this.maxId) {
await this.loadSegment(bizTag); // 号段用完，重新申请
}
return ++this.currentId;
}
private async loadSegment(bizTag: string) {
// 双 Buffer：提前加载下一号段，避免阻塞
const result = await db.execute(
'UPDATE id_generator SET max_id = max_id + step WHERE biz_tag = ? RETURNING max_id, step',
[bizTag]
);
this.currentId = result.max_id - result.step;
this.maxId = result.max_id;
}
}
美团 Leaf：号段模式 + 双 Buffer 预加载 + 雪花算法模式可选。
常见面试问题
Q1: 雪花算法和号段模式如何选择？
答案：
| 维度 | 雪花算法 | 号段模式 |
|---|---|---|
| 依赖 | 无外部依赖 | 依赖数据库 |
| 有序性 | 趋势递增 | 严格递增 |
| 性能 | 极高（本地生成） | 高（批量获取） |
| 可读性 | 64 bit 长数字 | 短序列号 |
| 风险 | 时钟回拨 | 数据库单点 |
- 对有序性要求不严格 → 雪花算法
- 需要短 ID、严格递增 → 号段模式
Q2: 为什么无序 UUID 不适合做 MySQL 主键？
答案：
MySQL InnoDB 使用 B+ 树组织聚簇索引（主键索引）。无序 UUID 导致：
- 页分裂：新记录随机插入，导致 B+ 树频繁分裂
- 碎片化：页利用率低（通常只有 50%~70%）
- 写入慢：随机 IO 远慢于顺序 IO
有序 ID（自增、雪花、UUID v7）总是追加到 B+ 树尾部，避免分裂。
Q3: 如何保证分布式 ID 不重复？
答案：
- UUID：128 bit 随机数，碰撞概率极低（可忽略）
- 雪花算法：
时间戳 + 机器 ID + 序列号，同一毫秒同一机器通过序列号区分 - 号段模式：数据库 UPDATE 的原子性保证不同节点拿到不同号段