SpatialHadoop实例：面向空间数据的高效MapReduce框架

转自：http://www.uml.org.cn/sjjm/201501131.asp

摘要：本文提供了一个如何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连接Space Love以输入具有空间属性的文件并生成输出文件结果。

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/）系统环境是一个有20个节点的系统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/）用户可以看到。