java如何从数学上证明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:在任何时候都不能选择当前权重为负的服务器（^{）。这又来自于#3：在每一步，所有当前权重之和都是0

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

如果总和始终为0，则意味着如果存在负电流权重，则必须存在正电流权重。显然，任何正电流权重都比负电流权重更好，因此我们证明了#2的说法

回到声明#1：假设第i个服务器被选择了Ni次，超过Wi。让我们看看上次这样的选择是什么时候。让它成为某个步骤号^ {< CD14> }（^ {CD15}}，严格地说，您还需要考虑第一步中的选择情况{{CD16}}，但是很明显，每个非零权重的服务器都会被选择至少一次，所以在第一步不能发生“溢出”。在第j步，它的当前权重CWi = j*Wi - (Ni-1)*S。因为Ni > Wi，它的意思是Ni-1 >= Wi；和j < S。所以j*Wi < (Ni-1)*S或CWi < 0。我们知道，永远无法选择当前权重为负的服务器。矛盾

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

至于“分布也相对一致”部分，它不是一个形式化的陈述，因此无法证明