平滑加权轮询负载均衡（轮询）算法

0. 引言

　　首先介绍下加权轮询负载均衡/调度算法（下面统称调度算法）的定义，来自维基百科：

Weighted round robin (WRR) is a network scheduler for data flows, but also used to schedule processes.

Weighted round robin is a generalisation of round-robin scheduling. It serves a set of queues or tasks. Whereas round-robin cycles over the queues or tasks and gives one service opportunity per cycle, weighted round robin offers to each a fixed number of opportunities, as specified by the configured weight which serves to influence the portion of capacity received by each queue or task. In computer networks, a service opportunity is the emission of one packet, if the selected queue is non empty.

　　简单的来说，加权轮询是一种网络调度算法，应用在数据流或者调度任务上。调度算法是从一系列消费者中选取一个来处理任务的算法，加权轮询调度算法将每一个消费者的消费能力绑定一个固定的权重，每个调度循环会遍历所有消费者，并且根据消费者的权重决定调度次数的比例。

　　加权轮询算法的实现包括CWRR(Classical WRR)和IWRR(Interleaved WRR)，CWRR会顺序遍历每个消费者，根据每个消费者的权重决定调度次数，遍历完一次后一个调度循环结束。下面我们主要介绍下IWRR，IWRR也是依次遍历每个消费者，但是每个消费者每次遍历只会调度一次，多次遍历后将所有消费者的权重决定的调度次数消耗完，这样一次调度循环结束，以下是IWRR的具体定义：

假设有n个消费者，编号依次为X_i，i的范围1~n，令W_i为X_i消费者的权重，为自然数，W_max=max{X_i}，IWRR的伪码如下：

for r in (1, 2, ..., Wmax)
    for i in (1, 2, ..., n)
        if r <= Wi
            dispatch(Xi)

在IWRR的具体实现中，需要保存当前遍历轮次r以及当前调度节点X_i。IWRR实现简单有效，但是存在一个问题，如果消费者权重差距较大的时候，比如有四个节点，权重依次为10，1，1，1，1，那么第一个节点会有9次调度连续发生，存在调度过于集中的现象。平滑加权算法就是为了解决IWRR调度过于集中的问题而提出的算法，nginx和dubbo都有应用该负载均衡/调度算法。

1. 算法简述

　　假设有n个消费者，编号依次为X_i，i的范围1~n，令W_i为X_i消费者的固定权重，为自然数，S为所有消费者固定权重之和，即S=sum(W_i)，CW_i为X_i的当前权重，初始值为0，CW_max表示当前权重的最大值，index记录该下标，算法伪码如下：

while true
    CWmax = 0
    index = 0
    for i in (1, 2, ..., n)
        CWi += Wi
        if CWi > CWmax
            CWmax = CWi
　　　　 index = i
    CWindex -= S
    dispatch(index)

假设有三个消费者A，B，C，固定权重分别为5，1，2，权重和为8，那么调度顺序如下表所示

当前权重CW_i	计算后CW_i（只做固定权重增加）	消费者
0，0，0	5，1，2	A
-3，1，2	2，2，4	C
2，2，-4	7，3，-2	A
-1，3，-2	4，4，0	A
-4，4，0	1，5，2	B
1，-3，2	6，-2，4	A
-2，-2，4	3，-1，6	C
3，-1，-2	8，0，0	A
0，0，0	5，1，2	A（下一轮）

这是一个平滑加权轮询算法的例子，我们可以看到，经过S次循环操作后，最后CW_i又变成了初始值0，而且每一次循环开始的时候CW_i之和都是等于0，而且每一个消费者被选取的次数等于它的权重W_i，作为权重最高的A也被B和C平均分割，避免某一个高权重的消费者聚集在一起，防止被大量连续调度。

更一般的，我们可以得到这样的结论：假设有n个消费者，编号依次为X_i，i的范围1~n，令W_i为X_i消费者的固定权重，为自然数，S为所有消费者固定权重之和，即S=sum(W_i)，令W_gcd为X_i的最大公约数，算法满足一下几个特性

每一次循环开始的CW_i之和等于0，在一轮的调度中，每个消费者被调度的次数等于W_i/W_gcd，经过S/W_gcd次的循环，一轮调度结束
对于任意一个消费者，都尽量被平均分割，量化的表述是，对于任何一个消费者i，如果经过连续的floor(W_i/(2*Wgcd))次被调度选择后，下一个循环必然不会调度消费者i

后面我们尝试来证明这些特性

2.算法证明

　　符号表示沿用上一章节，证明下面的结论（相比上一章的结论，其实就是通过最大公约数缩放，权重通过最大公约数缩小后满足下面的结论）：

每一次循环开始的CW_i之和等于0，在一轮的调度中，每个消费者被调度的次数等于W_i，经过S次的循环，一轮调度结束
对于任意一个消费者，都尽量被平均分割，量化的表述是，对于任何一个消费者i，如果经过连续floor(W_i/2)次被调度选择后，下一个循环必然不会调度消费者i

　　特性1证明（权重合理性）

　　对于每一个循环，都要完成两个步骤，第一，每个消费者自增W_i，第二，选择CW_i最大的消费者，扣减S

　　根据算法描述显然得到，每一次循环开始的CW_i之和等于0，也就是每一次循环结束的CW_i之和等于0，每次循环在完成第一步后CW_i之和等于S

　　假设总共执行S次的循环，消费者i在第t次循环前，假设已经被选中了W_i次，那么在完成当前循环的第一步后，CW_i = t*W_i-S*W_i= (t - S)*W_i，显然t <= S，那么CW_i <= 0，而此时CW_i 之和等于S，那么必然存在其他消费者的CW_i > 0，所以本次循环将不会选择消费者i

　　设每个消费者被选中M_i次，在总共S次的循环中，有M_i <= W_i，而M₁+M₂+...+M_n = S = W₁+W₂+...+W_n，因此M_i == W_i

　　经过S次循环后，CW_i均为0，一轮调度结束。一轮调度中，消费者i的权重Wi就表示了调用次数，权重合理性得证。

　　特性2证明（平滑性）

　　根据参考1的平滑性证明，可以得到，对于任何一个消费者i不可能连续Wi次都选中消费者i，本文的提出的特性2的论证待补充（还没想到怎么证明）

　参考1：https://tenfy.cn/2018/11/12/smooth-weighted-round-robin/

　参考2：https://zh.wikipedia.org/wiki/%E5%8A%A0%E6%9D%83%E8%BD%AE%E8%AF%A2%E7%AE%97%E6%B3%95