什么是一致性hash算法
一、什么是hash算法?
以分布式缓存为例,假设现在有3台缓存服务器(S0,S1,S2),要将一些图片尽可能平均地分配到不同的服务器上,hash算法的做法是:
(1) 以图片的名称作为key,然后对其做hash运算。
(2) 将hash值对服务器数量进行求余,得到服务器编号,最后存入即可。
举个栗子:
csdn.jpg 需要存入, 我们就得到hash(csdn.jpg) = 5 -------> 5%3 = 2 得到数据存入S2
思考:
上面的算法好像可以把图片均衡地分配到不同的服务器,当获取数据的时候也可以根据同样的思路访问对应的服务器,避免全局扫描。但是,这个时候服务器进行了扩容,加入了S4,我们还能否正常获取数据呢?
假设还是根据同样的思路获取csdn.jpg,我们就会得到 hash(csdn.jpg)%4 = 1。显然,我们去S1是无法获取数据的,这个时候就有可能会引发缓存的血崩,大量的请求落到数据库上。
那应该怎么办呢?
二、一致性hash算法
一致性hash算法会建立一个有2^32个槽点(0 - 2^32-1)的hash环,假设现在有A、B、C三台服务器,以A为栗,会进行hash(A)%2^32,得到一个0 - 2^32-1之间的数,然后映射到hash环上,如图所示:
接下来,我们同样以csdn.jpg为例,我们照样算出hash(csdn.jpg)%2^32的值,然后映射到hash环上,然后以该点出发,顺时针遇到的第一个服务器,即为数据即将存储的服务器。
这时增加了服务器D又会发生什么事情呢?
如果这个时候在A - C之间插入了服务器D,请求获取getKey(csdn.jpg)时,顺时针获得的服务器是D,从D上获取数据理所当然会失败,因为数据存在A上缓存。这样看缓存好像还是失效了。
那么做成hash环有什么好处呢?
虽然增加了节点D后,csdn.jpg的缓存失效了,但是,分布在 A-B,B-C 以及 D-A上面的数据仍然有效,失效的只是C-D段的数据(数据存在A节点,但是顺时针获取的服务器是D)。这样就保证了缓存数据不会像hash算法那样大面积失效,同样起到减轻数据库压力的效果。
思考:
既然hash环能保证在服务器节点发生变化的情况下,数据只会部分失效,那一致性hash是不是就结束了呢?
什么是hash偏斜?
A、B、C服务节点,如果像上图那样接近于将hash环平均分配那固然理想,但是如果他们hash值十分相近,会发生什么呢?
上图这种情况称之为hash偏斜,在这种情况下,大部分数据都会分部在C-A段,这个时候去A节点被删除,会有大量请求涌向B节点,给B节点带来巨大的压力,同时这部分缓存也会全部失效,有可能引发缓存雪崩。
怎么办呢?
这个时候我们可能会想到一句老话: 人多力量大。
如果我们的节点足够多,就应该可以防止服务器节点分布不均的问题了。
所以引入了虚拟节点的概念,以A节点为例,虚拟构造出(A0,A1,A2....AN),只要是落在这些虚拟节点上的数据,都存入A节点。读取时也相同,顺时针获取的是A0虚拟节点,就到A节点上获取数据,这样就能解决数据分布不均的问题。如图所示:
虚拟节点读写大概流程为: 数据读写 -> 虚拟节点 -> 真实节点 -> 读写
至此,一致性hash算法已经介绍完毕~ 感谢阅读
END-
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfihbj
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01