1. 什么是一致性哈希？

一致性哈希是一种特殊的哈希算法，主要用于分布式系统中，用于将数据分配到多个节点上，保证数据在节点变动时能够尽可能少地重新分配，提高系统的稳定性和扩展性。

它的核心思想是通过将数据和节点映射到一个虚拟的环形空间（哈希环）中，根据数据的位置决定存储在哪个节点上。当节点发生增删时，尽量减少数据的迁移量。

2. 背景与问题

在分布式系统中，数据存储在多个服务器（节点）上，为了实现负载均衡，我们通常需要通过哈希算法将数据映射到不同的节点。例如：

传统的哈希分布：

假设有 4 个服务器节点（A, B, C, D），我们用简单的哈希算法将数据分配到这些节点上：

hash(data) % N

• N 是节点数，hash(data) 是数据的哈希值。
• 比如：hash("data1") % 4 = 2，data1 被分配到节点 C。

问题：当节点变动时

• 如果增加一个新节点（如 E，节点数变为 5），所有的数据都需要重新分配：

  hash(data) % 5
  

• 这会导致几乎所有数据重新分布，迁移代价非常高。

3. 一致性哈希的核心思想

一致性哈希通过一个环形空间解决了传统哈希算法的上述问题。

3.1 哈希环

• 一致性哈希将整个哈希值范围（如 0 ~ 2^32-1）组织成一个环形结构。
• 节点（服务器）和数据都通过哈希算法映射到这个环上。
  • 节点的哈希：hash(node)
  • 数据的哈希：hash(data)

3.2 数据存储规则

• 一个数据被存储到环上顺时针方向第一个节点（或称“后继节点”）上。

• 比如，节点 A、B、C、D 在环上，数据 data1 映射到节点之间的位置，则：

  hash(data1) → 找到顺时针方向最近的节点
  

  如果 hash(data1) 位于节点 A 和节点 B 之间，则数据 data1 存储到节点 B。

3.3 动态增减节点

• 当有新节点加入或离开时，只需要迁移受影响范围内的少量数据。
• 例如：
  • 如果节点 E 加入环，它负责环上从前继节点（如 D）到自身之间的数据。
  • 其他节点的数据分布不会受到影响。

4. 虚拟节点

在实际应用中，由于节点的分布可能不均匀，容易导致数据倾斜问题（部分节点存储的数据量过大）。为了解决这个问题，引入了虚拟节点的概念。

4.1 什么是虚拟节点？

• 将一个物理节点映射到环上多个位置，即一个节点有多个哈希值。
• 每个虚拟节点相当于一个逻辑节点。

4.2 数据分配规则

• 数据仍然存储到虚拟节点上，但虚拟节点最终映射到对应的物理节点。

4.3 优势

• 平衡数据分布：通过增加虚拟节点，可以让数据更均匀地分布在物理节点之间。
• 提高容错性：即使某个物理节点失效，其对应的多个虚拟节点的数据会被其他节点接管，降低影响范围。

5. 示例：一致性哈希的基本过程

假设有 4 个节点（A、B、C、D）：

• 哈希环分布如下：

  0 ------------ A ------------ B ------------ C ------------ D
  

• 数据分布：

  • data1 的哈希值落在 A 和 B 之间，则存储在 B。
  • data2 的哈希值落在 D 和 A 之间，则存储在 A。

节点变动的处理

1. 节点增加（E 加入环）
   • 假设 E 的哈希值落在 B 和 C 之间，则 B 到 C 的部分数据转移到 E。
   • 其他数据保持不变
2. 节点减少（C 离开环）
   • C 的数据重新分配到其顺时针方向的节点（D）。