內容發布訂閱系統中的動態負載均衡
2008-01-01 00:00:00逯鵬林學練劉旭東李冬松
計算機應用研究 2008年5期
摘要：復雜廣域網絡應用帶來了內容發布訂閱系統動態負載失衡問題。提出了一種動態負載均衡框架解決該問題。采用周期性交換和計算負載的方法實現了負載探測，采用代理復制和區域重構的方法解決了負載遷移問題，設計了負載協商狀態機用于協商代理之間的負載遷移，采用轉移加入和動態自適應兩種方法進行負載均衡決策。實驗結果表明，該負載均衡框架能夠有效解決內容發布訂閱系統的動態負載失衡問題，將負載均衡效率提高了50%。
關鍵詞：負載均衡;發布訂閱系統;框架;動態自適應
中圖分類號：TP393．2文獻標志碼：A
文章編號：1001-3695(2008)05-1507-04
傳統內容發布訂閱系統[1，2]采用了泛洪或廣播路由協議，代理的負載基本相同，很少研究負載失衡問題。但面向廣域網絡的內容發布訂閱系統多數采用了動態網絡拓撲、單播路由協議等實現方式，并且需要支持復雜應用環境，如交通流量信息管理、實時股票信息管理應用等，因此易產生負載失衡問題。為解決該問題，設計了內容發布訂閱系統動態負載均衡框架，包括負載探測、負載決策、負載遷移、負載協商四個關鍵部分。實驗結果表明該解決方案以低開銷提高了50%的負載均衡效率。
1相關工作
動態負載均衡在分布式計算領域是經典研究問題，文獻[3~6]分別研究了網絡層、操作系統層、中間件層、應用層的負載均衡問題。但由于內容發布訂閱系統負載特征的特殊性，上述方法并不能直接應用(詳見1.3節)。
在類似的P2P系統研究中[6~8]主要采用了均衡劃分哈希數值空間的方法均衡初始負載。內容發布訂閱系統中的數據特點是具有內容語義，其數據分布是非哈希均勻且高度動態變化的，因此數值空間均勻劃分并不能解決其動態負載均衡問題且數據哈希會使得區間訂閱機制的代價很高[9]。文獻[10]中基于隨機加入新節點的方式實現了局部均衡負載。文獻[11]雖然實現了全局負載均衡，但其代價是維護整個系統的負載索引，限制了系統的可伸縮性。
目前的內容發布訂閱系統通常通過多代理網絡的結構實現[1]。基于事件空間劃分（圖1）的方法是目前內容發布訂閱系統研究的前沿。文獻[12]提出了一個基于K－D樹劃分內容發布訂閱系統解決方案，即將事件內容屬性及其值域集成為空間Ω(圖1)，并由代理維護不同區域內的事件匹配和路由轉發任務[12]。本文以此為基礎進一步解決其動態負載均衡問題。
2負載均衡框架
代理的負載均衡框架(圖3)由四個組成部分，即負載檢測器、負載均衡決策器、負載協商器、加載/卸載算法執行器。負載檢測器執行負載檢測、發現和報告；負載均衡器基于負載檢測信息和相應的算法進行選擇實施負載均衡的目標代理、加載/卸載算法執行器基于遷移算法和本地負載率執行負載遷移作業；負載協商器基于負載協商會話(session)協調代理之間的負載均衡操作。
a)代理當前的負載的度量值LMC(load metric)。該值是代理基于負載估計算法對其自身當前負載狀況的定量值。它表明現在的負載狀況。涵蓋了當前的系統資源的使用比例和系統延遲和消息隊列的長度信息。
b)當前代理的負載均衡操作狀態LBS(load balancing status)。包括正常（OK）、過載（OL）、均衡操作中（LB）和惰性(inert)四種狀態。負載協商協議使用其來判斷后續負載均衡操作。
c)代理的惟一標志BID：該標志代表了與定位惟一代理相關的信息。
LoadMessage是負載均衡決策的依據。相鄰代理的LoadMessage構成了負載信息列表Loadlist。
2．2負載協商
負載協商是代理之間協商完成負載遷移的過程。代理在該過程中的狀態自動機如圖4所示。其中OK表示負載正常狀態；OL表示過載狀態；LB表示正在進行負載均衡操作狀態；Inert表示代理進入一個不響應負載均衡相關請求周期T。Inert狀態是解決負載遷移后到產生實際系統開銷存在的滯后所導致的錯誤檢測問題，使得代理在時間T后探測本地負載。
代理之間的主要協商過程包括：
a)代理By向作為負載接收方的代理Bx發送請求request；
b)Bx在響應消息response中附加其當前負載均衡操作的狀態以及資源利用率V。
c)如果response中的負載狀態屬性是OK，則Bx、By同時將其狀態更新為LB，并分別啟動加載／卸載算法執行器實施負載遷移操作。
d)操作完成兩者同時將負載狀態更新為Inert，并在一個穩定周期之后更新狀態為OK。
2．3負載遷移
路由和匹配是代理的主要負載。
匹配是代理基于當前所維護的訂閱條件檢索到達事件訂閱者的過程，其開銷主要與訂閱條件數量成正比。而在事件空間中區域是訂閱條件的集合，訂閱條件即與地規模表現為區域的規模[12]，因此改變代理所駐留的區域規模是遷移訂閱條件并導致匹配負載改變的主要途徑。
在K－D樹劃分[12]的事件空間中，區域改變過程在K－D樹中表現問題葉子節點的合并和分裂，如圖5所示。因此，匹配負載卸載算法如算法1所示。
算法1匹配負載卸載算法
輸入：接收負載代理new_Broker
輸出：無
步驟：
a)If current_broker_match_load is overload{
b)new_Broker.zone=Split_zone_between (current _broker， new_Broker)}
c)If accept a match_load_request{
d)Current_broker.zone= Merge_zone_between(current_broker，other_Broker)
e)}
f)Updaterouting(new_broker);
g)Updaterouting(current_broker);
h)return new_Broker
i)end.
算法判斷:a)如果當前代理匹配負載過載，則將其當前維護的區域分裂為兩個區域，其中一個委派給進行負載均衡的代理；b)如果接受了匹配負載加載的請求，則將請求代理與當前代理的兩個區域進行合并。由于區域分裂改變了代理的相鄰關系，在區域分裂之后需要更新兩個代理的路由關系。
需要指出的是，算法并不需要全局信息，僅需要原區域的坐標和上一劃分維即可實現[12]。例如，原區域坐標是B3（X:0~4;Y:4~6;Y）。其中：前兩項分別是區域在X維Y維的區間坐標；最后一項是該區域最后一次劃分的維，因此二分區域重構僅將X維坐標二分即可形成兩個新的區域：B3（X:0~2;Y:4~6;X）B5（X:2~4;Y:4~6;X）。
匹配負載加載是節點區域合并的過程，若是非相鄰節點，則選擇一個相鄰節點作為替換節點[12]。
路由負載是由于代理轉發消息流產生的，與代理所維護的訂閱條件數量無關，而是與消息流量成正比。如圖6所示，將區域Z劃分為Zx、Zy兩個區域的方法并不能遷移代理Bx上的路由負載。
因此需采用代理復制技術遷移路由負載，即將區域駐留代理的功能在另一個代理復制，使得在線消息流在兩個代理之間二分，從而降低代理路由負載。如圖7所示，消息由兩個代理分別轉發。例如，區域Z的主代理Bx路由過載，通過復制代理By產生新的轉發路徑，從而減少了經過Bx的流量。相應地，取消復制代理則增加了原代理的路由負載。
2．4動態負載均衡決策
動態負載均衡決策主要基于負載檢測的動態反饋信息判斷何時與哪一個代理執行負載均衡操作的問題。
隨機加入方法[10]基于概率P發現負載最大的代理，利用Loadlist中的動態負載檢測采用轉移加入的方法概率增加為n×P(n=Length(Loadlist))，如算法2所示。
算法2轉移加入fwdaddrqst
輸入：加入請求newrequest
輸出：無
步驟：
a)Bp=Searchmaxload(Loadlist);
b)if(Bp.load<>1) (Bp.load>currentload){
c)forward newrequest to Bp
d)}else{
e)accept(newrequest)
f)}
算法首先查找Loadlist中最大負載代理Bp(算法第1行)；若Bp的負載大于本地負載（算法第2行），則將加入請求轉移到Bp（算法第3行）；否則，接受加入請求（算法第4～5行）。算法代價是維護并搜索2d個相鄰代理的負載信息（d為空間的維數）。
算法2存在的問題是：(a)局部均衡時無法發現其他區域的最大負載代理;(b)無代理加入時不能實施負載均衡。因此，通過引入子空間和負載比的概念提出自適應負載均衡方法以解決上述問題。
在文獻[12]中，K－D樹的中間節點(如圖2所示的節點BL1~BL4)代表了一組相鄰區域，將其定義為一個子空間G。如圖8所示，空間Ω分為四個子空間（G1~G4）。為了使負載能夠在子空間之間遷移，需要在代理建立指向子空間的指針。
定義|G|=m（2 在子空間概念基礎上的自適應負載均衡決策的步驟是：a）查找Loadlist中負載比TLoad<ε的代理觸發負載協商；b)若未發現，則使用SpanhopList查找。 當負載遷移的操作被觸發，由于區域的位置不相鄰，為了保證區域關系的一致性，不同子空間的代理負載遷移如算法3所示。 算法首先判斷是否接受負載遷移的請求（第1行）；然后檢測是否具有復制代理，若有則卸載，并在復制代理與過載代理之間進行負載遷移操作(第2~6行)，否則，則采用替換策略，即將其區域合并到最小負載相鄰代理，并與過載代理By實施負載遷移（第7~12行）。若B8.Load/B14.Load<ε，那么B8選擇B7發出移交請求，B8、B7合并區域到B7，B8與B14按照負載遷移策略實施負載均衡。 3仿真實驗分析 采用Java語言實現了基于二維實數事件空間中內容發布訂閱系統負載均衡仿真器。事件空間被劃分成2 500個區域，每個區域代表一個代理。其中的u和v維的數據分別產生符合Zipf分布的數據共106個(u，v)。負載由落入該區域的數據總量反映。主要負載性能指標是代理負載占數據總量的比例。在理想的情況下，每個代理平均分擔所有的系統負載。因此，負載比例曲線是y=x，如圖 9所示。但由于非均衡分布數據，產生了少數代理承擔大于數量比例的負載，曲線會偏離y=x。負載均衡算法的評價是測試系統中的代理負載比例是否接近y=x斜線。 測試了三種情況下的系統負載狀況： a)無負載均衡處理的系統在非均勻數據分布情況下的負載狀況。 b)使用轉移加入的負載均衡處理。設置2 000個區域作為系統初始狀態，然后向代理網絡加入500個新的代理。其中假定基于代理所維護的相鄰代理的負載，所以，每個新加入的代理能夠發現最小負載代理進行均衡。c）使用自適應負載均衡處理。設置ε=0.6。 測試結果如圖 9所示。無負載均衡處理情況下，20%的過載代理負載了接近50%的數據量，而20%的欠載代理僅負載了3%的數據量。轉移加入和自適應負載均衡處理之后，20%過載代理的負載數量分別降低到了36%和29%。自適應負載均衡優于轉移加入方式的原因在于提供了動態檢測和均衡，代價是維護SpanLoadlist中代理的負載信息。SpanLoadlist產生了外部指針的效果，避免了局部負載優化而全局負載失衡的現象，在少量負載維護代價的情況下實現了全局負載均衡。減小閾值ε可以產生更為動態的效果，但同時也增加了系統開銷，可以根據系統的情況設置具體經驗值。 4結束語 本文提出了解決內容發布訂閱系統中動態負載失衡問題的負載均衡框架，詳細描述了其中的負載檢測、負載遷移、負載協商、負載決策等關鍵組成部分。實驗結果表明系統的負載失衡得到了有效控制。進一步的工作是研究精確的負載計算方法，提高識別不同類別負載能力。 參考文獻： ［1］CARZANIGA A，ROSENBLUM D S，WOLF A L.Design and evaluation of a wide－area event notification service[J].ACM Trans on Computer Systems，2001，19(3):332-383. [2]PIETZUCH P R，BACON J M.Hermes:a distributed event－based middleware architecture[C]//Proc of the 1st International Workshop on Distributed Event－Based Systems.Berlin:Springer－Verlag，2002:611-618. [3]ALEKSY M，KORTHAUS A，SCHADER M.Design and implementation of an extensible load balancing service for CORBA－based applications[C]//Proc of International Conference on Parallel and Distributed Processing Techniques and Applications.New York:IEEE Press，2001:75-83. [4]BARTH T，FLENDER G，FREISLEBEN B，et al.Load distribution in a corba environment[C]//Proc of International Symposium on Distributed Objects and Applications.New York:IEEE Press，1999:158－162. [5]BERMAN F，WOLSKIR.Scheduling from the perspective of the application[C]//Proc of HPDC’96.New York: IEEE Press，1996:100－111. [6]DIAS D M，KISH W，MUKHERJEE R，et al.A scalable and highly available Web server[C]//Proc of the 41th IEEE Computer Society International Conference: Technologies for the Information Superhighway.New York:IEEE Press，1996: 85-93. [7]RAO A，LAKSHMINARAYANAN K，SURANA S，et al.Load balancing in structured P2P systems[C]//Proc of the 2nd International Workshop on Peer－to－Peer Systems.Berlin:Springer－Verlag，2003:68-79. [8]BYERS J W，CONSIDINE J，MITZENMACHER M.Simple load ba-lancing for distributed hash tables[C]//Proc of the 2nd International Workshop on Peer－to－Peer Systems.Berlin:Springer－ Verlag，2003:80-87. [9]ZHU Ying－ wu，HU Yi－ ming.Ferry:an architecture for content－based publish/subscribe services on P2P networks[C]//Proc of the 34th International Conference on Parallel Processing.New York:IEEE Press，2005:427-434. [10]CARZANIGA A.Architectures for an event notification service scalable to wide－area networks[D]. Italy:Politecnico Di Milano，1998. [11]GANESAN P，BAWA M，GARCIA M H.On－ line balancing of range－partitioned data with applications to peer－to－peer systems[C]//Proc of the 30th VLDB Conference.New York:IEEE Press，2004:444-455. [12]逯鵬，劉旭東，林學練，等.基于興趣劃分的內容發布訂閱系統關鍵算法[J].北京航空航天大學學報，2006 ，32(8):852-857. [13]逯鵬，劉旭東，林學練，等.基于事件空間劃分的高效發布訂閱系統路由算法[J].計算機應用研究，2007，24（7）：238-241. [14]KARGER D R，RUHL M.Simple efficient load－balancing algorithms for peer－to－peer systems[C]//Proc ofACM Symposium on Parallel Algorithms and Architectures.New York:ACM Press，2004:36-43. “本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
