一種基于MapReduce的矢量空間數(shù)據(jù)存儲與查詢方法*

陳 潔 褚龍現(xiàn) 夏棟梁

(1.銅川職業(yè)技術學院人文科學系 銅川 727031)(2.平頂山學院軟件學院 平頂山 467000)

一種基于MapReduce的矢量空間數(shù)據(jù)存儲與查詢方法*

陳 潔1褚龍現(xiàn)2夏棟梁2

(1.銅川職業(yè)技術學院人文科學系 銅川 727031)(2.平頂山學院軟件學院 平頂山 467000)

針對海量的矢量空間數(shù)據(jù)存儲和查詢問題,提出一種基于HBase的矢量數(shù)據(jù)存儲模型,實現(xiàn)了以MapReduce為計算框架的分布式數(shù)據(jù)導入與查詢方法。通過計算空間數(shù)據(jù)中心點的Geohash編碼設計數(shù)據(jù)表的行鍵,有效利用Geohash特性和行鍵范圍掃描數(shù)據(jù)的特點實現(xiàn)空間查詢。實驗表明,提出的分布式存儲與查詢方法有較好的可行性和較高的執(zhí)行效率。

MapReduce, HBase, Geohash, 矢量數(shù)據(jù), 分布式

1 引言

隨著地理信息技術的不斷發(fā)展,空間數(shù)據(jù)的獲取途徑日益增多,數(shù)據(jù)量規(guī)模不斷擴大,傳統(tǒng)矢量空間數(shù)據(jù)的管理方法已經(jīng)逐漸無法滿足現(xiàn)有信息處理的需求[1]。Apache Hadoop[2]的產(chǎn)生為分布式存儲和處理海量數(shù)據(jù)提供了平臺,使得在分布式文件系統(tǒng)(Hadoop Distributed File System,HDFS)中存儲矢量空間數(shù)據(jù)成為可能[3]。為了進一步提高矢量數(shù)據(jù)在Hadoop上的管理效率,研究人員開始關注基于HBase的存儲模型和查詢方案設計。

目前有關矢量空間數(shù)據(jù)存儲與查詢的研究工作主要有:按比例尺和圖層設計不同存儲模型,采用MapReduce并行創(chuàng)建索引的方法[4];注重存儲模型設計,完成幾何信息、非幾何信息和拓撲信息存儲方案[5];將空間對象經(jīng)緯度數(shù)據(jù)連接作為行鍵的一部分,再通過列族設計進行數(shù)據(jù)過濾掃描[6～7]的方法等。這些研究更多關注空間數(shù)據(jù)存儲模型和索引設計,對研究數(shù)據(jù)的并行導入和行鍵過濾查詢比較缺失。

因此,本文的主要工作是實現(xiàn)基于HBase和MapReduce的矢量空間數(shù)據(jù)模型設計、數(shù)據(jù)并行導入和區(qū)域查詢方法。計算矢量空間數(shù)據(jù)中心點的Geohash編碼作為行鍵,數(shù)據(jù)信息以WKB格式存儲,最后給出區(qū)域查詢算法。

2 HBase與MapReduce

2.1 HBase

HBase是Hadoop的分布式數(shù)據(jù)庫[8],同時支持結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)存儲。HBase在存儲數(shù)據(jù)時采用列式存儲方式,不會存儲列值為空的數(shù)據(jù)元素。在邏輯上,每個數(shù)據(jù)表包含行和列,多個列可以同屬于一個列族,每行數(shù)據(jù)通過行鍵唯一標識,行列對應的單元格可以根據(jù)不同時間戳有多個不同值[9]。單元格的值有以下多元組唯一確定:

(行鍵,列族:列名,時間戳)→元素值

2.2 MapReduce

MapReduce是Hadoop上的并行編程模型和計算框架[10],其計算思想是:將對HDFS中大規(guī)模數(shù)據(jù)集的操作由JobTracker分發(fā)給各個TaskTracker分別完成,最后整合處理各個節(jié)點中間結(jié)果得出最終結(jié)果[11～12]。一個MapReduce任務被分為Map和Reduce兩個階段,既可以運行在HDFS上,也可以運行在HBase上[13]。

