基于服務類型的動態反饋負載均衡算法
2009-01-01 00:00:00丁振國朱建新
計算機應用研究 2009年5期
（西安電子科技大學 計算機學院 西安 710071）
摘 要：針對現有靜態和動態負載均衡算法往往存在計算服務節點負載過程中引用特征信息過少，或忽視不同類型服務對于節點負載的影響等問題，提出了一種基于服務類型的動態反饋算法。該算法統計各節點的多種負載信息，通過NECP協議實現動態反饋，并引入負載權重向量和負載能力向量計算節點的綜合負載。算法在實際的仿真環境中得到了驗證，說明了具有可用性和優越性。
關鍵詞：網絡設備控制協議； 服務類型； 動態反饋； 負載均衡
中圖分類號：TP311; TP301.6文獻標志碼：A
文章編號：1001-3695(2009)05-1682-03
Dynamic feedback load balancing algorithm based on different services
DING Zhenguo ZHU Jianxin
(College of Computer Science Xidian University Xi’an 710071 China)
Abstract:The current static and dynamic load balancing algorithms are usually of using less simple factors in calculating the node’s load or having an overlook on the effect on system load caused by the different services. This paper presented a dynamic load balancing algorithm which collected many types of system’s payload and feeded them back by NECP. Introducedload weight vector and load capacity vectorin the calculating process of the node’s integrated load. Being tested in simulation system the algorithm carries usability and advantages.
Key words：NECP(network element control protocol); service types; dynamic feedback; load balancing
業務選擇網關(service selection gateway，SSG)是一種基于URL細粒度的內容選擇網關[1]，通過提供個性化的服務菜單，為客戶提供豐富多彩的內容服務。由于客戶層次的多級化，以及通過網關發布服務的多樣化等特點，決定了SSG設備必須能夠滿足較高的QoS要求。
在用戶訪問量和服務資源不斷膨脹的情況下，Web服務器的性能已成為了網絡服務質量的主要因素之一。網絡集群服務器以其較好的可擴展性、高可靠性、低性價比的特點，為Web服務器系統帶來了新的解決方案[2]。文獻[3]中介紹了一個服務器集群的應用實例。負載均衡是這類系統的核心技術，其應用保證了多臺服務器負載的均衡性，實現了對用戶請求進行公平合理的分配和調度，提高了系統的反應效率和自身的穩定性。
SSG作為發布網絡服務的網絡設備，如果能夠利用負載均衡技術實現對于一定規模的服務器集群系統的支持，必然能夠提高設備的功能性。本文針對SSG的功能特點設計并實現了一種基于服務類型的動態反饋負載均衡算法。
1 負載均衡算法
1.1 經典算法
Web服務器集群中實現負載均衡的請求調度算法主要分為靜態算法和動態算法兩類 文獻[5]中對其應用分別作了深入的分析。靜態負載均衡算法目前的應用范圍比較廣泛，并且技術比較成熟，經典算法包括輪轉調度(RR)、加權輪轉調度(WRR)、最小連接數調度(LC)、加權最小連接數調度(WLC)、目標地址散列調度(DH)等。
動態負載均衡算法主要引進了一種反饋機制，通過監測每一個節點的實時負載和響應能力，而不斷調整任務分布的比例，來盡量避免服務器利用率嚴重傾斜。
1.2 存在問題
隨著訪問用戶和新型服務的不斷增加，現有的負載均衡算法逐漸顯露出了各種弊端。
a)靜態算法使用少量靜態特征信息，實現相對簡單，僅能適用于小規模的、單一配置的靜態網頁Web服務系統[4]。由于網頁中越來越多地使用動態嵌入對象(Scripts程序等)和數據庫查詢任務，使得不同請求任務的工作負荷有很大差異，靜態網頁和動態網頁的負載可以相差 10倍或100倍[5]。單靠靜態算法已經不能達到負載均衡的效果。
b)現有的動態算法有的進行單一的負載信息的反饋，如CPU使用率、平均請求響應時間等，如文獻[6]中提出的算法，但這樣并不能反映不同服務對服務器各種資源負載的影響。另外，有的算法雖然能夠考慮到這一點卻又忽視了服務器自身處理能力上的差異。而且，算法對于系統的可擴展性也應有所考慮。
2 動態反饋負載均衡
算法思想：由于是在SSG中實現負載均衡，進行調度的連接請求將是基于URL級細粒度的[7]。本文中的算法將分兩部分，一部分是內核中的請求調度模塊；另一部分是用戶層的負載查詢器。對于到達的請求包，首先按照服務類型進行分類入隊，這里可以引用文獻[8]中的自適應隊列算法。來自不同請求隊列中的數據包將以一種基于動態權值的概率調度(dynamic weightbased probability scheduling，DWPS) 算法進行轉發。服務器負載的權值將根據不同的服務類型進行計算，并在后面介紹的反饋機制下進行動態修正。
2.1 動態反饋機制
本算法中的動態反饋機制包括負載查詢器(NECP server)和反饋代理(NECP agent)兩部分。前者運行于SSG上；后者運行于每個服務器節點上。它們均以用戶層進程形式實現，通過NECP協議進行通信。
2.1.1 NECP
該協議是一種嚴格按照控制協議來設計的、用于在網絡設備與服務節點之間進行通信的輕量級協議。NECP基于TCP，提供了一些方法，實現網絡設備感知服務節點的負載能力、可達性，以及獲得服務請求可否被響應的提示[9]。NECP的數據包格式如圖1所示。
文獻[9]中對NECP進行了詳細描述。本文中的應用主要是對其進行數據包擴展，在協議中添加多個基本有效負荷單元（BPU），每個BPU中記錄一種系統資源的當前負載，如CPU使用率、內存使用率等。
2.1.2 查詢器和反饋代理
查詢器NECP server和反饋代理NECP agent之間是一對多的關系，通過固定的TCP端口3262進行通信。反饋機制如圖2所示。
NECP server和NECP agent的工作以連接初始化過程開始，然后server向各服務節點發送NECP_KEEP_ALIVE類型查詢請求包，agent將會以NECP_KEEP_ALIVE_ACK包進行響應，同時返回各項系統資源的負載情況。NECP server負責將搜集的各服務器的負載通過接口交付給內核中的請求調度模塊，從而形成查詢—計算—修正—查詢的反饋循環。考慮到過于頻繁的負載信息統計會為SSG設備帶來負擔，應合理設定查詢時間間隔。
2.2 算法實現
2.2.1 權值計算過程
服務器集合為S={S0，S1，S2，…，Sn-1}，n為服務節點數。每個服務節點的權值應根據節點當前的負載和其固有的負載能力進行計算。節點Si(i∈{0，1，…，n-1}）的當前負載為L(Si)，基本負載能力為Ci，Si的權值為W(Si)，且有
W(Si)=L(Si)/Ci i∈{0，1，…，n-1}(1)
這里引用文獻[6]中的觀點，服務器達到平衡狀態時應有
W(S0)=W(S1)=…=W(Sn-1)(2)
但是實際情況并不能達到這種理想的平衡狀態，算法的目標是盡量逼近這一結果。
算法中計算節點負載時包括的系統資源有CPU、內存和網絡帶寬，由每個節點上的NECP agent反饋給SSG網關中運行的NECP server；再由NECP server將其定時更新到內核部分的負載信息表中。節點Si的負載可用向量描述為
Li=(Lcpu，Lmem，Lnet)(3)
式(1)中引入的節點Si的基本負載能力Ci也用向量表示。其中各值依據節點的實際硬件配置進行設定，有
Ci=(Cicpu，Cimem，Cinet)(4)
本算法實現的是基于服務類型的負載均衡，節點在提供不同類型服務的情況下對自身負載影響的參數也會不同。因此，在引入請求隊列集合Q={Q0，Q1，…，Qn-1} (m表示服務類型數)的同時，引入負載權重向量α，不同請求隊列對應的權重向量為
αt=(αcput，αmemt，αnett)
且｜αt｜=1，t∈{0，1，…，m-1}(5)
例如對于動態網頁服務，需進行大量的數據庫訪問和邏輯計算，服務節點的CPU和內存的負載權重會相對較大，網絡帶寬的負載權重次之，可以設定αdp=(0.5，0.3，0.2)。每個服務類型的權重向量都應根據實際的測試結果進行設置，從而達到較好的效果。
由于服務節點在不同服務類型下體現的負載能力不同，其權值的計算結果也不相同，在對Qt中的請求進行調度的過程中，Si的當前負載和負載能力可由下列表達式計算
Lt(Si)=αt×Li=αcput×Lcpu+αmemt×Lmem+αnett×Lnet(6)
Cti=αt×Ci=αcput×Cicpu+αmemt×Cimem+αnett×Cinet(7)
所以，請求調度前計算Si的權值為
Wt(Si)=αt×(Li/Ci)=Lt(Si)/Cit(8)
為了滿足式(2)的要求，在進行均衡調度時應盡量將較多的請求轉發至滿足min{Wt(Si)}的服務器上。同時負載較大的服務器將獲得較少的連接，負載增加減緩，從而使所有服務器節點在運行一段時間后逐漸逼近平衡狀態。
2.2.2 概率轉發
現有的靜態和動態負載均衡算法中，大都是基于加權分配算法對請求進行固定比例的分配，服務節點所分配到請求的比例與權值相對應。由于無法控制請求任務到達的具體時間和數量，這種固定轉發的模式本身就可能引起請求分配的不均衡[2]。為了兼顧請求調度的均衡性和隨機性，盡量避免不同分配周期間的關聯影響，本文引入隨機轉發的概念，即根據計算出的節點權值來構成請求轉發的概率空間。由于轉發同時受服務類型的影響，最終構成的應該是一個二維空間，縱向區域根據請求隊列Q劃分為m(服務類型個數)段；橫向通過節點權值將總長度為1的區域劃分成n(節點個數)段。段越長代表節點的負載較輕，被選中的概率較大。例如，有四個服務節點和三種服務類型的情況下，請求轉發的概率空間如圖3所示。
當對請求進行轉發時，首先判斷它來自哪個請求隊列，然后根據其對應的服務類型縱向選擇概率空間的區域，再根據各節點概率計算出一個(0，1)區間的隨機數。隨機數所屬區間對應的節點即為調度選取的節點。
3 算法仿真與性能分析
3.1 仿真環境
在SSG中加入負載均衡模塊之前，首先進行了算法的仿真實驗。實驗環境包括一臺服務器充當SSG設備，四臺服務器作為提供服務的server。所有設備連接在Cisco3750交換機上，并分配內網IP。設備的硬件配置如表1所示。
表1 測試環境
設備CPU內存/MB網絡帶寬/Mbps
SSGPentium IV 3.2 GHz512100
server 1Pentium IV 2.4 GHz512100
server 2Pentium IV 2.0 GHz512100
server 3Celeron 2.4D256100
server 4Celeron 2.4D256100
五臺設備采用一樣的操作系統RedHat Linux 9，內核版本為Linux Kernel 2.4.20，其他軟件配置包括gcc3.2.2、glibc2.3.2、GNUld2.14等。客戶端也要安裝Tomcat5.0和MySQL數據庫，用于發布測試的服務。除了這些必需的配置外，系統進行了最小化安裝，從而保證系統運行時的效率。充當SSG設備的服務器上安裝實現的負載查詢器NECP server，并在內核中實現均衡調度模塊，包含經典的WRR算法和本文中采用的DWPS算法，數據包轉發采用NAT的方式。每個服務器節點上安裝負載反饋器NECP agent。
3.2 結果分析
測試包括三項內容：a)測試傳統的靜態WRR算法性能；b)測試不考慮服務類型和服務器負載能力的DWPS算法性能，即將負載能力向量和權重向量設成一樣的值；c)測試完整的DWPS算法的性能。測試過程中，后臺服務器提供兩種服務(分別放到不同的目錄下)，即發布10 KB大小的靜態頁面，以及發布能夠觸發復雜運算的動態頁面(JSP文件)。結果如圖4所示。
從測試結果中可以看出，在訪問量不大的情況下，算法之間的區別并不明顯。隨著請求數量的增加，DWPS算法的優勢便逐漸體現出來了，并可得出以下結論：
a)帶有動態反饋功能的DWPS算法比WRR更能夠提高服務器系統的整體性能，使其具有更高的負載能力。
b)在考慮服務器的負載能力和服務類型的情況下，算法的負載均衡性能得到了一定的改善。
4 結束語
本文中實現的是一種基于服務類型動態反饋負載均衡算法，反饋機制采用NECP完成。該算法在仿真測試中體現出了一定的優越性，說明具有實際應用的價值，但是還存在需要進一步改進的地方。如何更加準確合理地設定權重向量，需要進一步的實驗進行驗證；在SSG設備上實現負載均衡模塊的效率問題也將是進一步研究的內容。
參考文獻：
［1］洪英杰 邵洪鋼. 業務選擇網關在增值業務系統中的應用[J]. 現代電信科技 2005(4):32-34.
[2]CHEN Lichuan CHOI H A. Approximation algorithms for data distribution with load balancing of Web servers[C]//Proc of the 3rd IEEE International Conference on Cluster Computing. Washington DC:IEEE Computer Society 2001:274-281.
[3]章文嵩. Linux服務器集群系統[EB/OL]. (2003-03-24)[2008-06-20].http://www.linuxvirtualserver.org.
[4]CASSLICCHIO E TUCCI S. Static and dynamic scheduling algorithm for scalable Web server farm[C]//Proc of the 9th IEEE Euromicro Workshop on Parallel and Distributed Processing. Mantova:[s.n.] 2001:369-376.
[5]IYENGAR A MACNAIR E NGUYEN T. An analysis of Web server performance[C]//Proc of Global Telecommunications Conference. New York:[s.n.] 1997:1943-1947.
[6]郭成城，晏蒲柳. 一種異構Web服務器集群動態負載均衡算法[J]. 計算機學報 2005，28(2)：179-184.
[7]趙大勇. 業務選擇網管中訪問控制機制的研究[D]. 西安：西安電子科技大學，2008.
[8]易勤勤.SSG中多優先級隊列管理機制的研究與設計[D]. 西安：西安電子科技大學，2008.
[9]CERPA A ELSON J. The network element control protocol[EB/OL].(2000-09-10)[2008-06-20].http://www.circlemud.org/~jelson/writings/draft-cerpa-necp-03.txt.
