哈希算法题目：设计一个基于哈希的分布式唯一ID生成器（支持趋势递增和分片标识）

题目描述
设计一个分布式唯一ID生成系统，要求生成的ID具备以下特性：

1. 全局唯一：在分布式环境下生成的ID不能重复。
2. 趋势递增：ID整体上随时间递增，便于数据库索引优化。
3. 支持分片标识：ID中需包含分片信息（如机器ID、业务标识），用于数据分片路由。
4. 高可用：避免单点故障，能应对时钟回拨等异常情况。

解题过程

步骤1：分析需求与约束

• 唯一性：通过结合时间戳、机器ID、序列号等字段保证唯一。
• 趋势递增：将时间戳作为ID的高位部分，确保时间有序。
• 分片标识：预留部分比特位存储机器ID或业务分片号。
• 时钟回拨处理：当服务器时钟异常回退时，需有容错机制（如等待或报警）。

步骤2：设计ID结构（基于Snowflake变种）

采用64位整数（如Long类型）存储ID，按比特位划分字段：

| 符号位(1bit) | 时间戳(41bit) | 分片ID(10bit) | 序列号(12bit) |

• 符号位：固定为0，保证ID为正数。
• 时间戳：当前时间与起始时间（如2020-01-01）的差值（单位毫秒），41位可用约69年。
• 分片ID：自定义的机器ID或业务分片标识（如10位支持1024个分片）。
• 序列号：同一毫秒内的自增序号（12位支持每毫秒4096个ID）。

步骤3：解决时钟回拨问题

• 问题：服务器时钟回退可能导致ID重复。
• 方案：
  1. 记录最后生成时间戳：每次生成ID时对比当前时间与最后时间戳。
  2. 时钟回拨检测：若当前时间小于最后时间戳，说明发生回拨。
  3. 容错策略：
     • 轻微回拨（如≤100ms）：等待时钟追平后再生成。
     • 严重回拨：报警并拒绝生成ID，或切换到备用时间源。

步骤4：分布式环境下的分片ID分配

• 静态配置：为每台机器预分配唯一分片ID（需维护映射表）。
• 动态分配：通过集中式服务（如ZooKeeper）或数据库分配分片ID，避免手动配置的繁琐。
• 哈希分片：对业务标识（如用户ID）哈希取模，映射到分片ID字段。

步骤5：序列号管理

• 同一毫秒内：序列号从0自增，达到最大值（4095）后等待下一毫秒重置。
• 并发控制：使用原子操作（如AtomicLong）或锁保证序列号线程安全。

步骤6：高可用设计

• 多实例部署：每个分片ID对应一个ID生成器实例，避免单点故障。
• 时钟同步：使用NTP协议同步集群机器时钟，减少时钟偏差。
• 降级策略：当时钟回拨无法快速恢复时，可暂时牺牲趋势递增性，依赖分片ID和序列号保证唯一性。

步骤7：示例代码（简化版）

public class DistributedIdGenerator {
    private final long startTime = 1577808000000L; // 2020-01-01 00:00:00
    private final long shardIdBits = 10L;
    private final long sequenceBits = 12L;
    private final long maxShardId = (1L << shardIdBits) - 1;
    private final long maxSequence = (1L << sequenceBits) - 1;

    private long lastTimestamp = -1L;
    private long sequence = 0L;
    private final long shardId;

    public DistributedIdGenerator(long shardId) {
        if (shardId < 0 || shardId > maxShardId) {
            throw new IllegalArgumentException("分片ID超出范围");
        }
        this.shardId = shardId;
    }

    public synchronized long nextId() {
        long currentTime = System.currentTimeMillis();
        if (currentTime < lastTimestamp) {
            throw new RuntimeException("时钟回拨，拒绝生成ID");
        }

        if (currentTime == lastTimestamp) {
            sequence = (sequence + 1) & maxSequence;
            if (sequence == 0) {
                // 当前毫秒序号用完，等待下一毫秒
                currentTime = waitNextMillis(currentTime);
            }
        } else {
            sequence = 0; // 新毫秒重置序列号
        }

        lastTimestamp = currentTime;
        return ((currentTime - startTime) << (shardIdBits + sequenceBits))
                | (shardId << sequenceBits)
                | sequence;
    }

    private long waitNextMillis(long currentTime) {
        while (currentTime <= lastTimestamp) {
            currentTime = System.currentTimeMillis();
        }
        return currentTime;
    }
}

步骤8：测试与优化

• 唯一性测试：多线程并发生成大量ID，验证是否重复。
• 时钟回拨模拟：手动调整系统时间，观察容错逻辑是否触发。
• 性能优化：减少锁粒度（如使用ThreadLocal存储序列号），提升QPS。

通过以上步骤，即可实现一个支持趋势递增和分片标识的分布式唯一ID生成器。