加权轮询算法(wrr)，这个考点，概率有点高！

原创：小姐姐味道（微信公众号ID：xjjdog），欢迎分享，转载请保留出处。

临近年关，招聘的和找工作的却忙的热火朝天，互相拿捏着。

今朝不同往昔，卖惨成为主流旋律，也加剧了从业人员的焦虑。很多人，工作了十来年没碰过算法，如今却不得不像蹲自习室一样，捧起大头书死命去看。

呜呼哀哉。

最近和不少参加面试的小伙伴交流了一下，发现出现了一个比较高频的算法题。不同于链表、树、动态规划这些有规律可循的算法题，加权轮询算法有很多小的技巧，在实际应用中也比较多。最平滑的Nginx轮询算法，如果你没有见过的话，那自然是永远无法写出来的。

所谓的加权轮询算法，其实就是Weighted Round Robin，简称wrr。在我们配置Nginx的upstream的时候，带权重的轮询，其实就是wrr。

upstream backend {
ip_hash;
server 192.168.1.232 weight=4;
server 192.168.1.233 weight=3;
server 192.168.1.234 weight=1;
1. 核心数据结构

为了方便编码，对于每一个被调度的单元来说，我们抽象出一个叫做Element的类。其中，peer指的是具体的被调度资源，比如IP地址，而weight指的是这个资源的相关权重。

public class Element {
protected String peer;
protected int weight;

public Element(String peer, int weight){
this.peer = peer;
this.weight = weight;
}
}


那么我们具体的调度接口，将直接返回peer的地址。

public interface IWrr {
String next();


我们将在代码中直接测试IWrr接口的调度情况。比如，分配7、2、1权重的三个资源，其测试代码如下。

Element[] elements = new Element[]{
new Element("A", 7),
new Element("B", 2),
new Element("C", 1),
int count = 10;
IWrr wrr = new WrrSecurityLoopTreeMap(elements);
for (int i = 0; i < count; i++) {
System.out.print(wrr.next() + ",");
System.out.println();


上面的代码调用了10次接口，我们希望代码实现，将以7，2，1的比例进行调度。

2. 随机数版本

最简单的方式，就是使用随机数去实现。当然，只有在请求量比较大的情况下，随机分布才会向7、2、1的比例逼近。这通常都没什么问题，比如SpringCloud的Robion组件，就是使用随机轮询的方式。

我们首先计算总的权重值，记作total，然后每次调用都取total区间的随机数，再依次遍历所有的权重数据。

next方法的时间复杂度，在最坏的情况下是O(n)。

随机调度获取的调用顺序也是随机的，对类似于微服务节点轮询这种场景，比较友好。但对于一些调用量比较小的服务，可能有些节点就会被饿死，毕竟是随机数嘛。

public class WrrRnd implements IWrr {
final int total;
final Element[] elements;
final Random random = new SecureRandom();

public WrrRnd(Element[] elements) {
this.total = Arrays.stream(elements)
.mapToInt(ele -> ele.weight)
.sum();

this.elements = elements;
}

@Override
public String next() {
final int n = elements.length;
int index = n - 1;
int hit = random.nextInt(total);

for(int i = 0; i < n; i++){
if(hit >= 0) {
hit -= elements[i].weight;
}else{
index = i - 1;
break;
}
}

return elements[index].peer;
}
}
3. 递增版本

随机数大多数情况下是美好的，但有时候我们确实需要非常准确的调度结果。这种情况下，使用一个原子递增的计数器，去存放当前的调度次数，是常见的方式。

所以逻辑就比较清晰了，我们可以直接使用原子类去实现这个计数器。

代码与上面的类似，只不过在获取hit变量的时候，我们把随机数的获取方式，替换成自增的方式。

//原来的
int hit = random.nextInt(total);


现在的。当然，它还有一个小小的问题，那就是int的数值很可能会被用完了，这个小问题在下面的代码一并修复。

int hit = count.getAndIncrement() % total;
4. 红黑树版本

不论是随机数还是按照顺序轮询，它们的时间复杂度都是比较高的，因为它每次都需要遍历所有的配置项，直到达到我们所需要的数值。要想提高其运行效率，我们可以借助于Java的TreeMap，空间上换时间。

下面是一个线程安全版本的实现方法，使用物理上的存储来解决时间上的耗费。TreeMap底层是红黑树，实现了根据Key的大小进行排序的功能，它的平均时间复杂度是log(n)。

我们把上面代码的逻辑，直接转化成TreeMap存储，就可以通过ceilingEntry方法获取最近的调度单元。

在并发上面，直接使用了CAS原语。这时候，我们不再自增，而是将最大值严格控制在total以下，通过自旋来处理冲突。

public class WrrSecurityLoopTreeMap implements IWrr {
final int total;
final AtomicInteger count = new AtomicInteger();
final TreeMap pool = new TreeMap<>();

public WrrSecurityLoopTreeMap(Element[] elements) {
int total = 0;
for (Element ele : elements) {
total += ele.weight;
pool.put(total - 1, ele);
}
this.total = total;
}

@Override
public String next() {
final int modulo = total;
for (; ; ) {
int hit = count.get();
int next = (hit + 1) % modulo;
if (count.compareAndSet(hit, next) && hit < modulo) {
return pool.ceilingEntry(hit).getValue().peer;
}
}
}
}
5. LVS版本

上面的这些版本（除了随机），有一个最大的问题，就是调度不均衡。当我们的比例是7、2、1，它的调度结果是A,A,A,A,A,A,A,B,B,C,。

我们希望调度能够平滑一些，而不是一股脑的压在A节点上。下面是LVS代码里的一个算法，采用的是最大公约数来实现轮询。虽然它不能实现非常平滑的轮询，但起码比上面的自增式代码强多了。

这段代码的执行过程就包含两部分，一部分是计算最大公约数gcd，一部分是轮询算法。

对于7、2、1的权重，它的调度结果是A,A,A,A,A,A,B,A,B,C,，相比较按顺序轮询的方式，有了一些改善。当这些节点的权重数值差不多的时候，LVS版本会表现出较好的负载均衡效果。

我们首先在构造函数里，算出最大公约数的gcd。然后，基于这个最大公约数，进行轮询算法的运算。

根据介绍的地址，可以很容易写出对应的算法。

http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Scheduling


下面是具体的代码。

public class WrrGcd implements IWrr {
final int gcd;
final int max;
final Element[] elements;

public WrrGcd(Element[] elements) {
Integer gcd = null;
int max = 0;
for (Element ele : elements) {
gcd = gcd == null ? ele.weight : gcd(gcd, ele.weight);
max = Math.max(max, ele.weight);
}
this.gcd = gcd;
this.max = max;
this.elements = elements;
}

int i = -1;
int cw = 0;
@Override
public String next() {
for (; ; ) {
final int n = elements.length;
i = (i + 1) % n;
if (i == 0) {
cw = cw - gcd;
if (cw <= 0) {
cw = max;
if (cw == 0) {
return null;
}
}
}
if(elements[i].weight >= cw){
return elements[i].peer;
}
}
}

private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
6. Nginx版本

nginx这个版本就更上一层楼，可以达到A,A,B,A,A,C,A,A,B,A,的效果。在保证准确的权重前提下，实现了调用尽量的分散。

这个算法比较巧妙，可以说是非常天才的算法。如果你没有接触过的话，是绝对写不出来的。

虽然算法比较简单，但要证明算法的准确性却不是一件容易的事情。证明的具体过程可以参考以下链接。

https://tenfy.cn/2018/11/12/smooth-weighted-round-robin/


看我们的代码，封装了一个叫做Wrr的类。这个类在原来权重的基础上，增加了一个当前的权重值current。current没次调用都会改变。

在每一轮调用中，都会在current上加上对应节点的weight值，然后选择current值最大的那一个，当作本轮的调度节点。

被选中的节点，将会减去所有的权重值total，然后进行下一次调度。唯一的问题是，当节点比较多的时候，它的时间复杂度总是O(n)，执行效率上要打一些折扣。

public class WrrSmooth implements IWrr {
class Wrr {
Element ele;
int current = 0;
Wrr(Element ele){
this.ele = ele;


final Wrr[] cachedWeights;

public WrrSmooth(Element[] elements) {
this.cachedWeights = Arrays.stream(elements)
.map(Wrr::new)
.collect(Collectors.toList())
.toArray(new Wrr[0]);
}

@Override
public String next() {
int total = 0;
Wrr shed = cachedWeights[0];

for(Wrr item : cachedWeights){
int weight = item.ele.weight;
total += weight;

item.current += weight;
if(item.current > shed.current){
shed = item;
}
}
shed.current -= total;
return shed.ele.peer;
}
}


Nginx的这个版本，写法非常简单。建议好好理解，掌握红黑树和Ningx版本的写法即可。

End

一般的面试，其实集中在随机数和递增版本上，当然红黑树这一版也可以考虑一下。至于LVS和Nginx的这些写法，如果以前没有碰到过，大概率是写不出来的，除非你是天才。

但是如果你是天才，还用得着这样粗俗的面试么？

作者简介：小姐姐味道 (xjjdog)，一个不允许程序员走弯路的公众号。聚焦基础架构和Linux。十年架构，日百亿流量，与你探讨高并发世界，给你不一样的味道。我的个人微信xjjdog0，欢迎添加好友，进一步交流。

3.
4.
5.
6.