摘 要：負載均衡在集群系統(tǒng)中的作用日益重要，而現(xiàn)有算法的效率不高、部署復(fù)雜的原因限制了其更進一步發(fā)展。通過分析不同類型的服務(wù)請求對服務(wù)器造成不同負載，結(jié)合監(jiān)測服務(wù)器的CPU和內(nèi)存利用的即時性能，在克服了現(xiàn)有負載均衡算法的一些缺陷基礎(chǔ)上提出了一種簡單穩(wěn)定的基于服務(wù)分類和性能監(jiān)測算法，并通過Web壓力測試實驗比較了該算法在實際應(yīng)用中的均衡性能。結(jié)果驗證了其在服務(wù)器集群系統(tǒng)有大的訪問請求量時有突出性能，能夠使集群系統(tǒng)達到良好的負載均衡。

關(guān)鍵詞：負載均衡；服務(wù)分類；性能監(jiān)測；壓力測試

中圖分類號：TP302.1文獻標(biāo)識碼：A

文章編號：1004-373X(2008)24-137-03

Load Balancing Based on Services Sort and Capability Surveillance

LIN Hongxiang，LIU Damao

(College of Physics and Information Engineering，F(xiàn)uzhou University，F(xiàn)uzhou，350002，China)

Abstract：The further development of load balancing is blocked by the low efficiency and high complexity of current algorithms，although the importance of load balancing in Server Cluster is increasing day by day.After considering that different serve request makes different load to server and monitoring the instant performance of sever (using rate of CPU and memory)，a simple load balancing algorithm which gets over disadvantages of the current algorithms is proposed based on services sort and capability surveillance.The algorithm′s capability is excellence in the Web pressure test.It can make the Server Cluster load balancing usefully，especially when there is a large amount of request.

Keywords：load balancing;services sort;capability surveillance;pressure test

隨著計算機網(wǎng)絡(luò)的飛速發(fā)展，網(wǎng)絡(luò)成為大多數(shù)應(yīng)用的平臺，因而對網(wǎng)絡(luò)服務(wù)器性能和穩(wěn)定性的要求也越來越高^［1］。正基于此，服務(wù)器集群技術(shù)得到了飛速發(fā)展，并成了實現(xiàn)高性能網(wǎng)絡(luò)服務(wù)器的有效途徑?？墒怯捎谌蝿?wù)分配和服務(wù)器的差異使得集群中各服務(wù)器的利用率不同，系統(tǒng)整體性能不高。本文提出了一種對集群系統(tǒng)中的服務(wù)請求的按照類型進行分類，做系數(shù)化分析，然后結(jié)合服務(wù)器內(nèi)部實時的性能來判斷服務(wù)器的動態(tài)負載，最后通過實驗驗證了算法的性能。

1 服務(wù)器集群結(jié)構(gòu)分析

1.1 服務(wù)器集群的結(jié)構(gòu)

服務(wù)器集群系統(tǒng)（Server Cluster）由多臺同構(gòu)或異構(gòu)的服務(wù)器通過某種方式連接起來協(xié)同完成特定的服務(wù)或任務(wù)^［2］。集群的系統(tǒng)結(jié)構(gòu)如圖1所示。當(dāng)客戶發(fā)起服務(wù)請求到達時，分配器根據(jù)各服務(wù)器的負載狀況選擇一臺服務(wù)器，將服務(wù)轉(zhuǎn)定向給該服務(wù)器，由其響應(yīng)用戶請求。通過負載均衡，可以使多臺服務(wù)器同時為大量用戶提供服務(wù)。當(dāng)某臺服務(wù)器出現(xiàn)故障時，負載均衡服務(wù)器會停止將服務(wù)請求分發(fā)至該服務(wù)器，轉(zhuǎn)而由其他服務(wù)器繼續(xù)提供服務(wù)。

圖1 服務(wù)器集群系統(tǒng)的體系結(jié)構(gòu)圖

