基于遺傳算法的ＶＯＤ集群負載均衡研究
2007-01-01 00:00:00鄭世玨舒萬能馬衛杜建華
計算機應用研究 2007年1期
摘要：VOD集群技術解決了VOD服務器系統容量問題，其核心思想是負載均衡策略和算法。對VOD集群中的負載均衡技術進行了分析和探討，并提出了一種自適應遺傳算法，取得了比較理想的實驗結果。
關鍵詞：集群服務器; 負載均衡; 遺傳算法； VOD
中圖法分類號：TP391文獻標識碼：A
文章編號：1001－3695(2007)01－0107－03
因特網的迅速發展使VOD（Video On Demand）服務正成為人們觀看影視節目，參加遠程教育等網絡活動的重要途徑。而VOD服務器系統需要面臨不斷增長的訪問量和日益復雜的內容處理的挑戰，這集中反映到VOD服務器系統的處理能力上。早期依托更高處理性能的服務器來解決問題的辦法顯得笨拙而昂貴，因為客戶請求的增長速度總是遠遠超過服務器性能提高的速度。后來采取更加靈活而廉價的技術手段，如一些系統采用鏡像方式，在多個服務器上復制相同信息，以不同的URL供用戶選擇，這樣就可以減少一臺服務器需要處理的負載量。但是這種方法沒有很好的可擴展性，缺乏透明性，且系統本身無法控制用戶訪問，因而不能達到負載均衡分配的目的。
更有效的辦法是在一個基于LAN的分布式體系結構下構建VOD集群服務器和采用負載均衡技術，如圖1所示。負載均衡技術使所有來自客戶端的請求被透明地分配到若干服務器上。對用戶而言，整個分布式系統仿佛是一臺單一的邏輯服務器，稱為VOD集群服務器。這樣的集群系統能夠提供較強的可擴展性和較好的吞吐性能，它避免了VOD集群服務器中的一部分資源負載超重，并且有可能不堪重負而崩潰，而另一部分資源卻沒有什么事情可做[1]。
目前學術界與工業界已經提出并實現了諸多的負載均衡機制[2]，如輪詢調度（Round Robin）、加權算法、最小連接數策略和哈希表等。文獻[3]中討論了多種類型的負載均衡算法，然而多數負載均衡算法只設計了單一任務類型；在文獻[4]中根據負載平衡的節點類型，將現有方法分為四類，即基于客戶端、分配器、服務器和DNS；文獻[5]中詳細論述并分析了各種負載均衡算法的優缺點。
在對VOD集群服務器的分析基礎上，結合影響負載均衡的因素和遺傳算法的特點，本文提出一種自適應遺傳算法。
1負載平衡基本原理
負載均衡是由多臺服務器以對稱的方式組成一個服務器集合，每臺服務器都具有等價的地位，都可以單獨對外提供服務而無須其他服務器的輔助。通過某種負載分擔技術，將外部發送來的請求均勻分配到對稱結構中的某一臺服務器上，而接收到請求的服務器獨立地回應客戶的請求。
負載均衡設備有一個虛IP（Virtual IP，VIP）地址，它放在服務器群的前面。這個VIP就是向外界公布的地址，或者說是域名解析的地址。當請求到達負載均衡器時，它會重寫該請求的頭文件，并將其指定到服務器群中的機器上。如果某臺機器從集群中被移除了，請求不會發往已經不存在的服務器上，因為所有的機器表面上都具有同一個IP地址，即使集群中的某個節點被移除了，該地址也不會發生變化。當返回一個應答時，客戶端看到的只是從負載均衡器上所返回的結果，也就是說，客戶端操作的對象是負載均衡器，對于其更后端的操作，對客戶端來講是完全透明的。
負載平衡的目標是根據處理機的性能來分配與其相稱的任務，以最小化應用程序的執行時間，并且準確地評估服務器上的工作負載，分配新的請求任務到每臺服務器。本文的后續部分將準確地評估服務器上的工作負載，并提出一種以遺傳算法為基礎的遺傳均衡算法。圖2顯示的是利用自適應遺傳算法建立的負載均衡模型。
2自適應遺傳算法
遺傳算法（Genetic Algorithm，GA）是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法。它將問題的求解表示成染色體的適者生存過程，通過染色體群的一代代不斷進化，包括復制、交叉和變異等操作，直到滿足一定性能指標和收斂條件終止，從而求得問題的最優解或滿意解。本文提出的自適應遺傳算法，要在準確評估VOD集群服務器工作負載的前提下，結合遺傳算法的特點才能找到問題的最優解。所以，下面將從VOD集群服務器的權值計算開始討論。
2．1權值計算
在集群的節點初次投入系統中使用時，系統管理員根據節點的硬件配置情況對每個節點都設定一個初始權值IW（Ni）（通常性能越高的節點其初始權值越高），隨著節點負載的變化，均衡器對節點權值不斷進行動態調整。在自適應負載均衡算法的設計中，筆者周期性地從各個節點中收集以下參數[6]：
⑥進程總數pr(Ni)等作為計算公式的因子。結合每個節點當前的權值，可以計算出新權值的大小。動態權值的目的是要正確反映節點負載的狀況，以預測節點將來可能的負載變化。對于不同類型的系統應用，各個參數的重要程度也有所不同。為了方便在系統運行過程中針對不同的應用對各個參數的比例進行適當調整，為每一個參數設定一個常量系數πi，用來表示各個負載參數的重要程度，其中∑πi=1。因此，任何一個節點Ni的權值公式就可以描述為
均衡器的動態權值采集程序周期地運行，一般為5s~10s，根據上述公式，在刷新周期T(i)內，可查詢節點的負載情況，并計算出各節點的動態權值load(Ni)。
2．2自適應遺傳算法設計思想
(1)確定群體規模Popsize，終止進化代數Maxgen，雜交概率Pc，變異概率PM，各個體的適應值Fi，各個體的選擇概率Pi。其中，
(5)令循環變量K=0。
(6)隨機產生一個數r=random[0，1]， 0 (7)如果r≤Pr，執行繁殖操作，即將兩個父體不加更改地插入到新的群體P(t+1)中。 (8)如果r≥Pr+Pc， 執行雜交操作，并將兩后代插入到新群體P(t+1)之中。 (9)否則，對兩個父體分別執行變異操作，并將兩后代插入到新群體P(t+1)之 中。 (10)令K=K+2，當K (11)計算P(t+1)中個體的適應值，t=t+1;當終止進化代數不滿足時，返回到步驟(3)。 (12)返回最優解i的值。 2．3負載平衡調度策略 當有新的任務請求VOD集群服務器時，結合自適應遺傳算法設計思想進行合理分配： (1)查看任務就緒隊列Q，若Q非空，則執行步驟(2)，否則執行步驟(6)； (2)調用自適應遺傳算法，取隊頭任務執行； (3)根據自適應遺傳算法的結果進行任務的分配； (4)刪除任務就緒隊列Q的隊首，有新的任務請求時，自動將新任務添加到隊尾； (5)查看任務就緒隊列Q，若Q非空，則執行步驟(2)，否則執行步驟(6)； (6)負載平衡調度完成。 3測試結果及分析 為了驗證算法的有效性，筆者完成了一個基于Java的實現并對其進行了測試。測試環境為一個10CPU的集群服務器，其中選取一個節點為負載均衡節點，而其他九個節點則作為服務器節點。這里所用的交叉概率為0.9，突變概率為0.1，且群體規模Popsize為100×(客戶端數)。 圖3~圖5是自適應遺傳算法與傳統調度算法加權輪循(Weighted Round Robin，WRR)， 加權最少鏈接(Weighted Least Connections，WLC)在吞吐量、平均應答延遲和每秒連接數等方面的對比。 從實驗結果可以分析出：SGA與WRR和WLC相比，能夠有效地降低任務平均完成時間，增加吞吐量和連接數。當VOD集群規模較小時，這種性能改善不太明顯；當VOD集群規模達到一定程度，SGA的優勢才逐漸表現出來。另外，仿真發現隨著VOD集群規模增大，算法的運行時間并沒有顯著增加，仍能保持良好的性能。 4結束語 眾所周知，最優的負載均衡算法是很難實現的，它是一個NP完全問題。一種優良的負載均衡算法的設計往往與系統的體系結構、網絡流量特性和流量模型有關，它一般只在某些特殊的應用環境下才能發揮最大效用。因此在應用時可根據實際系統的訪問特性結合系統中各服務器站點的響應能力，把不同的算法策略和技術結合起來使用，使整個VOD集群服務器的性能得以充分發揮。 參考文獻： ［1］Wanneng Shu， Shijue Zheng. A RealcoursebasedLoad Balanced Algorithm of VOD Cluster[C].Ningbo:International Symposium on Computer Science and Technology (ISCST)，2005.2024， ［2］A Bestavros， M E Crovella， J Liu，et al.Distributed PacketRewriting and Its Application to Scalable Server Architectures[C]. Proceedings of the 6th IEEE International Conference on Network Protocols， 1998.290297. ［3］Kim C， H Kameda.Optimal Static Load Balancing of Multiclass Tasks in a Distributed Computer System[C].Proc. of the 10th Int’l Conf. on Distributed Computing Systems，1990.562569. ［4］Cardellini V， Colajanni M， P S Yu.Redirection Algorithms for Load Sharing in Distributed Webserver Systems[C]. Proceedings of the 19th IEEE International Conference on Distributed Computing Systems，1999.528535. ［5］Cardellini V， Colajanni M.Dynamic Load Balancing on Webserver Systems[J]. IEEE Internet Computing， 1999，3(3)：2839. ［6］Shijue Zheng，Wanneng Shu， Guangdong Chen. A Load Balanced Method Based on Campus Grid[C].Beijing:International Symposium on Communications and Information Technologies (ISCIT)，2005.1214. 作者簡介： 鄭世玨(1956)，男，湖北武漢人，副教授，博士，主要研究方向為高性能計算、智能計算； 舒萬能(1981)，男，碩士，主要研究方向為高性能計算、智能計算； 馬衛(1978)，女，碩士，主要研究方向為高性能計算； 杜建華(1981)，男，碩士，主要研究方向為高性能計算。 注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
