基于MapReduce的空間數(shù)據(jù)并行劃分算法

付艷麗，吳艷民，張金標(biāo)，鄭 坤，趙長虹，鄭 康,5，方發(fā)林,5

(1. 濟(jì)南市勘察測繪研究院，山東 濟(jì)南 250013; 2. 中國地質(zhì)大學(xué)(武漢)信息工程學(xué)院，湖北 武漢 430074;3. 北京創(chuàng)時(shí)空科技發(fā)展有限公司，北京 100083; 4. 廣東省氣象探測數(shù)據(jù)中心，廣東 廣州 510610； 5. 武漢兆圖科技有限公司，湖北 武漢 430070)

基于MapReduce的空間數(shù)據(jù)并行劃分算法

付艷麗1,2，吳艷民3，張金標(biāo)4，鄭 坤2，趙長虹3，鄭 康2,5，方發(fā)林2,5

(1. 濟(jì)南市勘察測繪研究院，山東 濟(jì)南 250013; 2. 中國地質(zhì)大學(xué)(武漢)信息工程學(xué)院，湖北 武漢 430074;3. 北京創(chuàng)時(shí)空科技發(fā)展有限公司，北京 100083; 4. 廣東省氣象探測數(shù)據(jù)中心，廣東 廣州 510610； 5. 武漢兆圖科技有限公司，湖北 武漢 430070)

針對海量空間數(shù)據(jù)分布式存儲中存在的不顧及空間鄰近性、分布不均和數(shù)據(jù)傾斜的問題，基于MapReduce并行編程模型，對Hilbert空間曲線層次分解的思想和節(jié)點(diǎn)容量感知的方法進(jìn)行了研究，提出了一種層次分解的空間數(shù)據(jù)并行劃分策略，并通過臨界值判定實(shí)現(xiàn)空間數(shù)據(jù)的均衡存儲。最后通過實(shí)例分析說明該方法可以在保證空間數(shù)據(jù)鄰近特性的同時(shí)，解決海量空間數(shù)據(jù)分布式存儲不均和數(shù)據(jù)傾斜的問題。

MapReduce；Hilbert空間曲線；空間數(shù)據(jù)并行劃分

隨著GIS應(yīng)用的逐步深入和拓展，各行業(yè)對GIS海量空間數(shù)據(jù)的處理能力及效率提出更高要求，分布式GIS及分布式空間數(shù)據(jù)庫應(yīng)運(yùn)而生[1]。特別是隨著現(xiàn)代測量計(jì)算技術(shù)的發(fā)展，空間數(shù)據(jù)呈TB和PB級增長，大規(guī)?？臻g數(shù)據(jù)的分布式處理效率顯得尤為重要[2]。

空間數(shù)據(jù)劃分是空間數(shù)據(jù)分布式存儲和處理的首要任務(wù)，其方法的優(yōu)劣和執(zhí)行效率直接影響空間數(shù)據(jù)分布式存儲管理的整體性能。常用面向并行數(shù)據(jù)庫的劃分方法主要有輪轉(zhuǎn)法、散列劃分、范圍劃分、混合劃分法等[3]。文獻(xiàn)[3]對目前4種空間數(shù)據(jù)劃分方法進(jìn)行了探討，指出這些劃分方法基本上只能在選定關(guān)系的一個(gè)屬性上劃分，不能有效地支持非劃分屬性上的查詢，并對常用的空間填充曲線Z-ordering曲線、Hilbert曲線進(jìn)行了介紹。由于Hilbert曲線沒有斜線，不能很好地保持空間鄰近性，引起更多學(xué)者的關(guān)注；文獻(xiàn)[4]基于Hilbert曲線自身的分形相似性特點(diǎn),提出了Hilbert快速編碼方法，通過空間層次分解提高了Hilbert曲線的編碼速度；文獻(xiàn)[1]基于Hilbert空間填充曲線提出了可以有效保證各存儲節(jié)點(diǎn)間存儲均衡的空間數(shù)據(jù)劃分方法；文獻(xiàn)[5]針對現(xiàn)有空間數(shù)據(jù)劃分方法不考慮相鄰對象空間關(guān)系對數(shù)據(jù)劃分的影響等問題，提出了一種基于Hilbert空間填充曲線層次分單元的空間數(shù)據(jù)劃分方法。這些研究為進(jìn)一步研究空間數(shù)據(jù)劃分算法提高了理論基礎(chǔ)，但面對TB級或PB級海量的空間數(shù)據(jù)，空間數(shù)據(jù)劃分效率低的問題一直沒有得到很好的解決。

