一致性哈希算法

一致性哈希在分布式缓存中的具体作用是：根据 Key 的哈希值将数据平摊映射到环形节点上，并在节点增减时只迁移少量相邻数据，从而稳定地定位数据归属。

一致性哈希（Consistent Hashing）是一种特殊的哈希算法，最早由麻省理工学院（MIT）的 Karger 等人在 1997 年提出。它主要用于解决分布式系统中动态节点扩缩容时，传统哈希取模算法导致的数据大规模失效和数据迁移问题。

---

一、 分布式缓存中，它到底解决了什么问题？

1. 传统哈希取模算法（hash(key) % N）的致命缺陷

在分布式缓存（如 Redis / Memcached 集群）中，假设最初有 $N=3$ 台缓存服务器。当客户端需要存储或查询 key 时，通常计算：

$\text{Server Index}=\text{hash}(key)(\mathrm{mod}N)$

如果此时集群遇到以下情况：

• 节点宕机或下线：集群节点数从 3 变为 2（$N=2$）。
• 节点扩容/加机器：为了应对大促流量，集群节点数从 3 增加到 4（$N=4$）。

后果： 由于取模的分母 $N$ 改变了，几乎所有 key 重新计算出的服务器节点都会发生改变（映射失效率高达 $1-\frac{1}{N}$）。这会导致：

1. 缓存雪崩：缓存集群中 80%~90% 以上的数据在同一瞬间全部失效，请求穿透直接打到数据库，导致数据库瞬间压垮宕机。
2. 全量数据迁移：整个集群需要重新拉取或同步绝大部分数据，造成极高网络与 CPU 开销。

---

2. 一致性哈希算法的解决原理

一致性哈希将寻址空间抽象成一个固定大小的虚拟环（Hash Ring），取值范围通常是 $0\sim 2^{32}-1$。

                       [0 / 2^32]
                     .            .
                 .                    .
            Node A (1000)          Node C (3000)
          .                              .
        .                                  .
     Key 1 (500)                        Key 2 (2500)
        .                                  .
          .                              .
            .                          .
                     Node B (2000)

1. 节点映射到环：将服务器节点的 IP 或名称进行 Hash 计算，得到在环上的位置（如 Node A, Node B, Node C）。
2. 数据映射到环：计算数据的 hash(key)，得到在环上的位置。
3. 顺时针查找：沿环顺时针方向寻找，遇到的第一个服务器节点就是该 key 存储的节点。

扩缩容时的优势（破坏范围极小）：

• 增加节点：假设在 Node A 与 Node B 之间新增 Node D，只有原本映射到 A~D 区间的数据需要迁移到 Node D，其他所有节点的数据保持不变。
• 删除节点：假设 Node B 宕机，只有原本属于 Node B 的数据会顺时针移交给 Node C 承担，其他节点不受影响。

---

3. 数据倾斜问题与“虚拟节点（Virtual Nodes）”

痛点： 如果节点数量较少，或者 Hash 映射不均匀，会导致节点在环上分布极不平衡（如 Node A 和 Node B 离得很近，Node C 占据了绝大部分环）。这会导致大部分流量落入同一个节点（数据倾斜/热点问题）。

解决方案： 引入虚拟节点（Replicas）。

• 为每个物理节点生成多个虚拟节点（如 NodeA-1, NodeA-2, NodeB-1, NodeB-2 …）。
• 计算每个虚拟节点的 Hash 值并放入环中。
• 当请求落到某个虚拟节点时，通过一张映射表（如你代码中的 hashMap[hash] = key）将其路由回真实物理节点。
• 效果：虚拟节点越多，节点在环上的分布越均匀，节点宕机时负载也会平摊给剩下的所有节点，而不是全部压给顺时针的下一个单点。

---

二、 一致性哈希在其他分布式场景的应用

除了分布式缓存之外，任何涉及数据分片（Sharding）、请求路由、负载均衡且需要应对节点动态变动的分布式系统，都会使用一致性哈希：

1. 分布式存储系统（Database & Storage）

• Amazon DynamoDB / Apache Cassandra / Riak： 在无中心架构（P2P）的分布式 Key-Value 数据库中，一致性哈希用于决定数据切片（Data Range / Partition）归哪个节点管辖，以及副本（Replicas）应该存储在顺时针紧随其后的哪几个节点上。
• Ceph（CRUSH 算法）： Ceph 对象存储在映射 OSD（Object Storage Daemon）节点时，采用了类似一致性哈希的思想来保证数据分布的均衡性与动态扩缩容效率。

2. 分布式 RPC 框架与网关的负载均衡

• Dubbo / gRPC / Spring Cloud Gateway： 在客户端负载均衡（Load Balancing）策略中，除了轮询、随机之外，通常都提供 “一致性哈希 (ConsistentHash)” 算法选项。
• 场景：例如有状态的会话服务、用户 TCP 长连接网关。
• 作用：根据 User-ID 或 Session-ID 进行一致性哈希，确保来自同一个用户的请求始终路由到同一台后端 Server，同时在后端服务增减节点时，最大限度减少会话断开或重新建立的范围。

3. 分布式消息队列（Message Queue）

• Apache RocketMQ / Kafka 的 Consumer 负载均衡： 当消费者（Consumer）组内新增或减少节点时，需要重新分配 Topic 下的 Message Queue/Partition。一致性哈希能够保证在 Consumer 变更时，最大限度减少队列在消费者之间的重新分配（Rebalance）开销。

4. CDN 与 HTTP 代理缓存（如 Nginx / HAProxy）

• 边缘缓存节点：CDN 边缘节点使用一致性哈希将特定 URL 路由到指定的上游缓存服务器（Consistent Hash Ring）。这样同样的资源 URL 始终打到相同的缓存服务器，提升 CDN 的本地缓存命中率。

---

总结比较

特性	传统取模哈希 (hash % N)	一致性哈希 (Consistent Hashing)
映射失效范围（扩缩容时）	接近 100% 的数据需要重新映射	仅影响变动节点及其相邻节点的数据（约 $1/N$）
数据分布均匀度	非常均匀	依靠虚拟节点机制实现高度均匀
适合场景	节点数极少变动的静态集群	节点动态扩缩容、有故障自愈要求的分布式系统