一致性哈希算法（Consistent Hashing）

1. 问题背景
在分布式系统中，数据通常需要分布到多个节点（如缓存服务器）上。传统方法是使用哈希函数（如`hash(key) % N``）将数据映射到N个节点之一。但这种方法在节点数量变化时（如节点加入或离开），大部分数据的映射关系会改变，导致大量数据需要重新分布，引发系统抖动。一致性哈希旨在解决这个问题。

2. 基本思想
一致性哈希将数据和节点都映射到一个固定的环形空间（通常是一个2^32的哈希环）。通过让每个节点负责环上的一段区间，使得当节点增减时，仅影响相邻区间的数据，从而最小化数据迁移量。

3. 算法步骤

• 步骤1：构建哈希环
  想象一个范围为[0, 2^32 - 1]的圆环，首尾相连。

• 步骤2：映射节点到环上
  对每个节点的唯一标识（如IP地址）计算哈希值，将其映射到环上的对应位置。例如，有三个节点A、B、C，其哈希值在环上的位置可能如下：

  环: 0 --- A(1000) --- B(3000) --- C(5000) --- 2^32-1
  

• 步骤3：映射数据到环上
  对每个数据的键（key）计算哈希值，同样映射到环上。例如，数据键K1的哈希值为2000。

• 步骤4：确定数据归属
  从数据在环上的位置出发，沿顺时针方向找到第一个节点，该节点即为数据所属节点。例如，K1(2000)顺时针找到的第一个节点是B(3000)，因此K1由节点B负责。

• 步骤5：处理节点变更

  • 添加节点：假设新增节点D，其哈希值为4000。此时，仅需将原本由C负责的、哈希值在(3000, 4000]区间内的数据重新分配给D，其他数据不受影响。
  • 移除节点：若节点B失效，原本由B负责的数据(1000, 3000]会顺时针交给下一个节点C负责，仅这部分数据需要重新分配。

4. 优化：虚拟节点
基本的一致性哈希可能存在节点分布不均的问题（数据倾斜）。为解决此问题，引入虚拟节点：

• 每个物理节点对应多个虚拟节点（如100~200个），虚拟节点的哈希值通过为物理节点标识添加后缀（如"A-1"、"A-2"）后计算得到。
• 数据先映射到虚拟节点，再通过虚拟节点与物理节点的对应关系找到最终归属。
• 优点：
  • 平衡负载：虚拟节点分散在环上，使数据分布更均匀。
  • 灵活调整：可通过调整虚拟节点数量来控制节点负载。

5. 总结

• 优点：节点变化时数据迁移量小，适合动态扩展的分布式系统。
• 缺点：基本实现可能数据倾斜，需通过虚拟节点优化。
• 应用：分布式缓存（如Redis Cluster）、负载均衡等。