一致性hash算法基本概念

一致性hash算法也是取模运算，一致性hash是对2^32取模。
首先把它想象成一个大圆，我们把这个圆想象成由 2^32 个点组成的圆。

圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1 ,
也就是说0点左侧的第一个点代表2^32-1 ，我们把这个由2的32次方个点组成的圆环称为hash环。
那么，一致性哈希算法与上图中的圆环有什么关系呢？
假设我们有3台缓存服务器，服务器A、服务器B、服务器C，那么，在生产环境中，这三台服务器肯定有自己的IP地址，我们使用它们各自的IP地址进行哈希计算，使用哈希后的结果对2^32取模，可以使用如下公式示意。

hash（服务器的IP地址） % 2^32

通过上述公式算出的结果一定是一个0到2^32-1 之间的一个整数，我们就用算出的这个整数，代表服务器，既然这个整数肯定处于0到2^32-1之间，那么，上图中的hash环上必定有一个点与这个整数对应，而我们刚才已经说明，使用这个整数代表服务器A，那么，服务器A就可以映射到这个环上，同理B C 也是一样用下图示意：

假设3台服务器映射到hash环上以后如上图所示（当然，这是理想的情况！）

假设，我们需要使用缓存服务器缓存图片，而且我们仍然使用图片的名称作为找到图片的key，那么我们使用如下公式可以将图片映射到上图中的hash环上。
hash（图片名称） % 2^32 ：就能在原中找到一个位置假设一下：就在这个位置

那么它需要到那个服务器呢。上图中的将会被缓存到服务器A上，因为从它的位置开始，沿顺时针方向遇到的第一个服务器就是A服务器，所以，上图中的将会被缓存到服务器A上。

一致性哈希算法就是通过这种方法，判断一个对象应该被缓存到哪台服务器上的，将缓存服务器与被缓存对象都映射到hash环上以后，从被缓存对象的位置出发，沿顺时针方向遇到的第一个服务器，就是当前对象将要缓存于的服务器，由于被缓存对象与服务器hash后的值是固定的，所以，在服务器不变的情况下，同一必定会被缓存到固定的服务器上，当下次想要访问它的时候，只要再次使用相同的算法进行计算，即可算出它被缓存在哪个服务器上，直接去对应的服务器查找对应的即可。

一致性hash算法的优点

如果简单的对服务器数量进行取模，那么当服务器数量发生变化时，会产生缓存的雪崩，从而很有可能导致系统崩溃，那么使用一致性哈希算法，能够避免这个问题吗？

假设，服务器B出现了故障，我们现在需要将服务器B移除，那么，我们将上图中的服务器B从hash环上移除即可

在服务器B未移除时，3应该被缓存到服务器B中，可是当服务器B移除以后，按照之前描述的一致性哈希算法的规则，3应该被缓存到服务器C中，因为从3的位置出发，沿顺时针方向遇到的第一个缓存服务器节点就是服务器C，也就是说，如果服务器B出现故障被移除时，3的缓存位置会发生改变。

但是，4仍然会被缓存到服务器C中，1与2仍然会被缓存到服务器A中，这与服务器B移除之前并没有任何区别，这就是一致性哈希算法的优点。
如果使用之前的hash算法，服务器数量发生改变时，所有服务器的所有缓存在同一时间失效了，而使用一致性哈希算法时，服务器的数量如果发生改变，并不是所有缓存都会失效，而是只有部分缓存会失效，前端的缓存仍然能分担整个系统的压力，而不至于所有压力都在同一时间集中到后端服务器上。
这就是一致性哈希算法所体现出的优点。

在增加服务器的时候：原图是ABC 三台服务器

在A-B 3的后边加入一台服务器D

此时3放在B里在查找的时候会先去D里面找找不到的时候会去B里面找

hash偏斜问题

在介绍时，我们理想化的将3台服务器均匀的映射到了hash环上。但是实际情况下可能会出现这种情况：可能还离得更近

如果服务器被映射成上图中的模样，那么被缓存的对象很有可能大部分集中缓存在某一台服务器上，如下图所示。

图中，1号、2号、3号、4号、6号均被缓存在了服务器A上，只有5号被缓存在了服务器B上，服务器C上甚至没有缓存任何，如果出现上图中的情况，A、B、C三台服务器并没有被合理的平均的充分利用，缓存分布的极度不均匀，而且，如果此时服务器A出现故障，那么失效缓存的数量也将达到最大值，在极端情况下，仍然有可能引起系统的崩溃，上图中的情况则被称之为hash环的偏斜，那么，应该怎样防止hash环的偏斜呢？

虚拟节点

虚拟节点”是“实际节点”(实际的物理服务器)在hash环上的复制品，一个实际节点可以对应多个虚拟节点。

从上图可以看出，A、B、C三台服务器分别虚拟出了一个虚拟节点，当然，如果你需要，也可以虚拟出更多的虚拟节点。引入虚拟节点的概念后，缓存的分布就均衡多了，上图中，1号、3号被缓存在服务器A中，5号、4号被缓存在服务器B中，6号、2号被缓存在服务器C中，如果你还不放心，可以虚拟出更多的虚拟节点，以便减小hash环偏斜所带来的影响，虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大。