仓库源文站点原文


title: Nginx SWRR 算法解读 date: 2019-08-10 13:13:49 tags: [Nginx, load balance]

categories: Nginx

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

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

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

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

<!--more-->

更新说明

在写下博客之前,我还没有翻到其他靠谱的证明过程,就草草记录了自己粗鄙的思路。可发布文章一年之后,再来回顾的我不禁汗颜,为了照顾读者(更未来的自己),参考 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 轮。即每个节点也不会被连续选择,平滑性得证。