一致性哈希算法是如何实现数据分布均衡的？

本文共计3869个文字，预计阅读时间需要16分钟。

哈希取模算法具有局部性，简单来说，哈希就是将一个键值对存储在一个存储结构中，当需要查找时，可以非常高效地找到对应的值。要理解一致哈希，首先需要了解传统的哈希及其在哈希取模中的原理。

一、传统哈希取模算法的局限性

简单地说，哈希就是一个键值对存储，在给定键的情况下，可以非常高效地找到所关联的值。

要了解一致性哈希，首先我们必须了解传统的哈希及其在大规模分布式系统中的局限性。

当数据太大而无法存储在一个节点或机器上时，系统中需要多个这样的节点或机器来存储它。比如，使用多个 Web 缓存中间件的系统。那如何确定哪个 key 存储在哪个节点上？针对该问题，最简单的解决方案是使用哈希取模来确定。

给定一个 key，先对 key 进行哈希运算，将其除以系统中的节点数，然后将该 key值 放入该节点。同样，在获取 key 时，对 key 进行哈希运算，再除以节点数，然后转到该节点并获取值。上述过程对应的哈希算法定义如下：

node_number = hash(key) % N # 其中 N 为节点数。

下图描绘了多节点系统中的传统的哈希取模算法，基于该算法可以实现简单的负载均衡。

传统哈希取模算法的局限性:

举例，对 semlinker、kakuqo 和 test 3 个键进行哈希运算并取余

1. 节点减少的场景

在分布式多节点系统中，出现故障很常见。任何节点都可能在没有任何事先通知的情况下挂掉，针对这种情况我们期望系统只是出现性能降低，正常的功能不会受到影响。