Linux伺服器叢集系統(四)

LVS叢集的負載排程

2002 年 5 月

本文主要講述了LVS叢集的IP負載均衡軟體IPVS在核心中實作的各種連接配接排程算法。針對請求的服務時間變化很大，給出一個動态回報負載均衡算法，它結合核心中的權重連接配接排程算法，根據動态回報回來的負載資訊來調整伺服器的權值，來進一步避免伺服器間的負載不平衡。

1. 前言

在上一篇文章中，我們主要講述了LVS叢集中實作的三種IP負載均衡技術，它們主要解決系統的可伸縮性和透明性問題，如何通過負載排程器将請求高 效地分發到不同的伺服器執行，使得由多台獨立計算機組成的叢集系統成為一台虛拟伺服器；用戶端應用程式與叢集系統互動時，就像與一台高性能的伺服器互動一 樣。

本文将主要講述在負載排程器上的負載排程政策和算法，如何将請求流排程到各台伺服器，使得各台伺服器盡可能地保持負載均衡。文章主要由兩個部分組 成。第一部分描述IP負載均衡軟體IPVS在核心中所實作的各種連接配接排程算法；第二部分給出一個動态回報負載均衡算法（Dynamic-feedback load balancing），它結合核心中的權重連接配接排程算法，根據動态回報回來的負載資訊來調整伺服器的權值，來進一步避免伺服器間的負載不平衡。

在下面描述中，我們稱客戶的socket和伺服器的socket之間的資料通訊為連接配接，無論它們是使用TCP還是UDP協定。對于UDP資料封包的 排程，IPVS排程器也會為之建立排程記錄并設定逾時值（如5分鐘）；在設定的時間内，來自同一位址（IP位址和端口）的UDP資料包會被排程到同一台服 務器。

2. 核心中的連接配接排程算法

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）

下面，我們先介紹這八種連接配接排程算法的工作原理和算法流程，會在以後的文章中描述怎麼用它們。

2.1. 輪叫排程

輪叫排程（Round Robin Scheduling）算法就是以輪叫的方式依次将請求排程不同的伺服器，即每次排程執行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;

輪叫排程算法假設所有伺服器處理性能均相同，不管伺服器的目前連接配接數和響應速度。該算法相對簡單，不适用于伺服器組中處理性能不一的情況，而且當請求服務時間變化比較大時，輪叫排程算法容易導緻伺服器間的負載不平衡。

雖然Round-Robin DNS方法也是以輪叫排程的方式将一個域名解析到多個IP位址，但輪叫DNS方法的排程粒度是基于每個域名伺服器的，域名伺服器對域名解析的緩存會妨礙輪 叫解析域名生效，這會導緻伺服器間負載的嚴重不平衡。這裡，IPVS輪叫排程算法的粒度是基于每個連接配接的，同一使用者的不同連接配接都會被排程到不同的伺服器 上，是以這種細粒度的輪叫排程要比DNS的輪叫排程優越很多。

2.2. 權重輪叫排程

權重輪叫排程（Weighted Round-Robin Scheduling）算法可以解決伺服器間性能不一的情況，它用相應的權值表示伺服器的處理性能，伺服器的預設權值為1。假設伺服器A的權值為1，B的 權值為2，則表示伺服器B的處理性能是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，則在一個排程周期内(mod sum(W(Si)))排程序列為AABABCABC。權重輪叫排程算法還是比較簡單和高效。當請求的服務時間變化很大，單獨的權重輪叫排程算法依然會導緻伺服器間的負載不平衡。

從上面的算法流程中，我們可以看出當伺服器的權值為零時，該伺服器不被被排程；當所有伺服器的權值為零，即對于任意i有W(Si)=0，則沒有任何 伺服器可用，算法傳回NULL，所有的新連接配接都會被丢掉。權重輪叫排程也無需記錄目前所有連接配接的狀态，是以它也是一種無狀态排程。

2.3. 最小連接配接排程

最小連接配接排程（Least-Connection Scheduling）算法是把新的連接配接請求配置設定到目前連接配接數最小的伺服器。最小連接配接排程是一種動态排程算法，它通過伺服器目前所活躍的連接配接數來估計服務 器的負載情況。排程器需要記錄各個伺服器已建立連接配接的數目，當一個請求被排程到某台伺服器，其連接配接數加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;

