一种基于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