蘇命峰，陳文芳，李仁發(fā)

(1.湖南大學信息科學與工程學院，湖南 長沙 410082;2.湖南商務(wù)職業(yè)技術(shù)學院，湖南 長沙 410205;3.湖南安全技術(shù)職業(yè)學院，湖南 長沙 410151)

Linux Virtual Server，簡稱LVS，是Linux開放源代碼的集群軟件［1］，常應(yīng)用于大型重負載站點.LVS集成在Linux內(nèi)核中，將一組服務(wù)器(節(jié)點)構(gòu)成一個虛擬服務(wù)器，對外提供一個虛擬IP地址，響應(yīng)用戶訪問請求，可提供可伸縮、高可用、高性能的WEB、FTP、MAIL、視頻等服務(wù).它有網(wǎng)絡(luò)地址轉(zhuǎn)換(VS/NAT)、IP隧道 (VS/IP Tunneling)和直接路由(VS/DR)三種負載均衡模式.為快速響應(yīng)客戶請求，LVS系統(tǒng)將大量并發(fā)的訪問請求，通過合理的策略調(diào)度到多個提供真實服務(wù)的節(jié)點.LVS系統(tǒng)應(yīng)根據(jù)不同的網(wǎng)絡(luò)應(yīng)用環(huán)境，選擇正確的負載調(diào)度算法.

1 負載調(diào)度算法介紹

LVS集群屬于任務(wù)級負載均衡集群，采用以IP連接為粒度的集中式任務(wù)分配，支持多種不同的負載調(diào)度算法，在一定程度上解決大量用戶突發(fā)性訪問引起的負載不均問題.負載調(diào)度算法是整個集群系統(tǒng)的關(guān)鍵，直接決定集群系統(tǒng)的性能和效率.好的調(diào)度算法讓整個集群系統(tǒng)的負載均勻分布，不發(fā)生傾斜，每臺服務(wù)器充分發(fā)揮各自性能.反之，整個集群系統(tǒng)出現(xiàn)傾斜，有些服務(wù)器負載過輕，另一些則負載過重.按照負載調(diào)度算法的實現(xiàn)原理可分為靜態(tài)調(diào)度算法、動態(tài)調(diào)度算法和自適應(yīng)調(diào)度算法.

1.1 靜態(tài)調(diào)度算法

靜態(tài)調(diào)度算法根據(jù)事先定好的調(diào)度策略分發(fā)用戶請求，不考慮集群系統(tǒng)運行時各真實服務(wù)器的負載情況.它簡單、易實現(xiàn)，無節(jié)點負載情況檢測和過載節(jié)點遷移等額外開銷，但適應(yīng)性不強，容易引起節(jié)點間的負載不平衡，特別是負載重時，集群系統(tǒng)性能變差.

1.2 動態(tài)調(diào)度算法

動態(tài)調(diào)度算法實時跟蹤真實服務(wù)器的活動連接，結(jié)合具體策略將新的請求分發(fā)到合適的真實服務(wù)器.算法實現(xiàn)較為復(fù)雜，對任務(wù)的分配管理以及信息收集等會造成額外的系統(tǒng)開銷，定期收集的信息也會有一定誤差.不過調(diào)度得當，還是可以明顯提高集群系統(tǒng)性能，是負載均衡研究的重點，應(yīng)用廣泛.

1.3 自適應(yīng)調(diào)度算法［2］

自適應(yīng)調(diào)度算法是一種智能的算法，為適應(yīng)不斷變化的系統(tǒng)狀態(tài)和復(fù)雜的網(wǎng)絡(luò)環(huán)境，可動態(tài)改變算法參數(shù)以及策略，來調(diào)整集群系統(tǒng)的負載調(diào)度行為，如動態(tài)反饋負載均衡算法等.它比動態(tài)調(diào)度算法更復(fù)雜，算法自身開銷較大，負載輕時集群系統(tǒng)性能提升不明顯，是負載均衡研究的熱點，處于發(fā)展階段，目前應(yīng)用較少.

2 常用負載調(diào)度算法

目前基于IP層的IPVS軟件提供10種調(diào)度算法［3］，適用不同的網(wǎng)絡(luò)應(yīng)用環(huán)境.

2.1 輪詢(Round －Robin Scheduling，RR)