當各個伺服器有相同的處理性能時，最小連接配接排程算法能把負載變化大的請求分布平滑到各個伺服器上，所有處理時間比較長的請求不可能被發送到同一台服 務器上。但是，當各個伺服器的處理能力不同時，該算法并不理想，因為TCP連接配接處理請求後會進入TIME_WAIT狀态，TCP的TIME_WAIT一般 為2分鐘，此時連接配接還占用伺服器的資源，是以會出現這樣情形，性能高的伺服器已處理所收到的連接配接，連接配接處于TIME_WAIT狀态，而性能低的伺服器已經 忙于處理所收到的連接配接，還不斷地收到新的連接配接請求。

2.4. 權重最小連接配接排程

權重最小連接配接排程（Weighted Least-Connection Scheduling）算法是最小連接配接排程的超集，各個伺服器用相應的權值表示其處理性能。伺服器的預設權值為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;

2.5. 基于局部性的最少連結排程

基于局部性的最少連結排程（Locality-Based Least Connections Scheduling，以下簡稱為LBLC）算法是針對請求封包的目标IP位址的負載均衡排程，目前主要用于Cache叢集系統，因為在Cache叢集中 客戶請求封包的目标IP位址是變化的。這裡假設任何後端伺服器都可以處理任一請求，算法的設計目标是在伺服器的負載基本平衡情況下，将相同目标IP位址的 請求排程到同一台伺服器，來提高各台伺服器的通路局部性和主存Cache命中率，進而整個叢集系統的處理能力。

LBLC排程算法先根據請求的目标IP位址找出該目标IP位址最近使用的伺服器，若該伺服器是可用的且沒有超載，将請求發送到該伺服器；若伺服器不 存在，或者該伺服器超載且有伺服器處于其一半的工作負載，則用“最少連結”的原則選出一個可用的伺服器，将請求發送到該伺服器。該算法的詳細流程如下：

LBLC排程算法流程

假設有一組伺服器S = {S0, S1, ..., Sn-1}，W(Si)表示伺服器Si的權值， C(Si)表示伺服器Si的目前連接配接數。ServerNode[dest_ip]是一個關聯變量，表示 目标IP位址所對應的伺服器結點，一般來說它是通過Hash表實作的。WLC(S)表示 在集合S中的權重最小連接配接伺服器，即前面的權重最小連接配接排程。Now為目前系統 時間。 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) AND there 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;

此外，對關聯變量ServerNode[dest_ip]要進行周期性的垃圾回收（Garbage Collection），将過期的目标IP位址到伺服器關聯項進行回收。過期的關聯項是指哪些目前時間（實作時采用系統時鐘節拍數jiffies）減去最 近使用時間超過設定過期時間的關聯項，系統預設的設定過期時間為24小時。

2.6. 帶複制的基于局部性最少連結排程

帶複制的基于局部性最少連結排程（Locality-Based Least Connections with Replication Scheduling，以下簡稱為LBLCR）算法也是針對目标IP位址的負載均衡，目前主要用于Cache叢集系統。它與LBLC算法的不同之處是它要 維護從一個目标IP位址到一組伺服器的映射，而LBLC算法維護從一個目标IP位址到一台伺服器的映射。對于一個“熱門”站點的服務請求，一台Cache 伺服器可能會忙不過來處理這些請求。這時，LBLC排程算法會從所有的Cache伺服器中按“最小連接配接”原則選出一台Cache伺服器，映射該“熱門”站 點到這台Cache伺服器，很快這台Cache伺服器也會超載，就會重複上述過程選出新的Cache伺服器。這樣，可能會導緻該“熱門”站點的映像會出現 在所有的Cache伺服器上，降低了Cache伺服器的使用效率。LBLCR排程算法将“熱門”站點映射到一組Cache伺服器（伺服器集合），當該“熱 門”站點的請求負載增加時，會增加集合裡的Cache伺服器，來處理不斷增長的負載；當該“熱門”站點的請求負載降低時，會減少集合裡的Cache伺服器 數目。這樣，該“熱門”站點的映像不太可能出現在所有的Cache伺服器上，進而提供Cache叢集系統的使用效率。

