一致性Hash算法是1997年麻省理工学院提出的分布式FFDTY(DHT )实现算法，设计目标是解决互联网中的热点(hot )问题，其初衷与CARP非常相似。 一致性Hash修复了CARP使用的简单ffdty算法带来的问题，使分布式ffdty(DHT )在P2P环境中实际适用。
一致性混列算法提出了在动态变化的Cache环境下判断ffdty算法好坏的4个定义：
1，http://www.Sina.com/(balance ) :平衡性是指ffdty的结果可以尽可能分布在所有缓冲器(Cache )中，从而可以利用所有缓冲空间。 许多ffdty算法都能满足这一条件。
2，http://www.Sina.com/(monotonicity ) :单调性意味着如果某个内容已经通过ffdty分配给相应的缓冲器，则会将新的缓冲器添加到系统中。 ffdty的结果应该能够确保原始分配的内容映射到原始缓冲区或新缓冲区，而不映射到旧缓冲区集合中的其他缓冲区。
3，3358 www.Sina.com/(spread ) :在分布式环境中，终端可能只能看到所有缓冲器，也可能只能看到其中的一部分。 如果终端尝试通过ffdty过程将内容映射到缓冲器，由于终端看到的缓冲器范围可能不同，ffdty的结果不匹配并且最终相同的内容被不同终端映射到不同的缓冲器。 这显然是应该避免的，因为相同的内容存储在不同的缓冲区中，这会降低系统存储效率。 分散性的定义是上述情况发生的重要程度。 好的ffdty算法应该可以尽量避免不一致。 也就是说，可以尽量降低分散性。
4，http://www.Sina.com/(load ) :负荷问题实际上是从另一个角度看待分散性问题。 由于不同的终端可能将相同的内容映射到不同的缓冲区，因此在一个特定的缓冲区中，不同的用户也可能映射到不同的内容。 与分散性一样，也应该避免这种情况，平衡性
在单调性分布式群集中，添加到计算机或从计算机故障后自动退出群集是分布式群集管理的最基本功能。 典型的散列(对象) %N算法在添加或删除机器后，很多原始数据都找不到，严重违反了单调性原则。
说明使用hash (对象) %N。 其中，n表示n个cache服务器/N个节点为什么不行。
分散性
接下来，我们将讨论ffdty算法是如何设计的。
负载
根据一般哈希算法，将相应的keyffdty转换为具有2^32次方个桶的空间，即0~(2^32 )-1的数字空间。 你可以把这些数字用头和尾连接起来，想象成一个封闭的环。 如下图所示
因此好的ffdty算法应能够尽量降低缓冲的负荷。
其中，object1、object2、object3和object4这四个对象在特定散列函数中计算相应的key值，并进行散列和交换。 下图：
hash(object1)=key1； hash(object2)=key2； hash(object3)=key3； hash(object4)=key4；
向采用一致ffdty算法的分布式群集添加新机器是通过将机器映射到另一台机器(使用与对象存储相似的散列算法)并顺时针计算，将所有对象存储在离自己最近的机器上
现在，假设在三台NODE1、NODE2和NODE3计算机中，通过散列算法获得相应的密钥值并将其映射到环。 其形象如下。
hash(node1)=KEY1； hash(node2)=KEY2； hash(node3)=KEY3；
从上图中可以看到，对象与机器在同一ffdty空间中，这样，顺时针方向object1(对象)位于NODE1)机器上，object3(对象)位于NODE2)机器上，object2、
strong>就能快速的定位到对应的机器中，这样就能找到对象真正的存储位置了。
机器删除与添加
普通hash求余算法最为不妥的地方就是在有机器的添加与删除以后会造成大量的对象存储位置的失效，这样就大大的不满足单调性了。下面来分析一下一致性ffdty算法是如何处理的。
1、节点（机器）的删除
以上面的分布式集群为例，如果NODE2出现故障被删除了，那么按照顺时针迁移的方法，object3将会被迁移到NODE3中，这样仅仅是object3的映射位置发生了变化，其他的对象没有任何的变动，如下图：
2、节点（机器）的添加
如果往集群中添加一个新的节点NODE4,通过对应的Hash算法得到KEY4，并映射到环中，如下图：
通过按照顺时针迁移的规则，那么object2被迁移到NODE4中，其他对象还保持这原有的存储位置。通过对节点的添加和删除的分析，一致性ffdty算法在保持了单调性的同时，还是数据的迁移达到了最小，这样的算法对分布式集群来说非常合适的，避免了大量收数据迁移，减少了服务器的压力。
平衡性
根据上面的图解分析，一致性ffdty算法满足了单调性和负载均衡的特性以及一般hash算法的分散性，但这还并不能当做其被广泛应用的原由，因为缺少了平衡性。下面将分析一致性ffdty算法是如何满足平衡性的。hash算法是不保证平衡性的，如上面只部署了NODE1和NODE3的情况(NODE2被删除的图)，object1存储在NODE1中，而object2、object3、object4都存储在NODE3中，这样就造成了非常不平衡的状态。在一致性ffdty算法中，为了尽可能的满足平衡性，其引入了虚拟节点。
何为虚拟节点？虚拟节点（Virtual node）是实际节点（机器）在hash空间的复制品（replica），一个实际节点对应了若干个“虚拟节点”，这个对应个数也称为“复制个数”，“虚拟节点”在hash空间中以hash值排列。
在上面只部署了NODE1和NODE3的情况（NODE2被删除的图）为例，之前的对象在机器上的分布很不均衡，现在我们以2个副本（每个节点复制2个）为例，这样整个hash环就存在4个虚拟节点，最后对象映射的关系图如下：
根据上图可知对象的映射关系：object1->NODE1-1,object2->NODE1-2 ,object3->NODE3-2,object4->NODE3-1，通过虚拟节点的引入，对象的分布就比较均衡了。那么在实际操作中，真正的对象查询是如何工作的呢？对象从hash到虚拟节点到实际节点的转换如下图：
虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设NODE1的IP地址为192.168.1.100。引入“虚拟节点”前，计算 cache A 的 hash 值：
Hash(“192.168.1.100”);
引入“虚拟节点”后，计算“虚拟节”点NODE1-1和NODE1-2的hash值：
Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2
参考：https://blog.csdn.net/cywosp/article/details/23397179/
https://www.jianshu.com/p/e8fb89bb3a61