一種LVS負載均衡調度算法WLC的改進

劉玉艷，沈明玉

（1. 池州學院，池州 247000；2. 合肥工業大學 計算機與信息學院，合肥 230009）

0 引言

隨著Internet的飛速發展和對人們生活影響的深入，越來越多的人選擇在互聯網上購物、娛樂、休閑、獲取信息或與人溝通；更多的企事業、單位、公司通過互聯網來完成它們的業務，建立與客戶的聯絡。這種變化促使互聯網的用戶數和網絡流量以幾何級數增長，對網絡服務的可伸縮性提出了更高的要求。

日益增長的訪問量和高強度的負荷對網絡服務器的性能要求越來越高，越來越多的應用要求能夠提供不間斷的服務，服務器端的任何中斷都將造成不可估量的損失，因此需要一套可靠的方案來解決網絡服務器的高可用性問題。

用Linux虛擬服務器（Linux Virtual Server）技術可以建立一個具有高性價比、可擴展性和高可管理性等特性的集群系統，能有效解決網絡服務負載均衡的問題[1]。

1 LVS調度算法及算法選用

1.1 LVS負載均衡調度算法

Linux Virtual Server（簡稱LVS）系統是一個開源項目，它采用基于IP層負載均衡的調度方法將TCP/IP請求均衡地分配到不同的真實服務器(Real Server，簡稱RS)上，負載均衡器自動屏蔽掉真實服務器的故障，將一組真實服務器構成一個高性能的、高可用的虛擬服務器[2～4]。

LVS系統屬于任務級負載均衡。它采用集中式任務分配，任務的分配是以連接為粒度。如在HTTP 協議中，每個從Web 服務器上獲得的對象都需要建立一個TCP 連接，用戶的不同請求會被調度到不同的服務器上，所以這種細粒度的調度在一定程度上可以避免了用戶訪問的突發性引起的負載不均的問題。

LV S系統支持八種調度策略：輪詢法（RR）、加權輪詢法(WRR)、最少連接法(LC)、加權最少連接法(WLC)、基于局部性的最少連接法(LBLC)、帶復制的基于局部性最少連接法(LBLCR)、目標地址散列法(DH)和源地址散列法(SH) 。

1.2 算法的選用

調度算法設計的好壞直接決定了集群在負載均衡上的表現，設計不好的算法，會導致集群的負載失衡。一般的平衡算法主要任務是決定如何選擇下一個集群節點，然后將新的服務請求轉發給它。有些簡單平衡方法可以獨立使用，有些必須和其它簡單或高級方法組合使用。而一個好的負載均衡算法也并不是萬能的，它一般只在某些特殊的應用環境下才能發揮最大效用。因此在考察負載均衡算法的同時，也要注意算法本身的適用面，并在采取集群部署的時候根據集群自身的特點進行綜合考慮，把不同的算法和技術結合起來使用。

通過研究發現，以LVS的八種調度算法為基礎，現在人們也研究出很多種動態調度算法，如動態負反饋[5,6]、基于Agent的調度算法[7]、最快回應最少連接調度算法[8]等。動態負載均衡算法就是負載均衡器周期性地從后端服務器獲取當前各節點真實服務器的負載狀態，并根據這些狀態來動態調整后續的分配策略，最為關鍵的步驟是動態地計算每臺服務器的當前負載權值。動態負載調度算法中，負載均衡器需及時、準確把握節點服務器的負載狀況，并根據各個節點真實服務器當前的資源使用狀態動態調整負載平衡的任務分布，這樣才能實現系統高效的負載均衡。因此，使用動態調度算法的集群系統，負載均衡器需要安裝收集和計算各節點服務器運行時的CPU頻率、CPU個數、CPU的使用率、內存大小、網絡流量、響應速度等狀態信息的監控軟件；各節點服務器則需安裝反饋傳遞自身狀態信息的響應軟件。這些軟件需要購買或二次開發，這會加大投資成本；此外，動態算法中負載均衡器與各節點服務器也需實時交互，這無疑會造成占用系統資源、加大系統內耗和增加額外開支等問題。因此當前的動態調度算法大都存在：如何降低負載信息獲取、交互所占用的系統資源[9]，使系統內耗資源降低等一些未能解決的問題，所以目前負載均衡系統中仍較多采用LVS調度算法。

WLC算法調度算法也是一種動態調度算法。這種算法實時地計算每個節點的連接數，并且考慮各真實服務器性能差異。它即克服了靜態調度算法只適用于同構服務器（即各節點服務器配置相差不大）集群系統的缺點，也解決了大多動態調度算法中負載均衡器和節點服務器需安裝額外軟件、頻繁交互額外產生內耗等問題。WLC是LVS提供的八種調度算法之一，是系統默認的調度算法。

