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

陳 潔 褚龍現 夏棟梁

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

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

陳 潔1褚龍現2夏棟梁2

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

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

MapReduce, HBase, Geohash, 矢量數據, 分布式

1 引言

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

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

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

2 HBase與MapReduce

2.1 HBase

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

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

2.2 MapReduce

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

3 數據模型設計

3.1 行鍵設計

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

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

1) 行鍵設計方案特點

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

2) Geohash編碼算法

Geohash編碼的基本思想是:將地球按照經度[-180,180],緯度[-90,90]交替二分,每五次二分為一個層。計算數據點經緯度分別落在哪個分區,若經緯度大于或等于中點,用數據位1表示,否則用0表示。按照精度要求整層重復這一過程,最后將得到的經度數據位和緯度數據位交叉并轉換成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矢量數據,包含兩類文件:shp數據文件,dbf屬性文件。在設計HBase數據表時用Geo和Attr列族分別表示兩個文件內容,geo列族含有一列wkb保存二進制形式的幾何數據;attr列族根據dbf中空間數據的實際屬性動態添加列以保存完整的幾何屬性值。最終設計的數據表shapeTable存儲模型如表1所示。

表1 矢量空間數據存儲模型

4 基于MapReduce的并行處理計算

4.1 數據并行導入算法

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

矢量數據并行導入的算法實現流程如下:

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

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

3) 將要素轉化為Geometry對象,通過getCentroid()方法獲取中心點坐標,調用GetGeohash()方法計算Geohash編碼作為數據表的行鍵,構建Put對象;

圖1 MapReduce分布式導入數據示意圖

4) 使用WKBWriter的write方法將Geometry對象轉換為字節數組,向Put對象添加geo列族的wkb列數據;

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

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

4.2 區域并行查詢算法

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

1) 按照精度要求獲取區域中心點的Geohash值,并判斷該精度下得到的Geohash值是否包含原區域對象,若不包含則降低精度重新計算Geohash值直到包含區域對象為止;

2) 根據最終得到的Geohash值構造帶有前綴匹配的Scan對象;

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

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

圖2 并行區域查詢流程圖

5 實驗與分析

實驗平臺搭建與實驗數據說明如表3所示。

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

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

表3 實驗環境與數據

圖3 不同區域查詢運行時間

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

6 結語

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

[1] 陳崇成,林劍峰,吳小竹,等.基于NoSQL的海量空間數據云存儲與服務方法[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的矢量空間數據分布式存儲研究[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的矢量空間數據存儲模型研究[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的空間數據分布式存儲和并行查詢算法研究[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的矢量空間數據存儲與訪問優化[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優化技術綜述[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的面數據區域查詢[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日

陳潔,女,碩士,講師,研究方向:大數據,旅游與城市發展。褚龍現,男,碩士,副教授,研究方向:大數據,數據挖掘。夏棟梁,男,碩士,講師,研究方向:云計算,大數據。

TP333

10.3969/j.issn.1672-9722.2017.04.025