| 摘要：本文实例介绍了SpatialHadoop平台，它是第一 个基于成熟MapReduce对空间数据具有原生支持的框架。SpatialHadoop是对Hadoop的做了一个全面的扩展，使其核心功能可以支持空 间数据。因此，对于处理空间数据，SpatialHadoop与目前存在的Hadoop项目相比具有更好的性能。SpatialHadoop主要包括一个 简单的空间高级语言、两级空间索引结构，以及建立在MapReduce层的基本空间组件和三个基本空间操作（范围查询、K-NN查询和空间链接）。其他的 空间操作同样也可以在SpatialHadoop平台上进行部署。本文展示了一个基于SpatialHadoop的原型系统。系统运行环境为Amazon EC2集群，空间数据是从Tiger文件和OpenStreetMap上获取，大小分别为60GB和300GB。 1、引言 许多类似于MapReduce系统，例如Hadoop等，发展的已经比较成熟，而且也有许多基于此的应用程序，如机器学习[3]、兆字节排序[9]、图像 处理[1]等，多年来也被证实了对于大数据分析来说是一个有效的框架。与此同时，对于空间数据也进入了一个爆炸的时代，如智能手机、医疗设备、太空望远镜 等不同来源的数据。然而，不幸的是，对于支持空间数据而言，Hadoop存在着先天的不足，它的核心框架并不能很好的支持空间数据的特性。现有基于 Hadoop处理空间数据主要集中在特定的数据类型和数据操作等方面，如根据轨迹进行范围查询[6]、基于点状数据进行KNN连接[5,13]等。而且这 些对空间数据操作的效率也受到Hadoop内在因素的限制。 
本文提出的SpatialHadoop平台可以通过在线的资源获取（http:// spatialhadoop.cs.umn.edu/.）。SpatialHadoop是基于Hadoop一个全面的扩展（约12000行核心代码），使 从代码层对空间结构和空间数据进行了支持。这保证了SpatialHadoop的工作方式与Hadoop的一致性，通过调用Map和Reduce函数库来 完成工作，因此现有Hadoop项目也能够在SpatialHadoop上运行。然而，对于处理空间数据而言，SpatialHadoop与Hadoop 相比具有更好的性能。如图1所示，（a）和（b）分别表示基于Hadoop和SpatialHadoop何进行空间范围查询。70000000条的空间数 据要素在20个节点的集群上运行同样的查询，Hadoop需要200s，而SpatialHadoop只需2s。 SpatialHadoop基于Hadoop所有层都嵌入了空间结构，包括语言层、存储层、MapReduce层以及业务层。在语言层，提供了一种简单高 级语言用于空间数据分析，即使非技术人员也可以进行操作。在存储层，提供了一个两级空间索引机制，即节点之间分区数据的全局索引和每个节点组织数据的局部 索引。通过这样的索引机制建立了格网索引[7]、R-tree[4]和R+-tree[11]索引。在MapReduce层，嵌入了两个新的空间组件，通 过该组件可以获取索引文件，即SaptialFileSplitter和SpatialRecordReader。 SaptialFileSplitter通过修剪分区来利用全局索引，但不会导致生成查询结果；而SpatialRecordReader利用局部索引来 获得每个分区内有效的访问记录。在业务层，提供了一系列空间操作（范围查询、KNN和空间连接），实现了在MapReduce层应用索引和新的空间组件。 其他的空间操作也可以通过同样的方式嵌入到该平台中。 SpatialHadoop是一个开源共享的平台，允许研究社 区的每一位贡献者对其功能进行拓展。针对不同的应用，SpatialHadoop中的核心基础组件都能够帮助用户高效的实现更多空间操作。通过一个案例研 究，SpatialHadoop已经拥有了三个空间操作，即范围查询，K-nearest-neighbor 查询和空间连接。我们设想，在未来SpatialHadoop将扮演者一个研究载体的角色，更多的研究者将在此基础上共享他们的空间操作和分析工具，形成 一套丰富的体系供开发者、实践者和科研者使用。 本文将通过一个真实的原型系统来介绍SpatialHadoop。该系统采用了两套数据，数据分别来自Tiger文件集[12]和 OpenStreetMap[10]，运行环境为Amazon EC2集群。Tiger文件集包含7000,0000条记录（大小为60GB），有道路、水体和其他的美国地理信息。OpenStreetMap包含全世 界的道路、热点和建筑物边界，数据大小为300GB。 2、SpatialHadoop框架 图2为SpatialHadoop系统框架。SpatialHadoop集群主要包括一个主节点，用来接收用户的查询，并将其分割为更小的任务，并通过多 个从节点类执行这些任务。根据与SpatialHadoop交互目的，用户可以分为三类：普通用户、开发者和管理者。普通用户（非技术人员）可以通过该平 台提供的语言处理他们的数据集；开发者（更高级用户）可以实现一些针对具体应用的新空间操作功能；管理者能够通过调整配置文件中的系统参数来控制整个系 统。 SpatialHadoop采用了分层设计，主要包含四层，即语言层、存储层、MapReduce和业务层。语言层提供了一个简单高级类SQL语言，支 持空间数据类型和操作。存储层包含了全局和局部两个空间索引结构。全局索引用于计算节点间的数据划分，局部索引用于节点内部数据组织。MapReduce 层拥有两个新的空间组件，即SpatialFileSplitter和SpatialRecordReader，分别利用全局（修剪数据但不产生查询结 果）和局部索引。业务层对基于空间索引和MapReduce层新组件实现的多种空间操作进行了封装。SpatialHadoop与生具有高效实现三个基础 空间操作，即范围查询、KNN和空间连接。其他的空间操作也可以通过类似的方法嵌入到该平台中。 
3、语言层 SpatialHadoop提供了一种简单高级语言，非技术人员也可以通过该语言与系统进行交互。该语言内置支持空间数据类型、空间基础功能以及空间操 作。空间数据类（点、矩形和多边形）定义了文件加载过程中的输入文件模式。空间基础功能包括测距、叠加以及MRB（最小外包矩形）。测距即通过空间属性计 算两要素质心之间的距离；叠加分析是发现两个要素之间是否有重叠区域；而MRB是用来计算面状要素的最小外包矩形。空间操作包括范围查询、KNN和空间爱 你连接用来输入带有空间属性的文件和生成输出文件结果。 SpatialHadoop并没有从底层开发一个新的空间语言，而是扩展了Pig Latin[8]。这样不仅保留Pig Latin语言的原始功能，同时也加入了空间结构。尤其是SpatialHadoop语言重写了关键的FILTER和JOIN类库，当输入参数具有空间谓 词时，将分别执行范围查询和空间连接。例如，当FILTER关键词带有Overlays谓词时，SpatialHadoop将执行范围查询操作。对于 KNN查询，引入了一种新的KNN算法。例如计算查询点query_loc距离最近的100间房屋。 houses = LOAD ’houses’ AS (id:int,loc:point); nearest_houses = KNN houses WITH_K=100USING Distance(loc, query_loc); 4、存储层 在存储层，SaptialHadoop增加了新的空间索引。而且索引适合MapReduce运行环境。通过索引客服了Hadoop仅支持无索引堆文件的限 制。在Hadoop上直接运用传统的空间索引具有两大挑战。一方面传统空间索引是采用过程编程范式，而SpatialHadoop采用的是 MapReduce编程范式；另一方面传统索引采用局部文件系统，而SpatialHadoop采用的是Hadoop分布式文件系统，这样的方式有一个内 在的限制，文件仅以一种附加的方式被写入，同时一旦写入就不能被修改。为了克服这些挑战，SpatialHadoop通过两级组织其索引，即全局索引和局 部索引。全局索引通过集群中的节点分割数据，而局部索引在每一个节点内部高效组织数据。全局和局部索引的分离适合MapReduce编码范式。全局索引用 于准备MapReduce工作，而局部索引用于处理Map任务。将文件拆分成更小的文件，允许每个内存分区索引并以顺序的方式将其写入文件。 全局索引保存在主节点的内存中，而每一个局部索引存储在从节点的文件块（通常为64M）中。SpatialHadoop支持格网文件[7]，R- tree[4]和R+-tree[11]索引。通过发行新的文件系统命令writeSpatialFile（SaptialHadoop中）为已经存在的 文件建立索引，用户需要明确输入文件、列建立索引和索引类型。 通过MapReduce工作建立索引经过三个阶段，即分区，局部索引和全局索引。在分区阶段，一个文件被按照空间分区，每一个分区包含一个矩形适合一个文 件块（64MB）。格网索引通过一致的网格进行分区，而R-tree和R+-tree通过一个分布清晰的R-tree分区，从输入文件中随机读取一个样 本、批量加载此样本到临时内存R-tree，然后使用边界的叶节点分割整个文件。值得注意的是，在格网和R+-tree索引中，当每一个记录被写入最合适 的分区时，如果重叠多个分区，那么这些记录可能被复制[4]。在查询过程中，重复的记录会被后期处理掉，这样就避免了产生重复的结果。在局部索引阶段，根 据被构造的索引类型，每一个分区独立创建并同步到一个HDFS块文件中，这个块文件需要标记分区的MBR。因此，每一个分区都有一个固定大小的文件 （64M），局部索引在一次性写入此本之前在内存中构建。最后一个阶段是全局索引。包含局部索引的文件组成一个大的文件，全局索引通过他们的MBRS来建 立所有分区的索引并存储在主节点的主存中。一旦系统发生故障，全局所有就会根据需要重新建立。 5、MapReduce层 传统的Hadoop MapReduce层设计的目的是为了处理不带有索引的堆文件。而SpatialHadoop中的空间操作是以带有空间索引的文件为输入的，处理方式是有 区别的。此外，一些空间操作，如空间连接等，是对二元操作，需要两个输入文件作为输入条件。为了能够处理这些索引文件，SpatialHadoop在 MapReduce层引入了两个新的组件，即SpatialFileSplitter和SpatialRecordReader，利用全局和局部索引分别对不同的数据进行高效访问。 SpatialFileSplitter需要输入一个或两个空间索引文件，除非用户提供过滤功能。然后，利用全局索引修剪文件块，这些修剪块不会导致查 询结果（如外围查询范围），索引创建的同时，基于最小外包矩形进行分配。在进行需要两个输入文件的二元操作中，SpatialFileSplitter采 用两个全局索引去选择需要被一起处理的文件块的对组，作为一个文件（例如，在空间连接中进行叠加分析块）。SpatialRecordReader利用局 部索引，通过局部索引获取一个分块中允许的记录，而不是循环遍历所有记录。它从指定的分区中读取局部索引，将这个索引的指针传递给Map函数，该函数通过 这个索引去选择在整个记录中不需要迭代的处理记录。同时，SpatialFileSplitter和SpatialRecordReader帮助开发者编 写许多类似于MapReduce程序的空间操作。 6、业务层 存储层建立的空间索引，以及MapReduce层新的组件保证了SpatialHadoop可以实现高效的空间操作功能。在这个实例中，本文展示了范围查 询、KNN和空间连接三个案例功能的实现。展示了如何使用SpatialHadoop中存储层和MapReduce层。其他的空间操作如KNN连接和最短 路径分析也能够通过如下类似的方法实现。 在范围查询当中，SpatialFileSplitter利用全局索引选取仅仅覆盖查询范围的区块。每一个查询出来的区块都将通过 SpatialRecordReader提取在该块中的局部索引，然后基于这个索引执行一个传统的范围查询去寻找匹配的记录。对于建立索引过程中重复的记 录，采用参考点副本避免技术[2]来确保每一个结果记录都只出现一次。 KNN操作运用于两次迭代操作当中。第一次迭代，SpatialFileSplitter利用全局索引选取到包含查询点的区块。通过 SpatialRecordReader来提取出这个区块中的局部索引，然后在这个区块中查找KNN。为了验证查询的结果是否正确，以查询点作为圆心，以 Kth邻近目标作为半径，绘制一个测试圆。如果测试圆在处理的区块中完全符合，那么结果就认为是正确的。如果测试圆覆盖到了其他的分区，将通过第二个迭代 来处理这些重叠区域。 对于空间链接，SpatialFileSplitter在两个文件中利用两个全局索引去查找所有重叠区域组对。每一对都通过SpatialRecordReader来处理，SpatialRecordReader采用局部索引去查找重叠的记录。 7、演示情景 本文展示了一个SpatialFileSplitter原型系统（http://spatialhadoop.cs.umn.edu/），该系统环境为 具有２０个节点的Amazon EC2集群。采用了两份数据集，包括Tiger[12]文件集和OpenStreetMap[10]。对已Tiger文件集，本文提取出了三个文件包括美 国的现有的道路段、河流和湖泊。OpenStreetMap，本文提取了全球现有的道路段、热点、公园、建筑范围等。参与者可以通过前端机器（例如，笔记 本）访问Amazon EC2，而所有的处理都在集群后端执行。 
7.1 前端 图3展示了系统的前端，主要帮助用户和管理者与 SpatialHadoop交互，提供了查询和可视化工具。左边有一个选择控件，显示系统加载的文件列表。用户可以通过加载按钮上传新的文件，也可以通过 删除按钮去除已经存在的文件。如果一个文件被选中，文件中的内容会在右侧屏幕中显示。当更多的文件被选中时，他们将以不同的颜色显示以加以区分。如图3所 示，蓝色和红色的线状地物分别代表美国的水体（河流和湖泊）和道路。然后用户可以通过上面的工具条执行查询（范围查询、KNN或者空间连接）操作。前端展 示了查询执行过程，当查询结束时，其结果会在前端进行显示。 
7.2 业务操作 首先，用户通过选择一个文件并点击让它在屏幕中显示。显示过程是通过MapReduce工作将选择文件中的数据生成了一副图像进行输出。生成的图像仅仅包 含了文件中的空间属性，并根据数据类型（点，矩形或者多边形）绘制记录。如图3所示，全局的索引边界也可以在屏幕中显示，便于用户进行索引展示。系统允许 用户对格网索引和R-tree索引进行对比，会发现格网索引更适合一致的分布式数据集，而R-tree索引更适合不一致的数据。由于数据不一致（不规 则），图中的边界是有R-tree索引生成的。显示索引边界是可选的，而且仅显示系统内部。 用户选中一个文件，就可以通过选择上面工具条中的操作来执行一个查询。可用的操作包括范围查询、KNN和空间连接。其中只有空间连接操作需要选择两个文 件执行二元操作。如图4所以，用户选择一个操作后，会弹出一个对话框，用户可以填写查询参数和输的出文件名称。对于范围查询，用户需要提供查询范围的两个 角点。对于KNN，需要提供查询点和邻近对象的个数（k）。对已空间连接，主需提供连接的操作词，默认为叠加。一个有趣的例子是通过连接公园和湖泊去查找 所有公园中含有湖泊的公园，并在屏幕上显示结果。如图4所示，设置完查询参数之后，前端会显示SpatialHadoop中查询空间语句写入的过程。一旦 用户向系统提交了查询请求，前端将会把查询提交到后台进行处理。如图5所以，用户可以看到系统后台查询处理的整个进程。在所有的工作完成之前，这个管理界 面列出了所有正在运行的工作的进展。用户也可以提交随后的查询，这些操作也会同时在后台进行。一旦一个查询执行成功，其结果将会在屏幕上展示。 7.3 与Hadoop对比 
为了对比SpatialHadoop和Hadoop，本文又搭建了一个拥有20个节点的Hadoop集群。用户可以在两个集群（Hadoop集群和 SpatialHadoop）上执行相同的查询，同时观察两者的执行进度。由于SpatialHadoop保留了传统Hadoop的功能，所以非空间查询 也可以在SpatialHadoop上没有任何条件的运行。这样用户可以测试非空间查询功能来比较两个集群的性能。 7.4 安装和配置 SpatialHadoop是开源代码的，在网络上可以公开获取。在实例中，提供了快速安装指南，如何在单机上快速安装和运行 SpatialHadoop。第一步下载安装压缩包并解压到本地磁盘；然后，通过编辑配置文件配置安装。之后，启动SpatialHadoop服务，一些 操作案例就可以和与服务交互并执行。这些步骤可以通过SpatialHadoop官方网页获得更多信息 （http://spatialhadoop.cs.umn.edu/），用户可以看到。 |