跳到主要内容

全局 ID 生成器设计

问题​

如何设计一个分布式全局唯一 ID 生成器？

答案​

方案对比​

方案原理有序性QPS缺点
UUID随机 128 位❌ 无序极高太长、无序不利于索引
数据库自增AUTO_INCREMENT✅低（千级）单点瓶颈
号段模式批量取 ID✅高重启浪费
雪花算法时间+机器+序列✅ 趋势递增百万级时钟回拨
Redis INCR原子自增✅万级依赖 Redis

雪花算法（Snowflake）​

 0 | 0000...0000 (41位时间戳) | 00000 (5位机房) | 00000 (5位机器) | 0000...0000 (12位序列号)
 1位符号  41位毫秒级时间戳           10位工作机器ID              12位序列号
雪花算法实现
public class SnowflakeIdGenerator {
    private final long epoch = 1640995200000L;  // 2022-01-01 起始时间
    private final long workerIdBits = 10L;
    private final long maxWorkerId = ~(-1L << workerIdBits);
    private final long sequenceBits = 12L;
    private final long sequenceMask = ~(-1L << sequenceBits);
    
    private final long workerId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;
    
    public SnowflakeIdGenerator(long workerId) {
        if (workerId > maxWorkerId || workerId < 0) throw new IllegalArgumentException();
        this.workerId = workerId;
    }
    
    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();
        
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("时钟回拨，拒绝生成 ID");
        }
        
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) timestamp = waitNextMillis(lastTimestamp);
        } else {
            sequence = 0L;
        }
        
        lastTimestamp = timestamp;
        return ((timestamp - epoch) << (workerIdBits + sequenceBits))
             | (workerId << sequenceBits)
             | sequence;
    }
    
    private long waitNextMillis(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) timestamp = System.currentTimeMillis();
        return timestamp;
    }
}

号段模式（美团 Leaf）​

号段模式核心逻辑
// 数据库表：id_alloc (biz_tag, max_id, step)
// 每次取一个号段：UPDATE id_alloc SET max_id = max_id + step WHERE biz_tag = ?

public class SegmentIdGenerator {
    private AtomicLong currentId;
    private volatile long maxId;
    
    // 当前号段用完时从数据库取新号段
    public long nextId() {
        long id = currentId.incrementAndGet();
        if (id >= maxId) {
            synchronized (this) {
                if (currentId.get() >= maxId) {
                    loadNextSegment();
                }
            }
            id = currentId.incrementAndGet();
        }
        return id;
    }
    
    // 双 Buffer：异步加载下一个号段，避免取号段时阻塞
    private void loadNextSegment() {
        // UPDATE id_alloc SET max_id = max_id + 1000 WHERE biz_tag = 'order'
        // 返回新的 max_id
        long newMax = idAllocMapper.updateAndGet("order", 1000);
        this.currentId = new AtomicLong(newMax - 1000);
        this.maxId = newMax;
    }
}

常见面试问题​

Q1: 雪花算法的时钟回拨问题怎么解决？​

答案：

  • 短暂回拨（< 5ms）：等待追上
  • 较大回拨：拒绝生成 + 告警
  • 美团 Leaf 方案：依赖 ZooKeeper 分配 workerId，检测到回拨时切换 workerId

Q2: 号段模式的双 Buffer 预加载是什么？​

答案：

维护两个号段 Buffer。当前号段使用到一定比例（如 10%）时，异步加载下一个号段到另一个 Buffer。切换时无需等待数据库查询。

Q3: 为什么 UUID 不适合做数据库主键？​

答案：

  • UUID 无序，插入 B+ 树叶子节点随机，导致页分裂，性能差
  • UUID 128 位太长，占用索引空间大
  • 趋势递增 ID（雪花算法/号段）插入有序，性能好

相关链接​