2017, Vol. 42引用本文 |
| 基于Hadoop的地图瓦片云存储系统的设计与实现 |  [PDF全文] |
2. 北京吉威时代软件股份有限公司，北京，100043
2. Beijing GEOWAY Software Co., Ltd., Beijing 100043, China
地图瓦片缓存技术能够实现在线地图的高效浏览，被广泛应用于各种WebGIS系统中[1-4]。基于金字塔模型建立瓦片数据集具有单个文件小、文件数量大、整体数据量大等多重特点，这些特点对地图瓦片的高效存储和管理提出了挑战。当前普遍采用的集中式文件系统存储方式无法提供海量的存储能力，同时大量的小文件还会造成严重的磁盘碎片化，影响系统的IO性能，数据也存在安全问题[5]；而基于集中式数据库的存储方式虽然解决了瓦片数据磁盘碎片化和安全性的问题，但是依然无法对海量瓦片进行有效存储。
Hadoop云计算框架是一个能够对大数据提供分布式处理的开源框架，其主要由分布式文件系统HDFS (Hadoop distributed file system)、MapReduce并行计算框架和分布式NoSQL数据库HBase组成。HDFS能够方便地部署在普通的PC上，提供海量的存储能力和计算能力；MapReduce可以便利地使用HDFS提供的计算能力进行并行计算；HBase基于HDFS，能够克服HDFS对小文件的处理能力的不足，提供对海量小文件的高效读写[6, 7]。
因此，本文基于Hadoop云计算框架设计实现了一种地图瓦片云存储系统，系统采用HBase存储瓦片数据，基于MapReduce实现了瓦片的并行入库，并通过Hilbert曲线构建空间索引，提升查询效率。经性能测试，该系统能够实现海量瓦片的快速导入和高效查询。
1 地图瓦片云存储系统架构本系统搭建在普通的PC集群上，是一个典型的主从式架构，其架构如图 1所示。系统由一个主节点和若干个从节点组成，瓦片数据存储在HBase表中，系统底层依赖于HDFS分布式文件系统。存储瓦片的HBase表被分割成一系列行键相邻的子表，交由不同的从节点进行增、删、改、查管理，一个从节点可以管理多个子表；从节点亦是HDFS的一个数据节点，子表中的瓦片数据按照行键有序聚合成特定格式的数据文件，存储于数据节点中。主节点存储系统的元数据，元数据记录了行键到子表、子表到管理从节点的映射，主节点提供的元数据可以将客户端的操作请求路由派发到特定的从节点，交由从节点来执行；主节点还负责执行表级别的操作，执行子表的划分和合并操作。
 |
| 图 1 地图瓦片云存储系统架构图 Figure 1 Structure of Cloud Storage System for Map Tiles |
采用这种主从式架构，可以在不同的从节点上进行瓦片的并行入库，提升系统的瓦片写入能力；客户端对不同瓦片的查询请求交由不同的从节点来处理，可以减轻单节点的查询负载，提高系统的查询能力。
2 地图瓦片云存储系统关键技术 2.1 基于Hilbert曲线的空间索引的设计与构建空间填充曲线能够实现多维空间到一维的映射，可以维护多维空间关系，广泛应用于空间索引中[8]。传统的瓦片是按照层级、行、列来组织存储的，它是基于行序曲线来构造空间索引。而在所有的空间填充曲线中，Hilbert曲线具有最优的空间聚集性[9]。本文采用Hilbert曲线分别填充金字塔瓦片集的每一层瓦片矩阵，设计了附带层级信息的Hilbert空间排列码作为空间索引，在保证同级瓦片数据物理存储邻近的同时，同级瓦片矩阵中空间相邻的瓦片在物理存储上亦相邻，其相比基于行序曲线的空间索引，具有更好的空间聚集性，范围查询性能更优。
空间索引即行键在HBase中以字节数组形式存储，按照字典序排序。本文利用层级信息和Hilbert排列码设计了等长字符串作为空间索引，依照电子地图规范，瓦片地图具有1~20级数据[10]。层级数最大位数为2，第20级具有419张瓦片，其是空间排列码的最大值，有12位。故设计如图 2所示的空间索引字符串，前2位代表层级，后12位代表Hilbert排列码。
 |
