林业资源数据集群的快速索引设计

李惺颖,谢阳生,唐小明,罗 鹏,黄 龙,2

(1.中国林业科学研究院 资源信息研究所,北京 100091；2.北京林业大学 水土保持学院,北京 100083)

随着林业信息化建设的推进,林业资源数据的总量、质量和时效性都持续增长.在日渐丰富的数据支持下,林业业务系统从单纯的数据管理逐渐转向集数据生产、分析、辅助决策为一体的综合性业务系统.应用复杂度的增加对数据服务提出了更高速度和时效性的要求.目前,一些林业部门已经部署服务器集群以提高系统的整体性能,在这些集群中,通常由一个数据库支撑所有业务系统的运行,相关的数据也都保存在共享的存储空间上[1-5].这种模式下资源的访问是竞争性的,需要分布式锁处理互相冲突的数据访问进程.为避免其他进程破坏正在进行修改的数据,必须将当前的数据锁定,修改完毕后再解锁,新的进程介入后再次锁定,整个数据并行处理期间,分布式锁不断地重复锁定和解锁过程,并发进程越多,过程越复杂.该问题不能通过升级硬件得到解决,必须从存储机制上解决资源冲突的瓶颈.因此,本文提出一种分布式索引结构,能关联多个独立数据节点中的数据,通过大量的数据节点共同负载数据请求,减少互斥的数据访问过程.该索引分为两级,第一级在主服务器上,可快速定位数据所在的数据节点；第二级在数据节点上,延续第一级索引的检索过程,快速确认结果并返回所需数据.对于整个应用服务器集群,只需增加新的数据节点而不需变更数据结构和管理方式,业务系统的数据访问和处理过程也基本不变,只增加访问次数,最终能以较低成本提高整个数据集群的快速统计和更新能力.

1 快速数据索引的设计

数据索引是空间数据管理的关键,可高度并行的空间索引结构能大幅提高系统性能.在分布式环境中,索引结构的效率除依靠自身的效率和可并行度保证外,数据划分也是提高系统效率的关键.合理的数据划分可缩短查询次数,在尽可能短的时间内命中所需数据.R树是最常用的空间索引之一,在单机上通过多磁盘的I/O并发实现并行化.在多机环境中,M-R树和MC-R树采用主从模式分别存储R树的叶子节点和非叶子节点,以实现叶子节点查询过程的并行化[6].GPR树[7]和UPR树[8]等R树的变体也都是在共享内存环境下利用多磁盘存储实现并行化,但这些索引方法并不适用于分布式的存储环境.在分布式存储环境下,一般先进行空间数据划分,划分方法包括轮转法(round-robin)、散列划分(hash partition)、范围划分(range partition)、混合划分(hybrid-range partition)、CMD方法和Hilbert曲线划分法等,划分后能得到多个子区域并建立相应的索引,再为划分后的所有子区域建立第二级索引,如R树、R*树和R*Q树等,最后通过子区域的并行计算实现分布式空间数据的并行索引过程[9-12].

