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

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

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

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

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

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

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

1 引言

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

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

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

2 HBase與MapReduce

2.1 HBase

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

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

2.2 MapReduce

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

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

3.1 行鍵設(shè)計(jì)

HBase數(shù)據(jù)表中行鍵是唯一確定行的標(biāo)識(shí),也是用來(lái)查詢數(shù)據(jù)的唯一依據(jù),且以字節(jié)流形式按字典升序存儲(chǔ)[14]。因?yàn)椴樵冎恢С职葱墟I檢索記錄,包括單個(gè)行鍵訪問(wèn)、行鍵范圍訪問(wèn)和全表掃描,所以行鍵的設(shè)計(jì)決定了數(shù)據(jù)處理效率。

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

1) 行鍵設(shè)計(jì)方案特點(diǎn)

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

2) Geohash編碼算法

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

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 列族設(shè)計(jì)

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

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

4 基于MapReduce的并行處理計(jì)算

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

因?yàn)椴煌瑘D層shapefile數(shù)據(jù)文件之間沒(méi)有聯(lián)系,所以在使用MapReduce向HBase表中導(dǎo)入數(shù)據(jù)時(shí)只使用Mapper端,可以減少M(fèi)apReduce程序執(zhí)行時(shí)間,導(dǎo)入數(shù)據(jù)示意圖如圖1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)與分析

實(shí)驗(yàn)平臺(tái)搭建與實(shí)驗(yàn)數(shù)據(jù)說(shuō)明如表3所示。

將實(shí)驗(yàn)數(shù)據(jù)導(dǎo)入HBase數(shù)據(jù)庫(kù)按照兩種方法完成,一是通過(guò)單機(jī)導(dǎo)入,二是本文的并行導(dǎo)入方法,兩種方法運(yùn)行時(shí)間分別為:255s和102s。并行導(dǎo)入運(yùn)行效率是原來(lái)的2.5倍,這是因?yàn)?個(gè)節(jié)點(diǎn)中3個(gè)是DataNode,可以3個(gè)節(jié)點(diǎn)并行運(yùn)算,再加上初始化花費(fèi)時(shí)間導(dǎo)致運(yùn)行效率并非原來(lái)的3倍。

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

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

圖3 不同區(qū)域查詢運(yùn)行時(shí)間

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

6 結(jié)語(yǔ)

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

[1] 陳崇成,林劍峰,吳小竹,等.基于NoSQL的海量空間數(shù)據(jù)云存儲(chǔ)與服務(wù)方法[J].地球信息科學(xué)學(xué)報(bào),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ù)分布式存儲(chǔ)研究[J].地理與地理信息科學(xué),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ù)存儲(chǔ)模型研究[J].計(jì)算機(jī)應(yīng)用與軟件,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ù)分布式存儲(chǔ)和并行查詢算法研究[D].南京:南京師范大學(xué),2014. DING Chen. Research on Distributed Storage and Parallel Query Algorithm of Spatial Data in HBase[D]. Nanjing: Nanjing Normal University,2014.

[7] 張葉,許國(guó)艷,花青.基于HBase的矢量空間數(shù)據(jù)存儲(chǔ)與訪問(wèn)優(yōu)化[J].計(jì)算機(jī)應(yīng)用,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].電子學(xué)報(bào),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] 黃山,王波濤,王國(guó)仁,等.MapReduce優(yōu)化技術(shù)綜述[J].計(jì)算機(jī)科學(xué)與探索,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] 金安,程承旗,宋樹(shù)華,等.基于Geohash的面數(shù)據(jù)區(qū)域查詢[J].地理與地理信息科學(xué),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ù)挖掘。夏棟梁,男,碩士,講師,研究方向:云計(jì)算,大數(shù)據(jù)。

TP333

10.3969/j.issn.1672-9722.2017.04.025