| 图 2 附加层级信息的Hilbert排列码 Figure 2 Permutation Code of Hilbert Curve with Level |
Hilbert空间填充曲线由一系列以U字型穿过2×2格网矩阵的原子曲线组成，原子曲线有图 3所示的4种形态，即Hilbert曲线的状态向量；特定形态的原子曲线中各个子象限对应的子曲线形态是固定的，即Hilbert曲线的区域状态转移向量，如图 4所示。基于Hilbert曲线的以上特性，可以通过空间层级分解，逐级细化递归生成Hilbert排列码，该方法相比传统方法显著地提高了效率[11]。本文结合基于空间层次分解的Hilbert码生成算法来构建瓦片空间索引，其流程如下：
 |
| 图 3 Hilbert曲线状态向量 Figure 3 State Vector of Hilbert Curve |
 |
| 图 4 Hilbert曲线区域状态转移向量 Figure 4 State Transition Vector of Hilbert Curve |
1) 设定0阶曲线 (贯穿第1级单张瓦片) 的Hilbert码作为初始排列码，并依据Hilbert曲线预设的起终点设置1阶曲线 (贯穿第2级2×2张瓦片) 的初始状态向量；
2) 依据瓦片行列号，判断瓦片所处的子象限，由状态向量确定该子象限的空间排列码 (依据贯穿顺序依次为0、1、2、3)；
3) 对初始排列码做基于位的操作，将第2) 步所得的子象限排列码的二进制形式补位到初始排列码二进制形式的末尾，形成新的排列码；
4) 依据区域状态转移向量，确定该状态向量中对应子象限中子曲线的状态向量；
5) 重复步骤2)~4)，直到细化到瓦片所处层级，得到最终的Hilbert排列码；
6) 将Hilbert排列码前面用0补位到12位，将层级前面用0补位到2位，拼接即可得到瓦片对应的空间索引。
2.2 地图瓦片的并行入库海量地图瓦片在HDFS上串行入库会导致数据向计算迁移，节点间大量的数据传输会造成极大的耗费，使入库极为耗时。利用MapReduce并行计算框架对HDFS上的瓦片数据并行入库，使得计算向数据迁移，极大提高了入库性能。ArcGIS Server10.0所推出的紧凑型瓦片缓存格式是当前广泛采用的主流瓦片格式，其将每128×128瓦片方阵存储在一个bundle文件中，并对应一个同名的bundlx索引文件。本文设计了并行入库模块对该种类型瓦片进行并行入库，其流程如图 5所示。
 |
| 图 5 并行入库流程图 Figure 5 Flow Chart of Parallel Loading |
其中对于紧凑型瓦片的解析过程如下：
1) 解析瓦片文件bundle的路径和文件名，获取瓦片方阵的层级和左上角瓦片的行列号；
2) 循环遍历同名索引文件bundlx字节内容，获取每张瓦片的字节内容在bundle文件中的字节起点，获取瓦片相对瓦片方阵左上角的行列号；
3) 在bundle中定位到瓦片字节内容的字节起点，读取表示瓦片字节内容长度的字节片段，获取瓦片字节内容长度，依据长度和起点，获取瓦片数据；
4) 依据瓦片方阵层级、瓦片方阵左上角行列号、当前瓦片相对于矩阵左上角瓦片的行列号，获取当前瓦片的层级、行列信息。
3 性能测试与结果分析为了验证地图瓦片云存储系统的读写性能，本文利用测试数据对系统进行了并行导入和查询性能测试。
3.1 测试环境与测试数据本文在普通PC上搭建系统集群，每个集群节点对应一个PC机，节点采用虚拟机安装部署ubuntu.14.04 LTS操作系统，虚拟机配置统一为4核CPU、3 G内存、100 G硬盘，软件环境统一为Java JDK1.7.0 _76、Hadoop2.7.2、HBase1.1.3，软件配置一致。
将全国范围TIFF格式DEM影像数据在ArcGIS Server中进行切片处理，生成地形地图瓦片数据集，选择第10~13级的数据作为测试数据，数据的详细情况如表 1所示。
| 表 1 测试数据信息 Table 1 Information of Test Data |
 |
3.2 瓦片入库性能测试
典型的Hadoop集群中每个数据块具有两个数据副本，以保证系统的数据安全性，故一般集群至少需要1个主节点和3个从节点。入库测试中首先搭建1主3从的系统集群，设置单个任务处理的数据量为64 Mb，每个节点可运行两个任务，对瓦片数据并行入库，并与串行入库做了对比，测试结果如表 2所示。可以看出，并行入库相比串行大大地缩减了入库时间，并行入库速度随着数据量的增加不断提升，分析原因在于，随着数据量的增加，集群节点的运算能力得到了充分利用，任务分配和启动对应的固定耗费在整个入库耗费所占的影响越来越小，使得入库性能越来越好。
| 表 2 瓦片入库测试结果 Table 2 Test Result of Tile Loading |
 |