2 WLC算法及其優化

2.1 WLC算法

算法基本思想：該算法是最少連接算法的改進，它為每個真實服務器Si指定一個整數值Wi標記服務器的性能（性能較高的服務器具有較大值）。

算法的實現：當負載均衡器分配服務時，會在支持此服務的真實服務器分配鏈表中，從頭部開始尋找連接數與權值的比值最小、且權值不為零（表示服務器可用）的服務器，如果找到符合要求的服務器，則返回此服務器指針，否則返回空指針。算法流程如下：

假設有一組服務器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)。同時保證服務器的權值為零時，服務器不被調度。所以，算法只要執行以下流程：

算法的評價：算法既考慮了集群中各真實服務器的處理性能的不同，又考慮了各個真實服務器的狀態，可以實現真正意義上的負載均衡。雖然算法復雜度稍微大些，但是它提高了系統的效率，這種效率的提高不僅抵消了算法所帶來的開銷，而且大大地改善了系統地性能。WLC 是LVS的缺省負載分配算法，在通常的應用中一般都采用此算法。加權最小連接算法既考慮了各個真實服務器當前的連接狀態，又考慮了各個真實服務器的處理能力因素，因而是LVS集群系統任務分配算法中最優的。

2.2 WLC調度算法當前存在的問題

WLC調度算法雖被廣泛采用，這種算法也存在如下問題：1）權值估算的合理、科學性。WLC算法中用到的權值是管理員根據每臺服務器的性能及負載狀況為每臺服務器指定一個整數值。擁有比較高的權值的真實服務器在任何時候其上活動的連接數都占有比較高的百分比，權值直接影響系統中各節點能否“均衡”，因此使用科學、合理的方法計算權值，對異構負載均衡系統至關重要。傳統采用WLC算法的LVS負載均衡系統，其中的權值大都是管理員根據節點服務器硬件配置估算的，這種估算方法的科學性顯然有不科學的地方，本文將介紹一種節點服務器權值優化的方法。2）權值配置需要管理員手工配置，不能在系統運行過程中自動動態完成。以及無法估算出每臺節點服服器的動態權值等問題。這些是負載均衡器和節點服務器不需額外安裝監控和反饋軟件所帶來的負面問題，并不是算法本身存在的本質問題，所以不在本文討論范圍之內，本文要討論的是如何得到更反映服務器實際性能的權值問題，即權值計算方法的優化。

2.3 WLC算法優化

加權最少連接調度算法（WLC）是最少連接優先算法的超集。這種算法需為集群中的每個節點分配一個反映該節點處理能力的權重。任何時候，權重大的節點都應該得到份額較大的連接。服務器權值又稱砝碼是反映服務器處理能力的指標，它通常受帶寬、緩沖區I/O、CPU調度周期、需要處理的數據量、啟動的線程數、磁盤訪問時間等多種因素綜合影響[10]。

在WLC算法中，判斷條件語句是C（Sm）*W(Si)＞C(Si)*W(Sm)，i=0，1，2，……，n-1，W(Si)不為零,Si表示上次分配的服務器，Sm表示下一次將要分配的服務器，C（Si）和C（Sm），W（Si）W（Sm）分別表示服務器Si和Sm的當前連接數和權值。

服務器連接數是負載均衡器根據各節點服務器當前連接狀態，由系統動態自動獲得；權值是反映服務器性能高低的一個整數值，它以倍數形式反映服務器能力的差別，如權值為200的節點比100的服務器性能高2倍。因此WLC算法優化主要是對各節點服務器權值的優化。

任何工具或人都無法計算出動態運行機器的實際性能（即WLC算法中的權值），因此只能盡量使計算的權值科學、合理。服務器性能除受本身組成硬件CPU、內存、主板、硬盤等綜合作用的影響外，還受服務器軟件和網絡連接等因素影響，因此由管理員僅根據硬件配置估算出來的權值，明顯存在不妥之處。科學合理的權值計算方法，應綜合硬件因素協作結果的整機效能和作為網絡應用的服務性能指標（如響應時間，吞吐量等）等多種因素。

使用WLC調度算法的負載均衡系統，管理員給各個節點服務器配置的整數值（即權值），是以倍數形式反映各節點服務器間性能差異，因此只要得出各節點服務器性能比值，即可以配置WLC調度算法的各節點服務器的權值數。例如有三臺服務器分別用A，B，C，若三者的性能比例為1：2：3，則A，B，C的權值可分別配置為100，200，300。由此可推，計算各節點服務器權值可轉化為計算各節點服務器性能比值，然后再調整為適當的整數值即可。

