没有合适的资源?快使用搜索试试~ 我知道了~
一致性Hash(Consistent Hashing)原理剖析1
需积分: 0 0 下载量 139 浏览量
2022-08-03
16:27:11
上传
评论
收藏 536KB PDF 举报
温馨提示
试读
11页
响的虚拟节点包括c31,c22,c11(顺时针查找到第个节点),这3个虚拟节点分别对应机器c3,c2,c1。即新加的台机器,同时影响到原有的3台机器。理想情况下
资源详情
资源评论
资源推荐
⼀致性Hash(Consistent Hashing)原理
剖析
引⼊
在业务开发中,我们常把数据持久化到数据库中。如果需要读取这些数据,
除了直接从数据库中读取外,为了减轻数据库的访问压⼒以及提⾼访问速
度,我们更多地引⼊缓存来对数据进⾏存取。读取数据的过程⼀般为:
图1:加⼊缓存的数据读取过程
对于分布式缓存,不同机器上存储不同对象的数据。为了实现这些缓存机器
的负载均衡,可以使⽤式⼦1来定位对象缓存的存储机器:
m = hash(o) mod n ——式⼦1
其中,o为对象的名称,n为机器的数量,m为机器的编号,hash为⼀hash函
数。图2中的负载均衡器(load balancer)正是使⽤式⼦1来将客户端对不同
对象的请求分派到不同的机器上执⾏,例如,对于对象o,经过式⼦1的计
算,得到m的值为3,那么所有对对象o的读取和存储的请求都被发往机器3执
⾏。
图2:如何利⽤Hash取模实现负载均衡
式⼦1在⼤部分时候都可以⼯作得很好,然⽽,当机器需要扩容或者机器出
现宕机的情况下,事情就⽐较棘⼿了。
当机器扩容,需要增加⼀台缓存机器时,负载均衡器使⽤的式⼦变成:
m = hash(o) mod (n + 1) ——式⼦2
当机器宕机,机器数量减少⼀台时,负载均衡器使⽤的式⼦变成:
m = hash(o) mod (n - 1) ——式⼦3
我们以机器扩容的情况为例,说明简单的取模⽅法会导致什么问题。假设机
器由3台变成4台,对象o1由式⼦1计算得到的m值为2,由式⼦2计算得到的m
值却可能为0,1,2,3(⼀个 3t + 2的整数对4取模,其值可能为0,1,2,
3,读者可以⾃⾏验证),⼤约有75%(3/4)的可能性出现缓存访问不命中的
现象。随着机器集群规模的扩⼤,这个⽐例线性上升。当99台机器再加⼊1
台机器时,不命中的概率是99%(99/100)。这样的结果显然是不能接受
的,因为这会导致数据库访问的压⼒陡增,严重情况,还可能导致数据库宕
机。
⼀致性hash算法正是为了解决此类问题的⽅法,它可以保证当机器增加或者
减少时,对缓存访问命中的概率影响减⾄很⼩。下⾯我们来详细说⼀下⼀致
性hash算法的具体过程。
⼀致性Hash环
⼀致性hash算法通过⼀个叫作⼀致性hash环的数据结构实现。这个环的起点
是0,终点是2^32 - 1,并且起点与终点连接,环的中间的整数按逆时针分
布,故这个环的整数分布范围是[0, 2^32-1],如下图3所⽰:
剩余10页未读,继续阅读
艾闻
- 粉丝: 31
- 资源: 302
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0