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

有限负载一致性哈希（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 的操作，如果达到了上限则跳过当前节点继续往后查找。

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