一致性哈希 (Consistent Hashing)

一致性哈希是一种分布式计算和数据存储算法，用于确定如何将数据分布到多个节点或服务器。在节点加入或退出分布式集群时，它能最大限度地减少需要重新分布的键的数量。

基本原理

Source: 2026-06-21-note-硅谷Python工程师面试指南-数据结构-算法与系统设计（来源未公开） · 2026-10-07-book-grokking-the-system-design-interview.md（来源未公开）

• 哈希环 (Hash Ring)：一致性哈希将数据的键（或标识符）以及缓存节点的 IP/名称通过同一个哈希函数转换为哈希值，并将它们映射到一个虚拟的哈希环上（通常是 $0$ 到 $2^{32}-1$ 或 $2^{256}-1$ 的首尾相接闭环）。
• 数据定位：当需要存取某个键对应的数据时，先将其哈希为一个数值，沿着哈希环顺时针寻找，遇到的第一个节点即为该键对应的数据存储节点。
• 节点的加入与离开：
  • 当一个新节点加入时，只有该新节点在环上的前驱节点到新节点之间的数据需要迁移到新节点。
  • 当一个节点离开（或故障宕机）时，原本路由到该节点的数据将被顺时针路由到环上的下一个节点。
  • 再平衡复杂度：传统取模哈希（$Key(\mathrm{mod}N)$）在节点数变更时会导致全量键（$100\%$）重新映射；一致性哈希在有 $k$ 个键和 $n$ 台机器时，仅有 $k/n$ 个键需要重新映射，保证了水平扩缩容时系统的极高可用性与零停机迁移。

解决的问题与优化

• 哈希碰撞与数据倾斜 (Data Skew & Hotspots)：如果节点较少或哈希离散度不均，真实请求往往会集中在某几个物理节点上。
• 虚拟副本机制 (Virtual Replicas / Virtual Nodes)：
  • 不再将单台物理机仅映射到环上的单个点，而是为每台物理机配置多个虚拟副本点（例如 $A_1,A_2,A_3\dots$）。
  • 虚拟节点交错散落在整个哈希环的各个分段。当虚拟节点数量充分增加时，每个物理节点实际覆盖环形弧长的期望方差趋近于零，从而实现数据与流量的近乎完美平摊。
• 经典应用：Memcached、Cassandra、DynamoDB、YouTube 边缘缓存路由等分布式缓存与存储引擎。