以前的算法大都是由分配器記錄各臺服務(wù)器的連接服務(wù)請求數(shù)量，然后在新的服務(wù)請求到來時將其發(fā)往連接數(shù)最少的服務(wù)器。這類算法在異構(gòu)服務(wù)器集群中，由于沒有考慮各臺服務(wù)器的差異，系統(tǒng)性能的提高肯定有限^［3］。

1.2 集群負載分析

不同類型的請求占用服務(wù)器的資源不同，服務(wù)器的處理速度、響應(yīng)時間也不盡相同。Arlitt等人對 Waterloo大學(xué)^［4］肯尼迪宇航中心等服務(wù)器的日志進行分析，分析過程中將日志文件中涉及到的請求文檔分為７種類型。各種文檔的文件類型和在日志文件中所占的比重如表1所示。

表1

顯然不同的服務(wù)請求，給服務(wù)器帶來的負擔(dān)是不相同的。分配器在對集群中各服務(wù)器負載分析時，僅根據(jù)服務(wù)器的連接數(shù)來進行判斷是不夠的。因此對不同的服務(wù)請求設(shè)定不同負載系數(shù)，然后統(tǒng)計服務(wù)器的最終負載是必要的。

2 基于服務(wù)分類和性能監(jiān)測的負載均衡算法

2.1 算法基本思想

負載均衡是通過采集各服務(wù)器的負載信息，進行分析后將新的服務(wù)請求送到最適合的服務(wù)器，從而提高集群效率。為了能及時地收集負載信息，分配器不再主動查詢，改為被動接受。各服務(wù)器在有新的請求到來時，采集自身的負載信息，按照統(tǒng)一的量化標(biāo)準統(tǒng)計。將新的結(jié)果與原來的比較，如果差值超過設(shè)定的閥值，就將新的負載結(jié)果送到分配器。采集、計算負載的任務(wù)由各服務(wù)器自身來完成，送到分配器的僅就是一個量化值。原本由分配器完成的任務(wù)，分散到集群各服務(wù)器。服務(wù)器傳給分配器只有一個負載值，從而大大減少了通信量。分配器除在接收到新的負載值時進行重新排序外，就專心完成任務(wù)轉(zhuǎn)交。

集群服務(wù)器在統(tǒng)計自身負載的時候，其中關(guān)鍵的一項就是服務(wù)連接數(shù)。如前述可知，不能僅根據(jù)連接數(shù)量，還應(yīng)該考慮連接服務(wù)內(nèi)容的不同。以表1的分析可知，可以分析服務(wù)器的訪問日志將請求服務(wù)分為多個類。將其中某類作為一個標(biāo)準類，用該標(biāo)準類測試各臺服務(wù)器的處理一個該類服務(wù)請求的能力。其他服務(wù)類的權(quán)值可由其負載比重與標(biāo)準類的比值，然后進行統(tǒng)計。

集群系統(tǒng)中有n臺服務(wù)器，服務(wù)請求類別分為m類，則第i臺服務(wù)器的負載值為：

Loadi=∑mj=1rjcjεi

1≤i≤n，1≤j≤m;i，j∈N(1)

其中εi表示第i臺服務(wù)器處理單位標(biāo)準類給服務(wù)器所添加的負擔(dān)，也即服務(wù)器i處理單位標(biāo)準類效能；cj為j類服務(wù)請求的連接數(shù)，rj表示j類服務(wù)請求的權(quán)重，并且∑mj=1rj=1。

服務(wù)訪問請求對服務(wù)器帶來的負載充分反映到服務(wù)器的即時性能，即CPU和內(nèi)存利用率上，但反之則不然。服務(wù)器除了響應(yīng)服務(wù)請求外，也運行包括系統(tǒng)、安全、數(shù)據(jù)庫等多種軟件。這些軟件的運行具有很強的普遍性和隨機性，帶來的負載在其運行期間內(nèi)是不應(yīng)被忽略的。負載的計算僅按照連接數(shù)計算還是比較粗糙的。所以將反應(yīng)服務(wù)器動態(tài)處理性能的CPU使用率和內(nèi)存利用率同時計入負載值，雖然會帶來一部分的重復(fù)計算，但是卻可以更精確地得到動態(tài)負載值。由此可得到優(yōu)化的負載值計算公式：

