应用负载均衡之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。