LVS集群負載調度算法研究*

蘇命峰，陳文芳，李仁發

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

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

1 負載調度算法介紹

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

1.1 靜態調度算法

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

1.2 動態調度算法

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

1.3 自適應調度算法［2］

自適應調度算法是一種智能的算法，為適應不斷變化的系統狀態和復雜的網絡環境，可動態改變算法參數以及策略，來調整集群系統的負載調度行為，如動態反饋負載均衡算法等.它比動態調度算法更復雜，算法自身開銷較大，負載輕時集群系統性能提升不明顯，是負載均衡研究的熱點，處于發展階段，目前應用較少.

2 常用負載調度算法

目前基于IP層的IPVS軟件提供10種調度算法［3］，適用不同的網絡應用環境.

2.1 輪詢(Round －Robin Scheduling，RR)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 LVS負載調度算法測試

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

圖1 LVS負載調度算法測試平臺

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

表1 不同調度算法與無集群系統的TTFB值(ms)

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

圖2 不同調度算法與無集群系統TFFB的變化曲線圖

4 結語

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

［1］章文嵩.可伸縮網絡服務的研究與實現［D］.長沙:國防科學技術大學博士學位論文，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.