李素若

（荊楚理工學院，湖北 荊門 448000）

基于MapReduce分布式連接算法優(yōu)化技術(shù)研究

李素若

（荊楚理工學院，湖北 荊門 448000）

為了解決大規(guī)模數(shù)據(jù)集的并行運算問題，采用以映射與歸約為主體思想的編程模型MapReduce，以分布式QR－樹索引結(jié)構(gòu)與分布式并行編程模型MapReduce為組合進行連接算法設(shè)計。研究結(jié)果表明：采用該算法使得數(shù)據(jù)分布式并行編程計算更加便捷，也解決了傳統(tǒng)單機集群系統(tǒng)無法滿足海量數(shù)據(jù)時空開銷的迫切需求。在云計算背景下研究MapReduce分布式空間連接算法有很大的意義和價值。

MapReduce；集群技術(shù)；QR－樹索引；分布式空間連接；算法；優(yōu)化

MapReduce是誕生于Google所設(shè)計的并行編程模型和分布式計算框架，它是云計算中的關(guān)鍵技術(shù)，它是開源的，所以能為分布式空間連接計算提供實踐平臺［1］。在業(yè)界，基于MapReduce的分布式并行計算模型已經(jīng)掀起了一場“集群革命”，專門針對于大規(guī)模數(shù)據(jù)集的分析和處理，完全代替了原有的高性能節(jié)點計算模式，證明了其極高的可用性、可伸縮性和高容錯性。因此MapReduce分布式連接并行算法在各個領(lǐng)域獲得廣泛認可和應用也就成為必然。

一、基于MapReduce分布式連接算法的相關(guān)理論

基于MapReduce理論的分布式連接算法就是要在偌大的數(shù)據(jù)庫空間中快速鏈接索引相關(guān)數(shù)據(jù)并獲取，所以其算法過程具有化解其龐大性與復雜性的特征。本文也基于此介紹了與分布式連接算法相關(guān)的幾個理論，為后來的算法優(yōu)化技術(shù)研究打好基礎(chǔ)。

1．QR－樹索引

QR－樹索引基于R－樹索引展開，它的基本思想是要對一定的實際地理空間范圍進行合理的四叉樹規(guī)劃。換言之就是把二維空間范圍內(nèi)的常規(guī)四象限劃分為多個子索引空間，隨后通過R－樹構(gòu)建方式，借助GIS等系統(tǒng)軟件技術(shù)為數(shù)據(jù)庫系統(tǒng)應用擴容。如果當索引數(shù)據(jù)量不斷增加，R－樹與四叉樹不能解決數(shù)據(jù)存儲量空間交疊區(qū)域快速擴容問題時，就可以利用QR－樹來解決該問題。QR－樹所表現(xiàn)的是一棵具有深度d的四叉樹Qt和n棵R－樹所構(gòu)成的共同整體。在QR－樹中遵循以k為空間維度的公式即：

n所表示的就是Qt節(jié)點的數(shù)量，如果依據(jù)廣度便歷次序為它們編號，就可以表示為：Qt0，Qt1……Qtn－1。Qt在這里將全部空間數(shù)據(jù)區(qū)域都進行了劃分，共分割為n個d級別子空間數(shù)據(jù)區(qū)域，最后為他們依次編號記錄為S0，S1……，Sn－1（S0＝S）。在這里每個級別的數(shù)據(jù)區(qū)域之間都不能發(fā)生交疊，而根據(jù)R－樹可以將數(shù)據(jù)空間區(qū)域表示為Rt0，Rt1……，Rtn－1這些數(shù)據(jù)分別與Qt中的n個節(jié)點及n個子數(shù)據(jù)空余區(qū)域之間緊密相聯(lián)系在一起。綜上所述，QR－樹數(shù)據(jù)空間的結(jié)構(gòu)就應該如圖1。

如圖1所示，QR－樹中包括了2棵四叉樹和5棵子R－樹所組成，所以它的空間數(shù)據(jù)區(qū)域也被劃分為2個級別5個子空間。在這其中，S0～S4以及Rt0～Rt4這兩大數(shù)據(jù)集合之間呈緊密聯(lián)系狀態(tài)［2］。

2．并行計算技術(shù)

