201316

Size: px

Start display at page:

Download "201316"

某贺
7 years ago
Views:

1 Computer Engineering and Applications 计算机工程与应用 2013,49(16) 25 基于开源 Hadoop 的矢量空间数据分布式处理研究尹芳 1, 冯敏 2, 诸云强 2 3, 刘睿 YIN Fang 1, FENG Min 2, ZHU Yunqiang 2, LIU Rui 3 1. 长安大学地球科学与资源学院, 西安中国科学院地理科学与资源研究所, 北京重庆师范大学地理科学学院, 重庆 College of Earth Science and Resources,Chang an University,Xi an ,China 2.Institute of Geographic Sciences and Natural Resources Research,Chinese Academy of Sciences,Beijing ,China 3.College of Geographical Science,Chongqing Normal University,Chongqing ,China YIN Fang, FENG Min, ZHU Yunqiang, et al. Research on vector spatial data distributed computing using Hadoop projects. Computer Engineering and Applications, 2013, 49(16): Abstract:The paper designs a vector spatial data distributed computing system based on Open Source Hadoop Projects, in order to satisfy the needs of massive vector data. According to the characteristics of the vector spatial data, Key/Value data model and GeoJSON data format, the paper brings forward a distributed Key/Value storage method for vector spatial data based on HDFS. The key techniques on how to computing large-scale vector spatial data based on MapReduce are elaborated in detail, including data partitioning and parallel processing mechanism of Map step, results merging of Reduce step. A vector spatial data distributed computing prototype system is developed using Open Source Hadoop projects and applied to deal with the 1 100, 000 land use data of Guanzhong area in China. The evaluation result indicates that the Hadoop MapReduce can significantly leverage the performance of vector spatial data analysis, especially when more computing nodes are used. Key words:vector spatial data; Key/Value; GeoJSON; Apache Hadoop; MapReduce; distributed computing 摘要 : 为实现大规模矢量数据的高性能处理, 在开源项目 Hadoop 基础上, 设计与开发了一个基于 MapReduce 的矢量数据分布式计算系统根据矢量空间数据的特点, 通过分析 Key/Value 数据模型及 GeoJSON 地理数据编码格式, 构建了可存储于 Hadoop hdfs 的矢量数据 Key/Value 文本文件格式 ; 探讨矢量数据的 MapReduce 计算过程, 对 Map 数据分片并行处理过程及 Reduce 结果合并等关键步骤进行了详细阐述 ; 基于上述技术, 建立了矢量数据分布式计算原型系统, 详细介绍系统组成, 并将其应用于处理关中地区 1 10 万土地利用矢量空间数据, 取得较好效果关键词 : 矢量空间数据 ;Key/Value;GeoJSON;Apache Hadoop;MapReduce; 分布式处理文献标志码 :A 中图分类号 :TP391 doi: /j.issn 引言随着 GIS 在交通运输灾害预测资源调查等领域的应用, 矢量空间数据量和计算机处理运算量快速增加, 依靠单机系统的数据存储处理方式已经难以满足现代应用的需求面对海量和复杂的矢量空间数据, 如何对其进行高 [1] 效存储管理与处理, 成为地学领域的重要研究内容云计算为解决海量数据处理提出了 MapReduce 分布式计算模式开源项目 Hadoop 的出现, 促进了 MapReduce 的快速发展国外很多学者尝试利用 Hadoop 对 MapReduce 的运行效率应用前景进行研究 : 王永刚对 Hadoop 云计算平台下地理信息服务的若干关键技术进行了研究 [1] ;Yang [2] H 等对 MapReduce 进行扩展, 提出 Map-Reduce-Merge 计算过程, 用于处理关系数据 ;Zhang Wang 等针对空间数据集在 MapReduce 上的连接 ANN 查询操作进行了详细讨论 [3-4] ; 范建永对 HBase 如何存储矢量空间数据进行了探讨 [5] 基于上述研究, 结合开源 Hadoop 项目, 探讨一种适用基金项目 : 国家自然科学基金 (No ); 中国科学院地理科学与资源研究所一三五战略科技计划项目 (No.2012ZD010) 作者简介 : 尹芳 (1983 ), 女, 博士生, 主要研究方向为地理信息服务及分布式处理 ; 冯敏 (1981 ), 男, 助理研究员, 博士, 主要研究方向为地理信息服务和地学模型共享 ; 诸云强 (1977 ), 男, 副研究员, 博士, 主要研究方向为地理信息系统开发与应用, 地学数据共享关键技术研究, 地学信息化科研环境 (e-geoscience) 理论体系与关键技术研究 ; 刘睿 (1983 ), 男, 副教授, 博士, 主要研究方向为地理信息系统应用及资源环境遥感 liur@lreis.ac.cn 收稿日期 : 修回日期 : 文章编号 : (2013)

