缘起

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

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

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

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

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

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

一致性Hash-LMLPHP

缓存穿透

一致性Hash-LMLPHP

介绍 

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

原理

引入Hash环

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

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

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

一致性Hash-LMLPHP

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

如:f(x2)存储在Node4

一致性Hash-LMLPHP

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

实现

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

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

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

使用场景

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

优缺点

优点:在分布式缓存中

  • 冗余少
  • 负载均衡
  • 过渡平滑
  • 存储均衡
  • 关键词单调

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

一致性Hash-LMLPHP

解决策略

虚拟节点

一致性Hash-LMLPHP

08-13 11:23