Hash算法

  • 可以通过Hash算法，进行简单的运算实现，相同的 key 打到相同的服务器上
  • 例如：group 服务器 = key % N 服务器个数
  • 如果机器数增加，就会导致缓存失效，导致雪崩等问题


一致性Hash负载均衡算法

整个 Hash 空间被构建成一个首尾相接的环，使用一致性 Hash 时需要进行两次映射

  • 给每个节点（集群）计算 Hash，然后记录它们的 Hash 值，这就是它们在环上的位置
  • 给每个 key 计算 Hash，然后沿着顺时针的方向找到环上的第一个节点，就是该 Key 存储对应的集群
  • 增加、删除节点的时候，会有少部分的缓存失效，打到下一个节点不是原来存储的节点


问题

Hash偏斜
  • 如果节点的数量很少，而 Hash 环空间很大（一般是0 ~ 2^32），直接进行一致性 Hash， 大部分情况下节点在环上的位置会很不均匀，挤在某个很小的区域。最终使得每个集群上存储的缓存数据量不一致，发生严重的数据倾斜
缓存雪崩
  • 如果每个节点在环上只有一个节点，那么当某个集群从环中消失时，原本负责的任务会全部交由顺时针方法的下一个集群处理。比如：A 节点由于压力过大而崩溃、会将全部任务交给 B 节点，最终服务器的压力就像滚雪球一样，越滚越大，最终导致雪崩


解决

引入虚拟节点
  • 扩展整个环上的节点数量，因此我们引入虚拟节点的概念。一个实际节点将会映射多个虚拟节点，这样 Hash 环上的空间分割就会变得均匀
  • 引入虚拟节点还会使得节点在 Hash 环上的顺序随机化，意味着当一个真实节点失效退出后，原来所承载的压力会均匀的分散到其他节点上


数据结构

  • 采用 TreeMap 红黑树的数据结构，因为会涉及根据 key 进行排序，查找效率高
  • SortedMap<Integer, String> sortedMap = treeMap.tailMap(): 找到所有大于该 Hash 值的部分
  • Integer position = sortedMap.firstKey(): 找到最近的节点


新增节点扩容

我们希望在扩容时新的集群能够较快的填充好数据并工作，但是从一个集群启动，到真正加入并可以提供服务之间还存在着不小的时间延迟。

高频 Key 预热
  • 负载均衡作为路由层，可以收集并统计每个缓存 Key 的访问频率，如果能够维护一份高频访问 Key 的列表，新的集群在启动的时候根据这个列表提前拉取对应 key 的缓存值进行预热，可以大大减少因为新增集群导致的key失效
  • 如果高频 Key 本身的缓存失效时间很短，预热时储存的 Value 在实际被访问到时可能已经被更新或者失效，处理不当会导致出现脏数据
历史 Hash 环保留
  • 新增节点后，如果对应的 key 缓存在新节点上还没有被加载，可以去原来的节点上尝试读取
  • 增加了缓存读取的时间，但是可以随意扩容多台服务器，而不会产生大面积的缓存失效


删除节点缩容

  • 熔断机制：缩容后，剩余各个节点上的访问压力都会所有增加，如果某个节点因为压力过大而宕机，就可能会引发连锁反应。因此作为兜底方案，应当给每个集群设立对应熔断机制来保护服务的稳定性


拓展

  • Redis 基于 HashSlot + P2P 算法
  • HashSlot：增加节点的时候，将之前节点的一部分移动到新节点上
  • P2P：去中心化访问。每个节点都保存完整的 HashSlot-节点的映射表，节点会通过 CRC(key) % 16384 计算出该节点存在于哪个 Slot 服务器中，会通过内部转发，Gossip 协议实现找到对应的服务器


参考