在處理海量空間數(shù)據(jù)方面，并行計算技術(shù)顯然要優(yōu)于串行計算。并行計算技術(shù)主要涵蓋兩大類型：空間并行與時間并行。空間并行用到了多個處理器進行并發(fā)式的計算方式。時間并行則是典型的流水線技術(shù)。而并行計算根據(jù)其工作流程又分為兩類：數(shù)據(jù)并行和任務并行。數(shù)據(jù)并行會將一個大任務劃分為諸多子任務，并映射到不同的處理器或計算節(jié)點上同步處理，這樣可以大大提升對并行任務的完成效率。而管理和運作這些計算節(jié)點的支配者就是集群系統(tǒng)，集群系統(tǒng)將離散的計算機網(wǎng)絡重新組合起來，保證網(wǎng)絡中各個子系統(tǒng)能夠緊密協(xié)作。大企業(yè)會利用集群系統(tǒng)將高性能的計算機網(wǎng)絡集合起來形成計算機集群，這種數(shù)據(jù)密集型的應用對企業(yè)的集群技術(shù)發(fā)展很有幫助。尤其是在開源云平臺Hadoop問世以后，集群系統(tǒng)的可擴展功能也越來越多，比如在低端商用計算機上也能構(gòu)建平臺，讓并行計算技術(shù)與集群技術(shù)更加緊密的結(jié)合，從而保證對海量空間數(shù)據(jù)的穩(wěn)定管理和隨時獲?。?］。

目前企業(yè)所應用的集群技術(shù)主要有兩種，MPI和MapReduce，本文重點介紹MapReduce集群技術(shù)。MapReduce是典型的分布式計算軟件構(gòu)架，它的特點優(yōu)勢明顯，能夠合理有效的屏蔽底層實現(xiàn)更多細節(jié)，這就為程序員的編程工作降低了難度，讓并行程序編寫更加高效化。由于Hadoop平臺的出現(xiàn)，所以MapReduce也真正實現(xiàn)了開源，它在任務調(diào)度、實現(xiàn)機制和性能調(diào)優(yōu)三方面都有提升。

（1）MapReduce的實現(xiàn)機制

首先說實現(xiàn)機制，MapReduce分布式并行計算框架是由一個JobTracker和眾多個TaskTracker所組成的［4－6］。這其中JobTracker主要負責調(diào)度組成某個作業(yè)所涉及到的所有分布于集群TaskTracker中的子任務。而JobTracker則負責監(jiān)控這些任務的實際執(zhí)行狀況，當有任務分配失敗，它會對其進行重新分配。當客戶提交Job時，JobTracker就會接收和處理Job信息并進行信息配置，然后將配置信息發(fā)送給各個Task－Tracker，對其進行調(diào)度組成處理，這樣就構(gòu)成了一個完整的MapReduce分布式計算模型，它的程序運作流程如圖2。

圖2描述了MapReduce集群技術(shù)程序的整體運作流程?；旧?，當客戶提供Job任務時，JobTracker就會負責調(diào)度任務，通過執(zhí)行Map函數(shù)和Reduce函數(shù)來監(jiān)控Map和Reduce兩階段過程。而在數(shù)據(jù)輸入階段，用戶會通過ImputFormat來實現(xiàn)RecordReader接口，并將接口中的功能分片解析轉(zhuǎn)化為鍵值對，提供給Map函數(shù)繼續(xù)操作。當Map函數(shù)階段操作完畢后，就會進入Reduce階段，它一般要經(jīng)歷混洗、排序和Reduce三個過程。混洗階段主要負責為MapReduce計算框架生成key，并將相關(guān)結(jié)果傳輸給Reduce進行key區(qū)間內(nèi)節(jié)點值的獲??；而排序階段則與混洗階段同步展開，它為數(shù)據(jù)形成key鍵值的集合；最后是Reduce階段，此時數(shù)據(jù)集合已經(jīng)形成，利用Reduce方法對數(shù)據(jù)進行最終處理，然后再借助Output－Format將處理好的數(shù)據(jù)結(jié)果傳輸?shù)紿DFS上。

圖2 MapReduce集群技術(shù)程序運作流程示意圖

（2）MapReduce的任務調(diào)度

MapReduce的任務調(diào)度受限要保證數(shù)據(jù)分布的均勻性，這樣Map任務才能在本地順利執(zhí)行。另外，也要考慮到MapReduce任務調(diào)度策略的公平性，注意JobTracker在為Worker分配任務時可能存在的沖突性。而為了最大限度降低響應時間，MapReduce并行計算框架也采用了預測執(zhí)行機制。它的思路是如果某個所獲取的節(jié)點性能較差，就將該節(jié)點作為備份任務轉(zhuǎn)移到其它節(jié)點上輔助運行。

（3）MapReduce的性能調(diào)優(yōu)

利用MapReduce進行并行編程模型編寫中并行程序的性能調(diào)優(yōu)可以幫助其快速達到預期效果。用戶可以自定義Map和Reduce任務數(shù)量及系統(tǒng)參數(shù)。近些年來，MapReduce并行編程模型在執(zhí)行性能方面也得到了優(yōu)化，它的具體優(yōu)化主要體現(xiàn)在以下幾大方面。

第一，對集群參數(shù)的合理配置，對MapReduce中所使用的存儲設(shè)備進行mount到noatime選項的設(shè)

置，就可以提高磁盤的I／O性能，減少配置文件中內(nèi)存分配的mapred．child．java．opts屬性，從而提高分布式連接算法的性能。

第二，可以為基于MapReduce的并行編程模型添加combiner，因為在并行計算程序要涉及到一些分類聚合函數(shù)，所以添加combiner可以完成數(shù)據(jù)到達reduce端的初始聚合工作，這樣就能大量降低寫入磁盤的數(shù)據(jù)量與通過網(wǎng)絡途徑傳輸reduce的數(shù)據(jù)量，由此一來整體并行計算的性能也會隨之提高。

第三，也要考慮選擇合適的二進制Writable來進一步維護編程模型性能。一般來說，二進制Writable能夠做到對文件轉(zhuǎn)換時消耗的降低，從而降低中間數(shù)據(jù)結(jié)果所占用的空間，而減少中間結(jié)果空間也能夠為并行計算帶來更高的性能［7］。

二、基于MapReduce分布式空間連接算法的設(shè)計與優(yōu)化

1．分布式空間連接算法的設(shè)計

基于QR－樹和MapReduce的空間連接算法要依靠作業(yè)Job和MapReduce共同完成。它的具體操作步驟主要有對并行連接任務的生成；對空間連接查詢的計算。

（1）生成并行連接任務

若要生成并行連接任務要行使以下三個步驟，初始任務生成——初始任務分發(fā)——并行連接任務生成。這三個步驟都要通過MapReduce并行計算框架中的工作機制和作業(yè)Job進行預處理。

首先是初始任務生成，它主要是在編程模型的主節(jié)點上提交job作業(yè)前執(zhí)行，它的具體任務生成描述如下：為空間數(shù)據(jù)假設(shè)兩層空間關(guān)系R和S，為它們分別構(gòu)建QR－樹索引，并將它們重新標記為A與B。在掃描它們的根節(jié)點時就會產(chǎn)生初始任務，初始任務以一個三元組T＝｛Ai，Bj，BBoxij｝?？紤]到初始任務的生成僅僅對AB根節(jié)點進行掃描，所以空間復雜度很低，可以在job作業(yè)提交之前就快速高效完成。

其次是初始任務分發(fā)。初始任務分發(fā)是將初始任務集發(fā)布給Reduce任務開展并行處理工作，它需要Map任務配合共同完成。Map任務的介入可以為初始任務生成任務集｛Ai，Bj，BBoxij｝。

最后是并行連接任務生成，它需要P個Reduce任務同時處理，而P也代表了并行連接任務所生成的同步并行度。當并行連接任務生成并經(jīng)過Reduce任務處理之后，就會和上文中所提到的A／B子R－樹級別共同計算出交疊的子R－樹元組，它們就是并行連接任務的結(jié)果集［8］。

（2）分布空間連接計算

分布空間連接計算也可以分為兩個步驟，并行連接任務分發(fā)和執(zhí)行，它們都是基于MapReduce并行計算框架工作機制中的Map階段任務分配及Reduce階段的任務執(zhí)行所對應完成的。在連接計算過程中，MapReduce函數(shù)輸入輸出鍵值如下表1所示。

表1 分布式空間連接計算的MapReduce函數(shù)輸入輸出情況表格

2．分布式空間連接算法的優(yōu)化

在實際的應用中，我們發(fā)現(xiàn)分布式空間連接算法是存在連接和訪問問題的，而且算法性能也有待提升。本文主要基于實時緩存的方法優(yōu)化該算法。它得益于Hadoop分布式緩存機制所帶來的啟示。它的原理就是在提交Job作業(yè)之前，就對集群系統(tǒng)中的所有節(jié)點進行共享數(shù)據(jù)的復制和分發(fā)。而在算法方面，它會以并行連接任務生成與空間連接計算來解決存在的并發(fā)訪問問題。它的具體優(yōu)化步驟如下：