為了提高空間數(shù)據(jù)劃分效率，一些學(xué)者提出將空間數(shù)據(jù)劃分算法和并行計(jì)算技術(shù)相結(jié)合，如文獻(xiàn)[6—7]基于MapReduce對Z-ordering曲線空間數(shù)據(jù)劃分策略和基于X-means單元迭代的空間數(shù)據(jù)劃分策略算法進(jìn)行了并行執(zhí)行。MapReduce是2004年Google在OSDI國際會議上提出的一種并行編程模型[8]，公布了其基本原理和主要設(shè)計(jì)思想。由于其在海量數(shù)據(jù)處理方面的可擴(kuò)展、容錯性、高效率等特性，得到了很多學(xué)者廣泛的關(guān)注和迅速發(fā)展。Yahoo針對MapReduce不能支持多個(gè)關(guān)聯(lián)異構(gòu)數(shù)據(jù)集的不足，對該模型進(jìn)行了優(yōu)化，提出了Map-Reduce-Merge，此后有很多學(xué)者對MapReduce進(jìn)行了進(jìn)一步的發(fā)展，如MoustafaAbdelBaky[9-10]等提出MapReduce-CometCloud框架，解決了MapReduce并行模型處理不同數(shù)量、不同大小的數(shù)據(jù)集性能低的問題。但關(guān)于空間數(shù)據(jù)劃分算法和MapReduce技術(shù)相結(jié)合的研究相對較少，并且由于空間數(shù)據(jù)的分布特征，造成每個(gè)磁盤間的數(shù)據(jù)存儲容量不均衡而產(chǎn)生的數(shù)據(jù)傾斜現(xiàn)象一直沒有得到很好的解決。

基于以上分析和數(shù)據(jù)并行處理技術(shù)的研究，在顧及空間數(shù)據(jù)鄰近特征的基礎(chǔ)上，本文提出一種基于MapReduce的空間數(shù)據(jù)并行劃分處理模型，實(shí)現(xiàn)空間數(shù)據(jù)的并行劃分，以解決海量空間數(shù)據(jù)分布式存儲不均和數(shù)據(jù)傾斜的問題。

1 MapReduce并行編程模型

MapReduce并行編程模型，使開發(fā)人員只需要通過map()和reduce()接口定義自己的處理函數(shù)，處理一組key/value(鍵值對)的輸入，使用MapReduce映射規(guī)約進(jìn)行運(yùn)算，生成需要的key/value，很容易開發(fā)基于大型集群的程序，滿足高效處理海量數(shù)據(jù)的要求[11-12]。

MapReduce并行執(zhí)行框架對開發(fā)者隱藏了應(yīng)用層算法外的所有細(xì)節(jié)，結(jié)合圖1來說明MapReduce框架處理數(shù)據(jù)的執(zhí)行過程。在MapReduce編程模型中，集群中的節(jié)點(diǎn)由一個(gè)JobTracker和若干個(gè)TaskTracker組成，JobTracker負(fù)責(zé)任務(wù)調(diào)度，TsakTracker負(fù)責(zé)并行執(zhí)行任務(wù)，任務(wù)的執(zhí)行主要分為map、shuffle、reduce 3個(gè)階段。首先將輸入數(shù)據(jù)文件進(jìn)行劃分，文件劃分大小通過函數(shù)參數(shù)進(jìn)行配置，一般為16 MB到64 MB大小，然后通過JobTracker為M個(gè)Map和R個(gè)Reduce分配任務(wù)。Map()函數(shù)階段從HDFS讀取對應(yīng)的輸入數(shù)據(jù)塊，通過計(jì)算輸出中間結(jié)果；Shuffle階段將map()函數(shù)輸出的結(jié)果按照key值劃分成R分,每個(gè)劃分對應(yīng)于一個(gè)Reduce，并按key值做歸并merge()處理，將具有相同key的key/value對合并,形成新的鍵值對數(shù)據(jù)集并傳遞給Reduce()函數(shù)。Reduce()函數(shù)對傳入的每個(gè)key/value對進(jìn)行相應(yīng)的分析，輸出最終結(jié)果。

圖1 MapReduce框架數(shù)據(jù)處理執(zhí)行過程

2 顧及空間鄰近性且數(shù)據(jù)均衡分配的空間數(shù)據(jù)劃分算法

2.1 空間數(shù)據(jù)劃分思想

