一致性Hash

bluewelkin 2020-08-17

我有一个图片存取服务,为了快速获取图片,我架起了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偏斜,如

解决策略

回到顶部
虚拟节点

相关推荐

Cheetahcubs / 0评论 2020-02-13