关于平滑加权算法的思考以及证明

在nginx中有一个负载均衡算法,叫平滑加权轮训算法(smooth weighted round-robin balancing algorithm),网上可以搜索到很多关于这个算法的资料和计算过程,在这里我只想证明为什么这个算法是正确的。

1.基本原理

每个节点都有三个权重,一个是初始化的配置权重,一个是有效权重,一个是当前权重

  • weight 配置权重,值固定不变
  • currentWeight 当前权重,初始默认为0
  • effectiveWeight 有效权重, 初始化值等于weight。当调用该节点失败后,当前值减一,调用成功后,如果小于weight值,则加一

其运行过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (swrr *smoothWeightRoundrobin) Select() *SwrrNode {
total := 0
var selected *SwrrNode
for i := 0; i < len(swrr.nodes); i++ {
w := swrr.nodes[i]
w.CurrentWeight += w.EffectiveWeight
total += w.EffectiveWeight
if w.EffectiveWeight < w.Weight {
w.EffectiveWeight++
}
if selected == nil || w.CurrentWeight >= selected.CurrentWeight {
selected = w
}
}
selected.CurrentWeight -= total
return selected
}

通过对select节点数组的遍历,每个节点的Current Weight加上当前的 Effective Weight值,即: w.CurrentWeight += w.EffectiveWeight.
同时累计所有节点的EffectiveWeight为total值,最后选取Current Weight最大的节点,处理完请求之后,将改节点的currentweight减去total值。
算法浅显易懂,并通过运行可以证明算法的均匀。

2. 算法的证明

说实话,这个算法百度和google了很久的资料,最终没有找到一个明文的证明。

2.1 证明轮训的正确性

首先根据算法定义:
假设节点列表为$N$:$\{N_1,N_2,\cdots,N_n\}$,并且其权值为 $W$:$\{W_1,W_2,\cdots,W_n\}$,所有的节点存在一个当前权值,其初始化为0,设其值为 $CW$:$\{CW_1,CW_2,\cdots,CW_n\}$。任何一个节点其当前权值的在一次选择后的值的是:

用文字来表述就是 每个节点的下一次的当前的权值依赖与其是否被选中,如果选中则等于当前权值加上其固定初始权值,否则等于当前权值加上其固定初始权值减去总的权值
且很容易根据算法得出,不论循环多少次,

且可以得出在第 $i$ 次选择时,如果节点 $N_t$ 被选中了 $j$ 次,则其权值为:

轮训的正确性即每个节点在一个周期内会出现与其权重相等的次数,即:

即任何一个节点 $N_t$ 被选中的次数都等于 $W_t$, 且一轮周期之后节点的当前权值全部重置为0。
假设上述结论不成立,则在一轮周期 $SW$ 内 必有一个节点$N_t$其出现的次数不等于$W_t$,假设其出现的次数为$W_t^´$,则问题就转换为如何证明 $W_t^´\neq W_t$ 是不成立。

根据定义,一轮周期 $SW$ 之后,$N_t$的权值变成:

因为经过SW次选择后,所有的权值都会被重置为0,则 $CW_t^{W_t^´} = 0 $,即 $W_t = W_t^´$,则与上述矛盾,得证。

2.2 证明算法的平滑性

想了很久如何去证明平滑性,实际上平滑就意味着均匀的分布,我觉得这个均匀的分布很难理解,但是反过来,我们是否可以思考不均匀的分布是怎么样的分布?我认为不均匀的分布就是意味着某个节点连续的出现了与其权重相同的次数,只要证明这个是不可能的,就可以证明这个算法是均匀的。
根据算法,只有当每轮的的当前权值是最大的时候,才能被选中,所以在如果某个节点连续的出现了与其权重相同的次数,那么必定意味着它在连续的选中过程中最后一轮的权值也是最大的,假设其经过m轮的连续选中,则其当前权值为:

那么在第m+1轮,注意 $1<m+1<=W_t$

其权值为:

注意看选中的那个公式,假设$m+1=W_i$,则上式可以变成:

则被选中的节点最后权值可化简为:

我可以断定这个式子在当前条件下一定是小于0的,因为根据函数对$SW$ 求导可以得出:

根据上面的条件 $m+1<=W_t$,即 $W_t>=2$,则上面是一个递减函数,由于$SW>=W_t$,则带入可以得到上式的结果为 $W_t$,即经过 $W_t$的连续选中后,最后得到的权值最大值是 $W_t$,对于其余的节点来说,任何节点的值都是大于 $W_t$,所以该节点不可能被选中。

胜人者勇 胜己者智