一致性哈希算法

一致性哈希算法常用于分布式缓存的场景。通过关键字 key 从多个节点（也就是服务器）中找到缓存数据所在的节点。

一致性哈希算法是一种特殊的哈希算法。在使用一致性哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n 个关键字重新映射，其中 K 是关键字的数量，n 是槽位数量。然而在传统的哈希表中，添加或者删除一个槽位，几乎需要对所有的关键字进行重新映射。

传统哈希算法在分布式缓存场景中存在的问题：

传统哈希算法通过对哈希值取模的方式来确定判断数据应该分布在哪个节点。即

hash(key)/N N 为节点的个数

例：当前环境存在 3 个节点，依次过来 10 个数据，为了简单，我们忽略哈希值的计算，假设这 10 个数据的哈希值分别是 1-10。则数据的路由情况如下：

路由情况

如果此时线上复杂过高，又增加了一个节点，此时节点数变成了 4。则此时数据的命中情况如下：

路由情况

我们发现此时会有 8 个数据需要进行移动。此时对这 8 个数据的访问都是无法命中的，导致缓存失效。如果此系统非常依赖缓存，那么大量没有命中的数据需要从数据库中重新获取，导致数据库负载增高，甚至系统崩溃。

而一致性哈希算法就是为了解决这个问题而被提出的。一致性哈希算法也是取模。但是不是对节点数取模，而是对 2^32 取模。不管环境中存在多少节点都是对 2^32 取模。那么如何判断数据会被路由到哪个节点呢？

我们想象一个圆环，而 0 到 2^32-1 这些数字均匀的分布在这个环上面。假设我们有 3 个节点，这 3 个节点肯定都有自己的 IP。我们根据节点的 IP 地址计算哈希值，并将结果对 2^32 取模。所得的结果介于 0-2^32-1 之间，那么在圆环上肯定有一个点与之对应，如下图：

哈希环

当收到一个数据的时候，计算其哈希值并对 2^32 取模，从节点哈希值中查找，比此哈希值大且最节点此哈希值的节点即为数据缓存的节点。此处为了能够快速的找对这个节点，可以按照节点的哈希值进行排序，再使用二分法查找。

查找例子

同样以上面的例子举例：

假设当前有 3 个节点，为了简化问题，我们不构造 2^32 这么大的圆，我们构造一个 10 个节点的圆环。说明：为什么在一致性哈希算法中会构造数据量非常大的圆环呢？增大哈希值的域，避免冲突。另外假设，3 个节点的哈希值分别为 0，3，6。那么此时 10 个数据的路由情况是：

路由情况

当再增加一个节点时，假设节点的哈希值是 8，此时的路由情况是：

路由情况

我们发现只有 2 个数据未命中，过渡平滑得多。

但是上述算法依然存在问题，那就是无法应对数据的倾斜。比如数据的哈希值全部都集中在 0-3 之间，那么此时的访问压力全部都集中在节点 2 上面。为了解决这个问题，引入了虚拟节点的概念。虚拟节点是实际节点在哈希空间的复制品，一个实际节点对应了若干个虚拟节点，这个个数也成为复制个数。虚拟节点越多，哈希环上的节点就越多，数据被均匀分布的概率就越大。