为了测试节点数目对并行入库性能的影响，本文搭建了1主4从、1主5从的集群环境，对瓦片进行了入库测试，并与1主3从做了对比，其结果如表 3所示。
| 表 3 不同节点瓦片入库测试结果 Table 3 Test Result of Tile Loading for Different Node Number |
 |
可以看出，在小数据量下，节点数目的增加并不能提升入库的速率，入库速度的微小差异是由测试误差造成的；而在大数据量下，节点的增加可以提升入库的速率。分析其原因在于，少数几个节点就可以满足小数据量的入库性能要求，节点增加带来的性能提升被闲置，入库速率无提升；而在大数据量的情况下，节点增加带来的性能提升得到充分利用，入库速率得以提高。
3.3 查询性能测试为了验证系统的查询性能，本文基于1主3从的系统集群，分别对1×1、2×2、4×4、8×8、16×16、32×32、64×64的瓦片方阵模拟了100次查询请求，以请求的平均响应时间作为查询响应时间，并与传统基于行序的空间索引进行了对比分析。
图 6表示不同索引方式的查询响应时间，图 7表示查询响应时间差，负代表行序索引查询时间短，正代表Hilbert查询时间短。可以发现，单张瓦片查询时，行序性能占优；范围查询时，附加层级的Hilbert索引占优，随着范围增大，优势越来越明显。分析原因如下：查询响应时间是索引构造和索引查找时间的总和，单张瓦片查询时，索引查找的时间相差无几，主要的影响项是索引构造时间，而行序索引相比Hilbert索引的构造复杂度要小许多，故行序索引占优；在范围查询时，主要影响项是索引查找，附加层级信息的Hilbert索引具有更好的空间聚集性，能够充分利用缓存，索引查找时间短，查询性能更优。
 |
| 图 6 不同索引查询时间 Figure 6 Query Time of Different Indexes |
 |
| 图 7 不同索引查询时间差 Figure 7 Query Time Difference of Different Indexes |
4 结束语
本文基于Hadoop开源云计算框架设计并实现了地图瓦片云存储系统，将地图瓦片存储于HBase数据库中，实验表明，系统实现的瓦片并行入库方法可以大幅提高瓦片入库性能，附带层级信息的Hilbert空间排列码作为空间索引可以提升系统的查询性能。采用这种瓦片云存储方案，既可以实现海量瓦片的存储，也能保证高效的读写性能，是海量地图瓦片数据存储的一种新方式。
| [1] | 孙伟, 李治庆, 焦孟凯, 等. 瓦片地图动态缓存中间件的优化设计及实现[J]. 测绘通报, 2014, (1): 37–40 |
| [2] | 陈超, 王亮, 闫浩文, 等. 一种基于NoSQL的地图瓦片数据存储技术[J]. 测绘科学, 2013, 38(1): 142–143, 159 |
| [3] | 李海亭, 费立凡, 彭青山, 等. 预生成思想在地理信息服务中的应用研究[J]. 测绘信息与工程, 2009, 34(1): 31–32 |
| [4] | 邱儒琼, 郑丽娜, 李兵. 基于MongoDB的电子地图瓦片数据存储和服务研究[J]. 地理空间信息, 2014, 12(6): 155–157 |
| [5] | 罗智勇, 黎小东. 基于数据库存储方案的高性能瓦片地图服务研究[J]. 地理与地理信息科学, 2013, 29(3): 48–51, 108 |
| [6] |
霍树民. 基于Hadoop的海量影像数据管理关键技术研究[D]. 长沙: 国防科学技术大学, 2010 |
| [7] |
陈时远. 基于HDFS的分布式海量遥感影像数据存储技术研究[D]. 北京: 中国科学院大学, 2013 |
| [8] | 郝忠孝. 空间数据库理论基础[M]. 北京: 科学出版社, 2013 |
| [9] | Moon B, Jagadish H V, Faloutsos C, et al. Analysis of the Clustering Properties of Hilbert Space-filling Curve[J]. IEEE Transactions on Knowledge & Data Engineering, 2001, 13(1): 124–141 |
| [10] |
国家测绘地理信息局. CN/Z 9011-2011地理信息公共服务平台电子地图数据规范[S]. 北京: 测绘出版社, 2012 |
| [11] | 陆锋, 周成虎. 一种基于空间层次分解的Hilbert码生成算法[J]. 中国图象图形学报, 2001, 6(5): 59–63 |