3 數(shù)據(jù)模型設計

3.1 行鍵設計

HBase數(shù)據(jù)表中行鍵是唯一確定行的標識,也是用來查詢數(shù)據(jù)的唯一依據(jù),且以字節(jié)流形式按字典升序存儲[14]。因為查詢只支持按行鍵檢索記錄,包括單個行鍵訪問、行鍵范圍訪問和全表掃描,所以行鍵的設計決定了數(shù)據(jù)處理效率。

為了提高檢索矢量數(shù)據(jù)的效率,根據(jù)區(qū)域查詢特點,考慮矢量數(shù)據(jù)存儲時應該將地理空間位置相鄰的數(shù)據(jù)在表中連續(xù)保存。Geohash是一種可以表示坐標點的地理編碼[15],且空間地理位置相鄰時會得到相同前綴的編碼,所以本文將矢量空間數(shù)據(jù)抽象為數(shù)據(jù)的中心點,使用坐標點的12位Geohash編碼作為行鍵。

1) 行鍵設計方案特點

一是通過12位Geohash編碼的空間坐標點能精確到厘米級,充分區(qū)分地理位置的不同矢量對象,實現(xiàn)行鍵的唯一性;二是物理空間位置相鄰,行鍵具有相同前綴,數(shù)據(jù)存儲越近,利用行鍵范圍查詢時越準確,效率越高。

2) Geohash編碼算法

Geohash編碼的基本思想是:將地球按照經(jīng)度[-180,180],緯度[-90,90]交替二分,每五次二分為一個層。計算數(shù)據(jù)點經(jīng)緯度分別落在哪個分區(qū),若經(jīng)緯度大于或等于中點,用數(shù)據(jù)位1表示,否則用0表示。按照精度要求整層重復這一過程,最后將得到的經(jīng)度數(shù)據(jù)位和緯度數(shù)據(jù)位交叉并轉(zhuǎn)換成Base32編碼。計算流程如下。

String GetGeohash(double lon,doulbe lat,int pre)

1:pre=Min(5*pre,64)

2:double[] latR={-90.0,90.0},double[] lonR={-180.0,180.0}

3:int bit=0, ch=0; bool even=true;String geo="";

4:while(geo.Length< pre){

5:if(even==true) Reset(lonR,ch);

6:else Reset(lonR,ch);

7:even=!even;

8:if(bit < 4) bit++;

9:else {geo+=Base32[ch];bit=0;ch=0;}

10:}

3.2 列族設計

本文主要存儲shapefile矢量數(shù)據(jù),包含兩類文件:shp數(shù)據(jù)文件,dbf屬性文件。在設計HBase數(shù)據(jù)表時用Geo和Attr列族分別表示兩個文件內(nèi)容,geo列族含有一列wkb保存二進制形式的幾何數(shù)據(jù);attr列族根據(jù)dbf中空間數(shù)據(jù)的實際屬性動態(tài)添加列以保存完整的幾何屬性值。最終設計的數(shù)據(jù)表shapeTable存儲模型如表1所示。

表1 矢量空間數(shù)據(jù)存儲模型

4 基于MapReduce的并行處理計算

4.1 數(shù)據(jù)并行導入算法

因為不同圖層shapefile數(shù)據(jù)文件之間沒有聯(lián)系,所以在使用MapReduce向HBase表中導入數(shù)據(jù)時只使用Mapper端,可以減少MapReduce程序執(zhí)行時間,導入數(shù)據(jù)示意圖如圖1所示。

矢量數(shù)據(jù)并行導入的算法實現(xiàn)流程如下:

1) 在Driver類中將shapefile文件的路徑和HBase中數(shù)據(jù)表名稱傳給Maper類的map方法;

2) 在map方法中使用開源Geotools工具包讀取shapefile的shp文件和dbf文件,迭代處理每一個讀到的要素;

3) 將要素轉(zhuǎn)化為Geometry對象,通過getCentroid()方法獲取中心點坐標,調(diào)用GetGeohash()方法計算Geohash編碼作為數(shù)據(jù)表的行鍵,構(gòu)建Put對象;

圖1 MapReduce分布式導入數(shù)據(jù)示意圖

