ConsistentHashAlgorithm是麻省理工学院于1997年提出的一种分布式哈希（DHT）实现算法，其设计目标是解决互联网中的热点（Hotspot）。)问题，初衷和CARP很像。一致性哈希纠正了CARP使用的简单哈希算法带来的问题，使分布式哈希（DHT）真正应用于P2P环境。一致性哈希算法针对动态变化的Cache环境下判断哈希算法好坏提出了四种定义：1.平衡：平衡是指哈希结果尽可能的分布到所有的缓存中去，使得所有的缓存空间可以使用。许多哈希算法都可以满足这个条件。2.单调性：单调性是指如果某些内容已经通过哈希分配给相应的缓冲区，则系统会添加一个新的缓冲区。散列的结果应该能够保证原来分配的内容能够映射到原来的或者新的buffer，而不会映射到oldbufferset中的其他buffer。3.传播：在分布式环境中，终端可能看不到所有的缓冲区，而只能看到一部分。当终端要通过哈希过程将内容映射到缓冲区时，不同终端看到的缓冲区范围可能不同，导致哈希结果不一致。最后的结果是相同的内容被不同的终端映射到不同的缓冲区。在缓冲区中。这种情况显然应该避免，因为它会导致相同的内容存储在不同的缓冲区中，降低系统存储的效率。分散定义为上述情况发生的程度。一个好的哈希算法应该能够尽可能避免不一致，也就是尽量减少分散。4、负载：负载问题其实是换个角度看色散问题。由于不同的终端可能将相同的内容映射到不同的缓冲区，因此不同的用户也可能将特定的缓冲区映射到不同的内容。与去中心化一样，这应该避免，所以一个好的哈希算法应该最小化缓冲负载。在分布式集群中，增删机器，或者机器故障后自动退出集群，是分布式集群管理最基本的功能。如果使用常用的hash(object)%N算法，那么一台机器增删改查后，很多原始数据就找不到了，严重违背了单调性原则。下面主要讲解一下一致性哈希算法是如何设计的：环哈希空间按照常用的哈希算法，将对应的key哈希到一个有2^32个桶的空间，即0~(2^32)-1中数空间。现在我们可以将这些数字首尾相接，想象一个闭环。如下图所示，数据经过一定的哈希算法处理后映射到环上。现在我们通过特定的Hash函数计算出object1、object2、object3、object4这四个对象对应的key值，然后散列到Hash环中。如下图所示：Hash(object1)=key1;散列（对象2）=键2；散列（对象3）=键3；哈希（对象4）=键4；分布式中通过hash算法将机器映射到环上集群中新增机器的原理是使用与对象存储相同的Hash算法将机器映射到环上（一般机器的hash计算使用机器的IP或机器的唯一别名作为输入值），然后按顺时针方向计算，将所有对象存储在离你最近的机器中。假设有NODE1、NODE2、NODE3三台机器，通过Hash算法得到对应的KEY值，映射到环上。示意图如下：Hash(NODE1)=KEY1;散列（NODE2）=KEY2；散列（NODE3）=KEY3；从上图可以看出object和machine在同一个hash空间，所以顺时针转object1存放在NODE1，object3存放在NODE2，object2和object4存放在NODE3。在这样的部署环境中，哈希环不会发生变化。因此，通过计算对象的哈希值，可以快速定位到对应的机器，从而找到对象的真实存储位置。机器的删除和添加普通的哈希取余算法最不合适的地方是在机器添加或删除后，大量的对象存储位置将变得无效，这对单调性有很大的不满。让我们分析一下一致性哈希算法是如何工作的。1.节点（机器）的删除以上面的分布为例，如果NODE2出现故障被删除，object3会按照顺时针的迁移方式迁移到NODE3，这样只有object3的映射位置发生了变化，其他object没有变化已更改。如下图：2.添加节点（机器）如果在集群中添加一个新的节点NODE4，通过相应的哈希算法得到KEY4，映射到环上，如下图：通过顺时针迁移的规则，那么object2已经迁移到NODE4，其他object仍然保持原来的存储位置。一致性哈希算法通过对节点的增删分析，保持单调性，同时最小化数据迁移。这样的算法非常适合分布式集群，避免了大量的数据迁移，减轻了服务器的压力。平衡性根据上面的图解分析，一致性哈希算法满足了单调性和负载均衡的特点，也满足了一般哈希算法的去中心化性，但这并不能算是它被广泛应用的原因，因为它缺乏平衡性。下面将分析一致性哈希算法是如何满足平衡的。哈希算法不保证平衡。比如上面只部署了NODE1和NODE3的情况下（删除了NODE2的图片），object1存放在NODE1中，而object2、object3、object4都存放在NODE3中。不平衡状态。在一致性哈希算法中，为了尽可能满足平衡，引入了虚拟节点。——“虚拟节点”（virtualnode）是实际节点（机器）在哈希空间中的副本（replica）。一个实际节点（机器）对应若干个“虚拟节点”，这个对应的编号也成为“副本编号”，“虚拟节点”在哈希空间中按哈希值排列。以上面只部署了NODE1和NODE3的情况（NODE2被删除的图片）为例，之前的对象在机器上分布很不均匀。现在我们以2份（副本数）为例，使得整个哈希环中有4个虚拟节点，***对象映射关系图如下：根据上图映射对象关系：object1->NODE1-1，object2->NODE1-2，object3->NODE3-2，object4->NODE3-1。通过虚拟节点的引入，对象的分布比较均衡。那么在实际操作中，真实对象查询是如何进行的呢？对象从哈希到虚拟节点到实际节点的转换如下：“虚拟节点”的哈希计算可以使用对应节点的IP地址加上数字后缀。例如，假设NODE1的IP地址是192.168.1.100。在引入“虚拟节点”之前，计算缓存A的哈希值：Hash("192.168.1.100");引入“虚拟节点”后，计算“虚拟节点”节点NODE1-1和NODE1-2的哈希值：Hash("192.168.1.100#1");//NODE1-1Hash("192.168.1.100#2");//NODE1-2Java实现：publicclassShard{//S类封装了本机节点的信息，如名称、密码、ip、端口等privateTreeMapshards;//真实机器节点privatefinalintNODE_NUM=100;//每个机器节点关联的虚拟节点数publicShard(Listshards){super();this.shards=shards;init();}privatevoidinit(){//初始化一致性哈希环nodes=newTreeMap