LBLCR算法先根據請求的目标IP位址找出該目标IP位址對應的伺服器組；按“最小連接配接”原則從該伺服器組中選出一台伺服器，若伺服器沒有超載， 将請求發送到該伺服器；若伺服器超載；則按“最小連接配接”原則從整個叢集中選出一台伺服器，将該伺服器加入到伺服器組中，将請求發送到該伺服器。同時，當該 伺服器組有一段時間沒有被修改，将最忙的伺服器從伺服器組中删除，以降低複制的程度。LBLCR排程算法的流程如下：

LBLCR排程算法流程

假設有一組伺服器S = {S0, S1, ..., Sn-1}，W(Si)表示伺服器Si的權值， C(Si)表示伺服器Si的目前連接配接數。ServerSet[dest_ip]是一個關聯變量，表示 目标IP位址所對應的伺服器集合，一般來說它是通過Hash表實作的。WLC(S)表示 在集合S中的權重最小連接配接伺服器，即前面的權重最小連接配接排程；WGC(S)表示在 集合S中的權重最大連接配接伺服器。Now為目前系統時間，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) AND there 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]; } else if (|ServerSet[dest_ip]| > 1 AND Now - 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) then ServerSet[dest_ip].lastmod = Now; return n;

此外，對關聯變量ServerSet[dest_ip]也要進行周期性的垃圾回收（Garbage Collection），将過期的目标IP位址到伺服器關聯項進行回收。過期的關聯項是指哪些目前時間（實作時采用系統時鐘節拍數jiffies）減去最 近使用時間（lastuse）超過設定過期時間的關聯項，系統預設的設定過期時間為24小時。

2.7. 目标位址散列排程

目标位址散列排程（Destination Hashing Scheduling）算法也是針對目标IP位址的負載均衡，但它是一種靜态映射算法，通過一個散列（Hash）函數将一個目标IP位址映射到一台伺服器。

目标位址散列排程算法先根據請求的目标IP位址，作為散列鍵（Hash Key）從靜态配置設定的散清單找出對應的伺服器，若該伺服器是可用的且未超載，将請求發送到該伺服器，否則傳回空。該算法的流程如下：

目标位址散列排程算法流程

假設有一組伺服器S = {S0, S1, ..., Sn-1}，W(Si)表示伺服器Si的權值， C(Si)表示伺服器Si的目前連接配接數。ServerNode[]是一個有256個桶（Bucket）的 Hash表，一般來說伺服器的數目會運小于256，當然表的大小也是可以調整的。 算法的初始化是将所有伺服器順序、循環地放置到ServerNode表中。若伺服器的 連接配接數目大于2倍的權值，則表示伺服器已超載。 n = ServerNode[hashkey(dest_ip)]; if ((n is dead) OR (W(n) == 0) OR (C(n) > 2*W(n))) then return NULL; return n;

在實作時，我們采用素數乘法Hash函數，通過乘以素數使得散列鍵值盡可能地達到較均勻的分布。所采用的素數乘法Hash函數如下：

素數乘法Hash函數

static inline unsigned hashkey(unsigned int dest_ip) { return (dest_ip* 2654435761UL) & HASH_TAB_MASK; } 其中，2654435761UL是2到2^32 (4294967296)間接近于黃金分割的素數， (sqrt(5) - 1) / 2 = 0.618033989 2654435761 / 4294967296 = 0.618033987

2.8. 源位址散列排程

源位址散列排程（Source Hashing Scheduling）算法正好與目标位址散列排程算法相反，它根據請求的源IP位址，作為散列鍵（Hash Key）從靜态配置設定的散清單找出對應的伺服器，若該伺服器是可用的且未超載，将請求發送到該伺服器，否則傳回空。它采用的散列函數與目标位址散列排程算法 的相同。它的算法流程與目标位址散列排程算法的基本相似，除了将請求的目标IP位址換成請求的源IP位址，是以這裡不一一叙述。

在實際應用中，源位址散列排程和目标位址散列排程可以結合使用在防火牆叢集中，它們可以保證整個系統的唯一出入口。

3. 動态回報負載均衡算法

