一致性哈希的简单认识

简介

在分布式集群中，对机器的添加、删除或者是机器故障后自动脱离集群等操作是分布式集群管理最基本的功能。如果采用的是常见的取模哈希算法，当有机器添加、删除之后，需要对数据做迁移，非常麻烦。

而一致性哈希利用哈希环的概念，保证增加或减少服务器，数据存储的改变最少，相比取模哈希算法大大节省了数据移动的开销，非常方便。

一致性哈希认为在动态变化的缓存空间环境中，良好的哈希算法应该满足以下几个方面：

• 平衡性：指哈希的结果能够尽可能分布到所有的缓存中，这样可以使得所有的缓存空间都能得到利用
• 单调性：指当新的缓存空间加入时，原本已分配的数据可以被映射到原本或者新的缓存空间中，而不会被映射到旧的其他缓存空间中
• 分散性：避免出现相同的内容被不同的终端映射到不同的缓存空间中，降低系统存储的效率
• 负载：与分散性结合理解，对于一个特定的缓冲区，避免被不同的终端映射为不同的内容

一致性哈希可以理解成普通取模哈希算法的改良版，改变的是将普通的线性哈希空间变成环状的哈希空间，其中每一个缓存空间是环上的一个节点，数据一般存储在沿顺时针的方向找到的环上的第一个节点。

算法

哈希环

简单的说，一致性哈希是将整个哈希值空间想象成一个虚拟的圆环。

比如，假设哈希函数 H 的值空间为 0 ~ 232−1，整个哈希空间环如下：

假设这时有 k1、k2、k3、k4 这几个 key 值，通过一定的哈希算法，将这几个 key 值被平均分配到哈希环上。

同样的，现在有 3 台 cache 服务器，通过一定的哈希算法，也被平均分配到哈希环上。

下图展示的是 key 值被分配到哪一台 cache 服务器的一个示例：

如上所示：k1 存储在 c3 上，k4、k3 存储在 c1 上，k2 存储在 c2 上。

哈希环会将哈希后的 key 值按照顺时针的方向寻找最近的 cache 服务器，然后将数据存储在这台服务器上。

删除节点

假设 c3 服务器宕机，这时候需要从集群中将其摘除，其上的数据也需要做迁移。

按照一致性哈希的规则，原本存储在 c3 上的 k1 按照顺时针的方向寻找最近的 cache 服务器，即后续 k1 会存储在 c1 上：

从这里可知，当使用一致性哈希时，删除节点 c3 会影响到被删除节点 c3 上及其下一个节点 c1 的数据，迁移数据的时候，需要将被删除节点 c3 上的数据迁移到其下一个节点 c1 上。

新增节点

假设现在需要新增 c4 服务器，会破坏现在集群的平衡，需要对数据做一些处理。

假设 c4 服务器定位在 k4 和 k3 之间，按照一致性哈希的规则，原本存储在 c1 上的 k4 会迁移到 c4 上：

同样的，新增节点会影响到新增节点所在位置的后一个节点 c1，迁移数据的时候，需要将新增节点所在位置到其上一个节点 c3 之间的数据从其下一个节点 c1 迁移到新增的节点 c4 上。

虚拟节点

一致性哈希理论上没有什么问题，但实际使用会存在以下问题：

• 当节点较少时，哈希环中的节点容易出现分布不均衡，最终导致数据倾斜
• 当一个节点宕机时，数据会立马迁移到下一个节点，下一个节点的流量压力和内存压力都会增大，可能会导致其宕机，继而引发雪崩

这里就衍生出一个虚拟节点的概念，即对每个物理节点计算多个哈希值，将原来单一的物理节点在哈希环上虚拟出几个分身节点，这些分身节点称为虚拟节点。

映射到分身节点上的数据实际上就是映射到分身对应的物理节点上，这样一个物理节点可以通过虚拟节点的方式均匀分散在哈希环的各个部分，解决数据倾斜问题。

由于虚拟节点分散在哈希环各个部分，当某个节点宕机下线，虚拟节点所存储的数据会被均匀分配给下一个虚拟节点，则物理节点也会得到均匀分配，避免了对单一节点突发压力导致的节点雪崩问题。

在实际应用中，通常将虚拟节点数设置成 32 甚至更大，这样可以保证即使很少的服务节点也能做到均匀的数据分布。

优缺点

一致性哈希算法相比普通的哈希算法在扩展性和容错性上都有一定的优势：

• 扩展性：普通的哈希算法增加缓存空间的时候，需要对大量数据做迁移；一致性哈希算法扩展时仅需将下一个节点中的一部分数据迁移到这个新增节点上
• 容错性：普通的哈希算法减少缓存空间的时候，会出现哈希映射大面积失效的情况；而对于一致性哈希算法，如果出现需要减少缓存空间的情况，其实就是需要将当前减少的节点数据迁移到下一个节点中

实际上，不会存在一劳永逸的哈希算法，一致性哈希算法在以下场景需要谨慎使用：

• 对于数据占用空间大、但数量较小时，使用一致性哈希有些大材小用
• 一致性哈希解决了数据的均匀分布，但是没有解决流量和负载的均衡
• 数据和机器之间的映射通过哈希算法得到，这种关系比较固定，无法人工干涉