假如有兩臺服務器分別用A和B表示，它們的權值用WA和WB表示，則可用公式：WA/WB=(MA/MB+NA/NB)/2求得機器A和B性能之比，其中MA，MB表示機器A和B的整機系統性能，NA，NB分別表示機器A和B的網絡服務性能。無論是機器的整體性能，還是網絡應用服務性能都應根據問題的復雜程度選用多個或單個指標測試得到。為簡化計算過程，在選用各指標時要盡量統一選取為正向指標，即所選指標與性能成正比。若遇到特殊情況不得不選用某逆向指標時，則要將此項的比值取倒數后再代入公式計算。公式可以反映出節點服務器性能即權值，是由整機性能和網絡服務系統性能兩個指標來共同決定的。

3 實驗測試

3.1 測試工具

3.1.1 服務器整機性能測試工具

服務器的整機性能指標是衡量系統是否先進的一個重要參數，在測試中一般以速度作為衡量標準。如CPU的工作頻率、內存的數據存取時間、各種總線的數據傳輸帶寬等[11]。為準確衡量服務器整機的性能高底，單從表面的硬件配置上是無法準確和精確弄清楚的，應選用專業硬件測試軟件來實現計算機性能測試。針對安裝操作系統的不同，可選用相對應的測試軟件，如基于DOS系統的性能測試軟件Norton Utility等，基于Linux環境的I/O測試工具iozone和服務器網絡性能測試工具Netperf。基于Windows系統的性能測試軟件Iometer、Lavalys Everest、SiSoft Sandra Pro、WintuneWinsstem、Business Winstone、WinBench 2004和PCMark 2004等[12]。因本文設計的系統中節點服務器是安裝的Windows系統，因而只介紹Windows系統的性能測試軟件的使用方法，對于基于其他操作系統的性能測試軟件，用戶可自己查閱相關資料。

根據測試目的的不同，有不同的性能測試軟件，如Everest可鑒別CPU的真假、查詢內存詳細情況、硬盤轉速容量等狀況，也可以檢測顯卡、聲卡、機器整機性能等指標；SiSoft Sandra Pro則側重于系統分析與評測；WinBench 2004主要測試系統整體性能；Business Winstone 2004則是一種非常專業、嚴格的整機性能測試軟件；PCMark 2004是一款綜合性能測試軟件。

本文選用FutureMark公司的一款硬件測試工具PCMark04，取測試結果中的PCMark Score作為計算公式中的整機性能指標。

3.1.2 服務器網絡性能測試工具

常用的基本網絡服務包括DNS服務、郵件服務、WWW服務、FTP服務、DHCP服務、流媒體服務等等[13]。針對不同的網絡服務，測試指標和測試工具均有不同，如可用Avalanche 2200工具測試郵件服務器的瞬間提供SMTP服務的能力——最大并發數、成功發送郵件百分比、平均往返延遲等指標以反映服務器性能[14]； Spirent公司的Smartbits 600B工具可測試流媒體服務器性能，WebMark工具測試Web服務器性能，Mercury（美科利）Interactive公司的LoadRunner工具則可適用于各種體系架構，可以支持很多協議和技術如Web、Ftp、Database[15]，在客戶端使用WebServer stress Tool工具測試用戶訪問服務器一定大小的網頁時所用的時間(Time Spent)或者網絡流量(Traffic)，Avalanche 2500 Web工具測試服務器的最大新建用戶數、總響應數和成功響應數，RadView公司的webload工具可以測試服務器的吞吐量、每秒處理事務數等指標，微軟公司提供的免費Web Application Stress（簡稱WAS）工具能夠測試Web Server的吞吐率、請求響應時間等指標。

為保證測試數據的科學性和準確性，一般情況下，應采用兩種或兩種以上的測試軟件對服務器性能的不同指標進行測試，如選用Web server stress tool工具測試服務器的time spent，選用WAS測試服務器的請求響應時間、吞吐率等指標，并且最好采用多次測試取平均值的方法計算各服務器的相應指標。

本文所設計系統的實驗環節，選用微軟公司提供的免費測試工具WAS。用它來測試每臺服務器的請求響應時間（TTLB）和吞吐率（Requests per second），分別用A，B標識各臺服務器，用同一臺安裝WAS工具的客戶機，并在WAS測試環境中設置相同的測試條件如相同的用戶數、用戶并發數和測試時間等參數，使用相同的測試腳本。

3.2 實驗結果與分析

3.2.1 服務器整機性能測試結果

測試運行結束后，PCMark04出現的測試結果如圖1所示.

圖1 PCMark04出現的測試結果

其中PCMark Score的計算公式是：

PCMark Score = 66 × (File Compression ×File Encryption × File Decompression × Image Processing × File Decryption × Virus Scanning ×Grammar Check × Audio Conversion × Web Page Rendering × WMV Video Compression × DivX Video Compression × Physics and 3D × Graphics Memory)1/13

