一致性Hash
一致性Hash是分布式架构最重要最基础的东西，这里以分布式图片缓存服务器为例进行讲述。
原始问题：假设我们需要对一堆图片做缓存，缓存的图片放在了2台服务器上，当到来一个请求，应该如何知道请求的图片在哪台上面呢？
暴力遍历就不要去想了，否则缓存就没有意义了。一个自然的想法就是根据图片的名字做一个映射（Hash），将图片名字映射到0，1两个数字上面，例如有这样的映射函数：
$$ f(图片名称) = md5(图片名称) \% 2 $$
md5是一个典型的哈希函数，会产生128bit的值，模2后只可能是0或1，那么我们就根据这个值把图片存入0、1两台服务器，当请求过来，根据图片名称计算出值，就可以知道图片缓存放在第几号服务器了：
但假设现在我们图片太多了，需要再增加一台服务器分担压力，哈希函数必须更改成0、1、2映射，我们改为：
$$ f(图片名称) = md5(图片名称) \% 3 $$
理论上讲，会有(N-1)/N的缓存会失效，其中N是服务器的数量，例如上述图片缓存，除了0图片、1图片，其余图片的存放位置都变了，失效的缓存有 2/3 * 6 = 4张图片：
减少图片服务器数量造成的后果亦是如此——在同一个时刻将会有大量缓存同时失效，称为“缓存雪崩”。失效了就会直接去后端服务器取，大量的请求直接透过缓存打到后端服务器，后端服务器极有可能承受不住压力而接连崩溃，最终造成整个系统瘫痪。
所以出现进阶问题：当缓存服务器数量发生变化时，如何尽可能避免大量缓存同时失效？
答案就是一致性Hash。
一致性Hash原理
1、放置服务器
我们将服务器像图片一样也进行哈希，服务器的“图片名称”一般就使用固定IP地址，Hash取模也不再是服务器数量，而是2^32，Hash的方法也不局限于md5，用一个抽象的函数表示：
$$ f(服务器IP地址) = Hash(服务器IP地址) \% 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(图片名称) = Hash(图片名称) \% 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的。
