文章目录

• 简介
• 实现
• 令牌轮询
• 令牌轮询算法
• 令牌轮询示例
• 最大权重
• 最大权重算法
• 最大权重示例
• 代码模拟

简介

在测试各种负载均衡时，总会看到WRR算法，为每个后端RS(real server)设置一个权重值，根据权重值比例来向RS转发。
比如如下负载均衡，后端rs1,rs2,rs3权重值分别为40,30,20, 客户端过来的请求，负载均衡按照2:3:4进行转发

40 30 20 客户端 负载均衡 RS1 RS2 RS3

实现

令牌轮询

北京车牌号摇号序号生成采用的这种算法，根据每个人的倍数生成序号池

令牌轮询算法

1. 初始时分别给rs相应比例的token
2. 按照token大小排序(有的实现这一步跳过)
3. 逐个选择，如果token为0则跳过
4. 如果全部都为0，则重新用原始比例填充

令牌轮询示例

1. 第一次，选中Rs1

第9次..................................................... 第8次..................................................... 第7次..................................................... 第6次..................................................... 第5次..................................................... 第4次..................................................... 第3次..................................................... 第2次..................................................... 第1次..................................................... 0 1 0 0 0 0 1 1 0 2 1 0 2 1 1 2 2 1 3 2 1 3 2 2 3 3 2 4 3 2 初始 重填 4 3 2

最大权重

这个算法是本次介绍的重点，也是nginx在wrr中使用的算法

最大权重算法

1. 初始时分别给rs相应比例的权重
2. 选择权重最大的RS，如果最大权重有多个，可以选择第一个，或者随机一个
3. 计算未选中的权重和
4. 选中的权重减去上一步的权重和
5. 未选中的加上自身权重
6. 重复步骤2

最大权重示例

1. 三个权重分别为2,3,4,
2. 第一次，选中权重最大rs3,未选中部分权重和为2+3=5，更新选中rs3: 4-5=-1更新未选中 rs1: 2+2=4，rs2: 3+3=6
3. 第二次，选中权重最大rs2,未选中部分权重和为2+4=6，更新选中rs2: 6-6=0更新未选中 rs1: 4+2=6，rs3: -1+4=3

第9次..................................................... 第8次..................................................... 第7次..................................................... 第6次..................................................... 第5次..................................................... 第4次..................................................... 第3次..................................................... 第2次..................................................... 第1次..................................................... +2 +3 -5 +2 -6 +4 -7 +3 +4 +2 +3 -5 +2 -6 +4 +2 +3 -5 -7 +3 +4 +2 -6 +4 +2 +3 -5 2 0 3 0 4 9 -2 6 5 5 3 1 3 0 6 1 6 2 -1 3 7 6 0 3 4 6 -1 2 3 4 初始 初始态

代码模拟

import copy
import collections
weights = [4,3,2]
reqs = sum(weights)
ws = copy.deepcopy(weights)
print("init weights:", ws)

summary = collections.defaultdict(int)
for round in range(9):
    choose = ws.index(max(ws))
    mv = sum([v for i,v in enumerate(weights) if i != choose ])
    ws = [v+weights[i] if i != choose else v-mv for i,v in enumerate(ws)]
    print(f'round {round+1}, choose: {choose+1}', ws)
    summary[weights[choose]] += 1

print(dict(summary.items()))

执行，输入如下：

init weights: [4, 3, 2]
round 1, choose: 1 [-1, 6, 4]
round 2, choose: 2 [3, 0, 6]
round 3, choose: 3 [7, 3, -1]
round 4, choose: 1 [2, 6, 1]
round 5, choose: 2 [6, 0, 3]
round 6, choose: 1 [1, 3, 5]
round 7, choose: 3 [5, 6, -2]
round 8, choose: 2 [9, 0, 0]
round 9, choose: 1 [4, 3, 2]
{4: 4, 3: 3, 2: 2}