一、工作流程
1.1：实现加权轮询的方式
WRR叫做加权轮询算法，相比普通的轮询算法，它支持给每个节点配置权重，权重越大，越容易被访问，且符合轮询的特点。
一般情况下，我们会按照下方逻辑设计算法的实现：
如图1中流程执行完毕，接下来就跟普通RR算法一样做轮询即可，保证每个虚拟节点都被均匀访问到，而被访问概率也与权重值成正比。
但正如上图所说，乱序那一步是比较容易出问题的，可能会出现下面这样的情况：
1.2：SWRR算法
如果不足够散列，意味着轮询窗口内访问不足够均匀，基于此，便有了SWRR算法，它是一种可以平滑访问的、nginx默认的加权轮询算法，相比普通加权轮询，它在轮询访问节点时表现的更加散列。
在该算法中，每个节点有如下基本属性：
结合上面几个属性，来看下SWRR算法下，选举流程是怎样的：
首先是Node信息的初始化，按照图3的描述，每个Node在初始化的那一刻，effective_weight跟它的weight值相等，current_weight都为0：
然后开始pick，来看下pick的流程：
每次pick，都会经历上面的流程，这样来模拟一下这个轮询过程，假设现在有三个节点，节点名为a、b、c，对应权重值为：4:2:1，结合上面的pick流程，它的轮询流程如下：
上表为SWRR两次轮询的执行效果，可以看到pick出来的节点非常散列，而且每一次轮询得到的顺序是一致的，且每次轮询完成后，各项指标会还原为初始状态，以此类推，它的数学推导&证明请参考：Nginx SWRR 算法解读
1.3：SWRR存在的问题
上面的按照SWRR模拟的pick过程很完美，但该算法依然有一些漏洞，请参考：QPS 比 Nginx 提升 60%，阿里 Tengine 负载均衡算法揭秘
简单来理解，SWRR有以下缺陷：
- 算法复杂度为
O(N)，而且在pick节点时为了保证准确性，需要加锁
- 如果
刷新某节点的权重值，会导致该节点流量值瞬间暴增
第一点很好理解，因为每次都要选出current_weight最大的那个节点，必然要循环一次所有的节点。第二点存疑，参考上方文章评论区：
我在自测过程中，在算法启动后动态调整weight和effective_weight的值是不存在这个问题的，访问依旧均匀，并不会出现大规模pick到加权节点上的情况，个人猜测他们可能是在探听到weight变化后，把对应节点的current_weight也给改掉了才可能出现这个问题。
1.4：优化SWRR
按照上方文章里描述，我们现在需要将O(N)的算法变成O(1)，这样不仅仅性能迅速提升，pick时也无需加锁，对于使用SWRR算法来说是个不错的选择，那如何实现O(1)呢？表1告诉我们，按照算法pick出的节点是有规律性的，以权重和为模来界定一次轮询，而每个轮询窗口内的节点散列顺序完全一致，那么这样优化起来就简单多了：
经过上图里展示的方法，做一层转换，即可达成O(1)成就，这样在高QPS时的效率会显著提升，后续如果有节点信息变更，只需要以同样的方式，刷新虚拟节点有序集合即可。
二、实现
这里采用JAVA语言来实现：
代码块11
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| public class WrrLoadBalancer {
private int effectiveWeightSum;
private Node[] virtualNodes;
private AtomicLong pointer;
public WrrLoadBalancer(Node... nodes) {
refreshVirtual(nodes);
}
public void refreshVirtual(Node... nodes) {
int total = 0;
for (Node node : nodes) {
total += node.getEffectiveWeight();
}
int newEffectiveWeightSum = total;
Node[] newVirtualNodes = new Node[newEffectiveWeightSum];
for (int i = 0; i < newEffectiveWeightSum; i++) {
newVirtualNodes[i] = pickInit(newEffectiveWeightSum, nodes);
}
this.virtualNodes = newVirtualNodes;
this.effectiveWeightSum = newEffectiveWeightSum;
pointer = new AtomicLong((long) (Math.random() * effectiveWeightSum));
}
public Node pickInit(int effectiveWeightSum, Node... nodes) {
Node picked = null;
for (Node node : nodes) {
node.refreshCurrentWeight();
if (picked == null) {
picked = node;
} else {
if (picked.getCurrentWeight() < node.getCurrentWeight()) {
picked = node;
}
}
}
if (picked == null) {
throw new IllegalArgumentException("wrr pick error!");
}
return picked.pick(effectiveWeightSum);
}
public Node pick() {
return virtualNodes[(int) (pointer.incrementAndGet() % effectiveWeightSum)];
}
public static class Node {
private final String host;
private final AtomicInteger weight = new AtomicInteger();
private final AtomicInteger effectiveWeight = new AtomicInteger();
private final AtomicInteger currentWeight = new AtomicInteger();
public Node(String host, int weight) {
this.host = host;
this.weight.set(weight);
this.effectiveWeight.set(weight);
}
public Node pick(int total) {
try {
return this;
} finally {
this.currentWeight.addAndGet(total * -1);
}
}
public void refreshCurrentWeight() {
this.currentWeight.getAndAdd(this.effectiveWeight.get());
}
public int getEffectiveWeight() {
return this.effectiveWeight.get();
}
public int getCurrentWeight() {
return this.currentWeight.get();
}
public String getHost() {
return host;
}
}
}
|
四、算法验证
算法的验证会以实际压测的方式来进行，请前往：WRR算法验证实验