既然我们看到了一致的哈希，那么肯定有不一致的哈希。我们平时说的哈希算法就是不一致哈希。不用说，大家都不陌生，如果你不熟悉拉出一个hash，一般都是对一个大数取模，然后分散到不同的桶中。假设我们只有两个桶，里面有2、3、4、5这四个数，那么取模就是2分桶的结果是：这个时候我们认为桶太少，新加一个桶到哈希表扩展。这时候所有的数都需要对3取模，才能确定属于哪个桶。结果变成：可以看到在添加了一个新的桶之后，所有数字的分布都发生了变化，这意味着哈希表的每次扩容和收缩都会导致重新计算所有条目的分布，这在某些场景下是不可接受的。什么是一致性哈希？它是哈希的升级版本。为了解决分布式系统的负载均衡问题，可以使用哈希算法让固定的一部分请求落在同一台服务器上，这是根据服务器的个数来设计相应的哈希算法，这样每个服务器都可以固定处理一部分请求，并维护这些请求的信息，起到负载均衡的作用。但是，如果使用普通的哈希算法，则存在很大的问题，即算法的可扩展性很差。当新增或下线时，服务器数量发生变化，用户ID与服务器的映射关系会出现大量故障，导致大量请求迁移到服务器。比如我们的redis服务器还是5台，%5映射到对应的服务器后，服务器变成8台后，变成%8，可能大部分的hash值都变了，这就导致了映射它不是原始服务器。当服务器宕机时，负载均衡映射也会发生变化。服务器恢复后，负载均衡映射仍然会发生变化。上面的取模方法是对服务器个数取模，而一致性Hash算法是对2到32方取模。即一致性哈希算法将整个哈希空间组织成一个虚拟环。Hash函数的取值空间为0~2^32-1（32位无符号整数）。整个哈希环如下：整个环顺时针排列，环正上方的圆点代表0，0右边第一个圆点代表1，以此类推。第二步，我们使用Hash对每台服务器进行哈希。具体的，我们可以选择服务器的IP或者主机名作为关键字进行哈希，这样每台服务器就确定在哈希环中的某个位置。例如，我们有三台机器使用IP地址hash后在环空间的位置如下图所示：现在，我们使用如下算法定位到对应服务器的数据访问：使用相同的函数Hash计算出数据Key的hash值，并确定这个数据在环上的位置，从这个位置顺时针沿环搜索，遇到的服务器就是它应该定位的服务器。例如，现在有三个数据对象ObjectA、ObjectB、ObjectC。哈希计算后，环空间中的位置如下：根据共识算法，Object->NodeA,ObjectB->NodeB,ObjectC->NodeC一致性哈希算法的容错性和可扩展性现在，假设我们的节点Cdown了，从图中我们可以看出A和B不会受到影响，只有ObjectC对象会被重新定位到节点A。所以我们发现在一致性Hash算法中，如果某个服务器不可用，受影响的数据只是本服务器和它的环空间中上一个服务器之间的数据（这里是NodeC和NodeB之间的数据），其他的不受影响。如下图：还有一种情况，现在我们的系统中增加了一个服务器节点X，如图：此时对象ObjectA和ObjectB不受影响，只有对象C迁移到了新的节点X上。如前所述：一致性Hash算法对于节点的增减只需要对环空间中的一小部分数据进行搬迁，具有良好的容错性和可扩展性。数据倾斜问题在一致性Hash算法的服务节点过少的情况下，由于节点分布不均，很容易造成数据倾斜（大部分缓存对象都缓存在一台服务器上），具体示例如下：这时候，我们发现大量的数据都集中在节点A上，而节点B只有少量的数据。为了解决数据倾斜问题，一致性Hash算法引入了虚拟节点机制，即为每个服务器节点计算多个哈希，并为每个计算结果放置一个服务节点，称为虚拟节点。具体操作可以通过在服务器IP或者主机名后面加一个数字来实现，如图：数据定位算法不变，只需要增加一步：虚拟节点到实际点的映射.因此，加入虚拟节点后，即使在服务节点较少的情况下，也可以将数据均匀分布。既然一致性哈希有这么多好的特性，为什么主流的哈希都不一致呢？主要原因在于搜索效率。普通的哈希查询，一次哈希计算就可以找到对应的桶。该算法时间复杂度为O(1)，一致性哈希需要将排序好的桶组成一个链表，然后一路往下查找。k个桶的查询时间复杂度是O(k)，所以通常的hash还是使用不一致的实现。同样，一致性哈希之所以有用，是因为有一个想法和一个解决方案。我们在很多地方经常会涉及到这个思想，比如Redis集群。使用此解决方案可以更好地处理集群。分库分表等节点的动态增删也是一种思路
