最近看到的哈希算法，然后就有了一致性哈希算法，本文整理了网上搜集的资料，方便复习一致性的知识后面的哈希算法，这就是本文的由来《一文彻底读懂一致性哈希算法》；一致性哈希算法于1997年由麻省理工学院提出，是一种专门针对解决分布式缓存问题的哈希算法。在删除或添加服务器时，尽可能少地改变已有的服务请求和处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表（DistributedHashTable，DHT）中的动态伸缩问题。引言一致性哈希算法于1997年在论文《Consistent hashing and random trees》中提出，广泛应用于分布式系统中。一致性哈希是一种哈希算法。简单地说，当一个服务器被移除或增加时，该算法能够尽可能少地改变现有服务请求和处理请求服务器之间的映射关系，尽可能满足需求。单调性的需求，在普通的分布式集群中，服务请求和处理请求服务器可以是一一对应的，也就是说，服务请求和处理服务器之间的映射关系是固定的，某个请求是由固定服务器处理。这种方式无法对整个系统进行负载均衡，可能会导致部分服务器忙得无法处理新的请求，而另一些服务器则过于空闲，整个系统的资源利用率较低，而当分布式集群中，一台服务器宕机会直接导致部分服务请求无法处理。进一步改进可以使用哈希算法映射服务请求处理服务器之间的关系，达到动态分配的目的。服务请求通过哈希算法进行转换，转换后的结果在服务器节点值上取模，取模值为服务请求对应的请求处理服务器。这种方法可以处理节点故障。当分布式集群节点宕机时，可以通过哈希算法将服务请求重新分发到其他可用的服务器上。避免请求无法处理的情况。但是，这种方法的缺陷也很明显。如果服务请求对应的数据保存在服务器中，如果重新计算请求的哈希值，会导致大量请求迁移到不同的服务器，请求所需要的数据将失效，这种情况在分布式系统中是非常糟糕的。一个设计良好的分布式系统应该具有良好的单调性，即服务器的增减不会引起大量的哈希重定位，而一致性哈希正好可以解决这个问题。一致性哈希算法将整个哈希值空间映射成一个虚拟环，整个哈希空间的取值范围为0到2^32-1。整个空间按顺时针方向组织。0～2^32-1在零点方向重叠。接下来使用如下算法映射请求，使用hash算法计算出服务请求对应的hash值，然后根据hash值的位置沿圆圈顺时针查找，第一个遇到的服务器就是对应的处理请求服务器。添加新服务器时，受影响的数据只是新添加的服务器与其环空间中的上一个服务器之间的数据（即逆时针方向遇到的第一个服务器），其他不受影响。综上所述，一致性哈希算法对于节点的增减只需要对环空间中的一小部分数据进行迁移，具有良好的容错性和可扩展性。场景描述假设我们有三台缓存服务器用于缓存图片。我们将这三台缓存服务器的编号设置为服务器0、1、2，现在请求的图片平均缓存在这三台服务器上，这样他们就平均分担了缓存图片的请求。假设有30000张图片需要缓存，即平均每台服务器缓存10000张左右的图片。如果我们在三台服务器上平均缓存30000张图片，没有任何规律性，也能满足我们的需求，但是如果这样做的话，当我们访问某张图片时，最差的时候需要遍历三台服务器，从中找到我们需要的缓存30,000个缓存。这样的话，其实就失去了缓存的意义，并没有提升用户体验。所以，我们能做些什么？原方法是对图片名称进行哈希处理（假设图片名称唯一），对哈希结果和服务器数量进行取模运算，通过取模结果确定缓存应该存储在哪个服务器上，那么我们就可以通过下面的公式来判断图片应该存储在哪个服务器上hash(图片名称)%N因为图片的名称是不重复的，所以当我们对一张图片名称做相同的hash计算的时候，结果应该是不变的。如果我们有三台服务器，使用hash后的结果就是取三的余数，那么余数一定是0、1、2中的一个。是的，正好和我们的服务器编号一样，所以如果结果余数的结果为0，那么我们就可以将图片缓存到0号服务器上。反之，如果余数的结果为1，则缓存到1号服务器上。那么当我们访问任何一张图片时，只需要对图片名称进行上述操作就可以知道这张图片缓存在哪个服务器上了。如果该图片在相应的服务器上不存在，则证明没有缓存相应的图片，所以没必要再去其他服务器上查看。通过这种方式，平均可以在三台服务器上分布30000张图片，下次访问某张图片时，可以直接判断当前图片所在的位置。服务器，这样才能满足我们的需求。流程可以参考下图所示。这时候使用上面的hash算法会出现什么问题呢？试想一下，如果三台缓存服务器已经不能满足我们的缓存需求，那我们要不要加一台，那么缓存服务器的数量就会从3台变成4台，如果还是用上面的方法来缓存同一张图片，那么这个图片所在服务器的编号肯定和原来的一样。三个服务器的结果不一致。这种情况的后果是，当缓存服务器的数量发生变化时，所有缓存的位置也必须发生变化。也就是说，当服务器数量发生变化时，所有的缓存都会内部失效。当请求无法从缓存中读取数据时，会向后端服务器发送请求。同理，假设三台服务器中有一台发生故障无法缓存，那么我们需要设置当故障机器被移除后，此时响应的缓存服务器数量也会发生变化，之前缓存的图片就失去了意义。这时候大量图片缓存失效，造成缓存雪崩。这时候缓存无法分担压力，后端服务器就会承受压力，整个系统可能会不堪重负，所以我们不得不想办法防止这种情况发生，但是由于上面提到的哈希算法本身，当使用取模算法进行缓存时，这种情况是不可避免的，为了解决这些问题，一致性哈希算法应运而生。那么我们来回顾一下使用上面的hash算法会出现的问题：当缓存服务器的数量发生变化时，会造成大量的缓存失效和缓存雪崩，可能会增加后端服务器的压力而崩溃。当缓存服务器的数量发生变化时，几乎所有的缓存位置都会发生变化，那么如何减少受影响的缓存呢？其实这两个问题都可以使用一致性哈希算法来解决。下面我们继续了解一致性哈希算法的概念。第一，一致性哈希算法使用的是取模的方法，但是刚才的取模算法是对服务器的数量取模，所以我们只要不对服务器的数量取模，而是对一个常数取模，不就可以了吗？所以一致性哈希算法就是取2^32的模。我们把0-2的32次方想象成一个圆，就像一个时钟。时钟的圆可以想象成圆上有60个点，而我们的圆是由2^32个点组成的圆。示意图如下圆正上方的点代表0，0右边第一个点代表1，左边第一个点代表2^32-1，我们称0-2之间的环^32-1哈希环。下面，让我看看一致性哈希算法在这个圈子上是如何体现的。首先，我们还有三台服务器，分别是服务器A、服务器B、服务器C，那么在我们的生产环境中，我们对这三台服务器的IP地址进行hash，并使用hash后的结果对2^进行取模运算32，结果是服务器的Locationhash(服务器IP地址)%2^32这个公式计算出来的结果一定是0-2^32-1之间的一个数，我们用这个数来代表服务器A然后我们用同样的方法计算出服务器B，服务器C的位置表示如下。假设三个服务器的计算位置如上图所示（理想情况下是这样，但现实往往很无情）。好了，到这里，我们已经把服务器和哈希环绑定在一起了，接下来就是将数据绑定到哈希环上，接下来我们就用同样的方法把需要缓存的对象放到哈希环上或者按照刚才的例子缓存30000张图片。这时候我们还是用下面的公式hash(图片名)%2^32第一张图片映射的结果如下图（假设），那么它是怎么决定去哪个服务器的呢，上图会缓存在服务器A上，为什么会这样？因为从图片的位置开始，顺时针方向第一个遇到的服务器是服务器A，所以上面的图片会缓存在服务器A上，如下图，所以一致性哈希算法判断通过这个方法就可以了对象应该存储在哪个服务器上，即将缓存服务器和缓存对象绑定到哈希环后，从缓存对象开始，顺时针方向第一个遇到的服务器就是要存放缓存对象的服务器。由于缓存对象到服务器hash的值是固定的，所以在服务器不变的情况下，必须在固定的服务器中缓存一张图片，所以下次使用该图片时，只需使用相同的哈希算法计算该图片在哪个服务器上，然后直接去对应的服务器上获取即可。刚才的例子是一张图片，下面演示多张图片的一致性哈希的优势，图片1和图片2会缓存在服务器A上，图片3会缓存在服务器B上，图片4会缓存在服务器C上.经过上面的描述，我想你应该能理解一致性哈希的原理了，那么想一想，一致性哈希能解决上面两个问题吗？首先，第一个问题是，当服务器数量发生变化时，大量的缓存会同时失效，造成缓存雪崩，可能导致系统崩溃，使用一致性哈希算法能否避免这种情况问题？让我们看一下服务器B发生故障的假设。现在我们需要把B服务器移除，那么我们从hash开始把B服务器移除后，如下图，当B服务器没有故障，没有被移除的时候，图3应该缓存在B服务器上，但是当服务器B出现故障被移除，顺时针方向遇到图3第一个到达的服务器成为服务器C，所以此时图3缓存在服务器C中，也就是说如果服务器B出现故障，缓存位置图3的会改变。此时图片4仍然会缓存在服务器C中，图片1和图片2会缓存在服务器A中，移除前后不会影响服务器B。这就是哈希算法的优点。如果使用之前的hash算法，当服务器个数发生变化时，所有缓存对象都会发生变化，而使用一致性哈希算法后，如果服务器个数发生变化，并不是所有的缓存都会失效，只是部分缓存会失效，所以这种情况下不可能所有的缓存失效都同时集中在后端服务器上。哈希环的倾斜在引入一致性哈希时，我们理想地假设3台服务器均匀分布在哈希环上，如下图所示，但现实中往往不是这样。在实际使用中，服务器可能会映射如下。聪明的你一定想到，如果发生这种情况，缓存的对象可能会集中在一台服务器上的缓存中，这就是哈希环的倾斜，如下图。此时，如图所示，图片1、图片3、图片4、图片5都缓存在服务器A上，图片2缓存在服务器B上，服务器C上没有图片，也就是说，服务器资源使用不均。在最坏的情况下，如果此时服务器A发生故障，缓存失效对象将达到最大值，极端情况下，后端服务器也可能崩溃。这时，这种情况称为哈希环倾斜，那么如何防止哈希环倾斜呢？一致性哈希算法使用虚拟节点来解决这个问题。让我们看一下虚拟节点。或者按照我们说的，假设我们只有三台服务器。当我们将服务器映射到哈希环时，哈希环很可能会发生倾斜。当哈希环发生倾斜时，缓存往往会极度不平衡，分布在各个服务器上。聪明的你一定想到了，如果你想把缓存均衡的分布在三台服务器上，那么只要这三台服务器尽可能均匀的分布在hashring中，岂不是就足够了，但是真正的服务器资源只有3个，我们怎么凭空增加呢？没错，凭空增加服务器节点数量。由于没有冗余的真实物理服务器节点，我们只能将已有的物理节点虚拟化，也就是实际节点的虚拟副本。该节点被称为“虚拟节点”。加入虚拟节点后的哈希环如下。虚拟节点是哈希环上实际节点的副本。一个实际节点可以复制多少个虚拟节点？从上图可以看出，ABC三台服务器分别虚拟了一个虚拟节点。当然，您也可以根据需要虚拟化更多节点。此时我们只虚拟出一个节点进行绘图和演示。加入虚拟节点的概念后，缓存分布变得更加均匀。上图中，图1和图3缓存在服务器A上，图2和图4缓存在服务器B上，图5缓存在服务器C上。如果你还不放心的话，可以虚拟更多虚拟节点以减少哈希环倾斜的影响。虚拟节点越多，哈希环中的节点越多，缓存均匀分布的可能性就越大。因此，此时缓存对象已经均匀分布在哈希环上。如果发生服务器故障，受影响的缓存对象是故障服务器逆时针到第一个遇到的服务器之间的数据。受影响的缓存对象数量大大减少。好了，一致性哈希算法的原理就总结到这里了。如有错误，请赐教。参考链接百度百科维基百科参考博客参考博客参考链接收藏
