哈希算法题目：设计一个基于哈希的分布式唯一ID生成器（雪花算法变种）

题目描述
设计一个分布式唯一ID生成器，要求生成的ID全局唯一、趋势递增（便于数据库索引），且能支持高并发场景。系统需要部署在多个节点上，每个节点独立生成ID而不需要中心协调。你需要结合哈希算法解决节点标识分配问题。

解题过程

1. 核心需求分析

   • 全局唯一性：不同节点在同一时间生成的ID不能重复。
   • 趋势递增：ID的时间部分有序，避免数据库索引频繁分裂。
   • 高可用：节点无需通信，避免单点故障。

2. 雪花算法基础结构
   雪花算法（Snowflake）的ID结构通常包含：

   • 时间戳（41位）：毫秒级时间，支持约69年。
   • 节点ID（10位）：区分不同节点。
   • 序列号（12位）：同一毫秒内的自增序号，支持每节点每毫秒4096个ID。
     但传统雪花算法需要预先分配节点ID，而分布式环境下节点动态增减，需解决节点ID分配冲突。

3. 用哈希算法动态分配节点ID

   • 问题：直接配置节点ID可能导致冲突（如配置错误或节点扩容）。
   • 解决方案：
     1. 对节点唯一标识（如MAC地址、IP地址、随机种子）计算哈希值（如SHA-256）。
     2. 取哈希值的低10位（或所需位数）作为节点ID。
     3. 若哈希冲突（小概率），通过重试或扩展位数解决。

4. 详细步骤
   步骤1：生成节点标识

   • 每个节点启动时，读取本地唯一标识（例如IP地址的哈希值）：

     import hashlib  
     node_identifier = "192.168.1.10"  # 示例IP  
     hash_value = hashlib.sha256(node_identifier.encode()).hexdigest()  
     node_id = int(hash_value, 16) % 1024  # 取低10位（0-1023）  
     

   步骤2：时间戳处理

   • 定义起始时间戳（如2020-01-01），当前时间与起始时间的差值作为ID的时间部分：

     start_timestamp = 1577836800000  # 2020-01-01的毫秒数  
     current_timestamp = int(time.time() * 1000)  
     timestamp_part = current_timestamp - start_timestamp  
     

   步骤3：序列号管理

   • 同一毫秒内，序列号从0递增，到4095后等待下一毫秒。
   • 如果时间回拨（服务器时钟异常），通过等待或异常处理解决。

   步骤4：组合ID

   • 将三部分按位组合（时间戳左移22位，节点ID左移12位）：

     unique_id = (timestamp_part << 22) | (node_id << 12) | sequence_number  
     

5. 冲突处理与优化

   • 哈希冲突：若两个节点哈希到相同节点ID，引入重试机制（如叠加随机数重新哈希）。
   • 扩展性：若节点数超过1024，可增加节点ID位数或使用一致性哈希分配ID范围。

6. 总结
   通过哈希算法动态分配节点ID，避免了中心化协调的复杂性，同时保证了分布式环境下ID生成的唯一性和效率。此方法结合了雪花算法的有序性和哈希的分布特性，适合云原生架构。