Loadi=(∑mj=1rjcjεi)λc+uiλu+viλv(2)

其中:

λu+λv+λc=1(3)

ui，vi分別表示服務(wù)器i的CPU使用率和內(nèi)存利用率；λu和λv分別表示CPU使用率和內(nèi)存利用率在計算服務(wù)器的負載值Load中所占比重；λc表示連接數(shù)在計算服務(wù)器的負載值Load中所占比重。

2.2 算法的實現(xiàn)策略

在集群正常工作前，要進行集群部署、檢測等一系列初始化工作。和負載平衡相關(guān)的是進行軟件部署，測試取得一些重要數(shù)據(jù)。實現(xiàn)的步驟如下：

（1）由分配器進行測算，取得集群中各服務(wù)器的單位標(biāo)準類連接服務(wù)的負載值εi和負載更新閥值τi；

（2）進行服務(wù)器的日志統(tǒng)計，將服務(wù)請求分為m類，這個也可以由管理員設(shè)置得到，特別是在服務(wù)器開始工作沒有日志的情況下；

（3） 根據(jù)式（1）得到服務(wù)器負載值，送到分配器；

（4） 分配器維護一個Loadi列表，進行排序。

集群服務(wù)器系統(tǒng)開始工作后，分配器主要完成負載值排序和將服務(wù)請求轉(zhuǎn)交給負載值最小的服務(wù)器2項工作。服務(wù)器上的均衡軟件的算法流程圖如圖2所示。

由分配器進行Loadi列表排序，新的請求服務(wù)到來時將其轉(zhuǎn)到集群中負載值最低的服務(wù)器上，備用分配器上備份一個相同的負載列表；

服務(wù)器在接受新的服務(wù)請求后，重新計算負載值Loadi，將新負載值與原負載值比較，如果差值大于τi，則將新負載值送到分配器，否則僅用新負載值替代原值；

服務(wù)器在時間T內(nèi)接受新的請求，則按照式(2)重新計算負載值，并送到分配器內(nèi)。如果分配器在T時間內(nèi)沒有收到新的負載值，則進行專門檢測，以確定該服務(wù)器是否出現(xiàn)故障。如果出現(xiàn)故障，則將該服務(wù)器上維持的服務(wù)進行轉(zhuǎn)移。

圖2 服務(wù)器i的工作流程圖

3 實驗結(jié)果分析

Web壓力測試是檢測負載均衡性能的一種有效實驗方法。通過外部對集群系統(tǒng)進行一系列訪問，測試出完成服務(wù)請求的時間作為衡量指標(biāo)。實驗中采用Web-CT作為壓力測試工具對集群系統(tǒng)進行一系列的訪問，測試出系統(tǒng)完成任務(wù)所需要的最少時間。為了對算法的有效性進行比較驗證，同時測試了循環(huán)輪轉(zhuǎn)算法、最少連接算法。由實驗室自寫的實現(xiàn)本文算法的Web訪問插件（考慮到分配器列表維護的原因沒有包括故障檢測與處理部分）。實驗中對3種算法進行測試，研究各算法在Web壓力從小到大逐漸變時的平均響應(yīng)時間。

3種算法為：

循環(huán)輪轉(zhuǎn)算法：分配器將服務(wù)請求輪流轉(zhuǎn)交給集群中的服務(wù)器；

最少連接算法：分配器僅僅統(tǒng)計集群系統(tǒng)中個服務(wù)器的連接數(shù)，將新到來的服務(wù)請求轉(zhuǎn)交給連接數(shù)最少的服務(wù)器；

實現(xiàn)的算法：如上文所討論的改進算法，λu，λv和λc分別取為10%，10%和80%。對實驗中的系數(shù)實驗的結(jié)果如圖3所示。負載均衡分別采用式（1）和式（2），并將服務(wù)器集群中的一些服務(wù)器進行殺毒檢測，播放視頻文件等應(yīng)用服務(wù)，實驗結(jié)果如圖4所示。分析以上實驗分析可知：

