苗 放，马新凡，杨文晖

(1.成都大学 模式识别与智能信息处理四川省高校重点实验室，四川 成都 610106;2.成都理工大学 地质灾害防治与地质环境保护国家重点实验室，四川 成都 610059;3.成都理工大学 地球探测与信息技术教育部重点实验室，四川 成都 610059)

0 引 言

空间信息技术，特别是高分辨率传感器技术的飞速发展使得地理信息系统面临日益严峻的数据量爆炸性增长的局面，有效利用空间数据库的存储需求已经从目前的GB 级和TB 级达到了PB 级.海量空间数据已无法沿用传统的集中存储方式，空间数据显著的海量性和地域分布特征使其更适合于网络环境下的分布式存储［1］，并利用网络中的众多节点联合提供超大容量、高可用、高可靠的数据存储服务［2］.为了有效利用分布式资源，必须解决有关数据放置的挑战［3］.面向分布式存储中，针对空间数据的复杂多维属性，如何设计放置方法使得空间数据能够高效地访问是一个关键问题.本研究基于分布式存储并根据空间数据的特点，提出一种DHT-R放置策略，结合分布式哈希表(Distributed Hash Table，DHT)和R 树特点进行空间数据放置，从而实现空间数据的高效查找.

1 现有数据放置策略

目前，已有的分布式存储系统中根据不同的网络规模和应用，其数据放置策略主要分为2 类.

1)顺序放置策略.顺序放置策略通常是把各个存储节点看成是逻辑有序的，在对数据副本进行分配时先将同一数据的所有副本进行编号，然后采用固定的映射方式将各个副本放置到对应序号的节点上.许多存储系统在设计时的基本思路是基于成熟RAID 技术来实现数据的放置算法，从而能够获得较强的数据访问能力和可靠性.

2)随机放置策略.随机放置策略通常是基于某个哈希函数来决定数据的放置目标，因而可将其称之为伪随机放置策略［2］.

顺序放置策略通常能够获得比较稳定的、可量化的可靠性，当节点发生故障时系统的容错能力较强，但当发生故障的结节数量较多时，恢复系统可靠性的开销比较大.而随机放置策略可保证数据均匀的分布在系统中，从整体上看有利于存储的负载均衡，且在节点发生故障时恢复所丢失数据的开销远小于前者，但其数据访问的本地性较弱，对系统的性能影响较大，当系统随机地出现较多的节点故障时，故障范围覆盖各副本放置目标的概率会比较大，因而随机放置策略的容错能力相对较差［4］.

2 DHT-R 放置策略

从空间数据需求的观点看，任一地理空间实体的描述，必然涉及2 个最基本要素:空间要素和属性要素.空间要素定义实体的空间位置特征，并以指定的空间坐标系为参考，按其几何特征抽象归结成点、线、面或规则几何特征表示简单实体，各实体由相应的几何元素表示.多维属性的数据放置关系到数据的查找效率.利用R 树可将这些多维属性数据用其空间属性以R 树结构的形式组织起来，而DHT 作为一种分布式存储方法在不需要服务器的情况下，每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现整个DHT 网络的寻址和存储.

事实上，采用DHT 来维护网络中的各个节点，主要有以下优势:①这种放置方式使得哈希表在节点失效、遭受攻击和突发性高负载情况下都能表现出很好的健壮性;②这种放置方式具有良好的可扩展性，能以较低的系统开销获得较大的系统规模;③可以自我配置，不需要人工干预就可以自动把新加入节点合并到系统中;④能提供简单灵活的接口.

R 树作为一棵用来存储高维数据的平衡树，当需要进行一个高维空间查询时，只需要遍历少数几个叶子节点所包含的指针，查看这些指针指向的数据是否满足要求即可.这种方式使用户不必遍历所有数据即可获得答案，效率显著提高.DHT-R 可使空间数据按照分布式设置并易于组织索引，使用R树结构组织复杂的空间多维数据，便于实现快速访问.

2.1 空间数据设置索引

空间数据索引被表示成一个(K，V)对，K 称为关键字，可以是数据名(或空间数据的其他描述信息)的哈希值，V 是空间数据在R 树中cp 指针(cp指针指向对应的子节点在R 树中的存储位置).所有的空间数据索引条目(即所有的(K，V)对)组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出该文件的存储位置.然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每个节点负责维护其中的一块.将索引和R 树相结合的存储便于实现快速查找.

2.2 DHT-R 放置策略

索引建立之后，以经纬度作为叶子节点，可将空间数据按照其特定的属性以树型结构组织起来，具体如图1 所示.

