nginx使用的平滑权重轮询算法介绍以及原理分析。

轮询调度

轮询调度非常简单，就是每次选择下一个节点进行调度。比如{a, b, c}三个节点，第一次选择a， 第二次选择b，第三次选择c，接下来又从头开始。

这样的算法有一个问题，在负载均衡中，每台机器的性能是不一样的，对于16核的机器跟4核的机器， 使用一样的调度次数，这样对于16核的机器的负载就会很低。这时，就引出了基于权重的轮询算法。

基于权重的轮询调度是在基本的轮询调度上，给每个节点加上权重，这样对于权重大的节点， 其被调度的次数会更多。比如a, b, c三台机器的负载能力分别是4:2:1，则可以给它们分配的权限为4, 2, 1。 这样轮询完一次后，a被调用4次，b被调用2次，c被调用1次。

对于普通的基于权重的轮询算法，可能会产生以下的调度顺序{a, a, a, a, b, b, c}。

这样的调度顺序其实并不友好，它会一下子把大压力压到同一台机器上，这样会产生一个机器一下子很忙的情况。 于是乎，就有了平滑的基于权重的轮询算法。

所谓平滑就是调度不会集中压在同一台权重比较高的机器上。这样对所有机器都更加公平。 比如，对于{a:5, b:1, c:1}，产生{a, a, b, a, c, a, a}的调度序列就比{c, b, a, a, a, a, a} 更加平滑。

nginx平滑的基于权重轮询算法

nginx平滑的基于权重轮询算法其实很简单。算法原文 描述为：

Algorithm is as follows: on each peer selection we increase current_weight of each eligible peer by its weight, select peer with greatest current_weight and reduce its current_weight by total number of weight points distributed among peers.

算法执行2步，选择出1个当前节点。

1. 每个节点，用它们的当前值加上它们自己的权重。
2. 选择当前值最大的节点为选中节点，并把它的当前值减去所有节点的权重总和。

例如{a:5, b:1, c:1}三个节点。一开始我们初始化三个节点的当前值为{0, 0, 0}。 选择过程如下表：

我们可以发现，a, b, c选择的次数符合5:1:1，而且权重大的不会被连接选择。7轮选择后， 当前值又回到{0, 0, 0}，以上操作可以一直循环，一样符合平滑和基于权重。

一个go版本实现

type Node struct {
    Name    string
    Current int
    Weight  int
}

func SmoothWrr(nodes []*Node) (best *Node) {
    if len(nodes) == 0 {
        return
    }
    total := 0
    for _, node := range nodes {
        if node == nil {
            continue
        }
        total += node.Weight
        node.Current += node.Weight
        if best == nil || node.Current > best.Current {
            best = node
        }
    }
    if best == nil {
        return
    }
    best.Current -= total
    return
}

func example() {
    nodes := []*Node{
        &Node{"a", 0, 5},
        &Node{"b", 0, 1},
        &Node{"c", 0, 1},
    }

    for i := 0; i < 7; i++ {
        best := SmoothWrr(nodes)
        if best != nil {
            fmt.Println(best.Name)
        }
    }
}

证明权重合理性

以下证明主要由安大神证明得出
假如有n个结点，记第i个结点的权重是xi。
设总权重为S=x1 + x2 + … + xn
选择分两步

1. 为每个节点加上它的权重值
2. 选择最大的节点减去总的权重值

n个节点的初始化值为[0, 0, …, 0]，数组长度为n，值都为0。
第一轮选择的第1步执行后，数组的值为[x1, x2, …, xn]。
假设第1步后，最大的节点为j，则第j个节点减去S。
所以第2步的数组为[x1, x2, …, xj-S, …, xn]。 执行完第2步后，数组的和为
x1 + x2 + … + xj-S + … + xn =>
x1 + x2 + … + xn - S = S - S = 0。

由此可见，每轮选择，第1步操作都是数组的总和加上S，第2步总和再减去S，所以每轮选择完后的数组总和都为0.

假设总共执行S轮选择，记第i个结点选择mi次。第i个结点的当前权重为wi。 假设节点j在第t轮(t < S)之前，已经被选择了xj次，记此时第j个结点的当前权重为wj=t*xj-xj*S=(t-S)*xj<0， 因为t恒小于S，所以wj<0。

前面假设总共执行S轮选择，则剩下S-t轮，上面的公式wj=(t-S)*xj+(S-t)*xj=0。 所以在剩下的选择中，wj永远小于等于0，由于上面已经证明任何一轮选择后， 数组总和都为0，则必定存在一个节点k使得wk>0，永远不会再选中xj。

由此可以得出，第i个结点最多被选中xi次，即mi<=xi。
因为S=m1+m2+…+mn且S=x1 + x2 + … + xn。 所以，可以得出mi==xi。

证明平滑性

证明平滑性，只要证明不要一直都是连续选择那一个节点即可。

跟上面一样，假设总权重为S，假如某个节点xi连续选择了t(t<xi)次，只要存在下一次选择的不是xi，即可证明是平滑的。

假设t=xi-1，此是第i个结点的当前权重为wi=t*xi-t*S=(xi-1)*xi-(xi-1)*S。
证明下一轮的第1步执行完的值wi+xi不是最大的即可。
wi+xi=>
(xi-1)*xi-(xi-1)*S+xi=>
xi2-xi*S+S=>
(xi-1)*(xi-S)+xi

因为xi恒小于S，所以xi-S<=-1。 所以上面：
(xi-1)*(xi-S)+xi <= (xi-1)*-1+xi = -xi+1+xi=1。
所以，第t轮后，再执行完第1步的值wi+xi<=1。
如果这t轮刚好是最开始的t轮，则必定存在另一个结点j的值为xj*t，所以有wi+xi<=1<1*t<xj*t。
所以下一轮肯定不会选中x。