公式中的66是將最后成績進行一定倍數的擴大，以使測試結果有一定的有效位數和容易記憶，公式最后的 1/13 次方則代表對前面的乘積進行13次方開根號。

圖1中的PCMark Score的數值，即是所測機器的整機性能指標。為使測試數據具有可比性，所有真實服務器應設置相同的測試環境：格式化一樣的分區、安裝相同的操作系統和版本、安裝相同的軟件環境。測試每臺機器時均采用測試五次、每次機器重啟，最后將五次結果計算平均值。實驗中測得兩臺機器A和B的PCmark Score指標分別為2586和4215

3.2.2 服務器網絡性能測試結果

分別測試機器A和B，實驗所得數據如表1所示：

表1 機器A，B實驗測得數據

Requests per second即吞吐率，表示Web Server每秒處理客戶請求數，為正向指標，即此值越大表示性能越高[16]。TTLB Avg即平均請求響應時間，表示從發起一個請求開始，到客戶端收到最后一個字節所耗費的時間[17]，此指標為逆向指標，即值越小表示服務器性能越好。

3.2.3 實驗分析

將機器A和B測試數據，利用權值改進方法計算出A和B性能比值，再以此比值為基礎調整成合適的權值。將實驗中所測指標代入上文公式，得：

MA/MB=4215/2586≈1.63，

NA/NB=（44.31/15.24+3260.06/1125.33）/2≈1.62，（此公式中有逆向指標TTLB Avg，機器A的值是1125.33，B的值是3260.06，計算時用比值的倒數即3260.06/1125.33）

WA/WB=(1.63+1.62)/2≈1.6。

為在實際負載均衡系統中，更能明顯表示服務器性能變化，將A和B的權值分別用160和100表示。將實驗沒得數據配置在實際的負載均衡系統中，發現系統能實現很好均衡，權值大的即性能較高的服務器分配了較多的負載，而值小的則分配的負載較少。

4 結論

本文提出一種通過分別測試各節點服務器的整機性能和網絡性能，再按數學方法求得各節點的比值，最后再調整為合適的數值，作為服務器的權值配置到實際應用的LVS均衡系統中，配置到LVS負載均衡系統。實驗結果表明采用這種方法將會使系統中各節點服務器更好實現均衡。

[1] 章文嵩.Linux服務器集群系統[EB/OL]http://www.ibm.com/developerworks/cn /linux /cluster/lvs/part1/index.html.2002.

[2] YM TEO.Comparison of Load Balancing Strategies on Cluster-based Web Servers[DB/OL].Transactions of the Society for Modeling and Simulation.2001.

[3] L AVERSA,A BESTAVROS.Load balancing a cluster of Web Servers Us-ing Distributed Packet Rewriting[C].Proceedings of the 2000 IEEE International Performance,Computing,and Communications Confer ence,2000.2:24-29.

[4] 許廣斌.基于linux的集群系統[EB/OL]http://www.ibm.com/developerworks /cn/linux/cluster /linux_cluster/part1/index.html.2004

[5] V CARDELLINI P S Yu.Dynamic load balancing on web server systems[J].IEEE Internet Computing,1999.

[6] TA NGUYEN,BINH DUONG,SUIPING Zhou [J].A dynamic load sharing Algorithm for Massively Multiplayer Online Games[J].Sydney Australia.2003.

[7] 王晉鵬,潘龍法,李降龍.LVS集群中的動態反饋調度算法[J].計算機工程.2005,3(19).

[8] 鄭祺.一種基于動態反饋的負載均衡算法研究[J].計算機時代,2006.

[9] 喬治.基于Linux負載均衡系統的研究與實現[D].北京工業大學,2005.

[10]余勝生,楊立輝,等.一種基于可變權重的最少連接優先算法[J].小型微型計算機系統,2003,24(11).

[11]易建勛.計算機維修技術[M].清華大學出版社,2005.

[12]曹岳輝,李力,李夢暉.計算機硬件技術基礎[M]. 清華大學出版社,2006.

[13]MOHAN C.Application servers and associated technologies[J].New York:ACM Press.2002.

[14]姜波,張峰.＂郵＂系方寸間 -- E-mail服務器性能綜述[J].網絡世界,2006.

[15]服務器性能測試典型工具,網管員世[EB/OL],http://www.netadmin.com.cn /kt_article_show.php?article_id=12331&categ_code=10261003. 2007

[16]HUANAT.Redhat advance enterprise下架設雙機集群[EB/OL].http://www.ixpub.net/638747.html.2006.

[17]陳紹英,等.Web Performance Test Model And Application[M].電子工業出版社,2006.