一种并行r树空间的并行计算分析与管理

一种并行r树空间的并行计算分析与管理

空间数据处理、空间决策的支持、空间维度动态可视化、空间绩效模型和模型等属于计算形式和i/o型空间应用，目前的gis计算方法无法满足应用的需求。随着网格计算技术在GIS中的应用逐渐成为研究热点,其分布式并行计算模式与系统架构将有助于提高GIS的整体性能和运行效率。因此,分布式并行计算将成为解决传统GIS计算能力不足问题的重要方法。海量空间数据的组织与管理技术是各类复杂空间应用的基础,也是GIS技术的核心问题。其中,空间索引技术是数据组织与管理的重要研究内容。目前,在数据库管理系统及GIS等科研领域,空间索引技术的研究成果非常丰富,应用较为广泛。然而,针对海量空间数据的组织、管理、存取、处理与应用的分布式并行空间索引技术研究成果较少,已有的研究存在应用平台和应用领域的不同。本文提出一种分布式并行计算环境下基于R树索引和线性链表结构的分布式并行空间索引结构,其设计与开发是以经典的IanFoster并行计算方法论为依据,充分考虑数据划分、负载平衡等影响并行索引机制效率的因素,使得该索引结构更适合于网格等分布式并行计算环境中的各类复杂应用。1并行r树结构存储方式在并行GIS研究领域,已有的研究成果中并未涉及太多的海量空间数据存储方面的问题。然而,在分布式并行计算环境下,海量空间数据的组织与管理是关系到并行GIS整体性能优劣的关键。因此,人们开始研究和探索并行空间索引,以提高空间数据访问效率,其中针对R树并行化方法的研究成果较多。Karnel等最早提出了并行R树索引方法,其并行R树的硬件基础为单CPU多磁盘系统,使用并发I/O方法提高查询的数据吞吐量。Schnitzer等提出了M-R树和MC-R树(Master-ClientR树)方法,两种方法的相同之处在于均是将R树的所有非叶节点存储在多机环境中的主计算机上。两者的区别在于M-R树的叶节点和实体对象直接存储在子节点上,而MC-R树的各子节点存放在子R树。以上3种并行R树结构均采用主从模式,所以主节点很容易成为访问的热点和瓶颈,这将增加事务处理的响应时间,进而降低了系统的整体性能。R树空间索引结构具有固有的并行性特征,适合于并行GIS和并行空间数据库的应用,但从目前已有的并行R树索引研究成果发现,R树在并行计算环境下应用时存在如下不足:1)R树中越靠近根节点的非叶节点被数据库事务访问的概率越大,其成为热点的可能性越大;2)当R树的叶节点进行分裂或合并时,通常会影响该节点邻近的节点,甚至整个R树都需做相应调整;3)访问R树中的节点时,通常需在该节点附加共享锁或排他锁,如果对R树进行更新等操作,则被访问的节点将被锁住,其他事务也不能对该R树进行任何操作,从而降低了R树的事务并发处理能力。虽然R树存在弊端,但实践证明,经过优化设计,其仍是构建并行空间索引的最佳选择。从已有的并行R树索引机制可以看出,分布式并行计算环境中并行R树的构建关键在于新创建的叶节点如何在多个磁盘间分配,其原则包括:1)数据平衡准则,即理想状态下每个磁盘具有同等数量的叶节点,同时需保证数据总量平衡;2)面积平衡准则,即每个磁盘上存储的空间实体所覆盖的空间区域面积平衡,否则存储空间区域面积较大的磁盘很可能成为访问的热点和瓶颈;3)空间关系平衡准则,即尽量将重叠或空间距离较近的叶节点存储在不同的磁盘,以提高查询时的数据吞吐能力。本文根据这些准则,给出分布式并行计算环境(如网络集群)中并行R树空间索引结构的构造方法。2r树空间索引机制2.1空间数据特征在数据库领域,数据划分技术是解决划分后的数据块在各磁盘之间分布不均衡问题(即数据倾斜现象)的有效方法。同样,空间数据划分技术在空间数据库中也发挥着重要作用,在避免产生数据倾斜的前提下,可提高空间数据的并行查询与检索效率。空间数据划分策略是本文并行R树空间索引结构的基础,也是保证该索引机制具有高效率与高性能的前提条件。为遵循上述创建并行空间索引机制的原则,并满足空间数据划分策略的需求,本文采用文献中基于Hilbert空间填充曲线的空间数据划分算法(SpatialDataPartitioningbasedonHilbertCurve,HCSDP)。在充分考虑空间信息的海量特征以及矢量数据存储记录的不定长等特点的前提下,该算法可实现空间数据库中海量空间数据在多个磁盘上的均衡分布,从而避免出现数据倾斜现象。2.2r树索引结构组成已有的并行R树索引机制大部分采用两层或多层索引结构。本文构造的并行R树空间索引结构是基于HCSDP空间数据划分算法的多层并行R树索引(HilbertSpace-FillingCurvebasedMulti-tiersParallelR-tree,HCMPR-tree),图1给出HCMPR-tree索引结构组成。HCMPR-tree索引结构的设计遵循IanFoster的并行算法设计方法论,即经过划分、通信、聚集和映射,使得并行R树索引结构更适合于并行计算环境下的应用。其各层的功能如下:(1)空间实体对象间关系的持续性原则该层包括所有具有统一空间参考系统的空间实体对象和对应的属性数据的集合。使用HCSDP算法对空间区域进行划分,划分后的每个子区域所拥有的空间实体对象均具有连续的Hilbert排列码,这既保证了每个子区域中空间实体对象之间具有较强的空间相关性(如相邻关系等),从而避免经由数据划分后空间实体对象彼此之间的空间关系被严重割裂;同时,又保证了每个子区域之间空间实体对象总量上的平衡。(2)层是子区域的级别该层是待划分空间区域经由HCSDP算法处理后的结果集层。(3)vpe优化策略虚拟处理单元(VirtualProcessingElement,VPE)的引入有助于“聚集”操作的实现。该层中虚拟处理单元的个数为m,通常m<<n(n为子区域个数)。VPE物理上是不存在的,其将被映射到实际的处理单元上。实践证明,影响R树索引性能的一个主要因素是节点之间的重叠度,而产生重叠的重要因素之一是聚集后的空间实体对象之间彼此邻近,即最小边界矩形(MinimumBoundingRectangle,MBR)之间重叠度较高。VPE将为解决这一问题提供较好的策略。子区域层中的每个子区域通过某种数据划分策略(如轮循法)分别映射到VPE集合中,而VPE包含的子区域所覆盖的空间区域是彼此分离的。(4)处理单元映射该层对应实际的物理存储单元或处理单元(ProcessingElement,PE),即网络集群环境中的控制节点、计算节点和存储节点,可认为处理单元即为存储单元。PE的个数对应着集群中实际存在的计算节点的数目k,该值通常小于或等于VPE的个数m。该层实现了“映射”操作,即使用轮循法或其他数据划分算法将VPE映射到PE上。映射后的每个PE将包含一个或多个VPE,而包含的子区域个数的上限则根据n、m、k确定。(5)pe上的r树索引如图1所示,通过一次划分、一次聚集和一次映射操作,最终将所有的子区域分别存放到物理处理单元上。因为每个PE包含两个或两个以上的子区域,而子区域所覆盖的空间范围彼此是分离的,因此每个PE上R树的建立可以按照所包含的子区域进行分块处理,从而加快R树索引的创建速度。每个PE上所建立的R树索引实质上是一般的R树索引,其空间数据访问方法和R树索引的插入与删除操作均与传统R树索引的处理方法相同;而对于集群环境中所有的PE,所有的R树索引之间是彼此独立的,可以实现空间数据并行查询与更新。2.3子节点指向的r树HCMPR-tree索引的叶节点的物理存储包括一组项,其格式为(I,元组标识符),其中I为叶节点对应的MBR,元组标识符是数据库中对应于该MBR的对象的元组唯一标识符。HCMPR-tree索引的非叶节点分为两类,一类是子区域对应的非叶节点,其由一组(RID,I,子节点指针)表示,RID用于标识子区域,I为该节点对应的MBR,即子区域对应的MBR,子节点指针指向该子区域对应的R树的根节点;另一类是子区域对应的R树内的非叶节点,由(I,子节点指针)表示,I为该节点对应的MBR,子节点指针指向下一层节点。每个PE上的R树的根节点由(SID,I,子节点指针)表示,SID标识该R树所在的PE的标识符,I为该PE所覆盖的MBR,子节点指针指向非叶节点。与前人提出的并行R树索引不同,HCMPR-tree索引的最上层用链表保存,链表中每个元素包含5项(RID,SID,I,HS,HE):RID用于标识子区域,SID是存储该元素对应的子区域的PE的标识符,I表示该元素对应的子区域的MBR,HS表示该元素对应的Hilbert排列码的起始值,而HE表示其终止值。该链表保存于网络集群系统的主控制节点上。由于n的个数是有限的,因此可一次性装入内存,使其具有很快的查询速度。这种链表结构避免了将R树所有非叶节点存储于主控制节点而带来的访问冲突等限制。链表结构简单,查询与排序运算速度快,适合于分布式并行计算环境下的并行R树的应用。3hcmpr-创造设备的选择如前所述,HCMPR-tree索引结构的最下一层是对每个PE上的子区域建立的R树索引。与传统R树索引不同的是,HCMPR-tree索引的叶节点选择将关系到并行计算环境中针对并行R树进行的空间数据查询与检索的效率问题。叶节点大小的确定一般分为两种情况:1)如果叶节点过小(如只包含一个空间实体对象),则在进行小范围查询时必须访问多个PE,这就增加了网络通信量,从而会造成网络阻塞;2)如果叶节点过大,则在进行较大范围查询时很可能只在一个PE上进行,这样大大降低了空间数据查询与检索的并行化程度,进而减弱了并行GIS和并行空间数据库的整体性能优势。HCMPR-tree索引叶节点大小的确定受多种因素影响,如网络数据传输速度、PE的计算能力和PE的个数等。本文把针对空间数据库的空间范围查询的系统响应时间作为性能评估指标,在努力获得最小化系统响应时间的同时找到最优的叶节点值。表1是确定系统响应时间的各类参数的说明,其参考标准为运行Windows2000professional的IntelPentiumIV2.4GHz的计算机。表2是确定最优叶节点大小所需参数及其说明。用K表示某个查询需要访问的PE的个数,并建立如下C、K和Q的函数关系:Copt=−QNpe×log(1−Kopt/Npe)(1)Copt=-QΝpe×log(1-Κopt/Νpe)(1)任何一个空间数据查询首先必须通过对主控制节点上的HCMPR-tree的顶层链表结构进行操作,以确定查询范围qx和qy所覆盖的PE的个数及其SID;然后由主控制节点向这K个PE发送数据查询消息,并等待查询结果从这K个PE返回到主控制节点。在表1所示的计算机硬件配置条件下,C的最优取值为1个磁盘页大小,即1Spage。为验证HCMPR-tree索引结构选择的最优叶节点的有效性,本文采用空间查询系统响应时间和叶节点大小两个变量作为参数。实验方案中空间数据集选用全国1∶100万县市级行政区域边界图,大小为17.6Mbytes;处理单元个数分别为2、4、8,查询范围则选择0.1～0.5(qx=qy)。图2是3种PE配置条件下空间数据查询系统响应时间与叶节点大小变化关系的对比。其中,每个子图中的5条曲线从上至下分别为查询范围边界0～0.1的5种状态。本文采用的验证方案参考了Koudas等的相关测试方法,实验结果总体上与Koudas等的实验结果有相似之处,即在最优叶节点大小(1Spage)处,任何一种范围的空间数据查询在具有不同的PE个数条件下均获得了最小的系统响应时间。4基于数据的并行算法设计已有的基于