上述研究都针对基于空间范围的查询,假设P为空间对象集,r为某个空间区域,上述方法能够高效地查询到p⊂r,其中p∈P.但在实际应用中,空间查询过程通常会附带某些条件(如查询所有满足条件A

1.1 基于Hilbert码的等差数据划分

数据划分是指将数据按一定规则分配到不同的存储区域中.数据索引的效率取决于数据划分的合理性,尤其是空间数据的划分,直接影响整个系统的性能.空间数据的划分一般通过编码实现,文献[13]对Morton码、Gray码、Hilbert码和Sierpinsky码的空间聚类特征进行了分析和比较,其中Hilbert码在空间查询中效率最高.文献[14]利用Hilbert码空间聚类特性,将关联的数据尽可能集中在一个磁盘上.在共享内存和多磁盘存储的情况下,这种思路效率较高,能减少磁盘读取次数,提高效率.在本文以数据节点位存储和运算单元的环境下,集中在相同数据节点的相邻数据只能顺次访问,而分布在多个数据节点中的相邻数据却可同时访问.

本文提出基于Hilbert码的等差数据划分,先利用Hilbert曲线的空间聚类特性,将空间要素顺次编码[14],然后以数据服务器个数作为公差d,按编码顺序将第i个要素放进编号为i%d的数据节点中.从而相邻的要素将均匀地分布在所有的数据服务器上,能避免查询数据过于集中在某个节点,提高处理过程的并行度.

划分过程变量定义：hilCodeList为计算好的所有元素Hilbert及其编码的列表;serverCount为数据节点数量.划分算法伪代码如下：

Distribute (hilCodeList,serverCount){

int fetCount=1;//设置要素计数器

for each (hilCode in hilCodeList){//遍历列表中的每个要素

将要素hilCode分配至编号为fetCount%serverCount 的服务器上;

fetCount++;}//要素个数自增

}

1.2 快速索引结构

快速索引的核心思想是将数据请求分解为多个直接转向数据节点的子请求.因此,索引结构中不存储数据,只存储数据所对应的数据节点地址.

每个数据节点中都存在大量的属性字段,而数据划分优先保证空间范围的均匀划分而不是数据量的均匀划分,一旦有大量数据更新操作,保持属性字段查询树的平衡即尤其重要,因此需要一种能快速查询的自平衡查找树以实现对属性字段的索引.本文选用节点大小平衡树(size balanced tree,SB树),这是一种自平衡二叉查找树,相比红黑树、AVL树等自平衡二叉查找树更易实现,查询过程较稳定,其所有操作的时间复杂度不超过O(lgn).空间数据的索引通常使用R树,但本文在进行数据等差划分后,每个数据节点内部的数据间会相对分散.R树在未达到分裂需求前,数据的邻接距离差异较大会导致中间节点索引码的覆盖度增大,空间索引码的交叠因子也会增大,最终节点分裂次数增多而降低索引效率.R*Q树针对R树的上述问题进行了优化[12],较适合本文的使用环境.

快速索引的结构如图1所示,分为主服务器索引和数据节点索引两类,结构上都由一棵SB树和一棵R*Q树构成,每棵树都有一个查询入口.主服务器索引中的SB树记录所有的属性字段(Field),并记录当前属性存在于哪些数据节点(Server)上.数据节点索引中的SB树每个节点都是一个子SB树,记录每个字段值所对应空间区域(Region)的索引地址.索引结构中的R*Q树对要素的空间区域进行索引.主服务器上R*Q树的叶子节点上记录该区域的要素被分配在哪些数据节点中,数据节点上R*Q树的叶子节点则保存该区域中要素拥有的属性值及其对应的SB树节点地址链接.

图1 快速索引结构Fig.1 Structure of the fast index

主服务器上的索引,是为了快速找到数据所在的数据节点,数据节点上的索引是为了快速判断自己是否存有所需数据,经过这两次验证用户可同时向确实存有所需数据的数据节点发送数据请求,在避免网络流量压力过大的同时,也能避免在不存在所需数据的节点中盲目查询而影响系统的整体效率.具体数据的查询过程仍通过数据节点上的空间数据引擎进行.因此,主服务器上SB树记录的是整个系统所有的属性字段,R*Q树记录的范围是每个数据节点的整体区域.数据节点上的R*Q树也不能记录到具体要素,否则将导致树的深度过大,反而降低整体速度.数据节点上的R*Q树应该选取常用的最小查询范围,如一个行政村界.

1.3 数据查询及更新

下面通过一个实例说明快速索引的查询过程：查询在Region 5区域中所有属性Field 9的值在1～3的要素.查询过程如图2所示,首先从主服务器的R*Q树开始,在第8步查询到Region 5,然后向其列表中的所有数据节点同时发送请求,接到查询请求的数据节点开始查找自己的SB树,节点Server 1在第3步查找到Field 9属性并在其子SB树中查询到1～3的值2,查询结束.最后数据节点Server 1开始通过ArcSDE查询所需数据并返回给客户端.如果没查询到需要的Field值,则将空值返回客户端,不经过ArcSDE查询.

图2 查询过程Fig.2 Searching process

本文数据根据空间分布均匀划分,如果数据节点不足,则系统数据初始划分完后,主服务器R*Q树的节点中将存在大量的重叠区域,对提高整个系统的效率意义较小.快速索引结构的速度优势必须基于数据节点的数据保证.随着数据节点的增多,数据重叠区域逐渐减少,数据处理的并行度逐渐提高,每个数据节点处理的数据量减少,因而同样数据量的查询所需时间将逐步缩短.对于数据更新,小量而频繁的数据更新将在各自数据节点内进行,并不影响其他节点,只要不是整表,数据节点越多,整个系统中受数据更新影响的服务器比例就越小.对于整表或整个区域数据的更新,可直接将更新数据全部存放在新的数据节点上,建立好数据节点的索引后并入内网,对主服务器索引树的部分节点进行更新,即可快速完成数据更新.索引的更新包括节点的增加、删除及节点数据的更新,在数据产生变化后更新相关联的节点.

索引更新过程伪代码如下：

UpdateDataIndex ( ){

if (新增数据节点){

更新主服务器中的SB树和R*Q树;}

else {

if (整表更新){

更新当前数据节点的SB树和R*Q树;

更新主节点的SB树和R*Q树;}

else {

if (只更新边界){

更新当前数据节点的SB树和R*Q树;

更新主节点R*Q树;}

else if (只更新属性){

更新当前节点的SB树;

更新主节点SB树;}

else {

更新当前节点的SB树和R*Q树;

更新主节点SB树和R*Q树;}

}

}

2 实验分析

为验证快速索引结构在大量数据访问和更新时的效率,本文使用福建(2 354 322个要素,9.59 Gb)和广西(3 148 779个要素,33.1 Gb)两省5 503 101个林地保护规划区共44.69 Gb的数据进行测试,使用10个数据节点.数据库使用Orale,空间数据引擎使用ArcSDE,每个节点都安装了数据库和空间数据引擎.

根据快速索引的应用要求,先对这些数据进行划分,结果列于表1.由表1可见,每个数据节点的要素个数基本一致,每个节点的数据量不同,但其标准差约为0.27,表明数据量的偏离程度较小.在实际系统中,这样的数据倾斜度,并不会对系统效率产生太大影响.

表1 数据划分结果Table 1 Result of data distribution

划分结果的空间分布如图3所示,这是10个数据节点中的4个,其中绿色区域为对应节点所存储的要素.由图3可见,划分后的数据在数据节点上是分散的,但在数据节点间是连续的,表明在实际应用时可从不同的数据节点同时取到连续区域的数据.

图3 划分后的数据分布Fig.3 Distribution of data distributed

为了对比使用快速索引的分布式存储系统性能和现有单数据库存储系统的性能,测试在大量数据查询和更新上的效果,本文使用RAC建立了一个10个节点的单Oracle数据库进行比较,单Oracle数据库上也安装了ArcSDE空间数据引擎.

为保证测试结果尽可能不受ArcSDE和Oracle存储方式的影响,使用快速索引的所有节点和用于对比单数据库中的节点,全部启用ArcSDE的Spatial支持,在通过ArcSDE导入所有数据后为所有数据建立了数据库中的索引,加快库内查询速度以减小其对最终结果的影响,同时数据更新时禁止重建数据库中的索引.

单库集群和多库集群存储查询及更新数据的测试结果如图4所示.由图4可见,查询和更新结果相似,在数据量不大时,多库集群的性能不如或接近单库集群.但随着处理数据量的增大,多库集群耗时的增加相对于单库集群更慢.在达到一定数量级后,多库集群的性能将超过单库集群.

图4 数据查询和更新时间的对比Fig.4 Comparison of data searching time and updating time

图5 数据节点数与处理速度的关系Fig.5 Relationship between number of data nodes and process speed

为了验证节点数量与系统性能的关系,本文使用不同的数据节点查询同样数量的数据,结果如图5所示.由图5可见,系统处理的数据量越大,增加节点数对整体性能的提升效果越明显.

综上可见,本文提出的林业资源数据集群快速索引,能在不改变现有数据管理模式的前提下,以较低成本实现系统整体性能的提升.通过对数据进行划分和索引平均分配数据节点压力,通过增加数据节点减少每个数据节点的处理量,以达到提升系统整体性能的目的.该索引适用于林业系统中经常需要处理大量数据、能配置大量数据节点并有足够内部带宽的数据集群.

[1] ZHANG Dong-you,ZANG Shu-ying,FENG Zhong-ke.Design of Forestry Geographic Information Public Service Platform in Heilongjiang Province [J].Journal of Beijing Forestry University,2007,29(Suppl 2)：26-30.(张冬有,臧淑英,冯仲科.黑龙江省林业地理信息公共服务平台设计 [J].北京林业大学学报,2007,29(增刊2)：26-30.)

[2] PANG Li-feng,TANG Xiao-ming,LIU Peng-ju.Development of the Provincial Forestry Information Sharing Platform Based on WebGIS [J].Journal of Northwest Forestry University,2011,26(2)：180-184.(庞丽峰,唐小明,刘鹏举.基于WebGIS省级林业信息共享平台的研发 [J].西北林学院学报,2011,26(2)：180-184.)

[3] TIAN Bo,DING Li-xia,ZHOU Yun-xuan,et al.Construction of a Multi-layered Distributed Forestry Information Service Platform [J].Journal of Zhejiang Forestry College,2006,23(4)：429-434.(田波,丁丽霞,周云轩,等.多层分布式林业信息服务平台的构建 [J].浙江林学院学报,2006,23(4)：429-434.)

[4] FENG Tie,CHAI Sheng,ZHANG Jia-chen,et al.Approach of Dynamic Change Impact Analysis on Software Architecture [J].Journal of Jilin University：Engineering and Technology Edition,2011,41(2)：458-462.(冯铁,柴胜,张家晨,等.一种软件体系结构动态变动影响分析方法 [J].吉林大学学报:工学版,2011,41(2)：458-462.)

[5] ZHANG Xu,LI Zeng-yuan,DENG Guang,et al.Research and Implementation on Digital Forestry Platform [J].Scientia Silvae Sinicae,2006,42(Suppl 1)：37-40.(张旭,李增元,邓广,等.数字林业平台技术研究与实现 [J].林业科学,2006,42(增刊1)：37-40.)

[6] Kamel I,Faloutsos C.Parallel R-Trees [C]//Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data.New York:ACM Press,1992:195-204.

[7] FU Xiao-dong,WANG Ding-xing,ZHENG Wei-min.GPR-Tree：A Global Parallel Index Structure for Multiattribute Declustering on Cluster of Workstations [C]//Proceedings on Advances in Parallel and Distributed Computing.Piscataway:IEEE Computer Society,1997:300-306.

[8] ZUO Chao-shu,LIU Xin-song,CHEN Xiao-hui,et al.DPslR+：A Distributed and Parallel Spatial Index Tree Based on Dynamic Spatial Slot [J].Computer Science,2006,33(2)：121-126.(左朝树,刘心松,陈小辉,等.DPslR+：一种基于动态空间槽的分布式并行空间索引树 [J].计算机科学,2006,33(2)：121-126.)

[9] CHEN Zhan-long,WU Xin-cai,XIE Zhong,et al.GSHR-Tree：A Spatial Index Tree Based on Dynamic Spatial Slot and Hash Table in Grid Environments [J].Earth Science (Journal of China University of Geosciences),2010,35(3)：463-470.(陈占龙,吴信才,谢忠,等.GSHR-Tree：一种基于动态空间槽和哈希表的网格环境下的空间索引树 [J].地球科学(中国地质大学学报),2010,35(3)：463-470.)

[10] CONG Li,ZHANG Hai-lin,LIU Yi,et al.Particle Swarm Optimized Game Theory for Resource Allocation in Cooperative Networks [J].Journal of Jilin University：Engineering and Technology Edition,2012,42(1)：207-212.(丛犁,张海林,刘毅,等.基于粒子群优化的协作网络资源分配的博弈策略 [J].吉林大学学报:工学版,2012,42(1)：207-212.)

[11] Lawder J K,King P J H.Using Space-Filling Curves for Multidimensional Indexing [C]//Proceedings of the 17th British National Conference on Databases：Advances in Databases.London:Springer,2000:20-25.

[12] YU Bo,HAO Zhong-xiao.Research of Distributed and Parallel Spatial Index Mechanism Based on DPR-Tree [J].Computer Technology and Development,2010,20(6)：39-42.(于波,郝忠孝.基于DPR树的分布式并行空间索引机制的研究 [J].计算机技术与发展,2010,20(6)：39-42.)

[13] Breinholt G,Schierz C.Generating Hilberts Space-Filling Curve by Recursion [J].ACM Transactions on Mathematical Software,1998,24(2)：184-189.

[14] Kamel I,Faloutsos C.Hilbert R-Tree：An Improved R-Tree Using Fractals [C]//Proceedings of the 20th International Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann Publisher Inc,1994:500-509.