一種基于GridGIS的空間負載平衡算法

趙曉暉,方 裕,趙家敏,馬 艷

(1.國核電力規劃設計研究院,北京 100094;2.北京大學遙感與地理信息系統研究所,北京 100871）

一種基于GridGIS的空間負載平衡算法

趙曉暉1,方 裕2,趙家敏1,馬 艷1

(1.國核電力規劃設計研究院,北京 100094;2.北京大學遙感與地理信息系統研究所,北京 100871）

空間數據的廣泛應用需要高效的架構來管理,以增加空間數據的可用性。網格地理信息系統(GridGIS）支持快速的空間數據檢索,允許用戶在任何地方隨時透明地訪問數據,容易引起空間負載失衡。該文提出一種基于GridGIS的空間負載平衡算法——TLB-Cho rd,采用動態負載平衡思想,使用基于Chord算法的樹結構,實現了一個空間負載平衡模擬系統,展示了TLB-Cho rd在GridGIS中更加適用于空間數據。

GIS;網格計算;GridGIS;負載平衡;Cho rd

0 引言

隨著 GIS的快速發展和廣泛應用,空間數據的交互在分布式環境中更加頻繁,這需要有效的系統架構來管理,以便更好地增加空間數據的可用性。網格計算借助網絡技術,整合分散在不同地方的空閑資源,提供更好的、適于大規模資源的共享和協作,改善資源的利用率。傳統的 GIS技術結合網格計算,產生了網格地理信息系統(GridGIS）;GridGIS打破了空間的限制,可以跨平臺獲取空間數據。GridGIS中節點的連接方式會影響系統的執行效率。如果系統只是簡單地連接各個節點,不考慮各個節點的處理能力差異,則不能充分發揮 GridGIS優勢,導致繁忙節點負載失衡,而空閑節點未被有效使用,最終引起整個系統的負載失衡和性能下降。因此,節點連接模式在 GridGIS的空間負載調控中不容忽視。

另一方面,GridGIS中的節點具有高動態性,可以自由加入和退出,這使 GridGIS中如何有效地分配空間任務和利用空間資源變得至關重要。另外,如果分布在系統中的節點經常超載或異常失效,那么存儲在其上的空間數據不能保證被高概率的訪問,就會影響GridGIS整體性能,甚至造成整個系統癱瘓。因此,空間負載平衡研究是 GridGIS中提高系統性能最為關鍵的問題。

本文借助經典的Chord算法思想搭建節點的樹結構,結合GridGIS的特點和空間數據的特性,提出一種基于 GridGIS的空間負載平衡算法——TLBCho rd算法,實現空間負載在各個節點上的合理分配與空間數據共享,減少空間負載失衡現象的出現,改善系統性能。

1 相關研究概述

1.1 GridGIS

網格是一種分布式計算基礎設施,能夠集成不同的資源,進行資源共享,解決動態、多機構的虛擬組織中的問題[1-3];網格的出現加速了信息處理,隨之也在許多領域廣泛應用,著名的網格項目有Info rmation Power Grid[4]、NEESgrid[5]和 SpaceGrid[6]。顯然,對于地理分散的復雜信息,網格提供了一種計算和數據管理的平臺。因此,當網格在 GIS中應用時,GridGIS也就自然而然地產生了。

GridGIS使用網格技術構建網格環境,借助在分布式GIS環境中的地理信息服務器和地理信息服務,處理和共享空間信息,支持跨平臺的信息轉換,向用戶提供基本的網格系統服務和專業的地理服務。Wang等提出了一種 GridGIS軟件平臺體系架構[7],包括5個層次:網格資源層、網格運行環境層、網格系統服務層、領域支持層和應用層。網格資源層處理和共享空間信息,允許在不同操作系統之間進行資源交互;網格運行環境層主要對網格中的專門服務進行開發、部署、發布和環境應用;網格系統服務層實現基本的網格系統服務;領域支持層通過網格空間數據訪問和集成中間件提供方便的空間信息、數據處理和共享;應用層提供嵌入式 GIS、網絡GIS、專業 GIS和桌面 GIS的 GridGIS接口。Grid-GIS遵從網格標準和地理空間信息標準,并使這些標準具有普適性。

1.2 空間負載平衡

雖然 GridGIS能夠有效地集成和管理空間數據,但由于每個機器節點的處理速度各不相同,容易引起空間負載失衡問題。因此,空間負載平衡在GridGIS中至關重要,有助于提高系統性能,實現資源共享,增強延展性和可用性,減少時間消耗。

空間負載平衡算法結合空間信息的地理特性和常用的負載平衡思想,主要分為空間靜態負載平衡方法 (SSLBM）和空間動態負載平衡方法(SDLBM）[8-10]。SSLBM假定系統中有P個節點,將整個空間劃分為P個子部分(每個節點負責一個子部分）;然后,SSLBM把空間等分為T個矩形,使用Hash函數把每個矩形映射到各個節點上。這樣,某些分離的區域可能分配到同一個節點。SDLBM在系統運行階段以自適應的方式平衡節點上的負載,但不能解決節點異構問題。

在GridGIS中,空間負載平衡算法需要處理異構性、資源共享、可擴展性、高延遲性和系統狀態的實時變更。GridGIS中相互連接的網絡有不同的平臺和完全不同的性能,而且提交到系統中的任務形式和規則不同,這些特征使空間負載平衡問題更加復雜。通常,有3個主要方法:重新劃分資源、可分負載理論(DL T）和預測[11]。重新劃分資源把問題域當做一幅圖,通過負載的調配來減少子區域間的失衡和最小化切割邊界;DL T采用任意方式劃分負載,但以線性方式將負載分配到各個節點上;根據對未來估算的實際代價和通信代價,預測方法建立性能預測模型。上述方法在某種程度上能夠改善系統性能,但不能有效解決空間負載失衡問題。因此,本文提出一種空間負載平衡算法,在 GridGIS中使用基于Cho rd的樹結構來改善執行性能和維持系統中的空間負載平衡狀態。

2 基于GridGIS的空間負載平衡算法

2.1 基于樹結構的Chord算法

2.1.1 Chord[12]在大型網絡中,哈希函數廣泛應用在映射和訪問分布式數據上。目前,有很多實現分布式哈希算法的方法,本文主要研究Chord算法。該算法是一種在分布式網絡中存儲關鍵值對的分布式查詢服務,采用相容哈希函數的變體將關鍵值分配給 Cho rd服務器節點,使負載易于達到平衡。Chord算法以分布式方法確定存儲在數據項中的節點。本文在第3章利用Cho rd算法思想連接不同的節點。

2.1.2 基于Cho rd的樹結構 本文提出的算法體系結構由3部分組成:虛擬根節點、中間任務管理器和普通節點。虛擬根節點具有唯一性,負責協調GridGIS中的相關空間任務,并由任務管理器按順序選擇生成。從物理角度上看,虛擬根節點和任務管理器是相同的;從邏輯角度上看,虛擬根節點比任務管理器具有更多的權利。由于任務管理器是以樹結構進行連接,虛擬根節點最初由整體上具有最少負載的任務管理器擔當。本文基于二叉樹的思想,以一種相對平均的方式劃分任務,這樣,虛擬根節點有兩個子任務管理器節點,并且這兩個節點具有在最佳距離內的最輕負載量。一旦替換虛擬根節點,樹中任務管理器節點的位置就會被自動改變;但任務管理器節點的物理位置不會改變。如果虛擬根節點超載,它會發送消息給兩個子任務管理器節點,第一個返回接收消息的子任務管理器節點將接管超載的工作量。如果虛擬根節點不能工作,首先發現這種狀況的子任務管理器節點就會成為虛擬根節點并通知其他任務管理器。虛擬根節點使用全局負載平衡思想,監控、分配和調整每個任務管理器節點的負載。

任務管理器可以在任何時候加入和離開 Grid-GIS,提供空間負載信息和狀態,依據普通節點所處的實際地理位置信息,任務管理器劃分并選擇歸屬于自己的普通節點。同一個任務管理器中節點間的距離小于不同任務管理器中的節點距離,這樣,一旦某個任務管理器出現負載失衡,不會引起整個系統范圍內的網絡擁塞,避免了單點故障。在任務管理器中的空間資源副本信息只存儲在同一個任務管理器下的節點中,即使有一個節點失靈,同一個任務管理器下的其他節點仍然可以正常工作。

所有普通節點的連接是以一種類似Chord結構的形式進行,每個普通節點的空間副本存儲在其他臨近節點上,而且普通節點間的距離小于某個閾值。Chord算法將普通節點組成一個環狀,使空間數據可以快速地查詢和檢索,提高性能和效率。當某個普通節點超載時,它能使用Cho rd中的關鍵字發現有副本的其他普通節點,并轉換當前任務到這些節點上。依據普通節點的性能和數據量,任意一個普通節點將具有其他普通節點的部分副本或整個副本。每個普通節點都有自己的前趨節點或后繼節點。當某個普通節點的負載超過其最大負載值時,其前趨節點將未完成的任務轉換到另一個普通節點,而其后繼節點向與其連接的其他普通節點廣播超載消息。對于矢量數據,本文考慮普通節點所在系統的性能;對于柵格數據,本文把實際的地理圖形分割和合并作為主要因素。

虛擬根節點、任務管理器和普通節點都有自己的記錄表,使用哈希函數來映射這些節點的標識。虛擬根節點的記錄表有相關的地理信息和CPU信息以及任務管理器的摘要信息;任務管理器的記錄表存儲各自內部普通節點的相關內容;普通節點的記錄表包括其負載信息、副本信息、系統性能等。如果系統發生負載失衡,系統能夠及時遷移任務,盡可能減少系統宕機時間。

2.2 TLB-Cho rd算法

依照上節提出的結構,基于Chord的樹結構負載平衡算法(TLB-Chord）劃分為3個負載平衡層級。1）在普通節點層,根據當前負載值,每個普通節點決定是否調用負載平衡操作。普通節點會在給定的時間間隔內自動更新負載信息,監控是否出現負載失衡;一旦負載失衡出現,普通節點或者發起局部的負載平衡算法,或者向其任務管理器通知當前超載信息。2）在任務管理器層,負載平衡只關注任務管理器。只有當普通節點層負載失衡時,才會使用任務管理器層的負載平衡算法。任務管理器需要維護其內部的普通節點,并和其他任務管理器進行交互。由于每個任務管理器了解在其控制區域中的全局狀態,任務管理器可以均分在其內部的超載量。3）只有當任務管理器層的負載平衡算法失敗時,系統才會執行虛擬根節點層的負載平衡算法。虛擬根節點是一個虛擬的任務管理器,它的參數和任務管理器的參數一致,減少了 TLB-Cho rd算法程序的參數量和復雜性,并具有任務管理器信息和全局信息。在虛擬根節點層,本文只關注系統全局的記錄表。

TLB-Cho rd算法在用戶要求或給定的時間間隔內執行,其采用動態負載平衡思想,結合了局部負載平衡算法和全局負載平衡算法。TLB-Chord算法按照普通節點內、任務管理器內、全局的順序制定局部負載平衡的優先級,有效降低了普通節點間和任務管理器之間的信息量,減少了系統開銷。TLBChord算法程序描述如下:

3 實驗分析

本文使用 TLB-Chord算法,在小規模 GridGIS測試環境中構建空間負載平衡模擬系統[13,14];該模擬系統使用10臺計算機(7臺是普通節點,3臺是任務管理器）,這些計算機具有相同的存儲容量,并且都安裝了Globus Toolkit 4.0.5。7個普通節點標號為1～7,3個任務管理器依次命名為A、B、C。本文設定任務管理器A包括普通節點1、2,B包括普通節點3、4、5、6,C包括普通節點7。任務管理器C具有最少的負載,成為虛擬根節點。TLB-Cho rd算法被封裝為網格服務來解決空間負載失衡問題。

本文以河流分布作為地理測試應用,并將該河流分布的空間數據均分為7個連續區域。本文采用節點常規連接方式和 TLB-Cho rd算法中節點連接方式,進行對比實驗,并不斷迭代這個實驗10次以上,以便獲取可靠的測試結果。本文將節點常規連接方式的算法稱為普通算法,其系統中的10個節點按照自然順序依次連接起來組成一個環形,7個連續區域依次分配給普通算法中的節點1～7,而節點8、9和10為空閑節點。TLB-Chord算法將7個連續區域也依次分配給上述的7個普通節點。設定普通算法和 TLB-Cho rd算法中的7個節點都分別具有其他節點的全部副本(表1）。在用戶不斷查詢后,一些區域變成熱點區域,空間負載失衡出現。假設兩種算法中同步出現節點5超載,需要遷移節點5上的空間任務或空間數據,但此時節點3、4、6、7也已經滿負荷運行,不能再接受其他空間任務和空間數據。

表1 各節點副本分配Table 1 The duplicating partition of peers

在這種情況下,普通算法通常通過消息傳遞機制,由節點5向其相鄰節點傳遞超載消息,請求遷移空間任務或空間數據,但由于其相鄰節點4、6也是滿負荷運行,它們又發消息給其鄰居節點3、7;同樣,節點3、7再向其相鄰節點發消息。此時,節點2返回消息給節點3,告知具有節點5的空間數據副本,并可以接受節點5的空間任務遷移;節點8返回消息給節點7,告知可以接受節點5的空間數據遷移。節點3和節點7再把消息按節點5的請求路徑返回給節點5,節點5決定選擇遷移到節點2,還是遷移到節點8。由于空間任務的遷移量遠小于空間數據的遷移量,節點5再按照請求路徑,發出空間任務遷移消息到節點2,完成遷移操作。

在TLB-Chord算法中,每個節點可以通過查詢Cho rd關鍵字獲取具有存儲自己副本的節點信息。因此,當TLB-Chord算法中節點5出現超載時,節點5通過相鄰節點存儲的Chord關鍵字,直接找到節點2具有自己的空間數據副本,然后向節點2請求空間任務遷移;節點2返回接收消息給節點5,完成遷移操作。

盡管兩種算法都采用了空間任務遷移且遷移代價相同,但其通信代價和時間開銷差別很大。本文在帶寬為2 M的局域網中進行模擬測試,普通算法和TLB-Chord算法的網絡測試環境和空間測試數據都相同,采用空間任務遷移前的平均響應時間作為評價因素(圖1）。本文中的空間任務遷移前的平均響應時間是指節點5接收到遷移目標節點2所需的時間開銷。從測試結果可以看出,在單個節點進行空間任務遷移時,TLB-Cho rd算法的執行效率比普通算法的執行效率好,即使在傳遞相同的消息數量時,TLB-Chord算法也比普通算法的時間開銷少。另外,在普通算法進行節點5的遷移請求消息傳遞過程中,如果節點3、4、6和7中的某個節點也發生超載,就會引起系統擁塞,甚至系統癱瘓。然而, TLB-Cho rd算法由于采用Cho rd算法的節點連接方式和三級調控負載算法,可以及時處理節點超載狀況,減少負載失衡,盡可能地避免系統擁塞,改善系統性能。

圖1 時間開銷比較Fig.1 The comparison of time costs

4 結語

本文提出了基于 GridGIS的空間負載平衡算法——TLB-Chord,該算法采用混合結構,結合了基于樹的粗粒度和基于Chord算法的細粒度的負載平衡策略以及消息傳遞機制,減少了系統的停機時間,提高了處理空間數據的系統性能。本文構建了基于TLB-Cho rd算法的空間負載平衡模擬系統,展示了TLB-Chord算法更適于GridGIS中的空間數據。

[1] FOSTER I.What is the Grid?A three point checklist[J].Grid Today,2002,1(6）:32-36.

[2] FOSTER I,KESSELMAN C,TUECKE S.The anatomy of the Grid:Enabling scalable virtual organizations[J].Supercomputer Applications,2001,5(3）:200-222.

[3] FOSTER I,KESSELMAN C,N ICK J,et al.The physiology of the Grid:An open Grid services architecture for distributed systems integration[EB/OL].Open Grid Service Infrastructure WG,Global Grid Forum,2002.http://www.globus.org/alliance/publications/papers/ogsa.pdf.2010-12-31.

[4] EIGENMANN R,VOSSJ M.Towards a compilation paradigm for computational applications on the information power Grid [J].Mathematics and Computers in Simulation,2000,54(4-5）:307-320.

[5] SPENCERB,FINHOLT T,FOSTER I,etal.Neesgrid:A distributed collaboratory for advanced earthquake engineering experiment and simulation[EB/OL].Proceedings of the 13th World Conference on Earthquake Engineering,http://citeseerx.ist. psu.edu/view doc/dow nload doi=10.1.1.2.6552&rep= rep1&type=pdf.2010-12-31.

[6] ZHUGE H.Resource space Grid:Model,method and platform[J]. Concurrency and Computation:Practice and Experience,2004, 16(14）:1385-1413.

[7] WANG J Q,XUE Y,JIANG Y X,et al.Design of GridGIS architecture[A].ISPA 2006[C].2006,LNCS 4331,628-636.

[8] YAN K Q,WANG SC,CHANGC P,et al.A hybrid load balancing policy underlying Grid computing environment[J].Computer Standards&Interfaces,2007,29(2）:161-173.

[9] AN IRBAN M,GODA K,KITSUREGAWA M.Effective loadbalancing viamigration and replication in spatial grids[J].Database and Expert System Applications,2003,2736:202-211.

[10] 趙曉暉,方裕,趙家敏,等.空間負載平衡探討[J].地理與地理信息科學,2011,27(3）:7-11.

[11] L I YW,LAN Z L.A survey of load balancing in Grid computing[A].CIS 2004[C].2004.280-285.

[12] STOCIA I,MORRIS R,KARGER D,et al.Chord:A scalable Peer-to-Peer lookup service for internet app lications[A].ACM SIGCOMM 2001[C].2001.149-160.

[13] 方金云,何建邦.網格GIS體系結構及其實現技術[J].地球信息科學,2002(4）:36-42.

[14] 阮曉青,周義倉.數學建模引論[M].北京:高等教育出版社, 2005.

A Load Balancing Algorithm for Spatial Data in GridGIS ZHAO Xiao-hui1,FANG Yu2,ZHAO Jia-min1,MA Yan1

(1.State N uclear Electric Pow er Planning Design&Research Institute,Beijing 100094;
2.Institute of Remote Sensing&GIS,Peking University,Beijing 100871,China）

The w ide app lication of spatial data needs an efficient framewo rk to manage them and increase the availability of spatial data in geographical applications.The emergence of Grid computing coup led w ith Geographic Information System s(GIS） p rovides an excellent framework:GridGIS,w hich supports fast spatial data retrieval and allow s its users to transparently access data from anyw here at any time.GridGIS also causes spatial load unbalancing.This paper p resents a new load balancing algorithm(TLB-Chord）,w hich adop ts the tree structure based on the classical Cho rd algo rithm to imp rove system perfo rmance and increase the availability of spatial data.First,the relative researchesof GridGISand spatial load balancing are summarized.Secondly,the special thoughtsof the TLB-Chord algorithm are given.The paper discusses how to construct the tree structure based on Cho rd,divides the peers in the system into three kinds:the only virtual root peer,some task managers and many no rmal peers,and gives each kind of peers how to wo rk.Then,it is introduced that the TLB-Cho rd algo rithm has three levels to imp lement the spatial load balancing:the basic level composed by no rmal peers,themiddle level including task managers and the high level having the root peer.The algo rithm begins from the basic level.Once it fails to adjust the load,the algorithm w ill perfo rm themiddle level.If themiddle level also fails,the algorithm w ill adop ts the high level.Thirdly,a spatial load balancing simulation system is given and the TLB-algorithm(peers connected in Chord based on the tree structure）and the common algo rithm (peers connected in the physical o rder based on a ring structure）are compared through the testing environment in GridGIS, w hich uses the iterative way,and show s the TLB-Cho rd algorithm can imp rove the system performance better.

Geographic Info rmation System s;Grid computing;GridGIS;load balancing;Chord

P208

A

1672-0504(2011）04-0036-05

2011-02-22;

2011-04-27

趙曉暉(1979-）,女,博士研究生,研究方向為空間分布式計算。E-mail:zxhsmile@gmail.com