4) 使用WKBWriter的write方法將Geometry對象轉(zhuǎn)換為字節(jié)數(shù)組,向Put對象添加geo列族的wkb列數(shù)據(jù);

5) 迭代獲取剩余屬性數(shù)據(jù),通過Property對象的getName()方法獲取屬性名稱,getValue()方法獲取屬性值,分別作為attr的列名和列值添加到Put對象;

6) 調(diào)用context.write(ImmutableBytesWritable對象,Put對象)將Put對象寫入HBase。

4.2 區(qū)域并行查詢算法

區(qū)域查詢主要完成在數(shù)據(jù)庫中檢索所有與給定區(qū)域有相交關系的數(shù)據(jù),本文充分借助行鍵設計特點對數(shù)據(jù)進行過濾掃描,實現(xiàn)指定區(qū)域并行查詢的思路為

1) 按照精度要求獲取區(qū)域中心點的Geohash值,并判斷該精度下得到的Geohash值是否包含原區(qū)域?qū)ο?若不包含則降低精度重新計算Geohash值直到包含區(qū)域?qū)ο鬄橹?

2) 根據(jù)最終得到的Geohash值構(gòu)造帶有前綴匹配的Scan對象;

3) 讀取掃描結(jié)果記錄,依次判斷是否與指定區(qū)域相交,若是即為查詢結(jié)果。

并行查詢流程如圖2所示。

圖2 并行區(qū)域查詢流程圖

5 實驗與分析

實驗平臺搭建與實驗數(shù)據(jù)說明如表3所示。

將實驗數(shù)據(jù)導入HBase數(shù)據(jù)庫按照兩種方法完成,一是通過單機導入,二是本文的并行導入方法,兩種方法運行時間分別為:255s和102s。并行導入運行效率是原來的2.5倍,這是因為4個節(jié)點中3個是DataNode,可以3個節(jié)點并行運算,再加上初始化花費時間導致運行效率并非原來的3倍。

選擇三種不同大小的區(qū)域R1(拉斯維加斯)、R2(內(nèi)達華州)和R3(落基山地區(qū))完成并行查詢并與文獻[5]中方法對比,運行時間如圖3所示。

表3 實驗環(huán)境與數(shù)據(jù)

圖3 不同區(qū)域查詢運行時間

實驗結(jié)果表明,借助Geohash行鍵設計特性和MapReduce并行處理框架能有效提高區(qū)域查詢效率,隨著集群中節(jié)點數(shù)的增加,在數(shù)據(jù)量繼續(xù)增大的情況下執(zhí)行效率將提高更多。

6 結(jié)語

本文結(jié)合shapefile矢量空間數(shù)據(jù)的特點,提出一種基于HBase的數(shù)據(jù)存儲模型,實現(xiàn)了基于Geohash編碼的行鍵設計方案,設計了應用MapReduce計算框架執(zhí)行數(shù)據(jù)并行到如何并行查詢算法。實驗驗證了本文提出數(shù)據(jù)存儲和查詢方法的有效性,下一步將如何優(yōu)化分布式查詢策略作為研究方向。

[1] 陳崇成,林劍峰,吳小竹,等.基于NoSQL的海量空間數(shù)據(jù)云存儲與服務方法[J].地球信息科學學報,2013,15(2):166-174. CHEN Chongcheng, LIN Jianfeng, WU Xiaozhu, et al. Massive Geo-spatial Data Cloud Storage and Services Based on NoSQL Database Technique[J]. Journal of Geo-Information Science,2013,15(2):166-174.

[2] Yang G. The Application of MapReduce in the Cloud Computing[C]//International Symposium on Intelligence Information Processing and Trusted Computing. IEEE,2011:154-156.

[3] Wang Y, Wang S. Research and Implementation on Spatial Data Storage and Operation Based on Hadoop Platform[C]//Iita International Conference on Geoscience & Remote Sensing,2010:275-278.

[4] 范建永,龍明,熊偉.基于HBase的矢量空間數(shù)據(jù)分布式存儲研究[J].地理與地理信息科學,2012,28(5):39-42. FAN Jianyong, LONG Ming, XIONG Wei. Research of Vector Spatial Data Distributed Storage Based on HBase[J]. Geography and Geo-Information Science,2012,28(5):39-42.

