学习后端必须掌握的算法:一致性Hash

2021-02-09    分类: 网站建设

原始问题:假设我们需要对一堆图片做缓存,缓存的图片放在了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。

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就完成了。查找数据也是先映射、再顺时针行走找到第一台服务器。


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


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

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


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

分享名称:学习后端必须掌握的算法:一致性Hash
网站地址:/news/100085.html

成都网站建设公司_创新互联,为您提供网站排名网站设计公司品牌网站建设网站策划企业建站服务器托管

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

网站托管运营