動态回報負載均衡算法考慮伺服器的實時負載和響應情況，不斷調整伺服器間處理請求的比例，來避免有些伺服器超載時依然收到大量請求，進而提 高整個系統的吞吐率。圖1顯示了該算法的工作環境，在負載排程器上運作Monitor Daemon程序，Monitor Daemon來監視和收集各個伺服器的負載資訊。Monitor Daemon可根據多個負載資訊算出一個綜合負載值。Monitor Daemon将各個伺服器的綜合負載值和目前權值算出一組新的權值，若新權值和目前權值的內插補點大于設定的閥值，Monitor Daemon将該伺服器的權值設定到核心中的IPVS排程中，而在核心中連接配接排程一般采用權重輪叫排程算法或者權重最小連接配接排程算法。

圖1：動态回報負載均衡算法的工作環境

3.1. 連接配接排程

當客戶通過TCP連接配接通路網絡通路時，服務所需的時間和所要消耗的計算資源是千差萬别的，它依賴于很多因素。例如，它依賴于請求的服務類型、目前網 絡帶寬的情況、以及目前伺服器資源利用的情況。一些負載比較重的請求需要進行計算密集的查詢、資料庫通路、很長響應資料流；而負載比較輕的請求往往隻需要 讀一個HTML頁面或者進行很簡單的計算。

請求處理時間的千差萬别可能會導緻伺服器利用的傾斜（Skew），即伺服器間的負載不平衡。例如，有一個WEB頁面有A、B、C和D檔案，其中D是 大圖像檔案，浏覽器需要建立四個連接配接來取這些檔案。當多個使用者通過浏覽器同時通路該頁面時，最極端的情況是所有D檔案的請求被發到同一台伺服器。是以說， 有可能存在這樣情況，有些伺服器已經超負荷運作，而其他伺服器基本是閑置着。同時，有些伺服器已經忙不過來，有很長的請求隊列，還不斷地收到新的請求。反 過來說，這會導緻客戶長時間的等待，覺得系統的服務品質差。

3.1.1. 簡單連接配接排程

簡單連接配接排程可能會使得伺服器傾斜的發生。在上面的例子中，若采用輪叫排程算法，且叢集中正好有四台伺服器，必有一台伺服器總是收到D檔案的請求。這種排程政策會導緻整個系統資源的低使用率，因為有些資源被用盡導緻客戶的長時間等待，而其他資源空閑着。

3.1.2. 實際TCP/IP流量的特征

文獻[1]說明網絡流量是呈波浪型發生的，在一段較長時間的小流量後，會有一段大流量的通路，然後是小流量，這樣跟波浪一樣周期性地發生。文獻 [2,3,4,5]揭示在WAN和LAN上網絡流量存在自相似的特征，在WEB通路流也存在自相似性。這就需要一個動态回報機制，利用伺服器組的狀态來應 對通路流的自相似性。

3.2. 動态回報負載均衡機制

TCP/IP流量的特征通俗地說是有許多短事務和一些長事務組成，而長事務的工作量在整個工作量占有較高的比例。是以，我們要設計一種負載均衡算法，來避免長事務的請求總被配置設定到一些機器上，而是盡可能将帶有毛刺（Burst）的分布分割成相對較均勻的分布。

我們提出基于動态回報負載均衡機制，來控制新連接配接的配置設定，進而控制各個伺服器的負載。例如，在IPVS排程器的核心中使用權重輪叫排程 （Weighted Round-Robin Scheduling）算法來排程新的請求連接配接；在負載排程器的使用者空間中運作Monitor Daemon。Monitor Daemon定時地監視和收集各個伺服器的負載資訊，根據多個負載資訊算出一個綜合負載值。Monitor Daemon将各個伺服器的綜合負載值和目前權值算出一組新的權值。當綜合負載值表示伺服器比較忙時，新算出的權值會比其目前權值要小，這樣新配置設定到該服 務器的請求數就會少一些。當綜合負載值表示伺服器處于低使用率時，新算出的權值會比其目前權值要大，來增加新配置設定到該伺服器的請求數。若新權值和目前權值 的內插補點大于設定的閥值，Monitor Daemon将該伺服器的權值設定到核心中的IPVS排程中。過了一定的時間間隔（如2秒鐘），Monitor Daemon再查詢各個伺服器的情況，并相應調整伺服器的權值；這樣周期性地進行。可以說，這是一個負回報機制，使得伺服器保持較好的使用率。