[5] 鄭坤,付艷麗.基于HBase和GeoTools的矢量空間數(shù)據(jù)存儲模型研究[J].計算機應用與軟件,2015(3):23-26. ZHENG Kun, FU Yanli. Research on HBase and Geotools-based Vector Spatial Data Storage Model[J]. Computer Applications and Software,2015(3):23-26.

[6] 丁琛.基于HBase的空間數(shù)據(jù)分布式存儲和并行查詢算法研究[D].南京:南京師范大學,2014. DING Chen. Research on Distributed Storage and Parallel Query Algorithm of Spatial Data in HBase[D]. Nanjing: Nanjing Normal University,2014.

[7] 張葉,許國艷,花青.基于HBase的矢量空間數(shù)據(jù)存儲與訪問優(yōu)化[J].計算機應用,2015,35(11):3102-3105. ZHANG Ye, XU Guoyan, HUA Qing. Storage and access optimization of vector space data based on HBase[J]. Journal of Computer Applications,2015,35(11):3102-3105.

[8] WANG L, CHEN B, LIU Y. Distributed storage and index of vector spatial data based on HBase[C]//Proceedings of the 2013 21st International Conference on Geoinformatics. Piscataway: IEEE,2013:1-5.

[9] White T. Hadoop: The Definitive Guide[J]. O’reilly Media Inc Gravenstein Highway North,2010,215(11):1-4.

[10] Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters[J]. Communications of the Acm,2008,51(1):107-113.

[11] 李建江,崔健,王聃,等.MapReduce并行編程模型研究綜述[J].電子學報,2011,39(11):2635-2642. LI Jianjiang, CU Jian, WANG Dan, et al. Survey of MapReduce Parallel Programming Model[J]. Acta Electronica Sinica,2011,39(11):2635-2642.

[12] 黃山,王波濤,王國仁,等.MapReduce優(yōu)化技術綜述[J].計算機科學與探索,2013,7(10):865-885. HUANG Shan, WANG Botao, WANG Guoren, et al. A Survey on MapReduce Optimization Technologies[J]. Acta Electronica Sinica,2013,7(10):865-885.

[13] Dimiduk N, Khurana A, Ryan M H. HBase in Action[M]. HBase in action. Manning,2012.

[14] Zheng K, Fu Y. Research on Vector Spatial Data Storage Schema Based on Hadoop Platform[J]. International Journal of Database Theory & Application,2013,6(5):85-94.

[15] 金安,程承旗,宋樹華,等.基于Geohash的面數(shù)據(jù)區(qū)域查詢[J].地理與地理信息科學,2013,29(5):31-35. JIN An, CHENG Chengqi, SONG Shuhua, et al. Regional Query of Area Data Based on Geohash[J]. Geography and Geo-Information Science,2013,29(5):31-35.

A Vector Spatial Data Storage and Query Method Based on MapReduce

CHEN Jie1CHU Longxian2XIA Dongliang2

(1. Department of Humanities, Tongchuan Vocational and Technical College, Tongchuan 727031)(2. Software School, Pingdingshan University, Pingdingshan 467000)

According to the problems arising from mass of vector spatial data storage and query, a model of vector data storage was proposed based on HBase and the distributed data import and query methods was implemented using MapReduce as the computing framework. Through calculating the Geohash code of spatial data central point, the row-key of data table was designed, and spatial query was achieved by using the features of Geohash and the characteristics of the row-key range scan data. Experiments showed that the proposed distributed storage and query method has good feasibility and high execution efficiency.

MapReduce, HBase, Geohash, vector data, distributed Class Number TP333

2016年10月1日,

2016年11月27日

陳潔,女,碩士,講師,研究方向:大數(shù)據(jù),旅游與城市發(fā)展。褚龍現(xiàn),男,碩士,副教授,研究方向:大數(shù)據(jù),數(shù)據(jù)挖掘。夏棟梁,男,碩士,講師,研究方向:云計算,大數(shù)據(jù)。

TP333

10.3969/j.issn.1672-9722.2017.04.025