一致性哈希算法

一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：

• 平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
• 单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
• 分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
• 负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。接下来主要讲解一下一致性哈希算法是如何设计的：

环形Hash空间

按照常用的hash算法来将对应的key哈希到一个具有2^32次方个桶的空间中，即0~(2^32)-1的数字空间中。现在我们可以将这些数字头尾相连，想象成一个闭合的环形。如下图

把对象映射到hash空间

现在我们将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值，然后散列到Hash环上。

Hash(object1) = key1；
Hash(object2) = key2；
Hash(object3) = key3；
Hash(object4) = key4；

将机器通过hash算法映射到环上

在采用一致性哈希算法的分布式集群中将新的机器加入，其原理是通过使用与对象存储一样的Hash算法将机器也映射到环中（一般情况下对机器的hash计算是采用机器的IP或者机器唯一的别名作为输入值），然后以顺时针的方向计算，将所有对象存储到离自己最近的机器中。

通过上图可以看出对象与机器处于同一哈希空间中，这样按顺时针转动object1存储到了keyA中，object4存储到了keyB中，object2、object3存储到了keyC中。在这样的部署环境中，hash环是不会变更的，因此，通过算出对象的hash值就能快速的定位到对应的机器中，这样就能找到对象真正的存储位置了。

移除机器

添加机器

添加机器cache D,机器D经过Hash计算，位于object2和object3之间，顺时针来看，object2存储到cache D当中，object3存储cache C当中，其余的不变。

虚拟节点

考量 Hash 算法的另一个指标是平衡性 (Balance) ，定义如下：

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

hash算法并不是保证绝对的平衡，如果cache较少的话，对象并不能被均匀的映射到cache上。比如在上面的例子中，仅部署cache A和cache C的情况下，在4个对象中， cache A仅存储了object1 ，而cache C则存储了object2 、object3和object4 ；分布是很不均衡的。

为了解决这种情况， consistent hashing引入了“虚拟节点”的概念，它可以如下定义：

“虚拟节点”（virtual node）是实际节点在hash空间的复制品（replica），一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash空间中以hash值排列。

仍以仅部署cache A和cache C的情况为例，在上图中我们已经看到， cache分布并不均匀。现在我们引入虚拟节点，并设置“复制个数”为2，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2代表了cache A ； cache C1, cache C2代表了cache C ；假设一种比较理想的情况，如图

此时，对象到“虚拟节点”的映射关系为：

objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2

因此对象object1和object2都被映射到了cache A上，而object3和object4映射到了cache C 上；平衡性有了很大提高。

引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在cache时的映射关系如图所示。

“虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设cache A的IP地址为202.168.14.241 。

引入“虚拟节点”前，计算cache A的hash值：

Hash(“202.168.14.241”);

引入“虚拟节点”后，计算“虚拟节”点cache A 和cache A2的hash值：

Hash(“202.168.14.241#1”); // cache A1

Hash(“202.168.14.241#2”); // cache A2

基于一致性哈希的原理有多种具体的实现，包括Chord算法，KAD算法,CAN,Tapestry,Pastry...

有意思的是它们都是2001年发出来的paper，所以2001年大概是P2P下载的元年吧。

source

• 编程艺术第十六~第二十章：全排列/跳台阶/奇偶调序，及一致性Hash算法 CSDN July
• 每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)
• 一致性hash算法 - consistent hashing
• 程序员代码面试指南 左程云 第6章 大数据和空间限制 一致性哈希算法的基本原理