訪問的服務(wù)請求量較少時，改進的算法性能反而比較差。因為在服務(wù)訪問請求量較少時，改進算法的動態(tài)檢測和復(fù)雜計算反而影響了負載的分配，降低了均衡效能。隨著訪問請求的增加，改進算法的性能就與最少連接算法相當(dāng)，循環(huán)輪轉(zhuǎn)算法的性能就比較差了。當(dāng)訪問請求達到一定程度后，改進算法的性能就明顯優(yōu)于其他的兩種算法。實驗結(jié)果驗證了改進的均衡算法的性能較好，尤其是在服務(wù)器集群系統(tǒng)有很大訪問量時均衡效率更為突出。

圖3 三種算法的壓力測試結(jié)果比較

圖4的實驗結(jié)果說明在有較大的服務(wù)請求時，采用式（2）作為負載均衡的算法的比采用式（1）的更能高效。而式（2）正是考慮了對計算機系統(tǒng)性能進行了實時監(jiān)測。但在服務(wù)請求量較小時，式（2）相對復(fù)雜計算和所需參數(shù)采集反而成為負擔(dān)。在實驗結(jié)果中，在壓力測試集密度較小時，式（2）的平均響應(yīng)時間大于式（1）正說明了這一點。而且在λu，λv和λc取不同的值時對結(jié)果有不同的影響，這就需要一個動態(tài)分析得到最優(yōu)解。所以在實際應(yīng)用中應(yīng)該根據(jù)實際情況，權(quán)衡復(fù)雜性和效能選用最適合的負載均衡算法。

圖4 兩種公式的壓力測試結(jié)果比較

4 結(jié) 語

隨著集群系統(tǒng)的應(yīng)用越來越廣，為了提高集群的系統(tǒng)效率，負載均衡的重要性也更加突出。在此提出了一種基于服務(wù)請求分類和性能監(jiān)測的負載均衡算法，并且充分考慮了服務(wù)器內(nèi)部運行狀況，動態(tài)地測算計算機內(nèi)部負載。實驗結(jié)果驗證了改進的算法有較好的性能，能較好地實現(xiàn)負載均衡，提高集群的系統(tǒng)效率。

參考文獻

［1］Andresen D，Yang T，Holmedahl V，et al.SWeb:Toward a Scalable World Wide Web Server on Multi-computers［A］.In Proceeding of the 10th International Symposium on Parallel Processing (ISSP′96).1996:850-856.

［2］Devine，Karen D Boman，Erik G，et al.New Challenges in Dynamic Load Balancing［J］.Applied Numerical Mathematics，SPEC.ISS.，2005，52(2):133-152.

［3］趙宏，林建，朱淼良.針對Web服務(wù)的動態(tài)負載平衡模型.計算機工程與設(shè)計，2006(21):4 108-4 110.

［4］Arlitt M，Williamson C.Web Server Workload Characterization:the Search for Invariants［A］.In Proceedings of the ACM SIGMETRICS Conference.1996:126-137.

［5］林闖.隨機Petri網(wǎng)和系統(tǒng)性能評價［M］.北京:清華大學(xué)出版社，2000.

［6］陳志剛，李登，曾志文.分布式系統(tǒng)中一種動態(tài)負載均衡策略相關(guān)模型及算法研究 ［J］.小型微型計算機系統(tǒng)，2002，23 (12):1 434-1 437.

［7］劉振英，方濱興，胡銘曾，等.一個有效的動態(tài)負載平衡方法［J］.軟件學(xué)報，2001，12(4):563-569.

［8］廖羽，戴瑜興.基于內(nèi)容的分布式Web服務(wù)器負載平衡算法［J］.電子學(xué)報，2006，34(6):1 053-1 057.

［9］向建軍，白欣，左繼章.一種用于實時集群的多任務(wù)負載均衡算法［J］.計算機工程，2003，29(12):36-38.

［10］王曉川，葉超群，金士堯.一種基于分布式調(diào)度機制的集群體系結(jié)構(gòu)［J］.計算機工程，2002，28(3):131-133.

［11］王玥，蔡皖東，段琪.一種自適應(yīng)動態(tài)負載均衡算法［J］.計算機工程與應(yīng)用，2006，42(21):121-123.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文