一致性哈希学习

一致性哈希算法介绍

一致性哈希算法其实是一种特殊的哈希算法，哈希算法，简单的来说，就是对一个 key（可以是数字，字符串） 进行一个种运算，最终得到一个固定不变的数字，即哈希值。网上也有不少哈希算法具体实现，这里不具体展开了。

一致性哈希算法，是对固定长度（2^32）进行取模，得到一个固定的值a，我们可以把0~2^32看成一个首尾相接的环，固定值a，就落在环上的某个位置。比如，现在有三个节点A，B，C，经过哈希运算得到的数值再 % (2^32)，最终三个节点分别落在环上的三个位置，如下图。

现在有6个key，同样通过哈希运算后，得出在环中的6个位置，如下图

接下来，沿着顺时针方向走，遇到的第一个节点，就是要存储 key 的节点。key4，key1存储在节点A，key2，key5存储在节点B，key6，key3存储在节点C。每个节点负责环上的一部分分段，这样就做到了所有的 key 均匀分布在每个节点上。

使用场景

主要用在分布式系统中，如负载均衡，缓存数据分区等场景。当分布式集群添加或者删除一个服务器时，尽可能地减少服务器之间 key 的迁移，保证尽量有多的请求命中原来的机器节点，从而提升系统的可扩展性以及稳定性。

传统的hash取模对比

假设现在有3台服务器，6个key，分布如下

通过哈希取模算法将每个 key 都比较均匀的分散到了三个不同的服务器节点上，但如果遇到了服务器数量发生变化的时候，就会出现比较大的问题，基本上所有的 key 都要进行服务器之间的相互迁移。

如上图所示，key（aaa，bbb，ccc）分布在三个节点上，当节点个数从3变到4时，node0 上的 aaa，需要转移到 node3，node1上的 bbb 转移到 node3，node2 上的 ccc 转移到 node0。这就涉及到了原先的节点存在大量的 key 需要转移到其他节点上，加重了数据迁移成本。最终可能是 node0 即要迁移数据到 node1，也要迁移到 node2，node3，同理，node1，node2 也是如此。

如果使用一致性hash算法，就不会存在原有的节点数据相互迁移，最终达到的效果如下：

这样，就只需要把原先的节点 node0,1,2 迁移部分数据到新节点 node3。

扩容和缩容

当添加一个新节点D 时，通过哈希取模 2^32，把节点D 放到环上，如下图所示：

添加新节点D 后，只需要对原先节点 A 进行检测所有的 key，如果 key 按顺时针方向查找最近的节点是落在新节点 D 上的话，那么就需要把这个 key 迁移过去。此时，节点 B，节点 C 不受影响，不需要迁移数据。

当删除一个节点 C 时，只需要将节点 C 上 的数据按顺时针方向查找环上最近的下一个节点 D，然后把 C 节点上的数据全部迁移到节点 D 上，此时节点A，节点B上不受影响，不需要迁移数据。

虚拟节点

一致性哈希，虽然可以很好的解决数据迁移问题，但和传统哈希取模一样，存在一个比较严重的问题，那就是数据倾向，数据分布不均，大多数 key 可能会集中在少量的几个节点上的情况。

比如下图，key6 在节点C，其余key1~5 都集中在节点A上。

解决这个问题的最好办法，就是使用大量的节点来映射到环上，这样 key 分布就越均衡。但问题是，实际中我们没有那么多节点。所以这个时候我们就加入虚拟节点，也就是对一个真实节点做多个副本。

具体的做法，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到真实节点，所以这里有两层映射关系。

比如对每个节点分别设置 3 个虚拟节点：

对节点 A 加上编号来作为虚拟节点：A1、A2、A3
对节点 B 加上编号来作为虚拟节点：B1、B2、B3
对节点 C 加上编号来作为虚拟节点：C1、C2、C3

引入虚拟节点后，原本哈希环上只有 3 个节点的情况，就会变成有 9 个虚拟节点映射到哈希环上，哈希环上的节点数量多了 3 倍。

如上图所示，节点数量多了后，节点在哈希环上的分布就相对均匀了。这时候，如果有 key 请求到 A1这个虚拟节点，接着再通过 A1 虚拟节点找到真实节点 A，这样请求就能访问到真实节点 A 了。在上图中，会出现 B2，B3是相邻的。为了能更均匀些，可以再加大虚拟节点个数。

此外，还有一种情况需要考虑的是，如果两个或多个虚拟节点都映射到环上同一个位置，那么我们又应该怎么做呢。

此时，我们可以把相同槽位的虚拟节点放到一个数组里，如果 hash(key) % 2^32 是落在 节点 C2 位置上的话，我们再对这个位置上的虚拟节点数组个数取模，看看最终是落在 C2，还是 B2，又或者 A1 节点上。

参考：

得物面试：为啥Redis用哈希槽，不用一致性哈希？

dubbo-一致性hash负载均衡实现剖析

什么是一致性哈希？

java一致性哈希简单实现