基于“分治网格”的空间大数据快速分析方法贾文珏１，安　琼２（１．国土资源部信息中心，北京１００８１２；２．中国农业大学信息与电气工程学院，北京１０００８３）摘　要：为解决复杂空间数据快速处理分析的空间大数据开发利用难点问题，提出基于“分治网格”的空间大数据快速分析思路和技术框架。初步实现原型系统，基于原型系统，以土地利用变更调查数据叠加分析为实例，对关键技术进行验证。实例验证结果表明，利用该技术路线和框架，可以提升海量空间数据的处理分析速度。关键词：空间数据；大数据；快速分析；集群化；分治网格中图法分类号：ＴＰ３１１　文献标识号：Ａ 　文章编号：１０００－７０２４ （２０１５）０８－２３１７－０５ｄｏｉ：１０．１６２０８／ｊ．ｉｓｓｎ１０００－７０２４．２０１５．０８．０６０收稿日期：２０１４－０８－１１；修订日期：２０１４－１０－１５基金项目：国土资源部国土资源战略研究重点实验室开放课题基金项目（ＫＦＳ２０１３０９）作者简介：贾文珏（１９７６－），女，河北邢台人，博士，副研究员，研究方向为国土资源信息化、地理信息系统研究与应用；安琼（１９８０－），女，山西晋中人，博士，研究方向为农情遥感监测、地理信息系统应用等。Ｅ－ｍａｉｌ：ｊｉａｗｅｎｊｕｅ＠１６３．ｃｏｍＦａｓｔ　ｍｅｔｈｏｄ　ｆｏｒ　ａｎａｌｙｓｉｓ　ｏｆ　ｂｉｇ　ｓｐａｔｉａｌ　ｄａｔａ　ｕｓｉｎｇ　ｄｉｖｉｄｅ　ａｎｄ　ｃｏｎｑｕｅｒ　ｇｒｉｄｓＪＩＡ　Ｗｅｎ－ｊｕｅ１，ＡＮ　Ｑｉｏｎｇ２（１．Ｉｎｆｏｒｍａｔｉｏｎ　Ｃｅｎｔｅｒ　ｏｆ　Ｍｉｎｉｓｔｒｙ　ｏｆ　Ｌａｎｄ　ａｎｄ　Ｒｅｓｏｕｒｃｅｓ　ｏｆ　Ｐｅｏｐｌｅ’ｓ　Ｒｅｐｕｂｌｉｃ　ｏｆ　Ｃｈｉｎａ，Ｂｅｉｊｉｎｇ　１００８１２，Ｃｈｉｎａ；２．Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｅｌｅｃｔｒｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｈｉｎａ　Ａｇｒｉｃｕｌｔｕｒａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００８３，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｄｉｆｆｉｃｕｌｔｉｅｓ　ｏｆ　ｅｆｆｅｃｔｉｖｅｌｙ　ｐｒｏｃｅｓｓｉｎｇ　ａｎｄ　ａｎａｌｙｚｉｎｇ　ｃｏｍｐｌｅｘ　ｄａｔａ　ｉｎ　ｓｐａｔｉａｌ　ｄａｔａ　ｕｔｉｌｉｚａｔｉｏｎ，ａｎ　ｉｄｅａ　ｏｆ　ｄｉｖｉｄｅａｎｄ　ｃｏｎｑｕｅｒ　ｇｒｉｄｓ　ｗａｓ　ｉｎｔｒｏｄｕｃｅｄ　ａｎｄ　ａ　ｇｅｎｅｒａｌ　ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ｆａｓｔ　ｂｉｇ　ｓｐａｔｉａｌ　ｄａｔａ　ｐｒｏｃｅｓｓｉｎｇ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ａ　ｐｒｏｔｏｔｙｐｅ　ｓｙｓｔｅｍｗａｓ　ｒｅａｌｉｚｅｄ，ａｎｄ　ｔｈｅ　ｆｅａｓｉｂｉｌｉｔｙ　ａｎｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ｋｅｙ　ｔｅｃｈｎｉｑｕｅｓ　ｗｅｒｅ　ｖｅｒｉｆｉｅｄ　ｔｈｒｏｕｇｈ　ａ　ｒｅａｌ－ｗｏｒｌｄ　ｌａｎｄ　ｕｓｅ　ｃｈａｎｇｅ　ａｎａｌｙｓｉｓ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｆｒａｍｅｗｏｒｋ　ａｎｄ　ｔｅｃｈｎｉｑｕｅｓ　ｃａｎ　ｇｒｅａｔｌｙ　ｒｅｄｕｃｅ　ｔｈｅ　ａｎａｌｙｓｉｓ　ｔｉｍｅ．Ｋｅｙ　ｗｏｒｄｓ：ｓｐａｔｉａｌ　ｄａｔａ；ｂｉｇ　ｄａｔａ；ｆａｓｔ　ａｎａｌｙｓｉｓ；ｃｌｕｓｔｅｒｉｎｇ；ｄｉｖｉｄｅ　ａｎｄ　ｃｏｎｑｕｅｒ　ｇｒｉｄ０　引　言如何能够实现ＴＢ级空间数据的快速分析，是当前海量空间数据分析面临的重要问题［１－３］。学术界对大数据的管理和分析已经进行了深入研究，企业界也提出和研发了各类创新技术。如Ｇｏｏｇｌｅ针对文件类大数据应用需求，设计开发了ＧＦＳ （Ｇｏｏｇｌｅ　ｆｉｌｅ　ｓｙｓｔｅｍ）［４］分布式文件系统和Ｂｉｇｔａｂｌｅ［５］数据库，提出了Ｄｒｅｍｅｌ［６］计算模型；微软提出了Ｄｒｙａｄ［７］的数据处理模型，用来构建支持有向无环图类型数据流的并行程序；Ｆａｃｅｂｏｏｋ针对海量小文件的文件系统，推出了Ｈａｙｓｔａｃｋ［８］，通过多个逻辑文件共享同一个物理文件、增加缓存层、部分元数据加载到内存等方式有效地实现了海量图片的存储；Ａｍａｚｏｎ针对大数据时代的数据存储，推出了Ｄｙｎａｍｏ［９］，通过综合键／值存储、改进的分布式哈希表、向量时钟等技术实现了一个完全分布式、去中心化的高可用系统；开源界提出了类似Ｇｏｏｇｌｅ的Ｈａｄｏｏｐ［１０］技术框架体系，并在各个行业得到广泛应用。虽然目前已经形成了大量的大数据存储、管理和分析技术，但是这些技术大多数是针对文本数据、属性数据、图像图形数据的，在空间大数据的处理方面往往不能够直接应用。本文从空间数据的特点出发，结合空间数据分析的具体需求，提出基于“分治网格”的空间大数据并行快速分析思路，并基于此思路搭建了基于Ｈａｄｏｏｐ框架的分析原型系统，对关键技术进行验证，验证结果表明，利用该技术路线可以极大提升空间大数据的处理分析速度。１　基于“分治网格”的并行分析技术框架１．１　总体思路考虑空间数据海量，多图层叠加分析计算需求普遍，传统的单机计算模式难以满足时效性要求的情况，本文提出基于“分而治之”理念的空间数据并行化分析技术。其核心是按照一定的规则，将不同空间图层数据划分为不同的分治网格区域。在此基础上，利用集群处理技术，对需要进行分析的空间图层，按照各个分治网格进行分配调度，　计算机工程与设计２０１５年利用多台计算资源进行并行计算，之后进行汇总，形成统一的结果，实现分析速度的大幅度提升，总体思路如图１所示。图１　基于“分治网格”的集群空间计算流程１．２　分治网格划分在网格划分方面，一般来说，网格划分的越小，可以并行计算的基本单元也越小，可以并行的程度也越高。但同时，网格越少，网格数量就越大，继而导致整体数据存储量和前期切分工作量的大幅上升。在实际工作中，一般来说，对于局部范围的分析，可以采用较小的网格，对于大面积的分析，可以采用较大的网格。为方便分析，可以将网格划分为正方形格式。为方便不同比例尺网格的聚合和汇总，可以将网格体系设计为多级体系，上一级的网格可以由下一级别网格聚合而成。网格的划分可以根据不同的需求进行定制，比如采用平面坐标形式，可以基于公里网格进行向下拆分和向上聚合，见表１。表１　基于平面坐标的多级分治网格划分级别大小描述１　１００ｋｍ＊１００ｋｍ 全国１２００个网格２　１０ｋｍ＊１０ｋｍ 全国１２万个网格３　１ｋｍ＊１ｋｍ 全国１２００万个网格４　１００ｍ＊１００ｍ 全国１２亿个网格５　１０ｍ＊１０ｍ 全国１２００亿个网格分治网格划分也可以结合计算机中二进制计算特点，采用四分方式，下级网格面积为上级网格面积的１／４，方便多级网格的定位。１．３　网格大小选取网格划分后，在并行计算时，首先需要确定分治网格的大小。分治网格的大小直接影响着并行计算的性能。如果将全国划分为一个网格，则无法并行，计算模式退回为单机运行模式；如果网格划分到像素级别，则并行程度可以极大提升，但是计算任务数量又过大，导致运行额外开销增高。根据集群计算的特点，一般可以考虑按照一个分治网格内的要素数量进行网格大小的选取。如根据计算机性能，如果总要素数量为３００百万，有１０个并行处理节点，则平均每个节点需要处理３０万个要素分析。另外一种方式就是划分为１０个左右的网格，每个任务负责一个网格的处理。但这种方式中，如果某一网格运算量较少，任务结束后就会造成资源的浪费。因此应该适当加大网格数量，如可以让每个节点每次处理１万个左右的要素，也就是网格数量大约在３００个左右。这种模式下，１０个节点并行进行３００左右的并行任务。总体上看，网格大小的选取是一个和数据特点密切相关的工作，在具体工作中可以根据实际情况进行动态的优化。１．４　空间数据的预处理由于很多空间数据当前往往采用数据库形式存储，但是如果直接在集群环境下由各个任务读取数据库数据并进行分析，会导致数据库成为整个分析的瓶颈。因此有必要对数据库中的数据进行处理。预处理工作包括基于分治网格的图层分格、分格图层的分区存储、分格图层的索引建立等多个工作。分格主要是将网格和图层进行空间叠加，将原图层拆分为每个网格一个图层的格式。分区存储是指将分格后的图层进行格式转换，导入到分布式的分区行式或者列式存储系统中。索引建立是指在分区存储的基础上，利用空间四分树及其它索引方式，建立空间数据的索引，提升后续分析效率。１．５　集群式空间计算方式为应对海量数据的处理计算能力的需求，可以采用集群化计算技术，将不同图层和网格的叠加分析任务并行化，利用多个节点的计算能力并行处理，解决计算能力不足。在集群化处理方面，可以采用当前大数据技术体系中的Ｍａｐ　Ｒｅｄｕｃｅ计算模式，即：将大的计算任务分解为小的三类任务，总体分解任务、单个执行任务、数据汇总任务。总体分解任务负责将大的任务计算的环境、数据进行拆解分发，具体任务可以在多个节点上进行执行，数据汇总任务负责将各个子任务的数据进行汇总形成最终结果，并进行其它的清理工作。通过此类Ｍａｐ　Ｒｅｄｕｃｅ计算方式的应用，可以突破以往单机计算能力不足的缺陷。２　初步实现及性能评价２．１　初步实现基于上述框架，本文搭建了原型系统，对本文提出的关键技术进行验证。原型系统总体结构和采用的具体技术如图２所示。·２３１８·第３６卷　第８期　　贾文珏，安琼：基于“分治网格”的空间大数据快速分析方法　图２　原型系统技术架构　　通过数据抽取工具，将两年空间土地利用变更调查Ｓｈａｐｅｆｉｌｅ文件数据导入的Ｏｒａｃｌｅ空间数据库中，之后利用数据转换工具，将关系数据库表数据转换为ＣＳＶ文件，并将文件存储到ＨＤＦＳ分布式文件系统之中。之后基于ＥＳＲＩＧｉｓＴｏｏｌ　ｆｏｒ　Ｈａｄｏｏｐ，开发基于格网的并行空间数据叠加分析工具，分析结果通过并行程序存储到结果数据库，供其它分析引擎和显示引擎进行分析和展示。２．２　性能评价２．２．１　空间叠加运行时间比较本研究中选取某试点区域两年的土地利用变更调查数据样本数据。每年的利用变更调查数据包含约７０万图斑数据。原始Ｓｈａｐｅ矢量数据每个约３２４ＭＢ，转换为ＣＳＶ文件后每个文件大小约７４０ＭＢ。本研究中，基于Ｈａｄｏｏｐ搭建１个主节点、３个数据节点的Ｈａｄｏｏｐ集群环境，选取缺省的ＨＤＦＳ文件块大小为６４ＭＢ。每个数据节点配置１颗４核ＣＰＵ、８Ｇ内存、１ＴＢ硬盘和千兆网卡。在分析中，选取１０公里网格作为分析单元。在设计Ｍａｐ　Ｒｅｄｕｃｅ程序实例中，两年土地利用空间数据按照所相交１０公里网格进行分配，凡是与同一网格相交的图斑，所相交部分统一被分发至某一Ｒｅｄｕｃｅｒ任务进行叠加计算。本研究中，分别在单机环境、２个数据节点和３个计算节点环境下（１２个Ｍａｐｐｅｒ任务和２４个Ｒｅｄｕｃｅｒ任务），对上述土地利用数据进行分析，运行时间比较如图３所示。通过分析，可以看出利用ＡｒｃＧＩＳ１０．０，对两年土地利用图斑数据进行空间相交分析（Ｊｏｉｎ），在单台ＰＣ计算机，１颗４核主频３．１ＧＨＺ　ＣＰＵ，８ＧＢ内存，１ＴＢ　ＳＡＴＡ　７．２Ｋｒｐｍ硬盘，Ｗｉｎｄｏｗｓ　７　６４位环境下，运行时间约１５ｍｉｎ，运行期间ＣＰＵ 使用率最高约７６％，内存使用率约３０％。图３　不同环境下土地利用变更数据叠加分析时间比较利用Ｈａｄｏｏｐ的Ｍａｐ　Ｒｅｄｕｃｅ技术，在单机（单节点－伪分布式）环境下，完成同样分析，需要时间约为３５ｍｉｎ。可见，Ｈａｄｏｏｐ在单机环境下（伪分布式环境，ｎａｍｅｎｏｄｅ和ｄａｔａｎｏｄｅ均在该改服务器上）的性能比传统的ＡｒｃＧＩＳ分析更慢。这主要是由于Ｈａｄｏｏｐ的Ｍａｐ　Ｒｅｄｕｃｅ技术主要是利用并行来实现效率的提升，但为实现并行，本身引入一定的额外处理负担，导致单机环境性能明显低于传统技术方式。当将分析程序在２个数据节点的环境下时，可以实现性能的提升，Ｈａｄｏｏｐ双节点环境下，同样的分析任务可以在９ｍｉｎ左右完成，性能超过单机环境下的ＡｒｃＧＩＳ。这主要是由于两个节点上，通过Ｍａｐ　Ｒｅｄｕｃｅ，生成了１２个Ｒｅｄｕｃｅｒ任务，这１２个Ｒｅｄｕｃｅｒ任务被分配到两台数据节点的８个ＣＰＵ内核上进行预算，实现了同时多个任务并行计算，从而缩减了运行时间。继而，将任务提交到３个数据节点，启用２４个Ｒｅｄｕｃｅｒ后，运行任务可以在５ｍｉｎ左右完成，单机运行时间缩短为ＡｒｃＧＩＳ的１／３。由此可见，利用Ｈａｄｏｏｐ的并行处理，可以将大空间图层的分析效率大幅提升，·２３１９·　计算机工程与设计２０１５年满足海量数据的分析需求。２．２．２　网格划分对运行时间的影响分析在实际分析中，网格大小划分同运行时间有直接的关系。一般来说，网格数量的多少应根据计算集群的节点数量进行。图４显示了在３个Ｈａｄｏｏｐ集群节点、１２个Ｍａｐｐｅｒ任务、２４个Ｒｅｄｕｃｅｒ任务配置下，不同网格大小划分对应的土地利用图层数据相交操作所需的时间。不同大小的网格数量见表２。图４　不同环境下土地利用变更数据叠加分析时间比较表２　不同大小的网格数量级别网格大小网格数量１　３０ｋｍ＊３０ｋｍ　３６２　２５ｋｍ＊２５ｋｍ　６４３　１０ｍ＊１０ｋｍ　３２４４　５ｋｍ＊５ｋｍ　１２９６５　１ｋｍ＊１ｋｍ　３２０００由图４可以看出，网格数量和运行时间不是简单的线性关系。当网格是１０公里网格时，运行时间最小。更小的网格划分时，运行时间有所延长，但延长量不大。当网格划分更大时，运行时间也会延长，而且延长量较大。这主要是由于网格主要是用于拆分数据，使得同一网格内的要素可以独立进行处理。正常情况下，当网格数量低于Ｒｅｄｕｃｅｒ任务数量时，会造成部分Ｒｅｄｕｃｅｒ任务没有需要处理的数据，导致资源浪费。当网格数量高于Ｒｅｄｕｃｅｒ任务时，每个网格由一个独立的Ｒｅｄｕｃｅｒ任务对其进行处理。为了保障网格数量高于Ｒｅｄｕｃｅｒ任务数量时的Ｒｅｄｕｃｅｒ任务处理量相对均衡，一般可以考虑网格数量是Ｒｅｄｕｃｅｒ任务的整数倍数。同时，由于网格内的要素数量不同，为了避免一个Ｒｅｄｕｃｅｒ任务处理的网格数量相同，但网格内要素量差别较大的问题，可以使用随机算法分配网格到不同的Ｒｅｄｕｃｅｒ任务上，并且使网格数量级是Ｒｅｄｕｃｅｒ任务数量的１０倍左右，这样统计上看，负载不平衡程度可以控制在１０％以下。同时，网格也不应该太小，过小的网格会导致按网格数据分发任务到Ｒｅｄｕｃｅｒ任务时排序工作量加大，导致系统运行时间加长。一般来说，每个网格内的要素数量最好高于１万，但低于１０万，这样Ｒｅｄｕｃｅｒ任务可以利用内存空间索引技术，快速进行空间叠加操作。２．２．３　Ｍａｐｐｅｒ任务数量对运行时间的影响在Ｈａｄｏｏｐ环境中，Ｍａｐｐｅｒ和Ｒｅｄｕｃｅｒ任务数量对于任务的执行时间有直接影响。本研究中，Ｍａｐｐｅｒ任务主要负责将原始数据按照网格范围，分发到不同的Ｒｅｄｕｃｅｒ任务上；Ｒｅｄｕｃｅｒ任务主要负责将某一网格内的两年的土地利用图斑进行叠加计算。图５显示了在３个数据节点、固定Ｒｅｄｕｃｅｒ为２４的情况下，不同数量的Ｍａｐｐｅｒ任务对运行时间的影响。图５　不同数量的Ｍａｐｐｅｒ任务对运行时间的影响／ｓ由于本研究中选取的文件块大小为６４ＭＢ，输入文件为７４０ＭＢ左右，每个文件大约被拆分为１２个大小为６４ＭＢ的文件块。对于没有文件块，Ｈａｄｏｏｐ缺省启用至少１个Ｍａｐｐｅｒ任务。缺省的１２个Ｍａｐｐｅｒ任务下（２４个Ｒｅｄｕｃｅｒ），系统运行时间为３１１ｓ。实验中也可以增加Ｍａｐｐｅｒ数量，为每一个文件块配置２个Ｍａｐｐｅｒ任务，总Ｍａｐｐｅｒ任务为２４个时，系统运行时间为４３５ｓ。通过以上分析，可以看出，Ｍａｐｐｅｒ任务数量对系统运行性能影响不大。这主要是由于Ｍａｐｐｅｒ任务负责读取输入的数据文件，并将数据文件进行分发。分发阶段的主要时间消耗为文件读取和网络通信，计算量小，加大Ｍａｐｐｅｒ数量并不会减少文件读取的网络时间，反而会加大Ｍａｐｐｅｒ的管理负担，延长系统运行时间。因此，在实际图层叠加工作中，可以考虑按照文件块数量，每个文件块配置一个Ｍａｐｐｅｒ任务，这个也是Ｈａｄｏｏｐ中的缺省配置。２．２．４　Ｒｅｄｕｃｅｒ任务数量对运行时间的影响图６显示了在３个节点，１２个Ｍａｐｐｅｒ任务的情况下，不同数量的Ｒｅｄｕｃｅｒ任务对运行时间的影响。图６　不同数量的Ｒｅｄｕｃｅｒ任务对运行时间的影响／ｓ从图６可以看出，Ｒｅｄｕｃｅｒ任务的数量直接影响运行时·２３２０·间。当使用１个Ｒｅｄｕｃｅｒ任务的时候，网格内的叠加分析均由该Ｒｅｄｕｃｅｒ任务完成。而一个Ｒｅｄｕｃｅｒ任务只能运行在一台数据节点，且无法完全利用多核计算资源，导致运行时间较长。当Ｒｅｄｕｃｅｒ任务数量增加时，多个Ｒｅｄｕｃｅｒ任务可以同时在多台数据节点上运行，达到并行处理效果，缩短运算时间。由上图可以看出，Ｒｅｄｕｃｅｒ任务为３时，运行时间缩短为１０ｍｉｎ左右。随着Ｒｅｄｕｃｅｒ任务数量的增加，并行程度加大，运行时间缩短。当Ｒｅｄｕｃｅｒ任务达到２４时，运行时间降为约５ｍｉｎ。这时的ＣＰＵ 利用率基本达到饱和。如果进一步加大Ｒｅｄｕｃｅｒ任务数量，发现处理时间反而延长，在Ｒｅｄｕｃｅｒ任务数量为４８个时，运行时间变为６ｍｉｎ左右，这主要是由于ＣＰＵ 利用饱和情况下，继续增加Ｒｅｄｕｃｅｒ任务数量，加大了任务分发管理和额外负担，反而导致性能下降。一般来说，Ｒｅｄｕｃｅｒ任务的数量配置应该结合ＣＰＵ数量和处理能力进行，要保证ＣＰＵ 利用率相对饱和的情况下，减少Ｒｅｄｕｃｅｒ任务数量。对于空间数据分析，缺省可以考虑１核ＣＰＵ对应２个Ｒｅｄｕｃｅｒ任务。３　结束语传统的空间数据分析技术非常成熟，对中小量空间数据分析较为实用，但是对空间大数据在数据存储、计算方式、分析技术方面尚存在不足。针对这些问题，本文提出了基于“分治网格”的空间大数据快速分析思路和技术框架，初步实现了原型系统，并基于原型系统以土地利用变更调查数据叠加分析为实例，对关键技术进行了验证。实例验证结果表明，利用本研究提出的技术路线和框架，可以极大提升海量空间数据的处理分析速度。本研究提出的基于“分治网格”理念和空间大数据分析技术对海量空间数据的开发利用有着积极意义。