在權重輪叫排程算法中，當伺服器的權值為零，已建立的連接配接會繼續得到該伺服器的服務，而新的連接配接不會配置設定到該伺服器。系統管理者可以将一台伺服器的 權值設定為零，使得該伺服器安靜下來，當已有的連接配接都結束後，他可以将該伺服器切出，對其進行維護。維護工作對系統都是不可少的，比如硬體更新和軟體更新 等，零權值使得伺服器安靜的功能很主要。是以，在動态回報負載均衡機制中我們要保證該功能，當伺服器的權值為零時，我們不對伺服器的權值進行調整。

3.3. 綜合負載

在計算綜合負載時，我們主要使用兩大類負載資訊：輸入名額和伺服器名額。輸入名額是在排程器上收集到的，而伺服器名額是在伺服器上的各種負載資訊。 我們用綜合負載來反映伺服器目前的比較确切負載情況，對于不同的應用，會有不同的負載情況，這裡我們引入各個負載資訊的系數，來表示各個負載資訊在綜合負 載中輕重。系統管理者根據不同應用的需求，調整各個負載資訊的系數。另外，系統管理者設定收集負載資訊的時間間隔。

輸入名額主要是在機關時間内伺服器收到新連接配接數與平均連接配接數的比例，它是在排程器上收集到的，是以這個名額是對伺服器負載情況的一個估計值。在排程 器上有各個伺服器收到連接配接數的計數器，對于伺服器Si，可以得到分别在時間T1和T2時的計數器值Ci1和Ci2，計算出在時間間隔T2-T1内伺服器 Si收到新連接配接數Ni = Ci2 - Ci1。這樣，得到一組伺服器在時間間隔T2-T1内伺服器Si收到新連接配接數{Ni}，伺服器Si的輸入名額INPUTi為其新連接配接數與n台伺服器收到平 均連接配接數的比值，其公式為

伺服器名額主要記錄伺服器各種負載資訊，如伺服器目前CPU負載LOADi、伺服器目前磁盤使用情況Di、目前記憶體利用情況Mi和目前程序數目 Pi。有兩種方法可以獲得這些資訊；一是在所有的伺服器上運作着SNMP（Simple Network Management Protocol）服務程序，而在排程器上的Monitor Daemon通過SNMP向各個伺服器查詢獲得這些資訊；二是在伺服器上實作和運作收集資訊的Agent，由Agent定時地向Monitor Daemon報告負載資訊。若伺服器在設定的時間間隔内沒有響應，Monitor Daemon認為伺服器是不可達的，将伺服器在排程器中的權值設定為零，不會有新的連接配接再被配置設定到該伺服器；若在下一次伺服器有響應，再對伺服器的權值進 行調整。再對這些資料進行處理，使其落在[0, ∞)的區間内，1表示負載正好，大于1表示伺服器超載，小于1表示伺服器處于低負載狀态。獲得調整後的資料有DISKi、MEMORYi和 PROCESSi。

另一個重要的伺服器名額是伺服器所提供服務的響應時間，它能比較好地反映伺服器上請求等待隊列的長度和請求的處理時間。排程器上的Monitor Daemon作為客戶通路伺服器所提供的服務，測得其響應時間。例如，測試從WEB伺服器取一個HTML頁面的響應延時，Monitor Daemon隻要發送一個“GET /”請求到每個伺服器，然後記錄響應時間。若伺服器在設定的時間間隔内沒有響應，Monitor Daemon認為伺服器是不可達的，将伺服器在排程器中的權值設定為零。同樣，我們對響應時間進行如上調整，得到RESPONSEi。

這裡，我們引入一組可以動态調整的系數Ri來表示各個負載參數的重要程度，其中ΣRi = 1。綜合負載可以通過以下公式計算出：

例如，在WEB伺服器叢集中，我們采用以下系數{0.1, 0.3, 0.1, 0.1, 0.1, 0.3}，認為伺服器的CPU負載和請求響應時間較其他參數重要一些。若目前的系數Ri不能很好地反映應用的負載，系統管理者可以對系數不斷地修正，直到 找到貼近目前應用的一組系數。

