返回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。