內核中的連接調度演算法 IPVS在內核中的負載均衡調度是以連接為粒度的。在HTTP協議（非持久中），每個對象從WEB伺服器上獲取都需要建立一個TCP連接，同一用戶的不同請求會被調度到不同伺服器上，所以這種細粒度的調度在一定程度上可以避免單個用戶訪問的突發性引起伺服器間的負載不平衡。 在內核中的連接調度 ...
內核中的連接調度演算法
IPVS在內核中的負載均衡調度是以連接為粒度的。在HTTP協議（非持久中），每個對象從WEB伺服器上獲取都需要建立一個TCP連接，同一用戶的不同請求會被調度到不同伺服器上，所以這種細粒度的調度在一定程度上可以避免單個用戶訪問的突發性引起伺服器間的負載不平衡。
在內核中的連接調度演算法上，IPVS已實現了以下八種調度演算法：
- 輪叫調度（Round-Robin Scheduling）
- 加權輪叫調度（Weighted Round-Robin Scheduling）
- 最小連接調度（Least-Connection Scheduling）
- 加權最小連接調度（Weighted Least-Connection Scheduling）
- 基於局部性的最少鏈接（Locality-Based Least Connections Scheduling）
- 帶複製的基於局部性最少鏈接（Locality-Based Least Connections with Replication Scheduling）
- 目標地址散列調度（Destination Hashing Scheduling）
- 源地址散列調度（Source Hashing Scheduling）
1、輪叫調度
該演算法是以輪叫的方式依次將請求調度不同的伺服器，即每次調度執行i = （i + 1）mod n，並選出第i台伺服器。演算法的優點是簡單，它無需記錄當前所有連接的狀態。它是一種無狀態調度。
在系統實現時，我們引入一個額外條件，當伺服器的權值為零時，表示該伺服器不可用而不被調度。這樣做的目的是將伺服器切出任務（如屏蔽伺服器故障和維護），同時與其他加權演算法保持一致。所以，演算法要作相應的改動，演算法流程如下：
假設有一組伺服器S = {S0, S1, …, Sn-1}，一個指示變數i表示上一次選擇的
伺服器，W(Si)表示伺服器Si的權值。變數i被初始化為n-1，其中n > 0。
j = i;
do {
j = (j + 1) mod n;
if (W(Sj) > 0) {
i = j;
return Si;
}
} while (j != i);
return NULL;
輪叫調度演算法假設所有伺服器性能均相同，不管伺服器當前連接數和響應速度，該演算法簡單，不適用於伺服器組中處理性能不一樣的情況，而且當請求服務時間比較大時，輪叫調度演算法容易導致伺服器間的負載不平衡。
2、加權輪叫調度
該演算法可以解決伺服器間性能不一的情況，它是相應的權值表示伺服器的處理性能，伺服器的預設值為1。假設伺服器A的權值為1，B的權值為2，則表示伺服器的處理性能是A的兩倍。加權輪叫演算法是按權值的高低和輪叫方式分配請求到各台伺服器。加權值高的先收到的連接，權值高的伺服器處理更多的連接，相同權值的伺服器處理相同的連接數。演算法流程如下：
假設有一組伺服器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分別有權值4/3/2，則在一個調度周期內，順序為AABABCABC.次方法也比較簡單，高效。當請求的服務時間變化很大，單獨的加權輪叫調度演算法依然會導致伺服器之間負載不平衡
3、最小連接調度
該演算法是將新的連接請求分配到當前連接數最小的伺服器，最小調度是一種動態調度演算法，它通過伺服器當前所活躍的連接數來估計伺服器的負載情況。調度器需要記錄各個伺服器已連接的數目，當一個請求被調度到某台伺服器時，其連接數加1；當連接中止或超時，其連接數減一。
在系統實現時，我們也引入當伺服器權值為零時，表示該伺服器不可用或不可被調度，演算法流程如下：
假設有一組伺服器S = {S0, S1, ..., Sn-1}，W(Si)表示伺服器Si的權值，
C(Si)表示伺服器Si的當前連接數。
for (m = 0; m < n; m++) {
if (W(Sm) > 0) {
for (i = m+1; i < n; i++) {
if (W(Si) <= 0)
continue;
if (C(Si) < C(Sm))
m = i;
}
return Sm;
}
}
return NULL;
4、加權最小連接調度
該演算法是最小連接調度的超集，各個伺服器用相應的權值表示其處理能力。伺服器的預設值為1，系統管理員可以動態的設置伺服器的權值。加權最小連接調度在調度新連接時儘可能使伺服器的已建立連接數和其權值成比例。
假設有一組伺服器S = {S0, S1, ..., Sn-1}，W(Si)表示伺服器Si的權值，
C(Si)表示伺服器Si的當前連接數。所有伺服器當前連接數的總和為
CSUM = ΣC(Si) (i=0, 1, .. , n-1)。當前的新連接請求會被髮送伺服器Sm，
當且僅當伺服器Sm滿足以下條件
(C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)} (i=0, 1, . , n-1)
其中W(Si)不為零
因為CSUM在這一輪查找中是個常數，所以判斷條件可以簡化為
C(Sm) / W(Sm) = min { C(Si) / W(Si)} (i=0, 1, . , n-1)
其中W(Si)不為零
因為除法所需的CPU周期比乘法多，且在Linux內核中不允許浮點除法，伺服器的
權值都大於零，所以判斷條件C(Sm) / W(Sm) > C(Si) / W(Si) 可以進一步優化
為C(Sm)*W(Si) > C(Si)* W(Sm)。同時保證伺服器的權值為零時，伺服器不被調
度。所以，演算法只要執行以下流程。
for (m = 0; m < n; m++) {
if (W(Sm) > 0) {
for (i = m+1; i < n; i++) {
if (C(Sm)*W(Si) > C(Si)*W(Sm))
m = i;
}
return Sm;
}
}
return NULL;
參考：http://www.linuxvirtualserver.org/zh/lvs4.html
