# 负载均衡策略之轮询策略

## 轮询选择 (Round Robin)¶

```>>> 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)¶

```>>> 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']
```

### 改进¶

```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 不用减少。

```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>]
```

```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
```