应用负载均衡之LVS(五)：lvs和nginx的wrr加权调度算法规律分析 - 好文

返回LVS系列文章：http://www.cnblogs.com/f-ck-need-u/p/7576137.html
<http://www.cnblogs.com/f-ck-need-u/p/7576137.html#lvs>

加权调度算法(wrr)是一种很常见的调度算法。它们按照权重比例进行调度，但实际调度选中的节点顺序可能和想象中并不一样。它们有各自的算法支持，但无论什么算法，对于a、b、c三个节点，如果它们的权重比例为
a:b:c=x:y:z，在节点都健康的情况下，每一轮轮询过程中a总是被选中x次，b总是被选中y次，c总是被选中z次，只不过被选中的顺序可能因算法不同而不同，

所以，本文主要介绍lvs和nginx的wrr算法是如何计算的。

lvs的wrr调度算法

1.加权调度算法公式

首先，给一个LVS官方手册给的加权调度算法公式：

假设有一组服务器S = {S0, S1, …, Sn-1}，W(Si)表示服务器Si的权值，一个
指示变量i表示上一次选择的服务器，指示变量cw表示当前调度的权值，max(S)
表示集合S中所有服务器的最大权值，gcd(S)表示集合S中所有服务器权值的最大
公约数。变量i初始化为-1，cw初始化为零。
while (true) { i = (i + 1) mod n; if (i == 0) { cw = cw - gcd(S); if (cw <= 0)
{ cw = max(S); if (cw == 0) return NULL; } } if (W(Si) >= cw) return Si; }
比如，A、B、C三个后端的权重比是2:3:4，那么一个调度循环内的调度顺序是CBCABCABC。

如果你不想从算法公式里找规律，那么看下面。

2.加权调度通俗规律

记住三个权重调度规则：
1.先约分
2.从最大权重开始调度
3.同权重的后端，从前向后调度

例如，三台后端A:B:C=2:3:4。这里没法约分。

* 调度C
调度之后，比率变成A:B:C=2:3:3，B和C权重相同，从B开始调度
* 调度B
调度之后，比率变成A:B:C=2:2:3，所以下次调度C
* 调度C
调度之后，比率变成A:B:C=2:2:2，下次从A开始
当权重全部调整到相同值时，就按照先后顺序不断循环，直到调度完所有权重

* 调度A，调度之后，比率变成A:B:C=1:2:2

* 调度B，调度之后，比率变成A:B:C=1:1:2

* 调度C，调度之后，比率变成A:B:C=1:1:1

* 调度A，调度之后，比率变成A:B:C=0:1:1

* 调度B，调度之后，比率变成A:B:C=0:0:1

* 调度C，调度之后，比率变成A:B:C=0:0:0

* 进入下一个调度循环，顺序是：CBCABCABC
所以，每个调度循环的调度顺序为：CBCABCABC

调度过程如下图：

再给个示例，A:B:C:D=2:4:6:8

首先约分，得到A:B:C:D=1:2:3:4

* 调度D

* 调度C

* 调度D

* 调度B

* 调度C

* 调度D

* 调度A

* 调度B

* 调度C

* 调度D
所以，调度顺序是DCDBCDABCD。

nginx的wrr调度算法

以前nginx的wrr调度算法和lvs的算法类似，都是直接剃短高权重节点的权重值，最后趋于均衡。但这样的算法实际上对请求而言并不均衡，比如a:b:c =
5:1:1，调用的顺序将是aaaaabc、aaaaabc，a将被连续多次调用。

后来nginx的wrr算法改进了，变得更复杂一些，但更趋于调度均衡。

假设a:b:c=A:B:C，算法是这样的：

* 所有权重加总得到总权重(total)：A+B+C=N

* 第一个请求进来，选择权重最大的。假设为a，于是选中A。选中之后，对选中的节点的权重减去总权重N，于是现在的比例是a:b:c=A-N:B:C

* 第二个请求进入，将比如全部加上原始比例(eff_weight)，得到(A-N+A):(B+B):(C+C)
，然后选中最大的权重节点，假如选中B。选中之后，对选中的节点的权重减去总权重N，于是比例变为(2A-N):(2B-N):2C

* 之后每个请求进来，都首先加上原始比例，然后选择权重最大的，并对最大的权重值减去总权重N。

* 每一轮询的最后一次调度，都会使被选中的节点权重变为N，其它权重变为0，减去总权重之后全部变成0，使得下一轮轮询调度开始，重新回到原始比例。
例如，a:b:c=4:3:2的调度过程为：总权重为4+3+2=9

* 第1个请求，a权重最大，选中a
* 选中之后，比例变为a:b:c=-5:3:2

* 第2个请求，加上原始比例，得到a:b:c=-1:6:4，选中b
* 选中之后，比例变为a:b:c=-1:-3:4

* 第3个请求，加上原始比例，得到a:b:c=3:0:6，选中c
* 选中之后，比例变为a:b:c=3:0:-3

* 第4个请求，加上原始比例，得到a:b:c=7:3:-1，选中a
* 选中之后，比例变为a:b:c=-2:3:-1

* 第5个请求，加上原始比例，得到a:b:c=2:6:1，选中b
* 选中之后，比例变为a:b:c=2:-3:1

* 第6个请求，加上原始比例，得到a:b:c=6:0:3，选中a
* 选中之后，比例变为a:b:c=-3:0:3

* 第7个请求，加上原始比例，得到a:b:c=1:3:5，选中c
* 选中之后，比例变为a:b:c=1:3:-4

* 第8个请求，加上原始比例，得到a:b:c=5:6:-2，选中b
* 选中之后，比例变为a:b:c=5:-3:-2

* 第9个请求，加上原始比例，得到a:b:c=9:0:0，选中a
* 选中之后，比例变为a:b:c=0:0:0
一轮循环完成，调度的顺序是a b c a b a c b a，这轮循环完成之后，它们的比例变为0:0:0，下一个请求到来，加上原始权重后回到原比例4:3:2。

如果是两后端节点，它们的比例为3:1，它们的调度顺序将是aaba aaba aaba...

热门工具换一换