一致哈希(Consistent Hashing)简介

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

一致哈希在分布式计存储架构中无处不在。是被证明的可以解决经典哈希视图发生变化时，数据搬迁尽可能少的算法。最早是在分布式缓存中提出，参考如下文档，这里提供原文的下载链接：《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》。

经典的哈希使用场景为，在使用n台缓存服务器时，一种常用的负载均衡方式是，对资源o的请求使用hash(o) mod n来映射到某一台缓存服务器。当增加或减少一台缓存服务器时这种方式可能会改变所有资源对应的hash值，也就是所有的缓存都失效了，这会使得缓存服务器大量集中地向原始内容服务器更新缓存。因此需要一致哈希算法来避免这样的问题。

一致哈希尽可能使同一个资源映射到同一台缓存服务器。这种方式要求增加一台缓存服务器时，新的服务器尽量分担存储其他所有服务器的缓存资源。减少一台缓存服务器时，其他所有服务器也可以尽量分担存储它的缓存资源。 一致哈希算法的主要思想是将每个缓存服务器与一个或多个哈希值域区间关联起来，其中区间边界通过计算缓存服务器对应的哈希值来决定。（定义区间的哈希函数不一定和计算缓存服务器哈希值的函数相同，但是两个函数的返回值的范围需要匹配。）如果一个缓存服务器被移除，则它所对应的区间会被并入到邻近的区间，其他的缓存服务器不需要任何改变。

一致哈希将每个对象映射到圆环边上的一个点，系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时，需要用一致哈希算法计算得到对象对应圆环边上位置，沿着圆环边上查找直到遇到某个节点机器，这台机器即为对象应该保存的位置。 当删除一台节点机器时，这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时，这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。 更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。

下面两张图直观呈现了上述一致哈希的思想：

同样减少节点时，也只影响哈希空间的下一个节点。这样能做到节点加入和退出时挪动的数据量最少。

上述算法存在一个明显的数据分布不均衡的问题，如果N个节点分割好了哈希环，那么加入第N+1个节点时，必然会将一个原有的1/N的空间再一分为2，有N和N+1两个节点来分享，这样，如果数据在环上的分布是均衡的话，那么这两个节点上的数据量是其他节点一半，并且这两个节点在以后的业务中接到的数据也是其他节点的一半，不能完全发挥这两个节点的性能，也就失去了新增节点的意义。

如何解决一致哈希中数据在节点间分布不均匀的问题？算法中引入了虚拟节点的概念。将整个0-2^32的哈希空间分割成一定数量的虚拟节点空间。每个物理节点认领其中的若干个空间。如将整个哈希环分割成1152个虚拟节点，当节点数为32时，每个节点认领1152 / 32 = 36个虚拟节点。当扩容时，假设一次性扩容4个节点，则修改为每个节点认领1152 / 36 = 32个虚拟节点，这样每个物理节点只需要让出4个虚拟节点空间给新加入的第五个节点即可。如果希望整个哈希空间的分配绝对均衡，那么对节点数、扩容步长和虚拟节点总数将有严格的要求。一般而言难以达到，我们只需要确保虚拟节点数足够多，那么扩容或者故障节点时，数据分配仍然能保持大致均衡。