在分布式系统的设计与面试中，一致性哈希是一个高频话题。虽然实际业务中未必直接实现它，但理解其思想对于构建高可用的服务至关重要。
开始之前，先说两个常见的核心应用场景：
- 负载均衡：由于访问人数太多，我们的网站部署了多台服务器共同提供相同的服务，但每台服务器上可能维护着用户会话等状态信息。为了保证请求的正确响应，相同参数（key）的请求（比如同一个用户的请求）需要被路由到同一台服务器处理。
- 分布式缓存：由于缓存数据量太大，我们部署了多台缓存服务器共同提供服务。缓存数据需要尽可能均匀地分布在这些服务器上，并且通过一个 key 能够快速定位到数据所在的服务器。
这两种场景的本质，都是需要建立一个 从 key 到服务器/节点的稳定映射关系。
为了实现这个目标，你首先会想到什么方案呢？
普通哈希算法
相信大家很快就能想到 “哈希+取模” 这个经典组合。通过哈希算法计算出 key 的哈希值，再对服务器数量取模，从而将 key 映射到固定的服务器上。
公式也很简单：
node_number = hash(key) % N
hash(key): 使用哈希函数（建议使用性能较好的非加密哈希函数，例如 SipHash、MurMurHash3、CRC32、DJB）对唯一键进行哈希。% N: 对哈希值取模，将哈希值映射到一个介于 0 到 N-1 之间的值，N 为节点数/服务器数。
然而，传统的哈希取模算法有一个致命的缺陷：无法很好地应对节点动态增减的场景。无论是机器宕机还是水平扩容，都会引发大规模的数据迁移。
想象一下，服务器的初始数量为 4 台 (N = 4)。如果其中一台服务器宕机，N 就变成了 3。此时，对于同一个 key，hash(key) % 3 的结果很可能与 hash(key) % 4 完全不同。
这意味着几乎所有的数据映射关系都会错乱。在分布式缓存场景下，这会导致 大规模的缓存失效和缓存穿透，瞬间将压力全部打到后端的数据库上，极易引发系统雪崩。
据估算，当节点数量从 N 变为 N-1 时，平均有 (N-1)/N 比例的数据需要迁移，这个比例 趋近于 100% 。这种“牵一发而动全身”的效应，在生产环境中是完全不可接受的。
为了解决节点动态变化带来的巨大扰动，一致性哈希算法应运而生。
一致性哈希算法
一致性哈希算法在 1997 年由麻省理工学院提出（论文 PDF），是一种特殊的哈希算法，其目标是在添加或移除一个服务器时，能够 最小化 已存在的 key 与服务器之间映射关系的变化。它有效地解决了传统哈希算法在分布式哈希表（DHT）中存在的动态伸缩问题。
一致性哈希算法的核心在于引入了 哈希环 的概念。
哈希环
该算法将整个哈希值空间组织成一个虚拟的环形结构。这个环的起点是 0，终点是 2^32 - 1，并且首尾相连，因此哈希值的整数分布范围是 [0, 2^32-1]。
传统哈希算法是对服务器数量 N 取模，而一致性哈希算法则是对这个固定大小的哈希空间取模（通常为 2^32）：
node_number = hash(key) % 2^32
服务器/节点如何映射到这个环上呢？同样使用哈希取模。通常，根据服务器的 IP 地址或主机名进行哈希计算：
hash（服务器ip） % 2^32
如下图所示，四个节点通过计算被放置在哈希环的特定位置：
我们将数据和节点都映射到哈希环上，每个节点负责从自身位置开始，沿顺时针方向到下一个节点之间的环形区域。对于上图来说：
- Node1: 负责 Node4 到 Node1 之间的区域（包含 value6）。
- Node2: 负责 Node1 到 Node2 之间的区域（包含 value1, value2）。
- Node3: 负责 Node2 到 Node3 之间的区域（包含 value3）。
- Node4: 负责 Node3 到 Node4 之间的区域（包含 value4, value5）。
节点移除/增加
当节点发生变动时，哈希环的优势就体现出来了。它能够将影响范围局限在相邻节点之间，从而大幅减少需要迁移的数据量。
仍以上图为例，假设 Node2 节点被移除，那么原本由 Node2 负责的环形区间（Node1->Node2）将由其顺时针方向的下一个节点 Node3 接管。我们只需要将 Node2 上的数据迁移到 Node3 即可，其他节点（Node1, Node4）完全不受影响。
同样地，如果我们在 Node1 和 Node2 之间新增一个节点 Node5，那么原本落在 Node1 到 Node5 之间的数据（如图中的 value1）将会由 Node5 负责。我们只需要将这部分数据从 Node2 迁移到 Node5，影响范围同样非常有限。
数据倾斜问题
理想很丰满，现实却可能很骨感。一致性哈希环虽然解决了动态伸缩的问题，但引入了一个新的挑战：数据倾斜。
当节点数量较少，或者哈希结果不够均匀时，节点在环上的分布可能非常集中。这会导致绝大部分数据都由其中一两个节点负责，其他节点则非常空闲，完全违背了负载均衡的初衷。
如上图所示，Node3 承担了远超其他节点的数据量。这种不均衡还会带来另一个隐患：当某个负载过重的节点宕机时，其所有数据会瞬间压垮它的顺时针后继节点，可能导致连锁故障。
如何解决这个问题呢？答案是引入 虚拟节点。
虚拟节点
虚拟节点是解决数据倾斜的“银弹”。它的思想是为每个物理节点在哈希环上创建多个分身（即虚拟节点）。数据落到任何一个虚拟节点上，都等同于落到其背后的真实物理节点。通过将大量虚拟节点均匀分散在哈希环上，可以使得数据分布更加平均。
如下图所示，每个物理节点（Node1-4）都对应了多个虚拟节点（例如 Node1.1, Node1.2...）。
在上图的虚拟节点布局下，数据的最终分布变得更加均匀：
- Node1: value4
- Node2: value1, value3
- Node3: value5
- Node4: value2, value6
引入虚拟节点的好处是巨大的：
-
数据均衡：虚拟节点越多，环上的“服务点”就越密集，数据分布自然越均匀，从根本上解决了数据倾斜问题。在实践中，每个真实节点通常对应 100 到 200 个虚拟节点。我们还可以通过调整虚拟节点数量（即权重）来区分处理能力不同的服务器，能力强的服务器获得更多虚拟节点，承载更多流量。
-
容错性与扩展性增强：这是虚拟节点最精妙的地方。当一个物理节点宕机，相当于环上它的多个虚拟节点同时消失。这些虚拟节点原本负责的流量，会自然地、均匀地分散给环上其他多个不同的物理节点，而不会将压力集中于某一个相邻节点。新增节点时，同理也会从多个现有节点那里获取一部分数据，避免了热点问题。这极大地提升了系统的稳定性和弹性。
总结
从简单的哈希取模到引入哈希环的一致性哈希，再到通过虚拟节点解决数据倾斜，这一演进过程清晰地展示了如何一步步构建一个能够优雅应对节点动态变化的分布式路由方案。虽然在实际应用中（如 Redis Cluster, Nginx负载均衡）我们通常直接使用成熟的类库或中间件，但深入理解一致性哈希的原理，对于设计高可用、易扩展的分布式系统至关重要。
如果你想与更多开发者探讨此类系统设计话题，欢迎来到云栈社区交流分享。
参考
发表于 昨天 03:43
|
查看: 3|
回复: 0