把新的連接請求按順序調(diào)度到不同的服務(wù)器上，以實現(xiàn)負載均衡.每次負載調(diào)度執(zhí)行i=(i+1)mod n運算，輪流選出第i臺服務(wù)器.當服務(wù)器的權(quán)值為0時，表示其不可用而不被調(diào)度.算法簡單，實現(xiàn)容易，執(zhí)行效率高，是一種無狀態(tài)的靜態(tài)調(diào)度算法，它沒有考慮服務(wù)器的連接情況，適合服務(wù)器性能相同的集群系統(tǒng).否則容易造成服務(wù)器間的負載不均衡.

2.2 加權(quán)輪詢(Weighted Round－ Robin Scheduling，WRR)

根據(jù)服務(wù)器的性能為其設(shè)定一個相應(yīng)的權(quán)值，調(diào)度器根據(jù)權(quán)值的高低，采用輪詢方式將用戶的訪問請求發(fā)送給服務(wù)器，為改進的RR算法.服務(wù)器的缺省權(quán)值為1，需要手工確認不同服務(wù)器的權(quán)值，權(quán)值高的服務(wù)器先收到連接請求，比權(quán)值低的服務(wù)器處理更多的請求.如果三個服務(wù)器A、B和C的權(quán)值分別為1、2和3，則在一個調(diào)度周期內(nèi)調(diào)度序列依次為:CCBCBA.該算法繼承RR算法的簡易性，可在某種程度上解決服務(wù)器性能不一致的問題.但算法沒有考慮服務(wù)器當前連接等負載情況，當請求的服務(wù)時間變化很大時，容易導(dǎo)致服務(wù)器之間的負載傾斜.

2.3 目標地址散列(Destination Hash Scheduling，DH)

將請求報文中的目的IP地址作為散列關(guān)鍵字，從調(diào)度器上事先設(shè)定好的靜態(tài)哈希表中找出對應(yīng)的服務(wù)器，若該服務(wù)器可用且未過載，就將請求發(fā)送到該服務(wù)器.在實現(xiàn)時可采用素數(shù)乘法Hash函數(shù)，使散列值均勻分布，以盡量避免出現(xiàn)Hash沖突情況.

2.4 源地址散列(Source Hash Scheduling，SH)

與DH算法正好相反，源地址散列算法將請求報文中的源IP地址作為散列關(guān)鍵字，從調(diào)度器上的靜態(tài)哈希表中查找到對應(yīng)的服務(wù)器，若服務(wù)器可用且未過載，就將請求發(fā)送過去，否則返回空.算法流程與DH算法相似，可一起使用，它們常應(yīng)用于防火墻集群，都是靜態(tài)調(diào)度算法.

2.5 最小連接(Least－ Connection Scheduling，LC)

把新的訪問請求調(diào)度到當前連接數(shù)最少的服務(wù)器，是一種動態(tài)調(diào)度算法，當前連接數(shù)=256*活躍連接數(shù)+非活躍連接數(shù).調(diào)度器需要記錄每臺服務(wù)器當前的活躍和非活躍連接數(shù)，用來估計服務(wù)器的負載情況.最少連接法沒有考慮服務(wù)器之間性能的差異.當服務(wù)器性能相同時，該算法能將請求平滑分布到各服務(wù)器，否則算法的負載均衡性能不理想.

2.6 加權(quán)最小連接(Weighted Least－Connection Scheduling，WLC)

根據(jù)服務(wù)器的性能設(shè)定一個相應(yīng)的權(quán)值，服務(wù)器默認權(quán)值為1，權(quán)值越大表示其處理能力越強.調(diào)度器根據(jù)服務(wù)器的權(quán)值與其活躍連接數(shù)的比值將新的用戶請求發(fā)送到處理能力強的服務(wù)器.假設(shè)有一組服務(wù)器 S={S0，S1，…，Sn－1}，服務(wù)器Si的權(quán)值為W(Si)，當前連接數(shù)為C(Si).只有服務(wù)器Sm滿足條件:

當前新用戶請求才會發(fā)送到服務(wù)器Sm.算法考慮了服務(wù)器的當前連接情況和處理能力，是改進的LC算法.對于普通應(yīng)用，算法調(diào)度效率高，應(yīng)用比較廣泛，是IPVS默認的調(diào)度算法.缺點是當前連接數(shù)表示服務(wù)器的綜合負載不夠精確和全面，服務(wù)器權(quán)重不能動態(tài)修改，當用戶的訪問方式相差比較大時，該算法也會引起服務(wù)器之間的負載不平衡.

