李素若

（荊楚理工學(xué)院，湖北 荊門 448000）

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

李素若

（荊楚理工學(xué)院，湖北 荊門 448000）

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

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

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

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

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

1．QR－樹索引

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

n所表示的就是Qt節(jié)點(diǎn)的數(shù)量，如果依據(jù)廣度便歷次序?yàn)樗鼈兙幪?，就可以表示為：Qt0，Qt1……Qtn－1。Qt在這里將全部空間數(shù)據(jù)區(qū)域都進(jìn)行了劃分，共分割為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é)點(diǎn)及n個子數(shù)據(jù)空余區(qū)域之間緊密相聯(lián)系在一起。綜上所述，QR－樹數(shù)據(jù)空間的結(jié)構(gòu)就應(yīng)該如圖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ù)主要涵蓋兩大類型：空間并行與時間并行?？臻g并行用到了多個處理器進(jìn)行并發(fā)式的計算方式。時間并行則是典型的流水線技術(shù)。而并行計算根據(jù)其工作流程又分為兩類：數(shù)據(jù)并行和任務(wù)并行。數(shù)據(jù)并行會將一個大任務(wù)劃分為諸多子任務(wù)，并映射到不同的處理器或計算節(jié)點(diǎn)上同步處理，這樣可以大大提升對并行任務(wù)的完成效率。而管理和運(yùn)作這些計算節(jié)點(diǎn)的支配者就是集群系統(tǒng)，集群系統(tǒng)將離散的計算機(jī)網(wǎng)絡(luò)重新組合起來，保證網(wǎng)絡(luò)中各個子系統(tǒng)能夠緊密協(xié)作。大企業(yè)會利用集群系統(tǒng)將高性能的計算機(jī)網(wǎng)絡(luò)集合起來形成計算機(jī)集群，這種數(shù)據(jù)密集型的應(yīng)用對企業(yè)的集群技術(shù)發(fā)展很有幫助。尤其是在開源云平臺Hadoop問世以后，集群系統(tǒng)的可擴(kuò)展功能也越來越多，比如在低端商用計算機(jī)上也能構(gòu)建平臺，讓并行計算技術(shù)與集群技術(shù)更加緊密的結(jié)合，從而保證對海量空間數(shù)據(jù)的穩(wěn)定管理和隨時獲?。?］。

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

（1）MapReduce的實(shí)現(xiàn)機(jī)制

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

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

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

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

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

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

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

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

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

第二，可以為基于MapReduce的并行編程模型添加combiner，因?yàn)樵诓⑿杏嬎愠绦蛞婕暗揭恍┓诸惥酆虾瘮?shù)，所以添加combiner可以完成數(shù)據(jù)到達(dá)reduce端的初始聚合工作，這樣就能大量降低寫入磁盤的數(shù)據(jù)量與通過網(wǎng)絡(luò)途徑傳輸reduce的數(shù)據(jù)量，由此一來整體并行計算的性能也會隨之提高。

第三，也要考慮選擇合適的二進(jìn)制Writable來進(jìn)一步維護(hù)編程模型性能。一般來說，二進(jìn)制Writable能夠做到對文件轉(zhuǎn)換時消耗的降低，從而降低中間數(shù)據(jù)結(jié)果所占用的空間，而減少中間結(jié)果空間也能夠?yàn)椴⑿杏嬎銕砀叩男阅埽?］。

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

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

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

（1）生成并行連接任務(wù)

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

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

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

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

（2）分布空間連接計算

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

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

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

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

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

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

三、結(jié)論

基于MapReduce的分布式空間連接算法是空間數(shù)據(jù)庫中一種極為復(fù)雜的操作過程，它對空間數(shù)據(jù)庫領(lǐng)域的發(fā)展具有較為深遠(yuǎn)的現(xiàn)實(shí)影響。所以隨著企業(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］．合肥：中國科學(xué)技術(shù)大學(xué)，2014．16－23．

［3］霍樹民．基于Hadoop的海量影像數(shù)據(jù)管理關(guān)鍵技術(shù)研究［D］．長沙：國防科學(xué)技術(shù)大學(xué)，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］．贛州：江西理工大學(xué)，2013．28－40．

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

［9］鄭啟龍，房明，汪勝，等．基于MapReduce模型的并行科學(xué)計算［J］．微電子學(xué)與計算機(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－），男，湖北荊門人，荊楚理工學(xué)院計算機(jī)工程學(xué)院副教授，碩士，研究方向：計算機(jī)網(wǎng)絡(luò)、軟件工程。

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