如何从数学上证明Nginx平滑权重负载平衡算法

Question

请参阅Nginx提交的代码：https://github.com/phusion/nginx/commit/27e94984486058d73157038f7950a0a36ecc6e35

class Server {
String name;
int weight;
int curWeight;
Server(String name, int weight) {
super();
this.name = name;
this.weight = weight;
}
void add(int weight) {
curWeight += weight;
}
void subtract(int weight) {
curWeight -= weight;
}
@Override
public String toString() {
return String.format("%s=%2d", name, curWeight);
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getCurWeight() {
return curWeight;
}
}
class LoadBalance {
private int matched = -1;
private Server[] servers;
LoadBalance(Server... servers) {
super();
this.servers = servers;
}
Server get() {
int totalWeight = 0;
for (int i = 0, len = servers.length; i < len; i++) {
servers[i].add(servers[i].getWeight());
totalWeight += servers[i].getCurWeight();
if (matched == -1 || servers[matched].getCurWeight() < servers[i].getCurWeight()) {
matched = i;
}
}
System.out.println(Arrays.toString(servers) + " " + servers[matched].getName() + " selected");
servers[matched].subtract(totalWeight);
System.out.println(Arrays.toString(servers));
return servers[matched];
}
}
public class LoadBalanceTest {
public static void main(String[] args) {
LoadBalance loadBalance = new LoadBalance(new Server("a", 5), new Server("b", 1), new Server("c", 1));
for (int i = 0; i < 10; i++) {
loadBalance.get();
}
}
} 

当输入节点(a，b，c)的权重比为(5,1,1)时，输出结果如下：

[a= 5, b= 1, c= 1] a selected
[a=-2, b= 1, c= 1]
[a= 3, b= 2, c= 2] a selected
[a=-4, b= 2, c= 2]
[a= 1, b= 3, c= 3] b selected
[a= 1, b=-4, c= 3]
[a= 6, b=-3, c= 4] a selected
[a=-1, b=-3, c= 4]
[a= 4, b=-2, c= 5] c selected
[a= 4, b=-2, c=-2]
[a= 9, b=-1, c=-1] a selected
[a= 2, b=-1, c=-1]
[a= 7, b= 0, c= 0] a selected
[a= 0, b= 0, c= 0]
[a= 5, b= 1, c= 1] a selected
[a=-2, b= 1, c= 1]
[a= 3, b= 2, c= 2] a selected
[a=-4, b= 2, c= 2]
[a= 1, b= 3, c= 3] b selected
[a= 1, b=-4, c= 3]

对于每7次执行(权重和)，权重被重置为0，并且服务分配次数的比例也满足权重比例，并且分布也相对均匀的a、a、b、a、c、a和a。

但我不明白为什么。如何从数学上证明算法？

Answer 1

目前还不清楚您想要证明的属性到底是什么。关于权重的正确性不难证明。

假设我们有整数权重Wi和S。

声明#1:在连续选择S时，每个i服务器将被精确地选择Wi次。

这是证据的草图。声明#1来自声明#2：在任何时候都不能选择具有负电流权重(CWi)的服务器。这反过来又源于权利要求#3：在每一步，所有当前权重的总和为0。

权利要求#3显然是正确的：在算法的每一步，我们将每个Wi添加到当前权重CWi，并从所选择的权重中减去S。所以我们加上和减去S。因此，总和保持与第一步之前相同，即0。

如果总和始终为0，则意味着如果存在某个负电流权重，则必须存在一个正电流权重。显然，任何正电流权重都是比负电流权重更好的选择，因此我们已经证明了权利要求2。

回到权利要求1：假设某个i服务器被选择Ni次，多于Wi次。让我们看看上一次这样的选择是什么时候。设为某个步骤编号j(0 < j < S，严格来说，您还需要考虑在第一步j=0进行选择的情况，但很明显，每个权重为非零的服务器都将至少选择一次，因此在第一步不会发生"溢出")。在CCD_ 17阶，其当前权重为CCD_。由于Ni > Wi，意味着Ni-1 >= Wi；和CCD_ 21。所以CCD_ 22或CCD_。我们知道，一个具有负当前权重的服务器永远无法被选择。矛盾

现在假设某个i服务器的选择次数少于Wi。由于服务器选择的总数是固定的，其他一些j——服务器被选择的次数比Wj多，我们已经知道这不可能发生。这就完成了我们对权利要求1的证明。

至于">分布也是相对均匀的"部分，它不是一个形式化的陈述，因此无法证明。