2.7 基于局部性的最少鏈接(Locality－Based Least Connections Scheduling，LBLC)

調(diào)度器根據(jù)請求報文中的目的IP地址，找到最近響應(yīng)該地址請求的服務(wù)器，如果服務(wù)器可用，就將請求發(fā)送給它;如果該服務(wù)器過載或不可用，則采用LC算法，從其他可用、不過載的服務(wù)器中選擇一臺服務(wù)器，再將請求發(fā)送過去.系統(tǒng)為請求報文中的目的IP地址與調(diào)度的服務(wù)器進行關(guān)聯(lián)，設(shè)定一個存活期限，并定期回收過期的關(guān)聯(lián)，有一定的靈活性.該算法為動態(tài)調(diào)度算法，考慮了局部性原理，可提高服務(wù)器的Cache命中率和處理效率，可應(yīng)用于Cache集群.

2.8 帶復(fù)制的基于局部性最少鏈接(Locality－Based Least Connections with Replication Scheduling，LBLCR)

根據(jù)請求報文中的目的IP地址，找到最近響應(yīng)請求服務(wù)器所在的服務(wù)器組，采用LC算法從當前服務(wù)器組中選擇一臺連接數(shù)最少的服務(wù)器，若該服務(wù)器沒有過載就將請求發(fā)送給它;如果該服務(wù)器過載，就從集群后臺中選一臺負載最輕的服務(wù)器加入到服務(wù)器組中，并將請求發(fā)送到該服務(wù)器.為降低對鏡像的拷貝，提高系統(tǒng)性能，可以將一段時間內(nèi)沒有發(fā)生變化的服務(wù)器組中的最忙服務(wù)器刪除.該算法為LBLC算法的補充和發(fā)展，也需要定期釋放目的IP地址與服務(wù)器的關(guān)聯(lián)，主要用于Cache集群.

2.9 最短期望延遲(Shortest Expected Delay Scheduling，SED)

一種期望最小化每個任務(wù)預(yù)期延時的動態(tài)算法，目的是找到預(yù)期任務(wù)量與處理速率比值最小的服務(wù)器.假設(shè)一組服務(wù)器 S={S0，S1，…，Sn－1}中，服務(wù)器 i的預(yù)期任務(wù)量為當前連接數(shù)C(Si)加1，處理速率為服務(wù)器權(quán)重W(Si)，權(quán)值越大處理速率越大.當服務(wù)器Sm滿足以下條件:

新連接請求會被調(diào)度到Sm.最短期望延遲改進了WLC算法，考慮了連接的預(yù)期成本，即當前連接數(shù)加1，在某些情況下要比WLC算法好.例如:ABC三臺服務(wù)器權(quán)重分別為1、2、3，連接數(shù)分別是 1、2、3.如使用 WLC 算法，一個新請求會分發(fā)給ABC中的任意一個.如果使用SED算法，通過進行［C(Si)+1］/W(Si)運算，新請求會分發(fā)給C.

2.10 無須隊列等待(Never Queue Scheduling，NQ)

當有空閑服務(wù)器(即當前連接數(shù)為0)時，不需要任何計算，調(diào)度器直接把請求分配給空閑服務(wù)器;當沒有空閑服務(wù)器時，按照SED算法找到預(yù)期任務(wù)量與處理速率比值最小的服務(wù)器，并將請求調(diào)度過去，是對SED算法的一種改進.

以上調(diào)度算法均以IP連接數(shù)表示服務(wù)器負載，其中RR、WRR、DH、SH 屬于靜態(tài)調(diào)度算法，LC、WLC、LBLC、LBLCR、SED、NQ 屬于動態(tài)調(diào)度算法.在 WRR、WLC、SED、NQ算法中體現(xiàn)服務(wù)器性能的權(quán)值W，一般根據(jù)服務(wù)器的CPU、內(nèi)存、磁盤I/O和網(wǎng)絡(luò)等使用率綜合設(shè)定.SH和DH主要用于防火墻集群，LBLC、LBLCR主要用于 Cache集群，WRR、WLC、SED、NQ 常用于 WEB、FTP等集群.

3 LVS負載調(diào)度算法測試

