负载均衡策略之轮询策略

前言¶

本文简单介绍一下轮询(Round Robin)这个负载均衡策略。

轮询选择 (Round Robin)¶

轮询选择指的是从已有的后端节点列表中按顺序依次选择一个节点出来提供服务。

一种轮询选择的方法是把所有的节点看做一个一个的点，并把这些点连起来组成一个圆，轮询选择就是在这个圆上按顺时针选择一个点。

可以通过用请求次数取模来实现这个顺时针选择的功能，比如用 python 来表示就是：

>>> nodes = ['A', 'B', 'C']
>>> choices = []
>>> n = 0
>>> for _ in range(10):
...     index = n % len(nodes)
...     choices.append(nodes[index])
...     n += 1
...
>>> choices
['A', 'B', 'C', 'A', 'B', 'C', 'A', 'B', 'C', 'A']

带权重的轮询选择 (Weighted Round Robin)¶

实际使用中各个节点往往都带有不同的权重，所以一般都需要实现带权重的轮询选择。权重高的被选中的次数多，权重低的被选中的次数少。

我们还是可以把带权重信息的节点排成一个圆，不过这一次根据不同的权重把对应的节点重复不同的次数。

然后还是顺时针选择一个点，因为每个节点根据权重重复了相应的次数，所以不同权重的节点被选中的次数也不一样并且选中的次数跟它本身的权重有关，这样就就简单实现了带权重的轮询选择。

同样的 python 表示（假设 A、B、C 的权重分别是 3、2、1）：

>>> nodes = ['A', 'A', 'A', 'B', 'B', 'C']
>>> choices = []
>>> n = 0
>>> for _ in range(10):
...     index = n % len(nodes)
...     choices.append(nodes[index])
...     n += 1
...
>>> choices
['A', 'A', 'A', 'B', 'B', 'C', 'A', 'A', 'A', 'B']

改进¶

上面的按权重重复节点的方式有一个明显的问题就是不够平滑：

权重高的节点会先被选中直至达到权重次数才会选择下一个节点或者说会出现请求连续的打在同一个节点上的情况，导致权重低的节点可能会处于空闲状态，没有平滑分配请求。

一种改进方法是：使用 nginx 中实现的一种平滑的带权重轮询的方法 [1]

A: 3, B: 2, C: 1
# 普通带权重轮询结果示例：
['A', 'A', 'A', 'B', 'B', 'C', 'A', 'A', 'A', 'B', 'B', 'C', ...]
# nginx 实现的平滑的带权重轮询的结果示例：
['A', 'B', 'A', 'C', 'B', 'A', 'A', 'B', 'A', 'C', 'B', 'A', ...]

这个方法的原文描述如下 [1] :

For edge case weights like { 5, 1, 1 } we now produce { a, a, b, a, c, a, a } sequence instead of { c, b, a, a, a, a, a } produced previously.

Algorithm is as follows: on each peer selection we increase current_weight of each eligible peer by its weight, select peer with greatest current_weight and reduce its current_weight by total number of weight points distributed among peers.

...

To preserve weight reduction in case of failures the effective_weight variable was introduced, which usually matches peer's weight, but is reduced temporarily on peer failures.

每个节点有三个属性，这三个属性的含义如下：

weight: 节点权重值，这个值固定不变。
effective_weight: 节点的有效权重。初始值等于 weight 。之所以有个 effective_weight 是为了在发现后端节点异常次数过多时（比如响应完成时发现选择的节点有问题，错误次数有点多）临时降低节点的权重。在轮询遍历选择节点时这个 effective_weight 的值会逐步增加恢复到 weight 的值，所以只是为了在异常时临时降低权重不会永久影响节点的权重（节点正常时会逐步恢复到原有的权重）。
current_weight: 节点当前权重。初始值为 0，后面会动态调整：
- 每次选取节点时，遍历可用节点，遍历时把当前节点的 current_weight 的值加上它的 effective_weight ，
- 同时累加所有节点的 effective_weight 值为 total 。
- 如果当前节点的 current_weight 值最大，那么这个节点就是被选中的节点，同时把它的 current_weight 减去 total
- 没有被选中的节点的 current_weight 不用减少。

整个过程用 python 简单的表示就是（也可以直接看 nginx 的实现 [2] ）：

class Node:
    def __init__(self, name, weight):
        self.name = name
        self.weight = weight
        self.effect_weight = weight
        self.current_weight = 0
        self.failed_number = 0

    def __repr__(self):
        return '<Node: {}>'.format(self.name)


class RB:
    max_fails = 10

    def __init__(self, nodes):
        self.nodes = nodes

    def select(self):
        best = None
        total = 0

        for node in self.nodes:
            node.current_weight += node.effect_weight
            total += node.effect_weight

            if node.effect_weight < node.weight:
                node.effect_weight += 1

            if best is None or node.current_weight > best.current_weight:
                best = node

        best.current_weight -= total
        return best

    def release(self, node, state):
        if state == 'failed':
            node.failed_number += 1
            if node.failed_number > self.max_faile:
                node.effect_weight -= node.weight / self.max_fails + 1
        else:
            node.failed_number = 0

        if node.effect_weight < 0:
            node.effect_weight = 0

效果:

>>> nodes = [Node('A', 3), Node('B', 2), Node('C', 1)]
>>> rb = RB(nodes)
>>> choices = []
>>> for _ in range(12):
...      choices.append(rb.select())
...
>>> choices
[<Node: A>, <Node: B>, <Node: A>, <Node: C>, <Node: B>, <Node: A>,
 <Node: A>, <Node: B>, <Node: A>, <Node: C>, <Node: B>, <Node: A>]

可以看到确实是比之前的 ['A', 'A', 'A', 'B', 'B', 'C', 'A', 'A', 'A', 'B', ...] 要平滑一些。

上面在介绍 effective_weight 时说这个属性主要用来临时降低节点权重，如果没有这个需求的话可以省去 effective_weight 直接用 weight 就好:

def select(self):
    best = None
    total = 0

    for node in self.nodes:
        node.current_weight += node.weight
        total += node.weight

        if best is None or node.current_weight > best.current_weight:
            best = node

    best.current_weight -= total
    return best

关于这个 nginx 实现的平滑的带权重轮询的方法的更多细节可以阅读参考资料中列出的一些资料。

总结¶

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

参考资料¶

[1]	(1, 2) Upstream: smooth weighted round-robin balancing. · nginx/nginx@52327e0

[2]	Upstream: smooth weighted round-robin balancing. · nginx/nginx@52327e0

前言¶

轮询选择 (Round Robin)¶

带权重的轮询选择 (Weighted Round Robin)¶

改进¶

总结¶

参考资料¶

Comments