College of Earth Science and Resources,Chang an University,Xi an 710054,China 2.Institute of Geographic Sciences and Natural Resources Research,Chinese Academy of Sciences,Beijing 100101,China 3.

2 ,49(16) Computer Engineering and Applications 计算机工程与应用于空间矢量数据的分布式处理方案分析适用于 Hadoop hdfs 存储的 Key/Value 数据模型及 MapReduce 计算模式的特点, 探讨矢量数据 hdfs 分布式存储组织策略 MapReduce 分布式计算流程等关键环节, 基于 Apache Hadoop 构建分布式矢量数据处理原型系统, 最后以关中地区 1 10 万土地利用数据为例开展应用实践 2 矢量数据分布式存储组织策略 2.1 Key/Value 数据模型分析关系模型是目前较为常见的数据模型之一, 但实际上从集合理论来讲, 关系可以被看成为高度和基数都等于 1 的 Key/Value 集合在关系模型中, 关系 R 可以表示成 R =< R r > 其中, R 表示关系模式,r 代表关系模式实例关系模式实例指由行 ( 也称为元组 ) 和列 ( 也称为属性 ) 组成的表关系模式可以表示为一个无序元组 < c1:d1 c2:d2 cn:dn >, 其中 < c1 c2 cn > 代表列名,< d1 d2 dn > 代表域名, 相应的列值必须属于指定的域集合 C 可以表示为 :C = < C c > 其中,C 表示集合模式 ;c 代表集合实例集合模式可以表示为 C = < K V > 其中,K 指 key 关键字, 比方说在 k:d 数值对中,k 表示 key 名字,d 表示域名 ;V 表示实际 value 值, 代表一个关系模式或是集合模式因此, 面向集合的数据模型可以表示为 C=<k1:d1,k2: d2kn:dn,r>; 集合实例 c 可以表示成一组 ( pi qi)(i Î{1 2 m}) 键值对的集合,m 为集合的基数,qi 代表一个关系实例或集合实例,pi 数据域表示为 dom(pi)= String Integer Double Boolean 集合实例 c 符合 C=<k:d, V> 模式, 表示为 :c =C 当且仅当 ( pi qi)(i Î{1 2 m})î c, dom( pi) = d pi = V 需要强调的是当 c =C 时, 集合实例 c 才是有效的假设一组模型实验参数数据集合 ( 图 1), 可表示为 Cparams=<Model:String,:Integer,<: m1 m2 m3 Model 图 1 实验参数数据集合 Double,:Integer>>, 其中 H(Cparams)=2, 第一级包含关键字为 Model 的键值, 属于字符串数值域 ; 第二级别包含关键字为的键值, 属于整型数值域 ; 而所有的内部关系实例满足 <:Double,:Integer> 关系模式可见,Key/Value 可以说是对关系模型的有效扩展所有基于 Key/Value 模型的数据操作, 都可规约到相关集合操作上, 最终规约到关系操作上同时, 也可以将关系运算中的相关操作拓展到集合模型中, 来支撑针对集合数据的相关运算, 如合并 (Union) 连接求差 (difference) 等文中空间数据模型都是基于面向集合的 Key/Value 模型基础理论构建的 2.2 矢量数据 Key/Value 数据模型构建在当前 NOSQL 数据库中, 普通数据采用的 JSON 格 [6] 式, 正是一个无序的名称 / 值对集合例如, 描述人基本信息的 JSON 数据格式如下 :{name:"yinfang",sex:"m", age:"26"} 对于矢量空间数据来讲, 直接采用基于 JSON 格式的 GeoJSON 实现空间几何实体的描述是可行的 GeoJSON 遵循 WKB 规范格式, 目前已能够支持点线多边形等几何形式和几何集合, 以及 Feature 和 Feature 集合的定义 ( 以点 (Point) 为例, 由 x,y 坐标构成, 表示方式如下 : { type : Point, coordinates :[100.0,0.0], properties :{ prop0 : value0, prop1 : valu } } 假定空间数据集 D 包含多个空间对象实体 O i, i = 1 2 D, 利用 GeoJSON 格式描述矢量空间数据几何实体, 形成如下结构的矢量数据文件格式 : 矢量数据文件 ={<O 1.ID,O 1.Geometry,O 1.Attribute><O 2.ID, O 2.Geometry,O 2.Attribute><O n.id,o n.geometry,o n.attribute>}, 其中 :O i.geometry={ type : 实体类型, coordinates :[ 几何实体 WKB 编码 ]};O i.attribute={ properties :{< 属性名, 属性值 > 键值对列表 }} 同时, 每个空间对象实体记录都以文本文件的方式保存为一行这样可以方便地利用 Hadoop 平台提供的基于文本行的文件操作函数, 实现每个空间对象实体记录的读取和写入此外, 对于矢量数据文件, 具体的元数据内容包含空间对象实体个数投影坐标属性数据域等基本信息 2.3 HDFS 矢量数据存储过程通过 HDFS 来存储和管理矢量数据文件, 就是直接将 2.2 节创建的空间对象实体记录文本及元数据文件上传到 HDFS 文件系统,HDFS 将其进行自动切割, 分成大量小的数据块 ( 缺省为 64 MB), 分别存储到不同的节点上

1 Key/Value 数据模型分析关系模型是目前较为常见的数据模型之一, 但实际上从集合理论来讲, 关系可以被看成为高度和基数都等于 1 的 Key/Value 集合在关系模型中, 关系 R 可以表示成 R =< R r > 其中, R 表示关系模式,r 代表

3 尹芳, 冯敏, 诸云强, 等 : 基于开源 Hadoop 的矢量空间数据分布式处理研究 2013,49(16) 27 3 矢量数据 MapReduce 计算处理流程利用 MapReduce 处理矢量数据, 首先要将空间对象实体按照一定的规则进行数据分片, 之后将这些块数据分配到各计算节点, 由各计算节点完成运算后,Reduce 对结果进行合并, 完成数据处理本章将详细介绍分块规则及 Map Reduce 过程的注意环节 3.1 矢量数据 MapReduce 计算流程分析目前, 针对矢量数据 MapReduce 分布式计算的相关研究较少并且, 现有研究基本没有考虑矢量数据的属性特 [7-10] 征然而, 在矢量数据进行处理分析过程中, 属性数据具有重要的作用本章在分析现有矢量数据 MapReduce 计算过程基础上, 对其进行改进, 使之兼顾空间和属性特征矢量数据 MapReduce 处理的过程主要分为三个阶段 : (1) 根据空间对象空间位置特征属性 O.Geometry, 构建划分映射函数 f, 将空间对象划分成 R 个数据分片, 并在不同计算节点上执行数据分片拷贝注意 : 第一阶段要重点确定分割函数 f, 函数输入为数据集 D 与正整数 R,R 代表划分成的分片数量,f 输出结果是将数据集 D 中的空间对象实体划分到 R 个分区中 f 函数最理想的状态是实现数据集 D 平均分配为 R 份但在实际操作中,f 函数将空间位置临近的对象分配到同一个分区内, 各分区间的数据量可以存在一定的微小变化, 保证分组之间数据量的负载均衡 (2) 主控程序分配 M 个 Mapper 和 R 个 Reducer, 通过资源监控机制控制各计算节点执行相应的单元, 利用 Mapper 对各分块数据进行相应空间分析处理, 利用 Reducer 对结果进行过滤合并注意 : 第二阶段在 Map 阶段,Mapper 读取第一阶段的分块数据, 并按照相应的 ( 如查询缓冲区分析等 ) 需求对分块数据进行处理 ; 之后, 利用 Reducer 将相应结果进行过滤归并等处理 (3) 将 R 个独立的 Mapper 分析结果, 发送到某个计算节点或主控节点, 由该节点将所有计算结果组合合并, 获得最终结果一般来讲, 前两个阶段是分布式并行执行的, 最后阶 [7] 段不需要很高的计算能力, 只需按顺序执行即可以下内容对分割函数 f 的建立及 Map 和 Reduce 处理过程进行详细阐述 3.2 矢量数据划分函数构建根据矢量数据的特征, 矢量数据 MapReduce 处理过程中数据划分阶段, 需要重点考虑邻近性和非均匀性特点通过对比分析, 选取 Z 序曲线法根据 O.Geometry 属性建立空间填充曲线, 完成数据的空间区域划分, 得到具有邻近性特征的一维空间实体对象序列基于获取到的空间实体对象, 在主要考虑数据量均匀分布的因素下, 将数据集 D 分布到接近均匀的 R 份则具体构建过程如下 : (1) 每个对象的 id 和空间位置生成 <key/value> 对集合,key 为每个对象的 id 号,value 为每个对象的 Geometry 值通过 Z 序填充曲线计算, 获得每个对象的 Z 序编码值 S ={U (O i i = 1 2 L} 式中,U 为 Z 序填充曲线 (2) 将 S 排序后分配到 R 个大小接近相等的块中当 S[ j - 1]<U (O S[ j] 时, 对象 O 被分配到第 j 块,j = 1 2 R (3) 得到分块函数 f 对数据集 D 进行分割, 定义如下 : ì 1 ï f (o = í j, S[ j - 1]< U (o S[ j], ï îr, U (o > S[R - 1] 1, U (o S[ ] j = 2 3 R Map 与 Reduce 计算流程实现在 Map 计算单元执行过程中, 基于数据划分函数, 可保证如果各节点中共有 M 个 Mapper, 则每个节点分配个对象, 其中数据量范围可控制在 16~64 MB 之间 Map 函数读取到的输入数据内容是包含空间数据 id 空间特征和属性特征的键值对 <O.ID,O.Geometry,O.Attribute>, 使得 Mapper 计算过程可以方便地读取到矢量数据的空间特征属性数据, 完成相关操作的处理在 Reduce 计算单元执行过程中, 主要是在得到空间分析处理中间结果后, 对空间特征相邻或接近的矢量数据进行归并处理当 Reduce 过程执行完成后, 根据键值对中的 O.ID 和 O.Geometry 对每个矢量数据进行排序, 得到按预先定义的数据键值排序的矢量数据空间分析结果假设矢量数据计算流由 TFn 表示,DFn 表示矢量数据流具体的数据处理流程如下 ( 图 2): (1) 矢量数据处理程序运行后, 首先对分治规约计算过程进行初始化 (TF1), 指定主控节点和各计算节点, 对各计算节点进行初始配置 (2)TF2 为由主控节点发出的数据分配, 将第一阶段分块数据分配到各计算节点 (DF1), 并由主控节点对输入数据生成 <O.ID,O.Geometry,O.Attribute> 键值对集合 (3)TF3 执行 Map, 得到由主控节点分配的矢量数据 <O.ID,O.Geometry,O.Attribute> 键值对映射表, 根据主控节点分配的数据处理, 各计算节点执行矢量数据空间分析处理并得到中间结果这一过程中包括 : 1Map 函数在各计算节点中读取矢量数据 (DF2), 在计算完成后, 将中间结果保存到中 (DF3) 2 各计算节点将计算的中间结果的 <O.ID,O.Geometry, O.Attribute> 键值对映射表发送给主控节点 (DF4), 主控节点在将映射表排序后反馈给计算节点 (DF5) (4)TF4 用于执行 Reduce, 这一过程根据矢量数据空间分析中间结果的键 (id 和空间特征 ) 进行排序, 对相

1 矢量数据 MapReduce 计算流程分析目前, 针对矢量数据 MapReduce 分布式计算的相关研究较少并且, 现有研究基本没有考虑矢量数据的属性特 [7-10] 征然而, 在矢量数据进行处理分析过程中, 属性数据具有重要的作用本章在分析

4 ,49(16) Computer Engineering and Applications 计算机工程与应用第一阶段 : 数据分块数据集 key = id value = O.Geometry S = U (O 1 S = U (O 2 S = U (O R f (O S[1] S[2] S[R] 分块结果空间数据库数据分配计算单维值 Map 阶段分块 Reduce 阶段第二阶段 : 空间数据分析处理矢量数据处理程序 S[1] DF1 TF2 TF1 TF1 主控节点 DF4 DF5 DF2 DF3 计算节点 1 DF6 计算节点 1 DF7 DF8 S[2] 计算节点计算节点 S[R] 分块结果 TF3 Map 阶段通信阶段 TF4 Reduce 阶段 TF5 第三阶段 : 结果合并计算节点 1 计算节点数据合并空间数据分析结果图 2 基于 MapReduce 处理矢量数据过程邻或接近的结果进行归并, 同时对数据进行精炼, 避免副本这一过程包括 : 1Reduce 函数执行后, 各计算节点将空间分析中间结果发送给其他计算节点 (DF6); 2 各计算节点根据键值对读取输入数据 (DF7); 3Reduce 函数将计算结果进行归并, 写入各计算节点 (DF8) 如果计算未完成, 执行新一轮的 Map-Reduce 计算过程 (TF4) 3.4 分析结果合并 Reduce() 函数根据每一个中间结果的键 (key) 来遍历排序后的数据, 并且把 key 和相关的中间结果 value 集合传递给 Reduce() 函数,Reduce() 函数的计算节点最终把输出结果存放在主节点机器的一个输出文件中, 获得分析的最终结果 4 原型系统架构及测试本文基于 Hadoop 版本开发了矢量数据分布式存储和计算原型系统该系统由基于 Hadoop MapReduce 模块的分布式计算模块基于 HDFS 的分布式存储模块分布式处理服务模块以及客户端等部分组成 ( 见图 3) 系统采用 J2EE 环境开发, 运行于 Linux 环境由于 MapReduce 适用于联合性能较低的计算机进行分布式并行计算, 在实验中以 3 台普通 PC 构建了系统的测试环境每个节点机器的配置相同,CPU:1 GHz; 内存 :1 GB; 硬盘 :100 GB 操作系统为 Ubuntu 在上述测试环境下, 随着计算节点数目从 1 台增加至 3 台, 关中地区 1:10 万土地利用数据 ( 数据量 75.8 MB,55 632

DF2 DF3 计算节点 1 DF6 计算节点 1 DF7 DF8 S[2] 计算节点计算节点 S[R] 分块结果 TF3 Map 阶段通信阶段 TF4 Reduce 阶段 TF5 第三阶段 : 结果合并计算节点 1 计算节点数据合并空间数据分析结果图 2 基于 MapReduce 处理矢量

5 尹芳, 冯敏, 诸云强, 等 : 基于开源 Hadoop 的矢量空间数据分布式处理研究 2013,49(16) 29 客户端 Internet 计算节点主节点分布式处理 Web 服务启动分布式处理模块创建监控 HDFS 数据存储列表接收 NameNode DataNode MapReduce 框架 Map/Reduce Interface Job Tracker Task Tracker 调度分配执行图 3 原型系统组成个多边形空间对象实体 ) 的空间范围查询时间 ( 查询范围为 [106.75,35 ]~[109.75,34 ], 查询数量为个多边形 ) 分别为 620 s 498 s 402 s 5 结论本文通过网络分布式连接多台 PC 计算机, 能够利用已有的普通计算资源, 完成对大规模矢量数据的高效处理探讨了利用 MapReduce 并行方法处理空间数据的基本步骤, 通过对关中地区 1:10 万土地利用数据的应用测试, 结果表明 : 分布式计算方法通过连接多计算节点, 能够有效地提升矢量数据的计算效率, 而且计算节点对计算性能的影响非常明显, 通过添加节点能够实现对性能的提升有助于提高地学矢量数据的分析计算能力, 解决地学相关模拟计算的性能瓶颈参考文献 : [1] 王永刚. 基于 Hadoop 云计算平台的地理信息服务若干关键技术研究 [D]. 北京 : 中国科学院研究生院遥感应用研究所,2011. [2] Yang H,Dasdan A,Hsiao R L,et al.map-reduce-merge:simplified relational data processing on large clusters[c]//zhou L Z,Ling T W.Proceedings of Intemational Confererlce on Management of Data,Beijing.USA:Association for Computing Machinery,2007: [3] Zhang Shubin,Han Jizhong,Liu Zhiyong,et al.sjmr:parallelizing spatial Join with MapReduce on clusters[c]//sterling T.Proceedings of International Conference on Cluster Computing and Workshops,New Orleans,LA.USA:IEEE Computer Society,2009:1-4. [4] Wang Kai,Han Jizhong,Tu Bibo,et al.accelerating spatial data processing with MapReduce[C]//Jiang H.Proceedings of the 16th International Conference on Parallel and Distributed Systems,Shanghai.USA:IEEE Computer Society,2010: [5] 范建永, 龙明, 熊伟. 基于 HBase 的矢量空间数据分布式存储研究 [J]. 地理与地理信息科学,2012,28(5): [6] Stonebraker M.SQL databases v.nosql databases[j].communications of the ACM,2010,53(4): [7] Cary A,Sun Zhengguo,Hristidis V,et al.experiences on processing spatial data with MapReduce[J].Scientific and Statistical Database,2009: [8] 张书彬, 韩冀中, 刘志勇, 等. 基于 MapReduce 实现空间查询的研究 [J]. 高技术通讯,2010,20(7): [9] 冯敏, 尹芳, 诸云强, 等. 基于 MapReduce 的分布式地形数据分析计算研究 [J]. 华中科技大学学报 : 自然科学版,2011,39 (S1): [10] 高昂. 面向空间数据的分布式计算服务研究 [D]. 北京 : 中科院中国科学院研究生院 ( 地理科学与资源研究所 ),2011.

75,34 ], 查询数量为 32 591 个多边形 ) 分别为 620 s 498 s 402 s 5 结论本文通过网络分布式连接多台 PC 计算机, 能够利用已有的普通计算资源, 完成对大规模矢量数据的高效处理探讨了利用 MapReduce 并行方法处理空间数据

ttian

ttian 2 1952 522 3 1 1976 241 1959 9 143 1980 3 135 136 1086 1093 1957 1988 1957 1961 1983 1984 1958 1961 1977 1984 1984 5 115 169 161 163 267 269 211 1979 1981 6 15 1984 5 210 1993 1983 1983