另外，關于查詢時間間隔的設定，雖然很短的間隔可以更确切地反映各個伺服器的負載，但是很頻繁地查詢（如1秒鐘幾次）會給排程器和伺服器帶來一定的 負載，如頻繁執行的Monitor Daemon在排程器會有一定的開銷，同樣頻繁地查詢伺服器名額會伺服器帶來一定的開銷。是以，這裡要有個折衷（Tradeoff），我們一般建議将時間 間隔設定在5到20秒之間。

3.4. 權值計算

當伺服器投入叢集系統中使用時，系統管理者對伺服器都設定一個初始權值DEFAULT_WEIGHTi，在核心的IPVS排程中也先使用這個權值。 然後，随着伺服器負載的變化，對權值進行調整。為了避免權值變成一個很大的值，我們對權值的範圍作一個限制[DEFAULT_WEIGHTi, SCALE*DEFAULT_WEIGHTi]，SCALE是可以調整的，它的預設值為10。

Monitor Daemon周期性地運作，若DEFAULT_WEIGHTi不為零，則查詢該伺服器的各負載參數，并計算出綜合負載值AGGREGATE_LOADi。我們引入以下權值計算公式，根據伺服器的綜合負載值調整其權值。

在公式中，0.95是我們想要達到的系統使用率，A是一個可調整的系數（預設值為5）。當綜合負載值為0.95時，伺服器權值不變；當綜合負載值大 于0.95時，權值變小；當綜合負載值小于0.95時，權值變大。若新權值大于SCALE*DEFAULT_WEIGHTi，我們将新權值設為 SCALE*DEFAULT_WEIGHTi。若新權值與目前權值的差異超過設定的閥值，則将新權值設定到核心中的IPVS排程參數中，否則避免打斷 IPVS排程的開銷。我們可以看出這是一個負回報公式，會使得權值調整到一個穩定點，如系統達到理想使用率時，權值是不變的。

在實際使用中，若發現所有伺服器的權值都小于他們的DEFAULT_WEIGHT，則說明整個伺服器叢集處于超載狀态，這時需要加入新的伺服器結點 到叢集中來處理部分負載；反之，若所有伺服器的權值都接近于SCALE*DEFAULT_WEIGHT，則說明目前系統的負載都比較輕。

3.5. 一個實作例子

我們在RedHat叢集管理工具Piranha[6]中實作了一個簡單的動态回報負載均衡算法。在綜合負載上，它隻考慮伺服器的CPU負載（Load Average），使用以下公式進行權值調整：

伺服器權值調整區間為[DEFAULT_WEIGHTi, 10*DEFAULT_WEIGHTi]，A為DEFAULT_WEIGHTi /2，而權值調整的閥值為DEFAULT_WEIGHTi /4。1是所想要達到的系統使用率。Piranha每隔20秒查詢各台伺服器的CPU負載，進行權值計算和調整。

4. 小結

本文主要講述了IP虛拟伺服器在核心中實作的八種連接配接排程算法：

• 輪叫排程（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. William Stalling, Viewpoint: Self-similarity upsets data traffic assumptions, IEEE Spectrum, January 1997.
2. Kihong Park, Gitae Kim, Mark Crovella, "On the Effect of Traffic Self-similarity on Network Performance", In Proceedings of the 1997 SPIE International Conference on Performance and Control of Network Systems, 1997.
3. Nicolas D. Georganas, Self-Similar ("Fractal") Traffic in ATM Networks, In Proceedings of the 2nd International Workshop on Advanced Teleservices and High-Speed Communications Architectures (IWACA'94), pages 1-7, Heidelberg, Germany, September 1994.
4. Mark Crovella and Azer Besavros, Explaining World Wide Web Traffic Self-Similarity. Technical report, Boston University, October 1995, TR-95-015.
5. Bruce A. Mah. An Empirical Model of HTTP Network Traffic. In Proceedings of INFOCOM 97, Kobe, Japan, April 1997.
6. Red Hat High Availability Server Project, ​​http://ha.redhat.com/​​
7. The Linux Virtual Server Project, ​​http://www.LinuxVirtualServer.org/​​