数据库水平分库分表下的全局唯一ID生成方案

题目描述
在数据库水平分库分表的架构中，传统的自增主键（如MySQL的AUTO_INCREMENT）会因分散在不同物理节点而产生重复ID，破坏全局唯一性。请设计一种既能保证全局唯一、又兼顾性能、有序性和可扩展性的ID生成方案，并解释其原理与实现细节。

解题过程

1. 问题分析

• 自增主键的局限性：单机数据库的自增主键依赖集中式计数器，分库分表后各节点独立计数，导致ID重复。
• 核心需求：
  • 全局唯一：整个分布式系统中无重复ID。
  • 高性能：低延迟、高吞吐，避免成为系统瓶颈。
  • 趋势有序：ID尽量递增，利于数据库索引优化（如B+树顺序插入）。
  • 可扩展性：支持水平扩容。

2. 常见方案对比

3. Snowflake算法详解

• ID结构（64位二进制）：

  0 | 0000000000 0000000000 0000000000 0000000000 0 | 0000000000 | 000000000000  
  └─────────────┬─────────────┘ └─────┬──────┘ └──────┬─────┘  
      41位时间戳（毫秒）       10位机器ID     12位序列号  
  

  • 时间戳：当前时间减去起始时间（如2020-01-01），可用约69年。
  • 机器ID：通过配置或服务发现分配，支持1024个节点。
  • 序列号：同一毫秒内的自增序号，支持每节点每毫秒生成4096个ID。

• 有序性原理：
  时间戳在高位，确保ID随时间递增。同一毫秒内靠序列号保证顺序。

• 时钟回拨处理：

  • 轻微回拨（如≤100ms）：等待时钟追平。
  • 严重回拨：报警并拒绝生成ID，或切换备用节点。

4. 优化变体方案

• Leaf-Segment（数据库号段优化）：
  • 每次从数据库获取一个号段（如1~1000），加载到内存中分配。
  • 通过双Buffer异步预取下一个号段，避免分配阻塞。
• Leaf-Snowflake：
  • 引入ZooKeeper协调机器ID分配，解决时钟回拨时切换机器ID。

5. 实现示例（Snowflake的Java伪代码）

public class SnowflakeIdGenerator {  
    private final long startTime = 1609459200000L; // 2020-01-01  
    private final int machineIdBits = 10;  
    private final int sequenceBits = 12;  
    private final long maxMachineId = (1L << machineIdBits) - 1;  
    private final long maxSequence = (1L << sequenceBits) - 1;  
    private final long machineId;  
    private long lastTimestamp = -1L;  
    private long sequence = 0L;  

    public synchronized long nextId() {  
        long currentTime = System.currentTimeMillis();  
        if (currentTime < lastTimestamp) {  
            throw new RuntimeException("时钟回拨！");  
        }  
        if (currentTime == lastTimestamp) {  
            sequence = (sequence + 1) & maxSequence;  
            if (sequence == 0) {  
                // 当前毫秒序号用完，等待下一毫秒  
                currentTime = waitNextMillis(currentTime);  
            }  
        } else {  
            sequence = 0L;  
        }  
        lastTimestamp = currentTime;  
        return ((currentTime - startTime) << (machineIdBits + sequenceBits))  
                | (machineId << sequenceBits)  
                | sequence;  
    }  
}  

6. 总结

• 小规模系统：优先考虑数据库号段模式，简单可靠。
• 大规模高并发：Snowflake及其变体更合适，需解决时钟同步问题。
• 混合方案：如结合号段模式的分段批量申请与Snowflake的去中心化特性（如美团Leaf）。