应用负载均衡之LVS(五)：加权调度算法的规律

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

 

加权调度算法是一种很常见的调度算法。如果只有两个后端，调度的顺序很容易，但是如果后端多于2个，可能就不像想象中那样的顺序进行调度。

所以，本文揭秘加权调度算法到底是怎么进行调度的。

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。这里没法约分。

1. 调度C
   调度之后，比率变成A:B:C=2:3:3，B和C权重相同，从B开始调度
2. 调度B
   调度之后，比率变成A:B:C=2:2:3，所以下次调度C
3. 调度C
   调度之后，比率变成A:B:C=2:2:2，下次从A开始
   当权重全部调整到相同值时，就按照先后顺序不断循环，直到调度完所有权重
   
4. 调度A，调度之后，比率变成A:B:C=1:2:2
   
5. 调度B，调度之后，比率变成A:B:C=1:1:2
   
6. 调度C，调度之后，比率变成A:B:C=1:1:1
   
7. 调度A，调度之后，比率变成A:B:C=0:1:1
   
8. 调度B，调度之后，比率变成A:B:C=0:0:1
   
9. 调度C，调度之后，比率变成A:B:C=0:0:0
   
10. 进入下一个调度循环，顺序是：CBCABCABC

所以，每个调度循环的调度顺序为：CBCABCABC

调度过程如下图：

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

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

1. 调度D
   
2. 调度C
   
3. 调度D
   
4. 调度B
   
5. 调度C
   
6. 调度D
   
7. 调度A
   
8. 调度B
   
9. 调度C
   
10. 调度D

所以，调度顺序是DCDBCDABCD。