负载均衡策略之有限负载一致性哈希

前言

本文简单介绍一下有限负载一致性哈希（Consistent Hashing with Bounded Loads）（或者叫有界负载一致性哈希、有负载界限/上限的一致性哈希）这个负载均衡策略。

之前介绍的 一致性哈希策略 有一个缺陷，那就是没有解决热点问题：当有部分资源是热点资源或者部分用户请求量比较大的时候，会出现部分节点需要处理大量请求（这些请求根据一致性哈希策略都选中了固定的部分节点），出现负载非常不均的情况，因为是一致性哈希所以这些请求没法分摊到其他节点上，导致出现持续的负载不均和热点问题。下面要介绍的 Consistent Hashing with Bounded Loads 就是一种解决这个问题的方法。

有限负载一致性哈希（Consistent Hashing with Bounded Loads）

有限负载一致性哈希（Consistent Hashing with Bounded Loads） 出自论文 Consistent Hashing with Bounded Loads ，主要思路是，根据当前负载情况对所有节点限制一个最大负载，在一致性哈希中对 hash 环进行查找时将跳过达到最大负载限制的节点，通过把过载的请求转移到其他节点上来解决热点和不均衡问题：

  • R: 当前所有节点的总负载（正在处理的总请求数）
  • T: 节点总个数
  • L: 当前所有节点的平均负载
  • L = R/T
  • ε: 一个参数用于表示在平均负载的基础上能够承受的额外负载上限，可以按照实际需求进行设置（根据 vimeo 分享的 经验 这个值推荐设置为 0.25~1）
  • M: 节点的最大负载上限
  • M = L*(1+ε) = R*(1+ε)/T
  • 一致性哈希中进行节点查找时，增加检查匹配的节点的负载（正在处理的请求数）是否达到负载上限 M 的操作，如果达到了上限则跳过当前节点继续往后查找。

通过上面可以发现 Consistent Hashing with Bounded Loads 结合了 最少连接策略 和一致性哈希 策略各自的优点，即平衡了负载又兼顾了一致性哈希，并且还可以通过调整转化为最少请求策略或一致性哈希策略：

  • 当 ε 的值是 0 的时候，就实现了最少连接策略的效果
  • 当 ε 的值是无穷大的时候，就是传统的一致性哈希策略。

权重问题

上面的方法是没有区分节点权重的，如果要支持节点权重的话，需要做一点改动:

  • R: 当前所有节点的总负载（正在处理的总请求数）
  • T: 所有节点的权重总和
  • L: 当前所有节点的平均负载（基于权重的平均负载）
  • L = R/T
  • W: 当前节点的权重值
  • ε: 一个参数用于表示在平均负载的基础上能够承受的额外负载上限。
  • M: 节点的最大负载上限
  • M = W*L*(1+ε) = W*R*(1+ε)/T
  • 一致性哈希中进行节点查找时，增加检查匹配的节点的负载（正在处理的请求数）是否达到负载上限 M 的操作，如果达到了上限则跳过当前节点继续往后查找。

可以看到主要区别是算平均负载的时候是基于节点的权重和来计算的，算负载上限的时候是按权重比来计算的。

总结

简单介绍了一下 Consistent Hashing with Bounded Loads ，更详细的内容请参考参考资料。

Comments