Как математически доказать алгоритм сглаживания веса нагрузки сглаживания 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 разболее 1031 *.Давайте посмотрим, когда в последний раз был сделан такой выбор.Пусть это будет некоторый номер шага j (0 < j < S, строго говоря, вам нужно также рассмотреть случай выбора на самом первом шаге j=0, но очевидно, что будет выбран каждый сервер с ненулевым весомхотя бы один раз, чтобы «переполнение» не могло произойти на первом этапе).На 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.

Что касается ", то распределение также относительно равномерно ", оно не является формализованным утверждением и поэтому не может быть доказано.