11.redis cluster的hash slot算法和一致性 hash 算法、普通hash算法的介绍

分布式寻址算法

  • hash 算法(大量缓存重建)
  • 一致性 hash 算法(自动缓存迁移)+ 虚拟节点(自动负载均衡)
  • redis cluster 的 hash slot 算法

一、hash 算法


来了一个请求,首先对key计算 hash 值,然后对节点数取模。然后打在不同的 master 节点上。

  • 存在的问题

一旦某一个 master 节点宕机,所有新请求都会基于最新的剩余 master 节点数去取模,尝试去取数据,而取不到有效缓存,导致大量的流量涌入数据库。

11.redis cluster的hash slot算法和一致性 hash 算法、普通hash算法的介绍



二、一致性 hash 算法


将整个 hash 值空间组织成一个虚拟的圆环,整个空间按顺时针方向组织,下一步将各个 master 节点(使用服务器的 ip 或主机名)进行 hash。这样就能确定每个节点在其哈希环上的位置。

首先计算可以的hash 值,并确定此数据在环上的位置,从此位置沿环顺时针“行走”,遇到的第一个 master 节点就是 key 所在位置。

11.redis cluster的hash slot算法和一致性 hash 算法、普通hash算法的介绍

  • 优势

在一致性哈希算法中,如果一个节点挂了,受影响的数据仅仅是此节点到环空间前一个节点(沿着逆时针方向行走遇到的第一个节点)之间的数据,其它不受影响。增加一个节点也同理。

  • 存在的问题

一致性哈希算法在节点太少时,容易因为节点分布不均匀而造成缓存热点的问题。

  • 应对方案

为了解决这种热点问题,一致性 hash 算法引入了虚拟节点机制,即对每一个节点计算多个 hash,每个计算结果位置都放置一个虚拟节点。这样就实现了数据的均匀分布,负载均衡。



三、redis cluster 的 hash slot 算法(虚拟桶)


redis cluster 有固定的 16384 个 hash slot,对每个 key 计算 CRC16 值,然后对 16384 取模,可以获取 key 对应的 hash slot。

redis cluster 中每个 master 都会持有部分 slot,比如有 3 个 master,那么可能每个 master 持有 5000 多个 hash slot。

hash slot 让 node 的增加和移除很简单:

  • 增加一个 master,就将其他 master 的 hash slot 移动部分过去,

  • 减少一个 master,就将它的 hash slot 移动到其他 master 上去。

优势

移动 hash slot 的成本是非常低的。客户端的 api,可以对指定的数据,让他们走同一个 hash slot,通过 hash tag 来实现。

任何一台机器宕机,另外两个节点,不影响的。因为 key 找的是 hash slot,不是机器。

11.redis cluster的hash slot算法和一致性 hash 算法、普通hash算法的介绍

参考:https://www.jianshu.com/p/90b3de6288c6

上一篇:redis一致性hash算法理解


下一篇:SignalR系列目录