一致性哈希算法

一致性哈希算法常用于分布式缓存的场景。通过关键字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上面。为了解决这个问题，引入了虚拟节点的概念。虚拟节点是实际节点在哈希空间的复制品，一个实际节点对应了若干个虚拟节点，这个个数也成为复制个数。虚拟节点越多，哈希环上的节点就越多，数据被均匀分布的概率就越大。