http://www.zsythink.net/archives/1182

场景描述

假设有三台缓存服务器用来缓存图片,三台服务器分别编号为0号,1号,2号.有3万张图片需要缓存,希望将这些图片均匀的分布到三台服务器上,以便平摊缓存的压力. 如果毫无规律的将这么多图片分配到三台服务器时,当再次查找的时候,就需要遍历这三台服务器的所有图片才能找到,这显然需要很长的时间,也就失去了缓存的意义.

最原始的做法就是进行节点取余,对缓存项的键进行哈希,哈希后使用取余的方法映射到三台服务器的其中一台,这样下次再次取的时候,只要服务器的个数没有变,图片的哈希值没有变,就直接知道了图片缓存在哪台服务器上.

缺点

缺点很明显,如果增加服务器或者减少服务器,再取余就有很大概率不在原来的服务器上,这样就需要把所有图片重新计算哈希,重新取余来找到该缓存的服务器,这显然是不能接受的.为了解决这个问题,创造了一致性哈希算法.

一致性哈希算法

其实，一致性哈希算法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而一致性哈希算法是对2^32取模.

首先，我们把二的三十二次方想象成一个圆，就像钟表一样，钟表的圆可以理解成由60个点组成的圆，而此处我们把这个圆想象成由2^32个点组成的圆，示意图如下：

圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1 .

回到前面的场景,那么，假设我们有3台缓存服务器，服务器A、服务器B、服务器C，那么，在生产环境中，这三台服务器肯定有自己的IP地址，我们使用它们各自的IP地址进行哈希计算，使用哈希后的结果对2^32取模，可以使用如下公式示意。

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

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

到目前为止，我们已经把缓存服务器与hash环联系在了一起，我们通过上述方法，把缓存服务器映射到了hash环上，那么使用同样的方法，我们也可以将需要缓存的对象映射到hash环上。

假设，我们需要使用缓存服务器缓存图片，而且我们仍然使用图片的名称作为找到图片的key，那么我们使用如下公式可以将图片映射到上图中的hash环上。

1
hash（图片名称） %  2^32

映射后的示意图如下，下图中的橘黄色圆形表示图片.

同时规定顺时针碰到的第一个服务器就是要缓存的服务器,所以上面的橙色代表的图片就应该缓存在A上.

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

一致性哈希的优点

一致性哈希可以解决前面增删服务器时所有图片的图片都乱的问题.

假设，有四张图片,服务器B出现了故障，我们现在需要将服务器B移除，那么，我们将上图中的服务器B从hash环上移除即可，移除服务器B以前和以后 示意图如下。

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

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

Hash环的倾斜

在实际的映射中，服务器的映射可能是不均衡的,那么就有可能很多都缓存在同一台服务器上.这就是哈希环的倾斜.

虚拟节点

如果想要均衡的将缓存分布到3台服务器上，最好能让这3台服务器尽量多的、均匀的出现在hash环上，我们狗仔一些虚拟节点,一个实际节点可以有好多虚拟节点.

浅蓝色的表示虚拟节点,这样就均衡了.