Linux服务器集群系统(四)--转
引用地址：http://www.linuxvirtualserver.org/zh/lvs4.html
LVS集群的負載調度
章文嵩?(wensong@linux-vs.org)?
2002 年 5 月
1. 前言?
在上一篇文章中，我們主要講述了LVS集群中實現(xiàn)的三種IP負載均衡技術，它們主要解決系統(tǒng)的可伸縮性和透明性問題，如何通過負載調度器將請求高 效地分發(fā)到不同的服務器執(zhí)行，使得由多臺獨立計算機組成的集群系統(tǒng)成為一臺虛擬服務器；客戶端應用程序與集群系統(tǒng)交互時，就像與一臺高性能的服務器交互一 樣。
本文將主要講述在負載調度器上的負載調度策略和算法，如何將請求流調度到各臺服務器，使得各臺服務器盡可能地保持負載均衡。文章主要由兩個部分組 成。第一部分描述IP負載均衡軟件IPVS在內核中所實現(xiàn)的各種連接調度算法；第二部分給出一個動態(tài)反饋負載均衡算法（Dynamic-feedback load balancing），它結合內核中的加權連接調度算法，根據(jù)動態(tài)反饋回來的負載信息來調整服務器的權值，來進一步避免服務器間的負載不平衡。
在下面描述中，我們稱客戶的socket和服務器的socket之間的數(shù)據(jù)通訊為連接，無論它們是使用TCP還是UDP協(xié)議。對于UDP數(shù)據(jù)報文的 調度，IPVS調度器也會為之建立調度記錄并設置超時值（如5分鐘）；在設定的時間內，來自同一地址（IP地址和端口）的UDP數(shù)據(jù)包會被調度到同一臺服 務器。
2. 內核中的連接調度算法
IPVS在內核中的負載均衡調度是以連接為粒度的。在HTTP協(xié)議（非持久）中，每個對象從WEB服務器上獲取都需要建立一個TCP連接，同一用戶 的不同請求會被調度到不同的服務器上，所以這種細粒度的調度在一定程度上可以避免單個用戶訪問的突發(fā)性引起服務器間的負載不平衡。
在內核中的連接調度算法上，IPVS已實現(xiàn)了以下八種調度算法：
- 輪叫調度（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）
?
下面，我們先介紹這八種連接調度算法的工作原理和算法流程，會在以后的文章中描述怎么用它們。
2.1. 輪叫調度
輪叫調度（Round Robin Scheduling）算法就是以輪叫的方式依次將請求調度不同的服務器，即每次調度執(zhí)行i = (i + 1) mod n，并選出第i臺服務器。算法的優(yōu)點是其簡潔性，它無需記錄當前所有連接的狀態(tài)，所以它是一種無狀態(tài)調度。
在系統(tǒng)實現(xiàn)時，我們引入了一個額外條件，當服務器的權值為零時，表示該服務器不可用而不被調度。這樣做的目的是將服務器切出服務（如屏蔽服務器故障和系統(tǒng)維護），同時與其他加權算法保持一致。所以，算法要作相應的改動，它的算法流程如下：
輪叫調度算法流程
| 假設有一組服務器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; |
?
輪叫調度算法假設所有服務器處理性能均相同，不管服務器的當前連接數(shù)和響應速度。該算法相對簡單，不適用于服務器組中處理性能不一的情況，而且當請求服務時間變化比較大時，輪叫調度算法容易導致服務器間的負載不平衡。
雖然Round-Robin DNS方法也是以輪叫調度的方式將一個域名解析到多個IP地址，但輪叫DNS方法的調度粒度是基于每個域名服務器的，域名服務器對域名解析的緩存會妨礙輪 叫解析域名生效，這會導致服務器間負載的嚴重不平衡。這里，IPVS輪叫調度算法的粒度是基于每個連接的，同一用戶的不同連接都會被調度到不同的服務器 上，所以這種細粒度的輪叫調度要比DNS的輪叫調度優(yōu)越很多。
2.2. 加權輪叫調度
加權輪叫調度（Weighted Round-Robin Scheduling）算法可以解決服務器間性能不一的情況，它用相應的權值表示服務器的處理性能，服務器的缺省權值為1。假設服務器A的權值為1，B的 權值為2，則表示服務器B的處理性能是A的兩倍。加權輪叫調度算法是按權值的高低和輪叫方式分配請求到各服務器。權值高的服務器先收到的連接，權值高的服 務器比權值低的服務器處理更多的連接，相同權值的服務器處理相同數(shù)目的連接數(shù)。加權輪叫調度算法流程如下：
加權輪叫調度算法流程
| 假設有一組服務器S = {S0, S1, …, Sn-1}，W(Si)表示服務器Si的權值，一個 指示變量i表示上一次選擇的服務器，指示變量cw表示當前調度的權值，max(S) 表示集合S中所有服務器的最大權值，gcd(S)表示集合S中所有服務器權值的最大 公約數(shù)。變量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，則在一個調度周期內(mod sum(W(Si)))調度序列為AABABCABC。加權輪叫調度算法還是比較簡單和高效。當請求的服務時間變化很大，單獨的加權輪叫調度算法依然會導致服務器間的負載不平衡。
從上面的算法流程中，我們可以看出當服務器的權值為零時，該服務器不被被調度；當所有服務器的權值為零，即對于任意i有W(Si)=0，則沒有任何 服務器可用，算法返回NULL，所有的新連接都會被丟掉。加權輪叫調度也無需記錄當前所有連接的狀態(tài)，所以它也是一種無狀態(tài)調度。
2.3. 最小連接調度
最小連接調度（Least-Connection Scheduling）算法是把新的連接請求分配到當前連接數(shù)最小的服務器。最小連接調度是一種動態(tài)調度算法，它通過服務器當前所活躍的連接數(shù)來估計服務 器的負載情況。調度器需要記錄各個服務器已建立連接的數(shù)目，當一個請求被調度到某臺服務器，其連接數(shù)加1；當連接中止或超時，其連接數(shù)減一。
在系統(tǒng)實現(xiàn)時，我們也引入當服務器的權值為零時，表示該服務器不可用而不被調度，它的算法流程如下：
最小連接調度算法流程
| 假設有一組服務器S = {S0, S1, ..., Sn-1}，W(Si)表示服務器Si的權值， C(Si)表示服務器Si的當前連接數(shù)。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; |
?
當各個服務器有相同的處理性能時，最小連接調度算法能把負載變化大的請求分布平滑到各個服務器上，所有處理時間比較長的請求不可能被發(fā)送到同一臺服 務器上。但是，當各個服務器的處理能力不同時，該算法并不理想，因為TCP連接處理請求后會進入TIME_WAIT狀態(tài)，TCP的TIME_WAIT一般 為2分鐘，此時連接還占用服務器的資源，所以會出現(xiàn)這樣情形，性能高的服務器已處理所收到的連接，連接處于TIME_WAIT狀態(tài)，而性能低的服務器已經(jīng) 忙于處理所收到的連接，還不斷地收到新的連接請求。
2.4. 加權最小連接調度
加權最小連接調度（Weighted Least-Connection Scheduling）算法是最小連接調度的超集，各個服務器用相應的權值表示其處理性能。服務器的缺省權值為1，系統(tǒng)管理員可以動態(tài)地設置服務器的權 值。加權最小連接調度在調度新連接時盡可能使服務器的已建立連接數(shù)和其權值成比例。加權最小連接調度的算法流程如下：
加權最小連接調度的算法流程
| 假設有一組服務器S = {S0, S1, ..., Sn-1}，W(Si)表示服務器Si的權值， C(Si)表示服務器Si的當前連接數(shù)。所有服務器當前連接數(shù)的總和為 CSUM = ΣC(Si) (i=0, 1, .. , n-1)。當前的新連接請求會被發(fā)送服務器Sm， 當且僅當服務器Sm滿足以下條件(C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)} (i=0, 1, . , n-1)其中W(Si)不為零 因為CSUM在這一輪查找中是個常數(shù)，所以判斷條件可以簡化為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) 可以進一步優(yōu)化 為C(Sm)*W(Si) > C(Si)* W(Sm)。同時保證服務器的權值為零時，服務器不被調 度。所以，算法只要執(zhí)行以下流程。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; |
?
2.5. 基于局部性的最少鏈接調度
基于局部性的最少鏈接調度（Locality-Based Least Connections Scheduling，以下簡稱為LBLC）算法是針對請求報文的目標IP地址的負載均衡調度，目前主要用于Cache集群系統(tǒng)，因為在Cache集群中 客戶請求報文的目標IP地址是變化的。這里假設任何后端服務器都可以處理任一請求，算法的設計目標是在服務器的負載基本平衡情況下，將相同目標IP地址的 請求調度到同一臺服務器，來提高各臺服務器的訪問局部性和主存Cache命中率，從而整個集群系統(tǒng)的處理能力。
LBLC調度算法先根據(jù)請求的目標IP地址找出該目標IP地址最近使用的服務器，若該服務器是可用的且沒有超載，將請求發(fā)送到該服務器；若服務器不 存在，或者該服務器超載且有服務器處于其一半的工作負載，則用“最少鏈接”的原則選出一個可用的服務器，將請求發(fā)送到該服務器。該算法的詳細流程如下：
LBLC調度算法流程
| 假設有一組服務器S = {S0, S1, ..., Sn-1}，W(Si)表示服務器Si的權值， C(Si)表示服務器Si的當前連接數(shù)。ServerNode[dest_ip]是一個關聯(lián)變量，表示 目標IP地址所對應的服務器結點，一般來說它是通過Hash表實現(xiàn)的。WLC(S)表示 在集合S中的加權最小連接服務器，即前面的加權最小連接調度。Now為當前系統(tǒng) 時間。if (ServerNode[dest_ip] is NULL) then {n = WLC(S);if (n is NULL) then return NULL;ServerNode[dest_ip].server = n; } else {n = ServerNode[dest_ip].server;if ((n is dead) OR(C(n) > W(n) ANDthere is a node m with C(m) < W(m)/2))) then {n = WLC(S);if (n is NULL) then return NULL;ServerNode[dest_ip].server = n;} } ServerNode[dest_ip].lastuse = Now; return n; |
?
此外，對關聯(lián)變量ServerNode[dest_ip]要進行周期性的垃圾回收（Garbage Collection），將過期的目標IP地址到服務器關聯(lián)項進行回收。過期的關聯(lián)項是指哪些當前時間（實現(xiàn)時采用系統(tǒng)時鐘節(jié)拍數(shù)jiffies）減去最 近使用時間超過設定過期時間的關聯(lián)項，系統(tǒng)缺省的設定過期時間為24小時。
2.6. 帶復制的基于局部性最少鏈接調度
帶復制的基于局部性最少鏈接調度（Locality-Based Least Connections with Replication Scheduling，以下簡稱為LBLCR）算法也是針對目標IP地址的負載均衡，目前主要用于Cache集群系統(tǒng)。它與LBLC算法的不同之處是它要 維護從一個目標IP地址到一組服務器的映射，而LBLC算法維護從一個目標IP地址到一臺服務器的映射。對于一個“熱門”站點的服務請求，一臺Cache 服務器可能會忙不過來處理這些請求。這時，LBLC調度算法會從所有的Cache服務器中按“最小連接”原則選出一臺Cache服務器，映射該“熱門”站 點到這臺Cache服務器，很快這臺Cache服務器也會超載，就會重復上述過程選出新的Cache服務器。這樣，可能會導致該“熱門”站點的映像會出現(xiàn) 在所有的Cache服務器上，降低了Cache服務器的使用效率。LBLCR調度算法將“熱門”站點映射到一組Cache服務器（服務器集合），當該“熱 門”站點的請求負載增加時，會增加集合里的Cache服務器，來處理不斷增長的負載；當該“熱門”站點的請求負載降低時，會減少集合里的Cache服務器 數(shù)目。這樣，該“熱門”站點的映像不太可能出現(xiàn)在所有的Cache服務器上，從而提供Cache集群系統(tǒng)的使用效率。
LBLCR算法先根據(jù)請求的目標IP地址找出該目標IP地址對應的服務器組；按“最小連接”原則從該服務器組中選出一臺服務器，若服務器沒有超載， 將請求發(fā)送到該服務器；若服務器超載；則按“最小連接”原則從整個集群中選出一臺服務器，將該服務器加入到服務器組中，將請求發(fā)送到該服務器。同時，當該 服務器組有一段時間沒有被修改，將最忙的服務器從服務器組中刪除，以降低復制的程度。LBLCR調度算法的流程如下：
LBLCR調度算法流程
| 假設有一組服務器S = {S0, S1, ..., Sn-1}，W(Si)表示服務器Si的權值， C(Si)表示服務器Si的當前連接數(shù)。ServerSet[dest_ip]是一個關聯(lián)變量，表示 目標IP地址所對應的服務器集合，一般來說它是通過Hash表實現(xiàn)的。WLC(S)表示 在集合S中的加權最小連接服務器，即前面的加權最小連接調度；WGC(S)表示在 集合S中的加權最大連接服務器。Now為當前系統(tǒng)時間，lastmod表示集合的最近 修改時間，T為對集合進行調整的設定時間。if (ServerSet[dest_ip] is NULL) then {n = WLC(S);if (n is NULL) then return NULL;add n into ServerSet[dest_ip]; } else {n = WLC(ServerSet[dest_ip]);if ((n is NULL) OR(n is dead) OR(C(n) > W(n) ANDthere is a node m with C(m) < W(m)/2))) then {n = WLC(S);if (n is NULL) then return NULL;add n into ServerSet[dest_ip];} elseif (|ServerSet[dest_ip]| > 1 ANDNow - ServerSet[dest_ip].lastmod > T) then {m = WGC(ServerSet[dest_ip]);remove m from ServerSet[dest_ip];} } ServerSet[dest_ip].lastuse = Now; if (ServerSet[dest_ip] changed) thenServerSet[dest_ip].lastmod = Now; return n; |
?
此外，對關聯(lián)變量ServerSet[dest_ip]也要進行周期性的垃圾回收（Garbage Collection），將過期的目標IP地址到服務器關聯(lián)項進行回收。過期的關聯(lián)項是指哪些當前時間（實現(xiàn)時采用系統(tǒng)時鐘節(jié)拍數(shù)jiffies）減去最 近使用時間（lastuse）超過設定過期時間的關聯(lián)項，系統(tǒng)缺省的設定過期時間為24小時。
2.7. 目標地址散列調度
目標地址散列調度（Destination Hashing Scheduling）算法也是針對目標IP地址的負載均衡，但它是一種靜態(tài)映射算法，通過一個散列（Hash）函數(shù)將一個目標IP地址映射到一臺服務器。
目標地址散列調度算法先根據(jù)請求的目標IP地址，作為散列鍵（Hash Key）從靜態(tài)分配的散列表找出對應的服務器，若該服務器是可用的且未超載，將請求發(fā)送到該服務器，否則返回空。該算法的流程如下：
目標地址散列調度算法流程
| 假設有一組服務器S = {S0, S1, ..., Sn-1}，W(Si)表示服務器Si的權值， C(Si)表示服務器Si的當前連接數(shù)。ServerNode[]是一個有256個桶（Bucket）的 Hash表，一般來說服務器的數(shù)目會運小于256，當然表的大小也是可以調整的。 算法的初始化是將所有服務器順序、循環(huán)地放置到ServerNode表中。若服務器的 連接數(shù)目大于2倍的權值，則表示服務器已超載。n = ServerNode[hashkey(dest_ip)]; if ((n is dead) OR(W(n) == 0) OR(C(n) > 2*W(n))) thenreturn NULL; return n; |
?
在實現(xiàn)時，我們采用素數(shù)乘法Hash函數(shù)，通過乘以素數(shù)使得散列鍵值盡可能地達到較均勻的分布。所采用的素數(shù)乘法Hash函數(shù)如下：
素數(shù)乘法Hash函數(shù)
| static inline unsigned hashkey(unsigned int dest_ip) {return (dest_ip* 2654435761UL) & HASH_TAB_MASK; } 其中，2654435761UL是2到2^32 (4294967296)間接近于黃金分割的素數(shù)，(sqrt(5) - 1) / 2 = 0.6180339892654435761 / 4294967296 = 0.618033987 |
?
2.8. 源地址散列調度
源地址散列調度（Source Hashing Scheduling）算法正好與目標地址散列調度算法相反，它根據(jù)請求的源IP地址，作為散列鍵（Hash Key）從靜態(tài)分配的散列表找出對應的服務器，若該服務器是可用的且未超載，將請求發(fā)送到該服務器，否則返回空。它采用的散列函數(shù)與目標地址散列調度算法 的相同。它的算法流程與目標地址散列調度算法的基本相似，除了將請求的目標IP地址換成請求的源IP地址，所以這里不一一敘述。
在實際應用中，源地址散列調度和目標地址散列調度可以結合使用在防火墻集群中，它們可以保證整個系統(tǒng)的唯一出入口。
3. 動態(tài)反饋負載均衡算法
動態(tài)反饋負載均衡算法考慮服務器的實時負載和響應情況，不斷調整服務器間處理請求的比例，來避免有些服務器超載時依然收到大量請求，從而提 高整個系統(tǒng)的吞吐率。圖1顯示了該算法的工作環(huán)境，在負載調度器上運行Monitor Daemon進程，Monitor Daemon來監(jiān)視和收集各個服務器的負載信息。Monitor Daemon可根據(jù)多個負載信息算出一個綜合負載值。Monitor Daemon將各個服務器的綜合負載值和當前權值算出一組新的權值，若新權值和當前權值的差值大于設定的閥值，Monitor Daemon將該服務器的權值設置到內核中的IPVS調度中，而在內核中連接調度一般采用加權輪叫調度算法或者加權最小連接調度算法。
?圖1：動態(tài)反饋負載均衡算法的工作環(huán)境
3.1. 連接調度
當客戶通過TCP連接訪問網(wǎng)絡訪問時，服務所需的時間和所要消耗的計算資源是千差萬別的，它依賴于很多因素。例如，它依賴于請求的服務類型、當前網(wǎng) 絡帶寬的情況、以及當前服務器資源利用的情況。一些負載比較重的請求需要進行計算密集的查詢、數(shù)據(jù)庫訪問、很長響應數(shù)據(jù)流；而負載比較輕的請求往往只需要 讀一個HTML頁面或者進行很簡單的計算。
請求處理時間的千差萬別可能會導致服務器利用的傾斜（Skew），即服務器間的負載不平衡。例如，有一個WEB頁面有A、B、C和D文件，其中D是 大圖像文件，瀏覽器需要建立四個連接來取這些文件。當多個用戶通過瀏覽器同時訪問該頁面時，最極端的情況是所有D文件的請求被發(fā)到同一臺服務器。所以說， 有可能存在這樣情況，有些服務器已經(jīng)超負荷運行，而其他服務器基本是閑置著。同時，有些服務器已經(jīng)忙不過來，有很長的請求隊列，還不斷地收到新的請求。反 過來說，這會導致客戶長時間的等待，覺得系統(tǒng)的服務質量差。
3.1.1. 簡單連接調度
簡單連接調度可能會使得服務器傾斜的發(fā)生。在上面的例子中，若采用輪叫調度算法，且集群中正好有四臺服務器，必有一臺服務器總是收到D文件的請求。這種調度策略會導致整個系統(tǒng)資源的低利用率，因為有些資源被用盡導致客戶的長時間等待，而其他資源空閑著。
3.1.2. 實際TCP/IP流量的特征
文獻[1]說明網(wǎng)絡流量是呈波浪型發(fā)生的，在一段較長時間的小流量后，會有一段大流量的訪問，然后是小流量，這樣跟波浪一樣周期性地發(fā)生。文獻 [2,3,4,5]揭示在WAN和LAN上網(wǎng)絡流量存在自相似的特征，在WEB訪問流也存在自相似性。這就需要一個動態(tài)反饋機制，利用服務器組的狀態(tài)來應 對訪問流的自相似性。
3.2. 動態(tài)反饋負載均衡機制
TCP/IP流量的特征通俗地說是有許多短事務和一些長事務組成，而長事務的工作量在整個工作量占有較高的比例。所以，我們要設計一種負載均衡算法，來避免長事務的請求總被分配到一些機器上，而是盡可能將帶有毛刺（Burst）的分布分割成相對較均勻的分布。
我們提出基于動態(tài)反饋負載均衡機制，來控制新連接的分配，從而控制各個服務器的負載。例如，在IPVS調度器的內核中使用加權輪叫調度 （Weighted Round-Robin Scheduling）算法來調度新的請求連接；在負載調度器的用戶空間中運行Monitor Daemon。Monitor Daemon定時地監(jiān)視和收集各個服務器的負載信息，根據(jù)多個負載信息算出一個綜合負載值。Monitor Daemon將各個服務器的綜合負載值和當前權值算出一組新的權值。當綜合負載值表示服務器比較忙時，新算出的權值會比其當前權值要小，這樣新分配到該服 務器的請求數(shù)就會少一些。當綜合負載值表示服務器處于低利用率時，新算出的權值會比其當前權值要大，來增加新分配到該服務器的請求數(shù)。若新權值和當前權值 的差值大于設定的閥值，Monitor Daemon將該服務器的權值設置到內核中的IPVS調度中。過了一定的時間間隔（如2秒鐘），Monitor Daemon再查詢各個服務器的情況，并相應調整服務器的權值；這樣周期性地進行?？梢哉f，這是一個負反饋機制，使得服務器保持較好的利用率。
在加權輪叫調度算法中，當服務器的權值為零，已建立的連接會繼續(xù)得到該服務器的服務，而新的連接不會分配到該服務器。系統(tǒng)管理員可以將一臺服務器的 權值設置為零，使得該服務器安靜下來，當已有的連接都結束后，他可以將該服務器切出，對其進行維護。維護工作對系統(tǒng)都是不可少的，比如硬件升級和軟件更新 等，零權值使得服務器安靜的功能很主要。所以，在動態(tài)反饋負載均衡機制中我們要保證該功能，當服務器的權值為零時，我們不對服務器的權值進行調整。
3.3. 綜合負載
在計算綜合負載時，我們主要使用兩大類負載信息：輸入指標和服務器指標。輸入指標是在調度器上收集到的，而服務器指標是在服務器上的各種負載信息。 我們用綜合負載來反映服務器當前的比較確切負載情況，對于不同的應用，會有不同的負載情況，這里我們引入各個負載信息的系數(shù)，來表示各個負載信息在綜合負 載中輕重。系統(tǒng)管理員根據(jù)不同應用的需求，調整各個負載信息的系數(shù)。另外，系統(tǒng)管理員設置收集負載信息的時間間隔。
輸入指標主要是在單位時間內服務器收到新連接數(shù)與平均連接數(shù)的比例，它是在調度器上收集到的，所以這個指標是對服務器負載情況的一個估計值。在調度 器上有各個服務器收到連接數(shù)的計數(shù)器，對于服務器Si，可以得到分別在時間T1和T2時的計數(shù)器值Ci1和Ci2，計算出在時間間隔T2-T1內服務器 Si收到新連接數(shù)Ni = Ci2 - Ci1。這樣，得到一組服務器在時間間隔T2-T1內服務器Si收到新連接數(shù){Ni}，服務器Si的輸入指標INPUTi為其新連接數(shù)與n臺服務器收到平 均連接數(shù)的比值，其公式為
服務器指標主要記錄服務器各種負載信息，如服務器當前CPU負載LOADi、服務器當前磁盤使用情況Di、當前內存利用情況Mi和當前進程數(shù)目 Pi。有兩種方法可以獲得這些信息；一是在所有的服務器上運行著SNMP（Simple Network Management Protocol）服務進程，而在調度器上的Monitor Daemon通過SNMP向各個服務器查詢獲得這些信息；二是在服務器上實現(xiàn)和運行收集信息的Agent，由Agent定時地向Monitor Daemon報告負載信息。若服務器在設定的時間間隔內沒有響應，Monitor Daemon認為服務器是不可達的，將服務器在調度器中的權值設置為零，不會有新的連接再被分配到該服務器；若在下一次服務器有響應，再對服務器的權值進 行調整。再對這些數(shù)據(jù)進行處理，使其落在[0, ∞)的區(qū)間內，1表示負載正好，大于1表示服務器超載，小于1表示服務器處于低負載狀態(tài)。獲得調整后的數(shù)據(jù)有DISKi、MEMORYi和 PROCESSi。
另一個重要的服務器指標是服務器所提供服務的響應時間，它能比較好地反映服務器上請求等待隊列的長度和請求的處理時間。調度器上的Monitor Daemon作為客戶訪問服務器所提供的服務，測得其響應時間。例如，測試從WEB服務器取一個HTML頁面的響應延時，Monitor Daemon只要發(fā)送一個“GET /”請求到每個服務器，然后記錄響應時間。若服務器在設定的時間間隔內沒有響應，Monitor Daemon認為服務器是不可達的，將服務器在調度器中的權值設置為零。同樣，我們對響應時間進行如上調整，得到RESPONSEi。
這里，我們引入一組可以動態(tài)調整的系數(shù)Ri來表示各個負載參數(shù)的重要程度，其中ΣRi = 1。綜合負載可以通過以下公式計算出：
例如，在WEB服務器集群中，我們采用以下系數(shù){0.1, 0.3, 0.1, 0.1, 0.1, 0.3}，認為服務器的CPU負載和請求響應時間較其他參數(shù)重要一些。若當前的系數(shù)Ri不能很好地反映應用的負載，系統(tǒng)管理員可以對系數(shù)不斷地修正，直到 找到貼近當前應用的一組系數(shù)。
另外，關于查詢時間間隔的設置，雖然很短的間隔可以更確切地反映各個服務器的負載，但是很頻繁地查詢（如1秒鐘幾次）會給調度器和服務器帶來一定的 負載，如頻繁執(zhí)行的Monitor Daemon在調度器會有一定的開銷，同樣頻繁地查詢服務器指標會服務器帶來一定的開銷。所以，這里要有個折衷（Tradeoff），我們一般建議將時間 間隔設置在5到20秒之間。
3.4. 權值計算
當服務器投入集群系統(tǒng)中使用時，系統(tǒng)管理員對服務器都設定一個初始權值DEFAULT_WEIGHTi，在內核的IPVS調度中也先使用這個權值。 然后，隨著服務器負載的變化，對權值進行調整。為了避免權值變成一個很大的值，我們對權值的范圍作一個限制[DEFAULT_WEIGHTi, SCALE*DEFAULT_WEIGHTi]，SCALE是可以調整的，它的缺省值為10。
Monitor Daemon周期性地運行，若DEFAULT_WEIGHTi不為零，則查詢該服務器的各負載參數(shù)，并計算出綜合負載值AGGREGATE_LOADi。我們引入以下權值計算公式，根據(jù)服務器的綜合負載值調整其權值。
在公式中，0.95是我們想要達到的系統(tǒng)利用率，A是一個可調整的系數(shù)（缺省值為5）。當綜合負載值為0.95時，服務器權值不變；當綜合負載值大 于0.95時，權值變小；當綜合負載值小于0.95時，權值變大。若新權值大于SCALE*DEFAULT_WEIGHTi，我們將新權值設為 SCALE*DEFAULT_WEIGHTi。若新權值與當前權值的差異超過設定的閥值，則將新權值設置到內核中的IPVS調度參數(shù)中，否則避免打斷 IPVS調度的開銷。我們可以看出這是一個負反饋公式，會使得權值調整到一個穩(wěn)定點，如系統(tǒng)達到理想利用率時，權值是不變的。
在實際使用中，若發(fā)現(xiàn)所有服務器的權值都小于他們的DEFAULT_WEIGHT，則說明整個服務器集群處于超載狀態(tài)，這時需要加入新的服務器結點 到集群中來處理部分負載；反之，若所有服務器的權值都接近于SCALE*DEFAULT_WEIGHT，則說明當前系統(tǒng)的負載都比較輕。
3.5. 一個實現(xiàn)例子
我們在RedHat集群管理工具Piranha[6]中實現(xiàn)了一個簡單的動態(tài)反饋負載均衡算法。在綜合負載上，它只考慮服務器的CPU負載（Load Average），使用以下公式進行權值調整：
服務器權值調整區(qū)間為[DEFAULT_WEIGHTi, 10*DEFAULT_WEIGHTi]，A為DEFAULT_WEIGHTi /2，而權值調整的閥值為DEFAULT_WEIGHTi /4。1是所想要達到的系統(tǒng)利用率。Piranha每隔20秒查詢各臺服務器的CPU負載，進行權值計算和調整。
4. 小結
本文主要講述了IP虛擬服務器在內核中實現(xiàn)的八種連接調度算法：
- 輪叫調度（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）
?
因為請求的服務時間差異較大，內核中的連接調度算法容易使得服務器運行出現(xiàn)傾斜。為此，給出了一個動態(tài)反饋負載均衡算法，結合內核中的加權連接調度 算法，根據(jù)動態(tài)反饋回來的負載信息來調整服務器的權值，來調整服務器間處理請求數(shù)的比例，從而避免服務器間的負載不平衡。動態(tài)反饋負載算法可以較好地避免 服務器的傾斜，提高系統(tǒng)的資源使用效率，從而提高系統(tǒng)的吞吐率。
參考文獻
關于作者
章文嵩博士，開放源碼及Linux內核的開發(fā)者，著名的Linux集群項目－－LVS(Linux Virtual Server)的創(chuàng)始人和主要開發(fā)人員。他目前工作于國家并行與分布式處理重點實驗室，主要從事集群技術、操作系統(tǒng)、對象存儲與數(shù)據(jù)庫的研究。他一直在自 由軟件的開發(fā)上花費大量時間，并以此為樂。
轉載于:https://www.cnblogs.com/davidwang456/p/3578924.html
總結
以上是生活随笔為你收集整理的Linux服务器集群系统(四)--转的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Linux服务器集群系统(三)--转
- 下一篇： java使用jsp servlet来防止