一致性哈希算法在分布式系统中的应用

题目描述：设计一个一致性哈希算法来解决分布式缓存系统中的数据分布和节点动态增减问题。当缓存节点增加或减少时，需要最小化数据迁移量，保持系统的可扩展性和高可用性。

解题过程：

1. 问题分析

   • 传统哈希采用hash(key)%N的方式分布数据，但当节点数N变化时，大部分数据需要重新分布
   • 一致性哈希将哈希空间组织成虚拟环，同时使用虚拟节点解决数据倾斜问题

2. 基本概念

   • 哈希环：将0～2^32-1的哈希值首尾相连形成环状结构
   • 虚拟节点：每个物理节点对应多个虚拟节点，均匀分布在环上
   • 数据定位：数据key的哈希值在环上顺时针找到的第一个虚拟节点

3. 算法设计

   import hashlib
   
   class ConsistentHash:
       def __init__(self, virtual_nodes=100):
           self.virtual_nodes = virtual_nodes
           self.ring = {}  # 哈希环：{hash值: 物理节点}
           self.sorted_hashes = []  # 排序的哈希值列表
   
       def _hash(self, key):
           return int(hashlib.md5(key.encode()).hexdigest(), 16) % (2**32)
   
       def add_node(self, node):
           # 为每个物理节点创建虚拟节点
           for i in range(self.virtual_nodes):
               virtual_key = f"{node}#{i}"
               hash_val = self._hash(virtual_key)
               self.ring[hash_val] = node
   
           # 重新排序哈希环
           self.sorted_hashes = sorted(self.ring.keys())
   
       def remove_node(self, node):
           # 移除节点的所有虚拟节点
           to_remove = []
           for hash_val, n in self.ring.items():
               if n == node:
                   to_remove.append(hash_val)
   
           for hash_val in to_remove:
               del self.ring[hash_val]
   
           self.sorted_hashes = sorted(self.ring.keys())
   
       def get_node(self, key):
           if not self.ring:
               return None
   
           hash_val = self._hash(key)
   
           # 二分查找找到第一个大于等于该哈希值的节点
           import bisect
           idx = bisect.bisect_left(self.sorted_hashes, hash_val)
   
           # 如果到了环的末尾，回到环的开头
           if idx == len(self.sorted_hashes):
               idx = 0
   
           return self.ring[self.sorted_hashes[idx]]
   

4. 关键优化

   • 虚拟节点数量：通常100-200个，平衡均匀性和性能
   • 数据迁移：节点变化时只影响相邻区域的数据
   • 容错性：节点故障时数据自动迁移到下一节点

5. 实际应用

   • 分布式缓存系统（如Redis Cluster）
   • 负载均衡器
   • 分布式数据库分片

这种设计确保了在节点动态变化时，只有少量数据需要重新分布，大大提高了系统的可扩展性和稳定性。