空間數(shù)據(jù)劃分思想主要分為兩部分：一是劃分過程中保持空間數(shù)據(jù)之間的鄰居特性；二是在劃分過程中，體現(xiàn)存儲節(jié)點(diǎn)之間性能的差異，使數(shù)據(jù)負(fù)載均衡。利用空間填充曲線中近似表示方法對空間數(shù)據(jù)進(jìn)行劃分，將數(shù)據(jù)劃分成大小相同的網(wǎng)格，并按照一定的規(guī)則對每個(gè)網(wǎng)格進(jìn)行編碼，在一定程度上保持空間鄰近性，將多維的空間數(shù)據(jù)降維在一維空間中表示[13]。Hilbert曲線利用一個(gè)線性序列來填充空間，由于階數(shù)不同的Hilbert網(wǎng)格之間遵循四叉樹分解規(guī)則，這就可以對子網(wǎng)格依據(jù)四叉樹的層次分解編碼方法，獲得子網(wǎng)格下一級的Hilbert編碼，這樣無需細(xì)分整個(gè)空間，就能達(dá)到良好的劃分效果。根據(jù)以上對MapReduce并行編程模型和空間數(shù)據(jù)劃分思想的分析，以MapReduce并行編程模型為基礎(chǔ)，利用Hilbert曲線層次劃分方法和臨界值限定來確保劃分后空間數(shù)據(jù)的鄰近性及多個(gè)存儲設(shè)備上的均衡劃分,具體的空間數(shù)據(jù)劃分思想如圖2所示。

圖2 基于MapReduce的空間數(shù)據(jù)劃分算法流程

結(jié)合圖2基于Hilbert曲線層次分解提出的空間數(shù)據(jù)劃分思想如下[14-15]：①根據(jù)空間數(shù)據(jù)對象個(gè)數(shù)n，確定Hilbert曲線的初始階數(shù)m和子網(wǎng)格層次分解的中止階數(shù)M，將整個(gè)空間范圍劃分成2m×2m的網(wǎng)格；②根據(jù)Hilbert編碼對空間對象進(jìn)行排序[11]，并從起始編碼累加各個(gè)空間對象的數(shù)據(jù)量，當(dāng)累加到第K個(gè)子網(wǎng)格時(shí)，如果總數(shù)據(jù)量超過單個(gè)存儲節(jié)點(diǎn)限定的平均存儲量Vavg，則對第K個(gè)子網(wǎng)格進(jìn)行四等分，計(jì)算下一級網(wǎng)格的Hilbert編碼，直至適量的空間對象放入存儲節(jié)點(diǎn)或子網(wǎng)格層次分解次數(shù)到達(dá)中止階數(shù)M，停止子網(wǎng)格的層次劃分；這樣不僅保證了空間數(shù)據(jù)間的鄰近性，又使得劃分后的數(shù)據(jù)量大致均衡。其中Vavg采用的公式如下

(1)

在保證數(shù)據(jù)劃分均衡的前提下，為體現(xiàn)節(jié)點(diǎn)之間的性能差異，應(yīng)使節(jié)點(diǎn)之間負(fù)載均衡。在空間數(shù)據(jù)劃分過程中采用節(jié)點(diǎn)容量感知的方法，設(shè)置每個(gè)存儲節(jié)點(diǎn)容量的臨界值Plow和Phigh，兩個(gè)值的計(jì)算公式如下

(2)

Plow=P(1-k)

(3)

Phigh=P(1+k)

(4)

式(3)—式(4)中，Si為第i個(gè)節(jié)點(diǎn)的物理地址范圍之和；Wi為每個(gè)節(jié)點(diǎn)的資源標(biāo)準(zhǔn)化權(quán)值(如采用100 GB為單位，300 GB的節(jié)點(diǎn)W值為3，200 GB的節(jié)點(diǎn)W值為2)；k0,1,k值的設(shè)定和物理節(jié)點(diǎn)的個(gè)數(shù)有關(guān)，物理節(jié)點(diǎn)數(shù)越多，k值越小，一般設(shè)置k值為25%。

2.2 基于MapReduce的空間數(shù)據(jù)劃分處理

根據(jù)以上對MapReduce并行編程模型和空間數(shù)據(jù)劃分思想的分析[16-17]可以看出,基于MapReduce的并行空間數(shù)據(jù)劃分算法主要分為以下4部分：①數(shù)據(jù)集分發(fā)管理階段；②數(shù)據(jù)預(yù)處理階段；③空間數(shù)據(jù)劃分執(zhí)行階段；④數(shù)據(jù)劃分結(jié)果的控制輸出。圖3為MapReduce空間數(shù)據(jù)處理流程。實(shí)現(xiàn)基于MapReduce空間數(shù)據(jù)劃分主要體現(xiàn)在Map()、Combine()、Reduce()函數(shù)的實(shí)現(xiàn)上，以HilbertBegin類為程序入口，通過setMapperClass()、setReducer()設(shè)定HilbertMap、HilbertCombine、HilbertReduce分別作為以上3個(gè)函數(shù)的實(shí)現(xiàn)類。

圖3 基于MapReduce數(shù)據(jù)劃分處理流程

3 算法實(shí)例分析

為了驗(yàn)證算法的有效性，基于Hadoop在一臺主頻2.3 GHz、四核i5處理器，內(nèi)存為4 GB的電腦上創(chuàng)建3臺操作系統(tǒng)為RedHatEnterprise 5的虛擬機(jī)，使用MyEclipse+Hadoop plugin開發(fā)環(huán)境進(jìn)行開發(fā)，對包含98 762個(gè)空間對象的數(shù)據(jù)集進(jìn)行數(shù)據(jù)劃分試驗(yàn)。表1是使用此劃分方法在3個(gè)存儲節(jié)點(diǎn)上的數(shù)據(jù)劃分結(jié)果，可以看出，該方法保證了相對均衡，基于層次分解的Hilbert編碼在保證空間鄰近性的同時(shí)，通過Vavg、Plow和Phigh兩次臨界值判定，保證各個(gè)存儲節(jié)點(diǎn)數(shù)的據(jù)量相對均衡，避免了數(shù)據(jù)傾斜，達(dá)到負(fù)載均衡的效果。

表1 各個(gè)存儲節(jié)點(diǎn)的數(shù)據(jù)劃分結(jié)果

此外為了驗(yàn)證算法的效率，與傳統(tǒng)串行Hilbert曲線劃分法進(jìn)行對比，結(jié)果如圖4所示。在相同磁盤I/O條件下,當(dāng)空間對象數(shù)目很少時(shí)，基于MapReduce的空間數(shù)據(jù)劃分算法沒有任何優(yōu)勢，但隨著空間對象的增加，基于MapReduce的并行空間數(shù)據(jù)劃分算法的時(shí)間優(yōu)勢逐漸顯著，從圖形曲線走勢可以推斷，基于MapReduce的并行空間數(shù)據(jù)劃分算法在海量空間數(shù)據(jù)劃分中具有更高的數(shù)據(jù)劃分效率。

圖4 兩種空間數(shù)據(jù)劃分方法效率比較

4 結(jié) 論

空間數(shù)據(jù)的劃分方法是分布式空間數(shù)據(jù)存儲的關(guān)鍵，關(guān)系空間數(shù)據(jù)整體應(yīng)用和服務(wù)功能。本文在MapReduce并行編碼模型的基礎(chǔ)上構(gòu)建了基于Hilbert的層次分解的空間數(shù)據(jù)劃分算法，在利用層次分解思想保證空間鄰近特征的同時(shí)，采用節(jié)點(diǎn)容量感知的方法增加臨界值判定，通過實(shí)例分析證明該方法克服了海量空間數(shù)據(jù)分布式存儲不均和數(shù)據(jù)傾斜的問題，在一定程度上提高了空間數(shù)據(jù)劃分的時(shí)間效率，為海量空間數(shù)據(jù)存儲提供了有益參考。由于受條件的制約，有關(guān)該算法的效率分析還有待今后在實(shí)踐中進(jìn)行更深入的驗(yàn)證和改進(jìn)。

[1] 趙春宇,孟令奎,林志勇. 一種面向并行空間數(shù)據(jù)庫的數(shù)據(jù)劃分算法研究[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2006, 31(11): 962-965.

[2] ZHENG K, GU D, FANG F, et al. Data Storage Optimi-zation Strategy in Distributed Column-oriented Database by Considering Spatial Adjacency[J]. Cluster Computing, 2017: 1-12.

[3] SHEKHAR S, CHAWL S. 空間數(shù)據(jù)庫[M]. 北京:機(jī)械工業(yè)出版社,2004.

[4] 陸鋒,周成虎. 一種基于空間層次分解的Hilbert 碼生成算法[J]. 中國圖象圖形學(xué)報(bào),2001,6(5): 465-469.

[5] 周艷, 朱慶, 張葉廷, 基于Hilbert曲線層次分解的空間數(shù)據(jù)劃分方法[J]. 地理與地理信息科學(xué), 2007,23(4):13-17.

[6] CARY A, SUN Zhengguo, HRISTIDIS V,et al.Experiences on Processing Spatial Data with MapReduce[C]∥21st International Conference on Scientific and Statistical Database Management. Berlin: Springer, 2009.

[7] CARY A, YESHA Y, ADJOUADI M, et al. Leveraging Cloud Computing in Geodatabase Management[C]∥2010 IEEE 16th International Conference on Parallel and Distributed Systems (ICPADS). [S.l.]: ICPADS, 2010：73-78.

[8] DEAN J，GHEMAWAT S. MapReduce：Simplified Data Processing on Large Clusters[J]. Conference on Symposium on Opearting System Design and Implementation, 2014, 51(1):10.

[9] ABDELBAKY M,KIM H,RODERO I,et al. Accelerating MapReduce Analytics UsingCometCloud[C]∥2012 IEEE 5th International Conference on Cloud Computing. [S.l.]: IEEE, 2012:447-454.

[10] BENDAHMANE A,ESSAAIDI E, MOUSSAOUI A E, et al. A New Mechanism to Ensure Integrity for MapReduce in Cloud Computing[C]∥2012 International Conference on Multimedia Computing and Systems (ICMCS). [S.l.]: ICMCS, 2012: 785-790.

[11] LI F, OOI B C, WU S. Distributed Data Management Using MapReduce[J]. ACM Computing Surveys, 2014, 46(3): 1-42.

[12] 王凱,曹建成,王乃生,等．Hadoop支持下的地理信息大數(shù)據(jù)處理技術(shù)初探[J]．測繪通報(bào)，2015(10)：114-117.

[13] 曹雪峰,萬剛,張宗佩.緊致的 Hilbert 曲線 Gray 碼索引算法[J]. 測繪學(xué)報(bào), 2016, 45(S1): 90-98.

[14] 付仲良,胡玉龍,翁寶鳳,等. M-Quadtree 索引: 一種基于改進(jìn)四叉樹編碼方法的云存儲環(huán)境下空間索引方法[J]. 測繪學(xué)報(bào), 2016,45(11):1342-1351.

[15] 周敬利,周正達(dá).改進(jìn)的云存儲系統(tǒng)數(shù)據(jù)分布策略[J]. 計(jì)算機(jī)應(yīng)用，2012， 32(2): 309-312.

[16] 陳德軍,高曉軍,王義飛. 基于 AHP 的云存儲負(fù)載均衡研究[J]. Computer Engineering and Applications, 2015, 51(7): 56-60.

[17] ELDAWY A, MOKBEL M F. SpatialHadoop: A MapReduce Framework for Spatial Data[C]∥2015 IEEE 31st International Conference on Data Engineering (ICDE). [S.l.]: IEEE, 2015: 1352-1363.

SpatialDataParallelPartitioningAlgorithmBasedonMapReduce

FU Yanli1,2,WU Yanmin3,ZHANG Jinbiao4，ZHENG Kun2,ZHAO Changhong3,ZHENG Kang2,5,FANG Falin2,5

(1. Jinan Geotechnical Investigation and Surverying Institute, Jinan 250013, China; 2. School of Information Engineering, China University of Geosciences(Wuhan), Wuhan 430074, China; 3. Beijing Create Space-time Science and Technology Limited Company, Beijing 100083, China; 4. Guangdong Meteorological Observation Data Center,Guangzhou 510610,China； 5. Wuhan Trillion Map Technology Limited Company,Wuhan 430070, China)

Spatial data partitioning method plays an important role in spatial data distributed storage, and its key problem is how topartition spatial data to distributed storage nodes in network environment. This paper discusses massive spatial data partitioning strategies and analyses their disadvantages which these partitioning methods have not taken into account spatial object size and spatial proximity. Aiming at these questions,this paper proposes a new spatial data parallelpartitioning strategy based on MapReduce and capacity-aware method to improve load balance which could avoid unevenly distributed data storage and data skew. Experimental analysis shows that the presented spatial data parallel partitioning algorithm not only achieves better storage load balance in distributed storage system,but also keeps well spatial locality of data objects after partitioning.

MapReduce; Hilbert space filling curve; spatial data parallel partitioning

付艷麗，吳艷民，張金標(biāo),等.基于MapReduce的空間數(shù)據(jù)并行劃分算法[J].測繪通報(bào)，2017(11)：96-100.

10.13474/j.cnki.11-2246.2017.0356.

P208

A

0494-0911(2017)11-0096-05

2017-05-16

國家重點(diǎn)研發(fā)計(jì)劃(2016YFB0502603)；湖北省自然科學(xué)基金(ZRY2015001543)；中國地質(zhì)大學(xué)(武漢)中央高?；究蒲袠I(yè)務(wù)費(fèi)資金(1610491B20)

付艷麗(1988—)，女，碩士，工程師，主要從事GIS開發(fā)工作。E-mail:fuyli@126.com

張金標(biāo)。E-mail: zhangjb@grmc.gov.cn