一致性Hash是分布式架构最重要最基础的东西，这里以分布式图片缓存服务器为例进行讲述。

原始问题：假设我们需要对一堆图片做缓存，缓存的图片放在了2台服务器上，当到来一个请求，应该如何知道请求的图片在哪台上面呢？

暴力遍历就不要去想了，否则缓存就没有意义了。一个自然的想法就是根据图片的名字做一个映射（Hash），将图片名字映射到0，1两个数字上面，例如有这样的映射函数：

$$f(\mathrm{图}\mathrm{片}\mathrm{名}\mathrm{称})=md5(\mathrm{图}\mathrm{片}\mathrm{名}\mathrm{称})\mathrm{\%}2$$

md5是一个典型的哈希函数，会产生128bit的值，模2后只可能是0或1，那么我们就根据这个值把图片存入0、1两台服务器，当请求过来，根据图片名称计算出值，就可以知道图片缓存放在第几号服务器了：

但假设现在我们图片太多了，需要再增加一台服务器分担压力，哈希函数必须更改成0、1、2映射，我们改为：

$$f(\mathrm{图}\mathrm{片}\mathrm{名}\mathrm{称})=md5(\mathrm{图}\mathrm{片}\mathrm{名}\mathrm{称})\mathrm{\%}3$$

理论上讲，会有(N-1)/N的缓存会失效，其中N是服务器的数量，例如上述图片缓存，除了0图片、1图片，其余图片的存放位置都变了，失效的缓存有 2/3 * 6 = 4张图片：

减少图片服务器数量造成的后果亦是如此——在同一个时刻将会有大量缓存同时失效，称为“缓存雪崩”。失效了就会直接去后端服务器取，大量的请求直接透过缓存打到后端服务器，后端服务器极有可能承受不住压力而接连崩溃，最终造成整个系统瘫痪。

所以出现进阶问题：当缓存服务器数量发生变化时，如何尽可能避免大量缓存同时失效？

答案就是一致性Hash。

一致性Hash原理

1、放置服务器

我们将服务器像图片一样也进行哈希，服务器的“图片名称”一般就使用固定IP地址，Hash取模也不再是服务器数量，而是$2^{32}$，Hash的方法也不局限于md5，用一个抽象的函数表示：

$$f(\mathrm{服}\mathrm{务}\mathrm{器}IP\mathrm{地}\mathrm{址})=Hash(\mathrm{服}\mathrm{务}\mathrm{器}IP\mathrm{地}\mathrm{址})\mathrm{\%}{2}^{32}$$

于是服务器被放置到了0到$2^{32}-1$某个数字对应的位置上去：

这里0到$2^{32}-1$是顺时针放置还是逆时针放置，网上的说法不一，虽然不影响算法，但统一会更好。我在原论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中没有找到相应的描述，于是采用了网上的主流选择：顺时针放置0到$2^{32}-1$。

为什么是$2^{32}-1$呢？因为第一次提出一致性Hash的论文是1997年发表的，那时候32位机器还是主流，$2^{32}-1$是最大的Integer。而现在64位早就普及了，完全可以将这个值扩大到$2^{64}-1$。

2、放置数据

我们将数据也按照相同的方式放到0到$2^{32}-1$的某个数字上去：

$$f(\mathrm{图}\mathrm{片}\mathrm{名}\mathrm{称})=Hash(\mathrm{图}\mathrm{片}\mathrm{名}\mathrm{称})\mathrm{\%}{2}^{32}$$

3、把数据放到服务器上

对于每个数据，从映射的位置开始，顺时针行走，放置到碰到的第一个服务器上。例如3、230将会放到0号图片服务器，232将会放到1号图片服务器，4175556547将会放到2号图片服务器：

这样一致性Hash就完成了。查找数据也是先映射、再顺时针行走找到第一台服务器。

一致性Hash如何缓解数据失效问题

假设现在1号服务器崩溃，图片232找不到1号服务器，顺时针行走的第一台服务器是2号服务器，于是232的缓存位置发生了改变，变为了2号：

而对于其他图片来说，缓存位置并没有发生变化，影响的数据量从（N-1）/ N 降为了 M，其中M是0号图片服务器到1号图片服务器之间的图片数量。需要重新获取的缓存数据量降低了，雪崩问题自然也就能够得到缓解。

Hash环偏斜和虚拟节点

前面讨论得太理想了，实际的服务器分布和数据分布很可能是这样的：

0、1、2三台服务器并没有均匀分布在环上，大量的图片数据都被放到了0号服务器上，而很少数据放到1、2号等其他图片服务器上，这种情况称之为Hash环偏斜。如果存放的是缓存则0号服务器崩溃就会引起缓存雪崩，如果存放的是数据则0号服务器就可能单点故障。

很自然可以想到，增加多台服务器就好了嘛。我们在Hash环上生成0、1、2三台服务器的虚拟节点：

具体的做法是，在服务器IP后面增加编号，每一台服务器产生多个Hash值，就能放置在0到$2^{32}-1$的多个位置上了。这样一来，顺时针行走能找到不同的服务器概率将会大大提高，避免了偏斜问题。虚拟的服务器节点数越多，偏斜出现的概率就越低。通常都需要设置32或以上的虚拟节点数目，我见过甚至有设置500的。