负载均衡策略之轮询策略

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

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

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

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', ...]

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

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 的实现）：

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 实现的平滑的带权重轮询的方法的更多细节可以阅读参考资料中列出的一些资料。