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和一个。

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

Answer 1

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

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

声明 #1:超过 S连选各i -th 服务器将被准确地选择 Wi次。

这是证明的草图。声明 #1 来自 声明 #2:在任何时候都不能选择具有负当前权重 ( CWi ) 的服务器。这又从声明 #3 得出:在每一步，所有当前权重的总和为 0。

声明 #3 显然是正确的:在算法的每一步我们添加每个 Wi到当前权重CWi并减去 S从被选中的那个。所以我们加减S .所以总和与第一步之前保持不变，即 0。

如果和始终为0，则意味着如果有一些负的当前权重，则必须有一个正的当前权重。显然，任何正的当前权重都是比负的更好的选择，因此我们证明了声明 #2。

回到声明 #1:假设一些 i -th 服务器已被选中Ni次，然后更多Wi .让我们看看上一次做出这样的选择。让它成为一些步骤编号 j ( 0 < j < S ，严格来说，您还需要考虑第一步选择的情况 j=0 ，但很明显，每个权重非零的服务器至少会被选择一次，因此“溢出”不会t发生在第一步)。在 j -th step 当前权重 CWi = j*Wi - (Ni-1)*S .自 Ni > Wi , 表示 Ni-1 >= Wi ;和 j < S .所以j*Wi < (Ni-1)*S或 CWi < 0 .而我们知道，当前权重为负的服务器是永远无法被选中的。自相矛盾。

现在假设一些 i -th 服务器的选择次数少于 Wi .由于服务器选择的总数是固定的，一些其他的j -服务器被选择的次数超过Wj我们已经知道那不可能发生。这完成了我们对声明 #1 的证明。

至于“分布也比较均匀”部分不是形式化的说法，无法证明。