运维开发网

一致性Hash

运维开发网 https://www.qedev.com 2020-08-14 10:15 出处:51CTO 作者:嘿嘿可乐
我有一个图片存取服务,为了快速获取图片,我架起了3台缓存服务器,用简单的Hash映射决定图片存储在哪台缓存上。比如:f(x)%3=0存储在s0上f(x)%3=1存储在s1上f(x)%3=2存储在s2上某天,缓存负载过高,需要扩容1台,缓存数量由3变为4,那么按获取图片按公式:f(x)%n,很多会请求失败,这样会直接访问后台服务,给后台服务造成很大的压力,可能造成雪崩。是否有这样的算法,解决分布式缓

我有一个图片存取服务,为了快速获取图片,我架起了3台缓存服务器,用简单的Hash映射决定图片存储在哪台缓存上。比如:

f(x) % 3 = 0 存储在s0上

f(x) % 3 = 1 存储在s1上

f(x) % 3 = 2存储在s2上

某天,缓存负载过高,需要扩容1台,缓存数量由3变为4,那么按获取图片按公式:f(x) % n,很多会请求失败,这样会直接访问后台服务,给后台服务造成很大的压力,可能造成雪崩。

是否有这样的算法,解决分布式缓存中,解决简单Hash随缓存服务器伸缩,造成大面积缓存失效的问题

缓存穿透

回到顶部

介绍

一致性哈希算法在1997年由麻省理工学院提出,是一种特殊的哈希算法,目的是解决分布式缓存的问题,解决了简单哈希算法在分布式哈希表中存在的动态伸缩等问题

回到顶部

原理

引入Hash环

假如有3个节点,三个节点位于环的不同位置

具体的值,根据Hash值取余环的大小,顺时针方向找到最近的节点就是具体的存储节点

比如:f(x1)存储在Node1, f(x2)存储在node2, f(x3)存储在Node0

此时,如果加入了节点Node4,那么原来指向Node2的红色箭头部分,缓存会失效,变成存储在Node4

如:f(x2)存储在Node4

可以看到的效果是:当缓存服务器数量发生伸缩时,只有部分缓存失效

回到顶部

实现

圆环大小:232,由来:整数4B=4*8bit(32位无符号整形),值从0~232 -1

每个节点位置:hash(ip) % 232

存储的key位置:hash(key) % 232

回到顶部

使用场景

在分布式系统中一致性hash起着不可忽略的地位,无论是分布式缓存,还是分布式Rpc框架的负载均衡策略都有所使用。

回到顶部

优缺点

优点:在分布式缓存中

冗余少

负载均衡

过渡平滑

存储均衡

关键词单调

缺点:可能存在Hash偏斜,如

解决策略

回到顶部

虚拟节点

0

精彩评论

暂无评论...
验证码 换一张
取 消