负载均衡策略之随机选择

前言

本文简单介绍一下随机选择这个负载均衡策略。

随机选择 (Random)

随机选择指的是从已有的后端列表中随机选择一个节点出来提供服务。 一种随机选择的方法是把所有的节点看做一个一个的点,并把这些点连起来排成一条直线, 随机选择就是在这条直线上随机选择一个点:

A - B - C

至于怎么做随机选择一个点,这个可以用各个编程语言官方实现自带的生成 指定区间(直线的开始到结尾区间)内的随机数的方法来生成一个随机数的方式来选择对应的点。

用 python 来表示就是:

>>> import random
>>> line = ['A', 'B', 'C']
>>> index = random.randint(0, len(line) - 1)
>>> choice = line[index]

带权重的随机选择 (Weighted Random)

实际使用中各个节点往往都带有不同的权重,即虽然是随机选择但是期望不同权重的节点被选择的几率不一样, 权重高的被选中的几率大,权重低的被选中的几率小。

我们还是可以把带权重信息的节点排成一条直线,不过这一次根据不同的权重把对应的节点重复不同的次数。 假设有三个节点 A、B、C 它们的权重分别是 3、2、4 ,那么就可以这样表示:

A1 - A2 - A3 - B1 - B2 - C1 - C2 - C3 - C4

然后还是随机选择一个点,因为每个节点根据权重重复了相应的次数,所以不同权重的节点被随机选中的概率也不一样, 就简单实现了带权重的随机选择。

同样的 python 表示:

>>> line = ['A', 'A', 'A', 'B', 'B', 'C', 'C', 'C', 'C']
>>> index = random.randint(0, len(line) - 1)
>>> choice = line[index]

改进

上面的按权重重复节点的方式有以下缺点:

  • 不支持权重信息包含小数的情况
  • 当权重的值很大时要重复很多次浪费资源

一种改进方法是:还是连成一条直线,不过这次是用各个节点的权重值组成一条直线,直线的不同区域属于不同的节点:

  A  B   C
|---|--|----|

然后取直线上的任意一个点,这个点属于直线上哪个节点的区域内就是选择了哪个节点:

  • 所有权重相加得到 S(其实就是直线的长度)
  • 从 [0, S) 的区间内取一个随机数 R(直线中随机选择一个点)
  • 遍历节点列表,把访问过的节点的权重相加得到 V,比较 V 与 R 的值,如果 V > R 当前节点即为选中的节点。(查找 R 在直线中的位置属于哪个节点所在的区域)

python 示例:

>>> import random
>>> weights = {
        'A': 3,
        'B': 2,
        'C': 4,
   }
>>> S = sum(weights.values())
>>> R = random.randint(0, S - 1)
>>> V = 0
>>> for node, weight in weights.items():
   V += weight
   if V > R:
       print(node)
       break

总结

本文简单记录了一下随机选择以及带权重的随机选择这两个负载均衡策略的实现方法, 当然还有其他的实现方法欢迎一起探讨。

参考资料

有任何意见欢迎在下方留言或者加我微信交流


Comments

comments powered by Disqus