全局唯一 ID 生成与雪花算法
分布式环境的 ID 需求
分库分表后，数据库自增主键不再可用——两个分片从 1 开始自增，会导致不同分片出现相同 ID。分布式系统需要一个全局唯一的 ID 生成方案。
全局 ID 的要求
- 全局唯一：绝对不能重复
- 趋势递增：便于数据库 B+Tree 索引维护，减少页分裂
- 高性能：生成速度快（微秒级），不能成为系统瓶颈
- 高可用：服务不能单点，出故障时仍能正常生成
- 有序性：排序、分页等操作依赖 ID 的有序性
常见方案对比
| 方案 | 特点 | 问题 |
|---|---|---|
| UUID | 简单，全球唯一 | 不递增，太长（36 字符），碎片化严重 |
| 数据库自增 | 有 ID 表或号段模式 | 性能一般，依赖于 DB |
| Redis 自增 | INCR 命令，高性能 | 需要维护 Redis 集群 |
| 雪花算法 | 趋势递增，高性能 | 依赖时钟（NTP 对时问题） |
雪花算法（Snowflake）
算法原理
Twitter 开源的分布式 ID 生成算法，结果是 64 位 long 整数。
bit 位结构（共 64 位）：
0 | 0000000000 0000000000 0000000000 0000000000 00 | 00000 | 00000 | 000000000000
各段含义：
第 1 位：符号位（始终为 0，保证 ID 为正数）
41 位：时间戳（毫秒级，可用 69 年）
10 位：工作机器 ID（最多 1024 台机器）
12 位：序列号（每毫秒可生成 4096 个 ID）
细分：
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
符号 时间戳（毫秒，相对于2020-01-01） 数据中心ID 机器ID 序列号
ID 生成示例
// 简化版雪花算法实现
public class SnowflakeIdWorker {
// 开始时间戳（2020-01-01）
private final long twepoch = 1577836800000L;
// 机器 ID 所占位数
private final long workerIdBits = 10L;
// 序列号所占位数
private final long sequenceBits = 12L;
// 最大值
private final long maxWorkerId = ~(-1L << workerIdBits); // 1023
private final long sequenceMask = ~(-1L << sequenceBits); // 4095
// 偏移量
private final long workerIdShift = sequenceBits;
private final long timestampLeftShift = sequenceBits + workerIdBits;
private long workerId;
private long sequence = 0L;
private long lastTimestamp = -1L;
public synchronized long nextId() {
long timestamp = timeGen();
// 时钟回拨处理
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing for %d ms",
lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
// 同一毫秒内，序列号递增
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) { // 当前毫秒用完 4096 个 ID
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0L; // 新毫秒，序列号重置
}
lastTimestamp = timestamp;
// 组合为 64 位 ID
return ((timestamp - twepoch) << timestampLeftShift)
| (workerId << workerIdShift)
| sequence;
}
}
雪花算法的优势
- 趋势递增：按时间顺序生成的 ID 在 B+Tree 中相邻插入，减少页分裂
- 高性能：纯内存计算，每毫秒单机支持 409.6 万个 ID
- 简单可靠：不需要网络通信，本地生成
- 反解信息：可以从 ID 中解析出生成时间和机器 ID
雪花算法的问题
1. 时钟回拨
这是最严重的问题。如果系统时间回拨（NTP 调整或人为修改），可能生成重复 ID：
// 处理方式
if (timestamp < lastTimestamp) {
// 方案一：直接抛出异常（使用中不推荐）
// 方案二：等待时间追上来
// 方案三：记录回拨，用备用序列号生成
waitUntil(lastTimestamp); // 等待到上次时间
}
2. 工作节点 ID 管理
每台机器的 workerId 需要手动或通过协调服务分配（如 ZooKeeper）。
改进版：百度的 UidGenerator 和美团的 Leaf
美团 Leaf
基于雪花算法 + 号段模式，解决了时钟回拨问题：
Leaf-segment：使用数据库号段模式，从 DB 中取号段
Leaf-snowflake：雪花算法的改进，用 ZooKeeper 管理 workerId
时钟回拨时等待，超过阈值则告警但不阻塞
// Leaf 处理时钟回拨：
// 10ms 以内：等待
// 10ms 以上：告警并上报
// 等待过程中不生成 ID
百度 UidGenerator
通过自定义时间戳起始值和 workerId 分配策略，支持更灵活的配置。
字节跳动 Leaf (Tinyid)
中心化的 ID 生成服务，客户端批量取号段。
面试要点
- 雪花算法是分布式 ID 的首选方案（性能好、趋势递增）
- 核心缺陷是时钟回拨——需要理解原因和常见处理策略
- 机械硬盘时代 UUID 是灾难（随机写入），SSD 时代有所缓解但仍不推荐
- 面试中能画出雪花算法的 64 位结构图
- 了解主流改进版（Leaf、UidGenerator）的核心设计思路
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
暂无评论内容