R 树采用了一种称为MBR(Minimal Bounding Rectangle)的方法［5］，从叶子节点开始用矩形(rectangle)将空间框起来，节点越往上，框住的空间就越大，以此对空间进行分割.所有最基本的最小边界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住这些矩形.把相邻的经纬度段划分到同一块区域，划分好所有经纬度段之后，再把邻近的区域划分到更大的区域，划分完毕后再次进行更高层次的划分，直到划分到只剩下两个最大的区域为止.图1中CDE，FGH 分别是作为A 区域和B 区域内的按照经纬度段划分的子区域.

图1 R 树组织方式示意图

2.3 DHT-R 空间数据查找

按照“2.1”项的方法设置好空间数据索引，输入空间数据名称，使用DHT 的直接定址法，

H(KEY)=KEY 或H(KEY)=a.key+b

得到空间数据在R 树中cp 指针，然后再利用R 树的Search 算法查找空间数据的存放位置，其查找方法为:

假设A 为一棵R 树的根节点，查找所有搜索经纬段1 覆盖的记录条目.

S1［查找子树］:如果A 是非叶子节点，且A 所对应的矩形与C 有重合，那么检查所有A 中存储的条目，对于所有这些条目.

S2［查找叶子节点］:如果A 是叶子节点，且A所对应的矩形与C 有重合，那么查找C 所指向的经纬段1，最后检查经纬段1 直接指向的指所有记录条目.返回符合条件的记录.

DHT-R 空间数据查找的程序如图2 所示.

图2 DHT-R 数据查找示意图

2.4 空间数据放置流程

空间数据放置流程如图3 所示.

图3 空间数据放置流程示意图

现有已知的空间对象m、M，首先提取此空间对象的信息Info，按照(K，V)对的方式先存储此Info，同时根据空间属性，对其按照R 树结构组织，底层使用Hash 划分并返回数据存放地址到节点，再将节点信息返回，加入到(K，V)对中，从而以DHT 来组织这些空间数据索引.

3 实验与分析

在实验中，本研究采用DHT-R 放置策略实现一个基于局域网环境的分布式存储系统，并对其性能进行实验分析.实验所用的计算机硬件资源和软件环境分别如表1、2 所示.

表1 测试采用的计算机硬件配置

表2 测试所需的软件环境

1)可靠性.依据数据一致性操作流程时节点的增删改查成功的次数占总的操作次数的百分比，由于节点的失效，删除等会导致业务操作的失败.可靠性测试结果如表3 所示.

表3 可靠性测试结果

表3 数据表明，在完成数据操作时，基本不会出现保存用户数据的3 个节点同时失效的情况.

2)操作时延.响应速度是评价一个存储系统系能的重要标准，为了测试系统的时延，采取批量上传和下载不同大小的文件，然后统计其响应时延，按照业界的测试数据，在此应用场景下，能接受的时延阀值为300 ms［6］.操作时延测试结果如表4 所示.

表4 操作时延测试结果

从表4 可以看出，数据取出的的平均操作时延明显低于数据插入的操作时延，这主要是因为执行数据取出操作，只需要把数据从从某个存储该数据的节点s 上找寻其对应的在R 树的存储位置，即代表完成操作，而数据插入操作需要执行从建立R 树子节点到地址返回〈K，V〉的存储和原始数据的存储才代表完成操作［6］.

3)带宽消耗.在模拟生命周期内对于带宽的消耗量，包括节点的出口带宽消耗分布，测试结果如图4 所示.

图4 带宽消耗

从图4 可以看出，域内带宽消耗一般都不超过20 000 Mb，其中主要是应用流量所占的比例，其次是备份流量和目录流量，而修复流量和维护流量所占的比例极小，可以忽略不计，这主要是因为正常情况下节点稳定，很少发生节点失效下线的情况.

4 结 论

本研究根据空间数据的特点设计了一种分布式哈希表(DHT)和R 树相结合的放置策略:按照分布式哈希表存储空间数据基本信息和索引地址，同时以R 树型结构组织和存放空间仿真据，R 树存储使得快速访问空间数据成为可能.实验证明，使用DHT-R 放置策略得到数据存取的可靠性较高，数据的吞吐时延也明显低于业界的阀值.

［1］朱庆，周艳.分布式空间数据存储对象［J］.武汉大学学报(信息科学版)，2006，31(5):391－395 +422.

［2］陈惟康，杜松.分布式存储中数据放置策略的研究［J］.计算机应用与软件，2009，26(1):6－8 +56.

［3］汤小春，胡杰.分布式计算中可靠的数据放置方法［J］.计算机工程，2008，34(23):76－78.

［4］刘翔，汪海玲.分布式存储中的一种数据放置策略［J］.计算机与数字工程，2009，37(5):27－29.

［5］Guttman A.R-trees:a dynamic index structure for spatial searching［C］//Proceedings of ACM Management of Data(SIGMOD).Massachussetts，USA:ACM Press，1984:47－57.

［6］温安宇.基于DHT 的key-value 分布式存储系统［D］.哈尔滨:哈尔滨工业大学，2010.