測試平臺見圖1，采用VS－DR模式［3］搭建一個提供Web服務(wù)的LVS集群，在一臺CPU為Intel酷睿i3(2.4G)、內(nèi)存4GB的物理計算機上通過虛擬機軟件VMware Workstation 8，同時運行4臺內(nèi)存為512MB的虛擬計算機，分別是負載均衡器(即調(diào)度器)和3臺真實服務(wù)器.

圖1 LVS負載調(diào)度算法測試平臺

負載均衡器和3臺真實服務(wù)器采用Redhat Enterprise Linux 6操作系統(tǒng)，都安裝Apache組件，啟動httpd進程.負載均衡器采用 LVS管理組件 ipvsadm，版本 1.2.1［4］.考慮到 3臺服務(wù)器性能相同，其權(quán)值都設(shè)置為1，每臺WEB服務(wù)器提供一個靜態(tài)測試主頁index.html，大小為20KB.測試客戶端采用Windows XP SP3操作系統(tǒng)，運行WEB應(yīng)用負載測試工具 Web Application Stress Tool［5］，通過設(shè)置不同的高并發(fā)連接數(shù)，模擬大量用戶并發(fā)訪問LVS集群系統(tǒng).每次測試時間周期為5分鐘，以發(fā)出足夠的訪問請求，避免產(chǎn)生失真的測試結(jié)果.主要參考Time To First Byte(TTFB)值，比較WRR、WLC、SED、NQ等負載調(diào)度算法和無集群系統(tǒng)的性能，TTFB指測試端收到真實服務(wù)器響應(yīng)請求的第一個數(shù)據(jù)包所用的時間，值越小說明系統(tǒng)性能越好.

表1 不同調(diào)度算法與無集群系統(tǒng)的TTFB值(ms)

由表1的分析結(jié)果可得到采用不同調(diào)度算法與無集群系統(tǒng)在不同并發(fā)數(shù)下TTFB的變化曲線圖，圖2表明，在不同的并發(fā)數(shù)下，采用WRR、WLC、SED、NQ等調(diào)度算法的集群系統(tǒng)的 TTFB值遠小于無集群系統(tǒng)，說明采用 WRR、WLC、SED、NQ等調(diào)度算法的集群系統(tǒng)性能相比較無集群系統(tǒng)，性能有明顯提升，在這些調(diào)度算法中，以NQ性能最佳.

圖2 不同調(diào)度算法與無集群系統(tǒng)TFFB的變化曲線圖

4 結(jié)語

通常情況下，動態(tài)調(diào)度算法比靜態(tài)調(diào)度算法更能反映系統(tǒng)的實際情況，實用性強，性能要高.常用的WLC和改進的SED、NQ等算法雖然能較好地用于集群系統(tǒng)的負載均衡調(diào)度，但也存在一些不足:沒有考慮CPU、內(nèi)存使用率等，僅以活動連接和非活動連接來表示真實服務(wù)器的綜合負載并不精確，隨著負載的增加，相應(yīng)服務(wù)器的處理能力會發(fā)生變化，進而引起服務(wù)器間的負載不平衡，算法不能及時掌握真實服務(wù)器的運行情況.為此，可采用動態(tài)反饋負載均衡算法等自適應(yīng)調(diào)度算法，在調(diào)度器運行Daemon進程，監(jiān)視服務(wù)器的實時負載和響應(yīng)情況，及時調(diào)整服務(wù)器的請求比例，以獲得更高的吞吐率，但需修改Linux系統(tǒng)內(nèi)核等，實現(xiàn)復(fù)雜.

［1］章文嵩.可伸縮網(wǎng)絡(luò)服務(wù)的研究與實現(xiàn)［D］.長沙:國防科學技術(shù)大學博士學位論文，2000.

［2］王強.基于LVS集群負載均衡算法的研究與改進［D］.成都:電子科技大學碩士學位論文，2010.

［3］蘇命峰.三種LVS負載均衡模式及性能研究［J］.自動化與信息工程，2011，(6):17 －21.

［4］Song W.IPVS［EB/OL］.http://www.linuxvirtualserver.org/software/ipvs.html，2011 －02 －08.

［5］Ching A，Silva P，Wagner A.利用 WebApplicationStressTool(WAS)做性能測試［EB/OL］.http://tech.ccidnet.com/art/1077/20040919/718477_1.html，2006 －08 －01.