Nginx SWRR 算法解读
source link: http://claude-ray.com/2019/08/10/nginx-swrr/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Nginx SWRR 算法解读
Posted on
2019-08-10 Edited on 2020-08-06 In Nginx
Disqus: 0 Comments Symbols count in article: 1k Reading time ≈ 4 mins.
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
也可以用等式表达当前的权重（状态）之和
Sum = 0 + 0 + 0 = 0
每次开始选择，各节点的状态会增加对应权重的大小。从中选择 CW 最大的节点，并将其值减去 W。
首先，所有节点加权，不妨设 A 为权重最大的节点，经过第一轮变换之后
A B C
a - W b c
此时，节点的状态和仍然为 0
Sum = (a - W) + b + c
= (a - a - b - c) + b + c
= 0
综上，每一轮选择都是将总资源根据权重分配给各自节，再由权重最大的节点一次性消耗掉。依此类推，无论第几次选择，他们的和恒等于零。
假设 A 已经被选择了 a 轮 (a < W)，即将开始第 n 轮选择（a < n < W），那么 A 节点的状态为
n * a - a * W = a * (n - W) < 0
由于状态总和恒为 0，而 A 节点状态小于 0 的时候一定不会被选中，因此 A 最多只能被选择 a 轮。同理，其他每个节点也最多只能被选择等同于节点权重的次数。
最后证明算法的平滑性，即 A 节点不会连续被选择 a 次。
不妨设 A 节点已经被连续选择了 a - 1 次，那么当前 A 节点的状态为
(a - 1) * a - (a - 1) * W = (a - 1) * (a - W) < 0
同上一条证明，由于状态总和恒为 0，而 A 节点状态小于 0 的时候一定不会被选中，因此 A 最多只能被连续选中 a - 1 轮。即每个节点也不会被连续选择，平滑性得证。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK