基于MapReduce的空間數據并行劃分算法

付艷麗，吳艷民，張金標，鄭 坤，趙長虹，鄭 康,5，方發林,5

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

基于MapReduce的空間數據并行劃分算法

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

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

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

MapReduce；Hilbert空間曲線；空間數據并行劃分

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

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

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

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

1 MapReduce并行編程模型

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

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

圖1 MapReduce框架數據處理執行過程

2 顧及空間鄰近性且數據均衡分配的空間數據劃分算法

2.1 空間數據劃分思想

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

圖2 基于MapReduce的空間數據劃分算法流程

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

(1)

在保證數據劃分均衡的前提下，為體現節點之間的性能差異，應使節點之間負載均衡。在空間數據劃分過程中采用節點容量感知的方法，設置每個存儲節點容量的臨界值Plow和Phigh，兩個值的計算公式如下

(2)

Plow=P(1-k)

(3)

Phigh=P(1+k)

(4)

式(3)—式(4)中，Si為第i個節點的物理地址范圍之和；Wi為每個節點的資源標準化權值(如采用100 GB為單位，300 GB的節點W值為3，200 GB的節點W值為2)；k0,1,k值的設定和物理節點的個數有關，物理節點數越多，k值越小，一般設置k值為25%。

2.2 基于MapReduce的空間數據劃分處理

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

圖3 基于MapReduce數據劃分處理流程

3 算法實例分析

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

表1 各個存儲節點的數據劃分結果

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

圖4 兩種空間數據劃分方法效率比較

4 結 論

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

[1] 趙春宇,孟令奎,林志勇. 一種面向并行空間數據庫的數據劃分算法研究[J]. 武漢大學學報(信息科學版), 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. 空間數據庫[M]. 北京:機械工業出版社,2004.

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

[5] 周艷, 朱慶, 張葉廷, 基于Hilbert曲線層次分解的空間數據劃分方法[J]. 地理與地理信息科學, 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支持下的地理信息大數據處理技術初探[J]．測繪通報，2015(10)：114-117.

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

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

[15] 周敬利,周正達.改進的云存儲系統數據分布策略[J]. 計算機應用，2012， 32(2): 309-312.

[16] 陳德軍,高曉軍,王義飛. 基于 AHP 的云存儲負載均衡研究[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

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

10.13474/j.cnki.11-2246.2017.0356.

P208

A

0494-0911(2017)11-0096-05

2017-05-16

國家重點研發計劃(2016YFB0502603)；湖北省自然科學基金(ZRY2015001543)；中國地質大學(武漢)中央高?；究蒲袠I務費資金(1610491B20)

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

張金標。E-mail: zhangjb@grmc.gov.cn