基于SpatialHadoop的空间大数据拓展研究
2018-04-24杨亚飞汤军宋树华陈建美李功权
杨亚飞 汤军 宋树华 陈建美 李功权
摘 要：文章针对空间大数据的处理框架SpatialHadoop作了系统性的研究。鉴于其在空间大数据实际应用中所存在的无法实现图属关联以及大多数空间分析空间分析不支持的问题对其做了一定程度上的扩展，首先为SpatialHadoop的默认数据类型添加了唯一的标识，并以此为基础关联了空间对象的属性信息。其次还增加了SpatialHadoop对其他类型数据的解析功能，最后扩展了空间操作对属性信息的支持。扩展后的SpatialHadoop将基本支持现有空间数据所常用的功能。
关键词：SpatialHadoop；数据类型；空间索引；空间操作；空间数据
Hadoop孕育自对海量数据的分布式存储和并行处理的应用，但因为针对的领域不同，其在对空间数据的支持设计上存在着明显的不足之处，它的核心框架不能对空间数据的空间特性做良好的支持。现有基于Hadoop的空间数据应用主要集中在特定的数据类型（如轨道的范围查询）和数据操作（如点集的最邻近查询）方面[1]，SpatialHadoop应运而生。
SpatialHadoop是第一个基于MapReduce计算框架的空间大数据处理框架，它对空间数据具有原生支持的特性[1]。
对于空间数据而言，位置和属性都不可或缺。然而，SpatialHadoop的核心框架并没有考虑空间对象的属性信息，纯粹的位置信息也不利于对空间数据进行复杂的空间分析。为了契合实际应用，必须对现有SpatialHadoop框架作必要的扩展。
1 空间大数据框架
1.1 SpatialHadoop简介
SpatialHadoop对Hadoop做了全面的扩展[2]，使其核心功能可以支持空间数据[1]。SpatialHadoop扩展了高级语言Pig Latin并取名为Pigon，不仅保留了Pig Latin的原本特性，同时还增加了支持空间数据的特性。不仅如此，SpatialHadoop还在框架中增加了两级空间索引结构[1-4]，较大程度地提高了处理空间数据的效率。另外，SpatialHadoop基于MapReduce框架还开发集成了两种基本空间组件和一系列的空间操作[2-4]，大大简化了空间大数据应用的开发工作[5]。
1.2 SpatialHadoop的基本功能
SpatialHadoop集群扩展自Hadoop集群，它和Hadoop集群一样都是拥有一个主节点和多个从节点的结构，主节点用来接收用户的查询请求，并将请求的任务（Map/Reduce任务）分割为较小的任务，这些小的任务将分配给不同的从节点来执行[1-2，4]。
SaptialHadoop在分布式文件系统（Hadoop Distributed File System，HDFS）堆文件的基础上增加了空间索引，通过增加索引克服了Hadoop仅支持无索引的堆文件的限制[1]。并将其组织成两级空间索引结构，即全局索引和本地索引[1-4]。
全局索引保存在主节点的内存中，而每一个本地索引都存储在从节点的文件块中[1-4]。将索引组织成全局和本地两个层次是因为这样的分离模式符合MapReduce的编码范式[4]。全局索引用于准备MapReduce工作，而本地索引用于处理Map任务[2]。
空间索引都在Hadoop的HDFS中得以实现，这样可以高效的访问存储在HDFS中的空间数据，而不仅仅是让数据成为堆在Hadoop中的文件[2-3]。对于空间信息而言，增加时间维度的信息具有重要的意义，在SpatialHadoop中可以通过在存储层增加时空索引信息来实现，分片时将考虑空间和时间两种要素[2，4]。
SpatialHadoop为空间数据集建立了一套空间索引机制，那么在空间数据的处理和操作时怎样获取这些索引。为此SpatialHadoop在MapReduce层新增了两个新的组件，SpatialFileSplitter和SpatialRecordReader[1-4]，可以通过这两个组件获取空间数据建立的索引。
空间索引的建立以及MapReduce层新增的组件保证了SpatialHadoop可以实现高效的空间操作功能。SpatialHadoop实现了3种基本的空间操作，分别是范围查询、最邻近点查询和空间连接操作[3]。SpatialHadoop还调用CG_Hadoop计算几何库函数实现了计算几何操作[4，7]。
SpatialHadoop并没像HiveQL和Pig Latin等语言一样从底层开发一种新的空间开发语言[2，5]。它在Pig Latin的基础上进行了空间方面的扩展，增加了对空间数据类型、空间基础功能以及空间操作的支持，并且遵循OGC的标准[5]。这样不仅使其保留了Pig Latin语言的原始功能，同时也加入了空间结构。由于Pig Latin不允许定义新的数据类型，所以Pigon重写了ByteArray数据类型，以此来定义新的空间数据类型。Pigon还支持OGC标准的空间谓词[3，5]。
1.3 SpatialHadoop的优势
SpatialHadoop修改了Hadoop的核心处理框架，使其更加适合处理空间数据，Hadoop和SpatialHadoop的處理逻辑对比如图1所示。
可以看到Hadoop和SpatialHadoop的处理方式是有区别的。
（1）Hadoop MapReduce层设计的目的是为了处理不带索引的堆文件。而SpatialHadoop中的空间操作是以带空间索引的文件为输入的。
（2）在任务分割过程中，SpatialHadoop增加了一个过滤函数可以过滤不需要处理的数据，从而减少map操作的任务量，以增加处理速率。
（3）Hadoop的map处理的是键值对的数据，而SpatialHadoop直接处理的则是小任务的本地索引文件。此外，SpatialHadoop的一些空间操作，如空间连接等，是对二元操作，需要两个输入文件作为输入条件，而Hadoop并不具备这样的能力。
2 扩展空间数据类型并关联属性信息
SpatialHadoop存储的数据类型主要包含3种空间数据类型，即点、矩形和多边形，默认每种数据类型的数据仅仅存储它们的空间信息，不包含任何其他额外的信息，所有类型都是二维的欧几里得空间图形[8]。
默认情况下点类型（Point）数据以二维的空间点位（x，y）来表示。矩形（rectangle）以一对角点来表示的，一个是矩形左下角的那个拐角点，另一个是矩形右上角的那个拐角点。多边形则以一系列的二维点来表示。
文本格式是SpatialHadoop中各类型空间数据的主要存储格式，这将方便我们导入或导出其他应用格式的文件。标准的格式是CVS格式，每条记录都将存储为一行。
纯坐标信息解决不了属性缺失的问题，在SpatialHadoop中不需要记录存储文件的大小，因为他们都是标准的块大小。SpatialHadoop也不需要记录文件中不同空间对象的记录条数，因为块够小，对于并行计算的大数据来说遍历就是最快的算法。而SpatialHadoop的空间数据类型又极具标识性，自然而然也就不需要有对象类型的标识。因此，只需要SpatialHadoop中的空间对象增加一个唯一标识的ID，就可以解决关联空间对象的属性信息问题。
在Spatialhadoop中定义自己的数据类型，需要自己定义一个新的类并且实现shap接口。方便起见，直接扩展现有的标准数据类型来实现自定义的数据类型，这样就可以不用从头开始编写了。
文章定义了3个继承自默认数据类型的新类并为其添加ID字段，当然，仅仅这样还不够，这3个类的对象必须能够被序列化，读取数据时要能识别这些数据类型，还要为新类型重写clone方法。
利用Hadoop的Hbase来存储空间对象的属性信息，因为需要关联空间数据所以Hbase中的属性表必须有一个和空间数据中的ID标识一一对应的属性，Hbase的Row Key就是一个不错的选择。这样在Spatialhadoop中就为空间对象的实体信息和属性信息建立了联系。
3 不同类型的空间数据的解析
对于SpatialHadoop默认的文本存储格式而言，解析不同类型的数据其实只需要解析出不同格式的空间坐标即可。但是对于扩展后的数据类型而言，就不是这么简单了，首先每个空间对象都需要生成一个唯一标识的ID，然后将对象关联的属性信息导入到HBase中并关联。另外，还有一个至关重要的问题，就是目前大多数空间数据的存储格式都将空间对象划分为点、线、面，这样就存在一个问题，线类型数据在SpatialHadoop中到底应该解析成什么类型的空间对象呢？很显然，答案只能是矩形。
无论是二进制文件还是如xml的文本文件，Java都有提供解析此类文件的库函数，如果知道文件的组织形式，解析起来就比较方便了。下面以ESRI的Shapefile文件类型举例说明。
ESRI的Shapefile文件支持14种几何类型，每种类型数据都用一个数字来标识，1代表点状类型数据，3代表线状类型数据，5代表面面状类型数据，而标识几何类型的位置在shp文件的自起始位置0开始计数的第32个字节位置上，在第24个字节处记录了文件的长度。从36到68这个区段还记录了整个文件数据的最小点和最大点信息，可以据此提取出该文件的最小外包矩形[9]。
接下来就是解析实体信息的内容了，空间实体对象在shp文件中用记录段来存储，记录段包含记录头部和记录内容两部分的内容，记录头部包含记录号和坐标记录长度，记录内容包括几何类型和坐标内容。默认情况下只需要把坐标信息提取出来就可以了。扩展后则需要为每条记录生成一个ID。
最后就是提取属性信息了，和实体信息关联的HBase表的表名需要和存储实体信息的文本文件名称相同。由于shp文件中的空间对象和dbf中的记录顺序是一一对应的，所以提取属性信息就简单得多，因为ID号是顺序生成的，所以提取属性信息时只需要知道首个ID号，之后只需顺序读写属性信息即可。
4 空间索引
空间索引是为了提高在空间数据集中查找或处理某个图形对象的效率，不同于在一台机器上建立索引，对于分布式存储必然涉及两种层次索引结构，一个是在集群中搜索数据存储的节点位置，另一个则是在本地搜索數据所在的块。这就需要在SpatialHadoop的主节点和从节点上分别建立空间索引文件。
4.1 索引布局
SpatialHadoop为空间数据集建立了全局和本地两种层次的索引。每一个空间数据文件的索引都会包含一个存储在主节点的内存中的全局索引存文件，而分片的数据将存储在本地索引文件中。
SpatialHadoop包含多种空间索引技术，最常用的是网格索引、R树和R+树索引，网格文件一般只适合用于均匀分布的空间数据，而R树和R+树则偏向用于倾斜的空间数据，即空间分布不均匀的空间数据[1，3-4]。
SpatialHadoop创建索引的过程（见图2）：（1）用户通过命令或者应用发出建立索引请求。（2）主节点读取空间数据的元数据信息，并为从节点分配建立索引的任务。（3）从节点构建空间数据的本地索引，并以块的形式存储在从节点上。（4）将所有本地索引的元数据信息组织起来存储到主节点的内存中。
那么，SpatialHadoop中全局索引和本地索引具体是如何建立的呢？建立索引大致可分为3个部分，分片、建立本地索引和建立全局索引，下面首先来介绍一下SpatialHadoop提供的分片技术，它是建立索引的必要技术。
4.2 空间分片
空间分片类似于Hadoop的分块策略，需要分片的原因在于一个数据块不能满足存储所有空间数据的需求，另外，并行计算也需要为数据集进行必要的分割。空间数据的分片策略不同于文件，分片的基础是空间的区域性质。如何高效地将空间数据以区域的形式分割成设定标准的块的大小，并在分片后快速建立空间索引，是选择不同分片策略的依据。空间分片是空间索引过程中的第一步，所以分片的策略影响着后期索引的建立，并且对后期数据的访问效率有着重要的影响。
目前，SpatialHadoop提供的空间索引包括网格，R树，R+数，四叉树，STR，STR+，K-D树，Z曲线和希尔伯特曲线索引[6]。
4.3 建立空间索引
通过MapReduce工作建立索引将经历了3个阶段，即分区、本地索引和全局索引[1-2]。
（1）在分区阶段，一个文件将被按照空间分布情况进行分区。邻近的对象将尽量被存储在一起，也就是说一个分区中的对象不存在空间隔断的现象。
确定分片数n：
确定n的大小依赖于以下公式[6]：
其中，S为空间数据集的大小，B为HDFS设置的存储文件块的大小，α是开销比（默认值为0.2），即重复记录和本地索引所占用的开销。
确定分区的边界，每个单独的分区都将有一个矩形作为它的边界。由于普遍存在数据集空间分布不均匀的情况，计算出来的边界的大小大多数是不一样的。输出的结果将以n个矩形代替n个分区。
（2）分区，利用第二步确定的n个矩形初始化MapReduce的工作任务来对输入的数据集进行实际分区，map程序结束后每条记录（记作r）都会被划分到一个确定的分片（记作p）中，这将生成一系列的
为了防止分区太大而不能用一个块完全存储，可以将分区分割成每个达到64 M大小的小块。同时，对于不能达到64 M大小的块将通过添加冗余数据而保证每个块都具有相同的大小[1-4]。
本地索引是通过Reduce函数来实现的，它将每个分片都用每行一条记录的形式存储起来作为分区中对象的索引。本地索引文件被组织为块（64 M）的大小，以便进行空间操作时能够将每一个本地索引文件用一个map工作任务来处理[2-3，6]。
添加全局索引的目的是为了对所有分区进行索引，一旦分区任务结束，SpatialHadoop将初始HDFS的concat命令，将所有的本地索引关联成一个文件[6]。
主节点将在内存中开辟一块空间存储这个文件，这就是SpatialHadoop的全局索引文件[3-4]。
4.4 获取空间索引
全局索引的所有信息都存储在主节点的内存中。可以调用Spatialhadoop的API检索全局索引[1-2]。
5 空间操作的扩展
空间操作可以通过常规的MapReduce程序来实现，相比本地的空间操作，SpatialHadoop的空间操作的输入是空间数据的空间索引而不是空间数据本身，当然，SpatialHadoop中的空间索引也和传统的空间索引有所区别，SpatialHadoop的本地局部空间索引中包含了空间数据的实体信息。另外，相较于常规的MapReduce函数，SpatialHadoop允许在map和reduce过程中实现过滤函数[1-4]，过滤函数可以对计算的内容进行筛选，这样可以尽可能地减少job的map任务数量。
空间数据的价值往往隐藏在数据之中，所以有空间数据就少不了空间数据的分析，为此SpatialHadoop提供了3种基本空间操作[1-4]，同时还集成了计算几何操作算法库CG_Hadoop[4，7]。在提供了这些基本的空间操作之后，实现空间分析就简单得多了。为了方便展示空间大数据，SpatialHadoop还提供了可视化的操作。当然，因为SpatialHadoop的出发点是不带属性的纯坐标形式的空间数据，所以这些空间操作功能还需要一些必要的扩展和改进。
SpatialHadoop在众多空间操作中选择实现了3种基本空间操作，分别是范围查询、最邻近查询和连接操作[1-4]。CG_Hadoop是一套基于MapReduce的计算几何操作算法库，目前，它包含了5种基本的计算几何操作，分别是合并多边形、凸包、轮廓线、最远点对和最近点对[7]。但是，实际上的空间操作是离不开属性信息的，而这3种操作都是基于纯坐标文本数据的，这并不能满足我们的需求，为此，必须在原有的基础上做属性支持上的扩展。
在前面的章節中，我们已经对数据类型做了扩展并关联上了属性信息，那么，这样就比较简单了，对于涉及属性上的操作，只需要在属性表中进行相关操作，之后再通过ID映射到实体信息上即可。
空间数据的可视化对其应用具有重要的意义，纯粹的数字对大多数人来说是没有意义的，只有将分析的结果以图形的形式展示出来，才能极大地发挥空间数据的作用和价值。传统的可视化技术依赖单一的机器来加载和处理数据的可视化，这种模式将无法处理大数据中的空间数据。
因此，SpatialHadoop提供了一套高效的可视化工具，尤其在空间数据量达到一定程度而我们又想通过图像的形式展示出来时候，这些工具将会格外有用。
SpatialHadoop支持两种类型的图像，即单级和多级图像。所谓单级图像就是一张具有确定分辨率的图像或者说一张图片。在单级图像可视化中，输入数据集被可视化为一个用户指定像素大小的单一的图像。一个单级图像的质量具有有限的分辨率，这意味着用户不能放大看到更多的细节。因此，SpatialHadoop还支持多级图像，由不同缩放级别的瓦片组成。一个多级图像是由在不同缩放级别的许多瓦片小图像组成，而每个小图像将展示不同的区域。这允许用户缩放或平移图像从而看到具体区域的更多细节。
自然而然地，这一套可视化工具也没有考虑到属性信息的可视化问题，由于实体信息和属性是通过ID直接关联的，因此，在制图时直接将属性信息一并显示在地图上就可以了。
6 结语
SpatialHadoop从存储、MapReduce框架、操作以及开发语言4个方面对Hadoop做了一个全方位的扩展，从而使得SpatialHadoop对于空间数据具有较强的亲和力，显著地增强了处理空间数据的能力。
但是在实际应用中其存在的问题也尤为明显，它不支持属性数据，同时也没有线性数据类型。为此，需要对其进行二次扩展，关联属性信息，采用了HBase存储关联的属性表，并且为空间对象添加了唯一的標识。这不仅解决了属性关联的问题，同时也解决了在建立空间索引时空间对象位序错乱的问题。另外由于HBase存在时间戳的关系也在一定程度上建立了时间维度的信息。为了解决复杂的空间操作的问题，我们也需要对现有的空间操作做一些必要的扩展，目的是为了支持需要处理空间属性的空间操作。
[参考文献]
[1]ELDAWY A，MOKBEL M F.A demonstration of SpatialHadoop：an efficient mapreduce framework for spatial data[J].Proceedings of the Vldb Endowment，2013（12）：1230-1233.
[2]ELDAWY A，MOKBEL M F.The ecosystem of SpatialHadoop[J].Sigspatial Special，2015（3）：3-10.
[3]ELDAWY A，MOKBEL M F.SpatialHadoop：a MapReduce framework for spatial data[C].Seoul：IEEE International Conference on Data Engineering，2015：1352-1363.
[4]ELDAWY A.SpatialHadoop：towards flexible and scalable spatial processing using mapreduce[C].Zeyna：ACM SIGMOD Phd Symposium，2014：46-50.
[5]ELDAWY A，MOKBEL M F.Pigeon：A spatial MapReduce language[C].Chicago：IEEE International Conference on Data Engineering，2014：1242-1245.
[6]ELDAWY A，ALARABI L，MOKBEL M F.Spatial partitioning techniques in SpatialHadoop[J].Proceedings of the Vldb Endowment，2015（12）：1602-1605.
[7]ELDAWYA，LI Y，MOKBEL M F，et al.CG_Hadoop：computational geometry in MapReduce[C].Orlando：ACM Sigspatial International Conference on Advances in Geographic Information Systems，2013：294-303.
[8]SpatialHadoop.Analyze your spatial data efficiently[EB/OL].（2017-12-13）[2018-01-16].http：//spatialhadoop.cs.umn.edu/.
[9]百度文库.shp文件详细格式[EB/OL].（2014-06-23）[2018-01-16].https：//wenku.baidu.com/view/e0bb64702f60ddccdb38a038.html.
