Nginx SWRR 算法解读

Smooth Weighted Round-Robin (SWRR) 是 nginx 默认的加权负载均衡算法，它的重要特点是平滑，避免低权重的节点长时间处于空闲状态，因此被称为平滑加权轮询。

该算法来自 nginx 的一次 commit：Upstream: smooth weighted round-robin balancing

在阅读之前，你应该已经了解过 nginx 的几种负载均衡算法，并阅读了 SWRR 的实现。

介绍此算法的文章有很多，但用数学角度给出证明过程的较少，尽管并不复杂。这里把自己的思路分享一下，为了便于理解，只考虑算法核心的 current_weight，忽略受异常波动影响的 effective_weight。

更新说明

在写下博客之前，我还没有翻到其他靠谱的证明过程，就草草记录了自己粗鄙的思路。可发布文章一年之后，再来回顾的我不禁汗颜，为了照顾读者（更未来的自己），参考 nginx平滑的基于权重轮询算法分析重新梳理了文章脉络。

以至于现在的内容更像是他人博客的学习笔记，和初版大不相同。这让患有原创洁癖的我深感羞愧，之后的自己务必用更数学的风格去做解析。

算法描述

由于所有节点都有原始权重和当前权重，为了方便区分，我们称当前权重为“状态”。

节点的初始状态均为 0，每开始一轮新的选择，先为各个节点加上其原始权重大小的值，然后选出权重最大的节点，将其值减去所有节点的权重和，最后，该节点作为命中节点返回。

接下来是官方的示例，对于权重占比 { 5, 1, 1 } 的 A, B, C 三个节点，每轮节点的选择和状态的变换如下

| Round |  A |  B |  C | Selected Node |
|-------|----|----|----|---------------|
|       |  0 |  0 |  0 |               |
|-------|----|----|----|---------------|
|     1 |  5 |  1 |  1 | A             |
|       | -2 |  1 |  1 |               |
|-------|----|----|----|---------------|
|     2 |  3 |  2 |  2 | A             |
|       | -4 |  2 |  2 |               |
|-------|----|----|----|---------------|
|     3 |  1 |  3 |  3 | B             |
|       |  1 | -4 |  3 |               |
|-------|----|----|----|---------------|
|     4 |  6 | -3 |  4 | A             |
|       | -1 | -3 |  4 |               |
|-------|----|----|----|---------------|
|     5 |  4 | -2 |  5 | C             |
|       |  4 | -2 | -2 |               |
|-------|----|----|----|---------------|
|     6 |  9 | -1 | -1 | A             |
|       |  2 | -1 | -1 |               |
|-------|----|----|----|---------------|
|     7 |  7 |  0 |  0 | A             |
|       |  0 |  0 |  0 |               |

证明思路

假设有三个服务器节点 A B C，它们的权重分别为 a、b、c 并保持不变，W 表示所有服务器节点权重的总和，即 W = a + b + c。

根据 SWRR 算法，每台服务器的初始权重均为 0。

A	B	C
0	0	0

也可以用等式表达当前的权重（状态）之和

1	Sum = 0 + 0 + 0 = 0

每次开始选择，各节点的状态会增加对应权重的大小。从中选择 CW 最大的节点，并将其值减去 W。

首先，所有节点加权，不妨设 A 为权重最大的节点，经过第一轮变换之后

A	B	C
a - W	b	c

此时，节点的状态和仍然为 0

1
2
3

Sum = (a - W) + b + c
    = (a - a - b - c) + b + c
    = 0

综上，每一轮选择都是将总资源根据权重分配给各自节，再由权重最大的节点一次性消耗掉。依此类推，无论第几次选择，他们的和恒等于零。

假设 A 已经被选择了 a 轮 (a < W)，即将开始第 n 轮选择（a < n < W），那么 A 节点的状态为

1	n * a - a * W = a * (n - W) < 0

由于状态总和恒为 0，而 A 节点状态小于 0 的时候一定不会被选中，因此 A 最多只能被选择 a 轮。同理，其他每个节点也最多只能被选择等同于节点权重的次数。

最后证明算法的平滑性，即 A 节点不会连续被选择 a 次。

不妨设 A 节点已经被连续选择了 a - 1 次，那么当前 A 节点的状态为

1	(a - 1) * a - (a - 1) * W = (a - 1) * (a - W) < 0

同上一条证明，由于状态总和恒为 0，而 A 节点状态小于 0 的时候一定不会被选中，因此 A 最多只能被连续选中 a - 1 轮。即每个节点也不会被连续选择，平滑性得证。