文章目录

前言

一致性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的。


转载请注明出处http://www.bewindoweb.com/253.html | 三颗豆子
分享许可方式知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
重大发现:转载注明原文网址的同学刚买了彩票就中奖,刚写完代码就跑通,刚转身就遇到了真爱。
你可能还会喜欢
具体问题具体杠