短链系统发号器设计
2015年，某公司上线了一个短链系统。上线第一周，数据团队发现一个问题：每天生成的短链ID居然是"乱序"的。
第一天生成的短链 abc12345，第二天生成的短链 xyz98765——一个递增的短链系统，短码却是随机分布的。
问题出在发号器上：他们用了UUID作为短链ID，转成Base62后，自然就是乱序的。
后果很严重：所有短链都散落在数据库各处，索引效率极低，查询延迟从5ms飙升到50ms。
这是一个被很多人忽视的设计细节。
【架构权衡】
短链发号器的核心不是"生成ID"，而是生成什么样的ID。递增的ID有利于索引和分片，无规律的ID有利于安全。短链系统通常选择递增ID，因为存储和查询性能比安全性更重要——短链本身就是公开的，不需要防猜。
一、发号器的核心要求 🔴
1.1 四大要求
1. 唯一性：绝对不能重复
→ 重复会导致两条短链指向同一长链，数据冲突
2. 趋势递增：ID随时间增长而增长
→ 有利于数据库B+树索引，减少页分裂
→ 有利于分库分表的数据分布均匀
3. 高性能：每秒能生成足够多的ID
→ 日均1000万：需要115 QPS
→ 日均10亿：需要11500 QPS
→ 峰值通常是均值的5-10倍
4. 足够短：ID转成62进制后长度可控
→ 雪花ID（41位时间戳）：约69年不重复
→ 8位62进制 = 218万亿组合
1.2 为什么不用UUID
UUID的缺点：
1. 无序：UUID.randomUUID() 生成的ID是随机的
→ 写入数据库时随机IO，索引效率低
2. 太长：标准UUID是36个字符，转Base62后更麻烦
→ 不适合作为短链码
3. 可读性差：550e8400-e29b-41d4-a716-446655440000
→ 无法直观判断生成顺序
UUID的优点：
1. 不需要中心节点
2. 绝对不会重复
3. 几乎不可能被预测
适用场景：分布式系统内部ID，而非对外暴露的短链码
1.3 为什么不用数据库自增ID
数据库自增ID的缺点：
1. 性能不够：每秒最多2000-5000次INSERT（单表）
2. 单点故障：依赖单一数据库
3. 跨库麻烦：分库后无法保证全局唯一
适用场景：单库单表、对ID顺序无要求的场景
【面试官心理】
面试官问发号器，通常想看两件事：
- 你知不知道雪花算法的原理和组成
- 你有没有考虑过时钟回拨的问题
大多数候选人能说出"时间戳+机器ID+序列号"的结构，但被追问"时钟回拨了怎么办"时就开始露馅。这是P6和P7的分水岭。
二、雪花算法原理 🔴
2.1 雪花ID结构
64位雪花ID：
| 符号位(1bit) | 时间戳(41bit) | 机器ID(10bit) | 序列号(12bit) |
| 0 | 0000000000 | 0000000000 | 000000000000 |
各部分详解：
1. 符号位(1bit)：固定为0，保留
2. 时间戳(41bit)：从某个epoch（2016-01-01）开始的毫秒数
→ 41bit能表示的最大值：2^41 - 1 ≈ 2.2万亿
→ 时间范围：2.2万亿毫秒 ≈ 69年
3. 机器ID(10bit)：最多支持1024个节点
→ 二进制范围：0 ~ 1023
4. 序列号(12bit)：每毫秒内递增，最多4096个/毫秒
→ 二进制范围：0 ~ 4095
2.2 雪花ID计算
// 雪花ID生成公式
long id = (timestamp - EPOCH) << 22 // 时间戳左移22位
| (machineId << 12) // 机器ID左移12位
| sequence; // 序列号占低12位
// 示例：
// 时间戳 = 1734067200000，EPOCH = 1451606400000
// 差值 = 282240000000 毫秒
// 左移22位 = 282240000000 << 22 = ...
// 机器ID = 5
// 序列号 = 100
2.3 雪花算法实现
public class SnowflakeIdGenerator {
private static final long EPOCH = 1609459200000L; // 2021-01-01
private static final long MACHINE_BITS = 10L;
private static final long SEQUENCE_BITS = 12L;
private static final long MAX_MACHINE_ID = ~(-1L << MACHINE_BITS); // 1023
private static final long MAX_SEQUENCE = ~(-1L << SEQUENCE_BITS); // 4095
private final long machineId;
private long sequence = 0L;
private long lastTimestamp = -1L;
public SnowflakeIdGenerator(long machineId) {
if (machineId > MAX_MACHINE_ID || machineId < 0) {
throw new IllegalArgumentException("machineId必须在0-1023之间");
}
this.machineId = machineId;
}
public synchronized long nextId() {
long timestamp = timeGen();
// 时钟回拨：等待时钟追上
if (timestamp < lastTimestamp) {
timestamp = lastTimestamp;
}
// 新的一毫秒，序列号重置
if (timestamp == lastTimestamp) {
sequence = (sequence + 1) & MAX_SEQUENCE;
if (sequence == 0) {
// 序列号用完，等待下一毫秒
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0L;
}
lastTimestamp = timestamp;
return ((timestamp - EPOCH) << 22)
| (machineId << 12)
| sequence;
}
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
}
⚠️
这段代码有几个关键点容易出错：
sequence & MAX_SEQUENCE 是为了防止溢出，不是简单地 sequence++- 时钟回拨时选择
timestamp = lastTimestamp 而非抛出异常，是为了让服务继续可用
synchronized 保证单线程内ID递增，如果要高性能，需要用CAS或Disruptor
三、雪花算法的三大问题 🟡
3.1 时钟回拨问题
问题：机器时间回拨，导致生成重复ID
场景1：NTP服务器同步时间，回拨了100ms
场景2：虚拟机挂起，恢复后时间回退
场景3：手动修改系统时间
解决方案：
方案A（等）：等待时钟追上，回拨100ms就等100ms
→ 简单但不可接受，回拨大时服务不可用
方案B（记录）：记录上一次最大时间戳，回拨时用记录值
→ 折中，性能损失可接受
方案C（换机器）：时钟回拨时切换机器ID
→ 需要提前预留备用机器ID
3.2 机器ID分配问题
问题：10bit机器ID，最多1024个节点
但分布式系统可能有上万个服务实例
解决方案：
1. 配置中心统一分配：Zookeeper / etcd
2. 启动时自注册：写入MySQL/Redis获取唯一ID
3. 内网IP取模：机器IP % 1024（机器IP唯一）
3.3 序列号耗尽问题
问题：12bit序列号，每毫秒最多4096个
如果单机QPS超过409万怎么办？
解决方案：
1. 多机分担：10台机器，每台扛40万QPS
2. 时间戳用微秒：精度从ms提升到μs，序列号耗尽概率降低1000倍
3. 改用19位序列号：需要修改雪花ID结构
四、号段预分配方案 🟡
4.1 号段模式的原理
发号器模式：每次向中心节点申请一段ID，用完再申请
Leaf模式 / 淘宝TDDL IDGenerator
架构：
应用服务器 发号器服务
| |
| → selectMaxId from DB 获取 |
| ← 返回 [1000001, 2000000] |
| |
| → 本地 AtomicLong += 1 |
| → (用完1百万个后) 再次申请 |
优点：
1. 应用层无锁，本地生成QPS无限制
2. 发号器服务可以集群部署
3. 可以批量申请，减少数据库压力
缺点：
1. ID不严格连续（段内连续，但段间可能有间隙）
2. 服务重启会浪费一段ID
4.2 号段服务实现
// 发号器服务 - 数据库表设计
// CREATE TABLE sequence (
// biz_tag VARCHAR(64) PRIMARY KEY, -- 业务标识，如 "short_url"
// max_id BIGINT NOT NULL, -- 当前最大ID
// step INT NOT NULL -- 步长，默认10000
// );
public class SegmentIdService {
private static final int STEP = 10000;
private final AtomicLong current = new AtomicLong(0);
private final AtomicLong next = new AtomicLong(0);
public long getNextId() {
if (current.get() >= next.get()) {
refresh();
}
return current.incrementAndGet();
}
private void refresh() {
// 从数据库获取下一个号段
long newMax = dbService.getNextSegment("short_url", STEP);
next.set(newMax);
current.set(newMax - STEP);
}
}
4.3 号段 vs 雪花：选哪个？
【架构权衡】
短链系统推荐用号段模式，原因：
- ID可预测性：短链本身就是公开链接，递增ID不会泄露更多信息，但可能被爬虫按顺序爬取。号段模式的间隙让爬虫更难批量爬取
- 性能更高：本地自增，没有时钟回拨风险
- 更适合多机房：各机房独立发号，不需要时钟同步
五、62进制转换优化 🟡
5.1 标准转换
public static String toBase62(long id) {
String chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
StringBuilder sb = new StringBuilder();
while (id > 0) {
int remainder = (int) (id % 62);
sb.append(chars.charAt(remainder));
id = id / 62;
}
return sb.reverse().toString();
}
// 雪花ID转8位短码
public static String snowflakeToShortCode(long snowflakeId) {
// 雪花ID去掉高位时间戳，取低41位
long id = snowflakeId & ((1L << 41) - 1);
return leftPad(toBase62(id), 8, '0');
}
5.2 优化：查表法
// 预计算62^2的所有组合，减少除法运算
private static final String[] BASE62_TABLE = new String[62 * 62];
static {
String chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
for (int i = 0; i < 62; i++) {
for (int j = 0; j < 62; j++) {
BASE62_TABLE[i * 62 + j] = String.valueOf(chars.charAt(i)) + chars.charAt(j);
}
}
}
public static String toBase62Fast(long id) {
StringBuilder sb = new StringBuilder();
while (id > 0) {
int remainder = (int) (id % 62);
sb.append(CHARS.charAt(remainder));
id = id / 62;
}
return sb.reverse().toString();
}
5.3 短码长度控制
雪花ID转Base62后的长度分布：
假设机器ID=5，序列号=100
雪花ID = (当前时间差 << 22) | (5 << 12) | 100
当前时间差约：280000000000 ms（从2016-01-01到2024-01-01）
转62进制：
62^6 = 56.8万亿
62^7 = 3.52千万亿
62^8 = 218万亿
雪花ID ≈ 10^12 量级 → 需要10位62进制
雪花ID低位部分 ≈ 10^8 量级 → 需要6位62进制
结论：用雪花ID的低48位（约2.8万亿）转62进制 = 8位
六、生产避坑 🟡
6.1 发号器的四大坑
坑1：时钟回拨导致ID重复
问题：NTP同步时间后，发号器开始生成重复ID
场景：系统运行1年后，NTP服务器把时间同步到出厂设置
影响：短链重复，数据覆盖
解决方案：
- 方案A：机器ID预留高位，遇到时钟回拨切换机器ID
- 方案B：时钟回拨时抛出异常，服务降级
- 方案C：用号段模式，彻底避免时钟依赖
坑2：号段耗尽时阻塞
问题：本地号段用完后，等待数据库返回新号段时服务暂停
场景：数据库主从切换，响应时间从1ms变成100ms
影响：批量请求等待，P99延迟飙升
解决方案：
- 提前刷新：当剩余号段 < 10%时，异步刷新
- 多级号段：本地+远程，本地用完前刷新远程
- 熔断降级：如果刷新失败，用雪花模式兜底
坑3：机器ID冲突
问题：多台机器被分配了相同的机器ID
场景：配置中心故障，机器重启后获取到重复ID
影响：两台机器生成相同的短链
解决方案：
- 机器ID = 内网IP的CRC32 % 1024（IP唯一性保证ID唯一）
- 或：机器ID写入本地文件，启动时检查
坑4：短码长度不可控
问题：雪花ID转Base62后，长度在6-10位之间波动
场景：用户看到有的短链6位，有的10位，体验不一致
影响：短链长度不一致，无法统一处理
解决方案：
- 统一补零到固定长度（如8位）
- 或：用号段模式，号段内ID递增，转Base62后长度固定
6.2 监控指标
七、真实面试回放 🟡
面试官：你的短链系统用雪花算法生成ID，但雪花算法有时钟回拨问题，怎么处理？
候选人（大张）：时钟回拨有两种场景：
一是NTP小幅度回拨（几毫秒到几秒），我选择等待。代码里 timestamp = lastTimestamp，等待时钟追上来再生成。最多等待几秒，不影响服务可用性。
二是NTP大幅度回拨（几分钟到几年），这是异常情况。我的处理是：抛异常 + 告警 + 服务降级为读数据库。同时准备备用机器ID，回拨时切换到备用ID。
面试官：如果等待时间太长怎么办？
大张：可以优化为"快等待+慢降级"：
- 回拨 < 100ms：同步等待
- 回拨 100ms-1s：异步等待 + 返回错误（降级）
- 回拨 > 1s：直接抛异常，切备用机器ID
面试官：为什么不用号段模式彻底避免时钟问题？
大张：号段模式确实更优雅，但我们评估后选择雪花是因为：
- 短链不需要防预测（链接本身就是公开的）
- 雪花ID可以反解出生成时间（方便排查问题）
- 不需要额外的数据库表和运维
号段模式更适合订单号这类需要防预测的场景。
面试官：雪花ID转Base62，怎么保证长度一致？
大张：我的做法是取雪花ID的低48位，这部分最大值约280万亿，转Base62后是8位。我统一补零到8位，不够的在前面加0。
如果8位不够（如业务增长超过预期），可以扩展到12位或16位，但这需要修改前端URL解析规则。
【面试官手记】
大张的回答展示了几个亮点：
- 时钟回拨分层处理：不是简单的"等待"或"抛异常"，而是分级别处理
- 知道什么时候用雪花、什么时候用号段：不是无脑推荐某种方案，而是分析trade-off
- 反问面试官"为什么不用号段"：说明他对两种方案都有深入理解
这场面试属于P7级别，亮点是"方案对比"和"trade-off分析"。雪花 vs 号段的讨论，是系统设计中经典的"正确性 vs 性能"矛盾的缩影。
发号器设计是短链系统中最体现功力的环节。记住三个关键点：
- 雪花 vs 号段：短链用雪花（简单），订单用号段（安全）
- 时钟回拨：分层处理，不要一刀切
- 长度控制：统一补零，保证用户体验
当你能在面试中讲清楚"为什么选这个方案而不是那个方案"，P7的offer就近在眼前了。