當并行連接任務生成過程中，要訪問QR－樹根節(jié)點，并且檢查本地數(shù)據(jù)空間是否存在緩存的分布式QR－樹子樹索引文件。如果不存在，則將索引文件恢復到本地磁盤上，再訪問本地磁盤數(shù)據(jù)空間；如果存在，則直接訪問本地磁盤上的緩存索引文件。分布式空間連接計算階段和并行連接任務生成過程同理。

總之，要考慮在優(yōu)化算法時空間數(shù)據(jù)庫中可能出現(xiàn)的實時緩存為本地磁盤所帶來的存儲負載問題，所以有效的優(yōu)化可以大幅度提升算法的性能，提升對大規(guī)模數(shù)據(jù)分析及處理的有效性［9］。

三、結(jié)論

基于MapReduce的分布式空間連接算法是空間數(shù)據(jù)庫中一種極為復雜的操作過程，它對空間數(shù)據(jù)庫領(lǐng)域的發(fā)展具有較為深遠的現(xiàn)實影響。所以隨著企業(yè)空間數(shù)據(jù)規(guī)模的與日俱增，利用MapReduce這樣的云計算技術(shù)來提高海量空間數(shù)據(jù)連接、計算和查詢已經(jīng)逐漸成為趨勢，這也證明了在云計算背景下研究MapReduce分布式空間連接算法的意義和價值。

［1］Jeffrey Dean，Sanjay Ghemawat．MapReduce：simplified data processing on large clusters［J］．Communications of the ACM，2008，51（1）：107－113．

［2］張常淳．基于MapReduce的大數(shù)據(jù)連接算法的設(shè)計與優(yōu)化［D］．合肥：中國科學技術(shù)大學，2014．16－23．

［3］霍樹民．基于Hadoop的海量影像數(shù)據(jù)管理關(guān)鍵技術(shù)研究［D］．長沙：國防科學技術(shù)大學，2010．［4］G．Dan．Development of Massive Astronomy Data Federation System and Research of Data Mining Algorithms–Tool Development and Algorithm Research［J］．Publications of the Astronomical Society of the Pacific，2008，120（874）：1357．

［5］Y．－W．Huang，N．Jing，and E．A．Rundensteiner，“Spatial Joins Using R－trees：Breadth－First Traversal with Global Optimizations［Z］．in Proceedings of the 23rd International Conference on Very Large Data Bases，San Francisco，CA，USA， 1997．396－405．

［6］P．Mishra and M．H．Eich．Join processing in relational databases［J］．ACM Comput．Surv．，1992，24（1）：63－113．

［7］劉杰．基于MapReduce的分布式空間連接查詢研究［D］．贛州：江西理工大學，2013．28－40．

［8］陳勇旭，陳夢杰，劉雪冰，等．基于MapReduce的連接聚集查詢算法研究［J］．計算機研究與發(fā)展，2013，50（z1）：306－311．

［9］鄭啟龍，房明，汪勝，等．基于MapReduce模型的并行科學計算［J］．微電子學與計算機，2009，26（8）：13－17．

Research on the Optimization Technology of Distributed Connection Algorithm Based on MapReduce

Li Su－ruo
（Jingchu University of Technology，Jingmen Hubei 448000，China）

To solve the problem of parallel computing with large data sets，using the mapping and reduction to the Juche idea about programming model MapReduce，distributed QR－tree index structure MapReduce distributed parallel programming model is a combination of the connection algorithm．The results show that the algorithm so that the data distributed computing parallel programming easier．The traditional single cluster system can not meet the urgent needs of massive data time and space overhead．In cloud computing，MapReduce distributed spatial join algorithm has great significance and value．

MapReduce；cluster；QR－tree；distributed spatical join；algorithm；optimization

TP311．13

A

1672-0547（2015）05-0107-03

2015－09－23

李素若（1969－），男，湖北荊門人，荊楚理工學院計算機工程學院副教授，碩士，研究方向：計算機網(wǎng)絡、軟件工程。

2015年湖北省教育廳科學研究項目“基于Mapreducn分布式連接算法優(yōu)化技術(shù)研究”（B2015241）；荊楚理工學院校級科研項目“面向大規(guī)模科學數(shù)據(jù)的基于Mapreducn分布式連接算法優(yōu)化技術(shù)研究”（ZR201405）。