学习后端必须掌握的算法：一致性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。

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。内容未经允许不得转载，或转载时需注明来源： 创新互联