CSPRJ:基于數(shù)據(jù)傾斜的MapReduce連接查詢算法

周 婭,魏夏飛,熊 晗,胡彩林,李 玲

(桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院,廣西 桂林 541004)

1 引 言

數(shù)據(jù)指數(shù)級增長給海量數(shù)據(jù)(massive data)[1]分析處理帶來了嚴(yán)峻挑戰(zhàn),而MapReduce[2,3]是一種線性可伸縮編程模型,其具有良好可擴(kuò)展性、高可用性以及容錯(cuò)性,適用于海量數(shù)據(jù)密集型計(jì)算任務(wù).海量數(shù)據(jù)分析處理常常和MapReduce聯(lián)系到一起,因?yàn)閷?shí)時(shí)海量數(shù)據(jù)分析處理需要像MapReduce這樣并行計(jì)算框架來向數(shù)十、數(shù)百甚至數(shù)千臺計(jì)算機(jī)來并行處理.但是,分析處理的海量數(shù)據(jù)信息常常存在數(shù)據(jù)傾斜場景,而采用傳統(tǒng)MapReduce框架并行計(jì)算連接查詢算法難以對數(shù)據(jù)傾斜做到有效負(fù)載均衡,不利于充分發(fā)揮MapReduce集群并行計(jì)算特性.

本文主要從以下幾個(gè)方面論述:第1節(jié)介紹國內(nèi)外關(guān)于MapReduce連接查詢算法研究現(xiàn)狀及不足,并引出本文研究內(nèi)容;第2節(jié)簡述問題定義、MapReduce連接查詢算法.第3節(jié)詳細(xì)描述本文提出的算法思想與實(shí)現(xiàn);第4節(jié)通過實(shí)驗(yàn)驗(yàn)證本文提出的算法性能,并給出詳細(xì)分析;第5節(jié)對全文進(jìn)行總結(jié)與簡述下一步工作目標(biāo).

2 相關(guān)工作

連接查詢是海量數(shù)據(jù)分析處理核心操作算子之一,在日志分析、聯(lián)機(jī)分析處理等數(shù)據(jù)密集型計(jì)算領(lǐng)域也頻繁使用.海量數(shù)據(jù)連接查詢思想很多都來源于傳統(tǒng)數(shù)據(jù)庫中的join算法,并借助MapReduce并行計(jì)算框架來提升性能.目前,國內(nèi)外針對MapReduce并行計(jì)算框架連接查詢主要可分為3種類型:傳統(tǒng)MapReduce連接、基于改進(jìn)MapReduce連接和基于索引MapReduce連接.

傳統(tǒng)MapReduce連接通過自定義Map函數(shù)和Reduce函數(shù)實(shí)現(xiàn)連接功能,如文獻(xiàn)[4]設(shè)計(jì)兩表等值連接的標(biāo)準(zhǔn)重分區(qū)連接算法,在shuffle階段使具有相同連接屬性的數(shù)據(jù)分發(fā)到同一個(gè)Reducer節(jié)點(diǎn),在Reducer節(jié)點(diǎn)進(jìn)行笛卡爾連接查詢操作;文獻(xiàn)[5]設(shè)計(jì)兩表相似度連接算法,過濾不符合連接條件的數(shù)據(jù),減少I/O網(wǎng)絡(luò)通信與CPU計(jì)算開銷;文獻(xiàn)[6]設(shè)計(jì)多表等值連接算法,利用一個(gè)MapReduce作業(yè)處理星型連接與鏈?zhǔn)竭B接,簡化實(shí)現(xiàn)連接操作復(fù)雜性;文獻(xiàn)[7]采用一種新重定向輸出策略,滿足連接條件的數(shù)據(jù)可以一次性發(fā)送到同一個(gè)Reducer節(jié)點(diǎn)進(jìn)行連接查詢處理.上述這些算法的共性是實(shí)現(xiàn)簡單,主要是通過增加計(jì)算節(jié)點(diǎn)來線性擴(kuò)展計(jì)算能力,而對于所處理數(shù)據(jù)本身的特點(diǎn)則鮮少考慮.

基于改進(jìn)MapReduce連接,如文獻(xiàn)[8]提出CHMJ算法,對連接屬性進(jìn)行多副本一致性哈希策略,有效提高連接查詢效率;文獻(xiàn)[9]設(shè)計(jì)Map-Reduce-Merge新型編程框架,在Reduce階段后面附加Merge操作,可以方便地實(shí)現(xiàn)關(guān)系數(shù)據(jù)庫中的笛卡爾連接查詢操作;文獻(xiàn)[10]設(shè)計(jì)Map-Join-Reduce編程模型,在Map和Reduce之間增加Join操作,利用一個(gè)MapReduce作業(yè)就可以完成多表連接查詢操作.上述這些算法在一定程度上擴(kuò)展了傳統(tǒng)MapReduce框架,增強(qiáng)了分析處理海量數(shù)據(jù)的效率,但這些算法只能用于一些簡單的連接查詢處理,對于復(fù)雜查詢其性能并不理想.

基于索引MapReduce連接,如文獻(xiàn)[11]將索引結(jié)構(gòu)引入MapReduce計(jì)算框架,借助索引實(shí)現(xiàn)數(shù)據(jù)剪枝預(yù)處理,縮減待處理數(shù)據(jù)空間;文獻(xiàn)[12]在Hadoop[13]和Hive[14]的基礎(chǔ)上,設(shè)計(jì)HadoopDB系統(tǒng),充分利用傳統(tǒng)關(guān)系型數(shù)據(jù)庫中的索引機(jī)制提高連接效率;文獻(xiàn)[15]實(shí)現(xiàn)了SpatialHadoop,在存儲層采用傳統(tǒng)的空間索引技術(shù),如網(wǎng)格、R-樹、R+樹建立二級空間索引,在空間查詢場景下比傳統(tǒng)Hadoop大約快兩個(gè)數(shù)量級;文獻(xiàn)[16]基于垂直分組設(shè)計(jì)一個(gè)多表連接混合系統(tǒng)Llama,將多表連接查詢分解為無數(shù)據(jù)耦合多個(gè)子查詢,大大減少M(fèi)apReduce作業(yè)數(shù).上述這些算法將傳統(tǒng)數(shù)據(jù)庫的索引機(jī)制引入MapReduce框架,很大程度上提高了查詢效率,然而隨著處理數(shù)據(jù)的急劇增加維護(hù)索引的代價(jià)也隨之增加,查詢性能也急劇下降.

現(xiàn)有針對MapReduce框架連接查詢優(yōu)化算法大都從集群層面出發(fā),對于更細(xì)粒度數(shù)據(jù)傾斜導(dǎo)致MapReduce集群連接操作性能下降的研究甚少.本文將聚焦于數(shù)據(jù)傾斜場景下海量數(shù)據(jù)連接查詢算法研究,設(shè)計(jì)并實(shí)現(xiàn)統(tǒng)計(jì)傾斜輪詢分區(qū)連接查詢算法.通過實(shí)驗(yàn),對比本文提出的算法與傳統(tǒng)MapReduce框架并行連接查詢算法在不同數(shù)據(jù)傾斜率下連接查詢性能,并給出詳細(xì)分析.

3 連接查詢

根據(jù)連接操作進(jìn)行位置不同,可以將基于MapReduce框架的連接查詢大致分為MapSideJoin、ReduceSideJoin、SemiJoin三種類型.本文主要圍繞ReduceSideJoin展開研究.

3.1 問題定義

定義參加連接查詢的兩張表分別為C和O,C約定為主表,O約定為從表,Ci和Oj分別為C和O的屬性,nc和no分別為C和O屬性數(shù)量,則C和O屬性集C′和O′可表示為:

C′={Ci|1<=i<=nc}

O′={Oj|1<=j<=no}

其中,連接屬性x∈C′∩O′、y∈C′、z∈O′,不失一般性,連接條件約定為C.x=O.x,查詢條件約定為Sc和So,投影屬性約定為P,連接操作可以描述為:

σC.x =O.x(C×O)

投影操作可以描述為:

πp(C×O)

則本文的連接查詢可以定義為:

(πP(σC.x=O.x∧SC∧SO(C×O)))

其對應(yīng)的SQL查詢用例可表示如下所示:

(πC.y,O.z(σC.x=O.x∧SC∧SO(C×O)))

3.2 MapReduce連接算法

為了衡量與評價(jià)本文提出的算法性能,本文選擇3種傳統(tǒng)經(jīng)典MapReduce連接查詢算法作為參考標(biāo)準(zhǔn).這3種算法分別為標(biāo)準(zhǔn)重分區(qū)連接算法[4](StandardRepartitionJoin,以下簡稱SRJ),改進(jìn)重分區(qū)連接算法[4](ImprovedRepartitionJoin,以下簡稱IRJ),過濾型改進(jìn)重分區(qū)連接算法[5](WithFilterImprovedRepartitionJoin,以下簡稱WFIRJ).上述3種算法的特性、優(yōu)缺點(diǎn)及其應(yīng)用場景請參考相應(yīng)的文獻(xiàn),本文不再累述.

4 統(tǒng)計(jì)傾斜輪詢分區(qū)連接算法

在2.2節(jié)中,對3種傳統(tǒng)經(jīng)典MapReduce連接查詢算法進(jìn)行了簡單的介紹,這些算法都采用Hadoop平臺默認(rèn)哈希分區(qū)算法.哈希分區(qū)在數(shù)據(jù)均衡場景下能較有效的將數(shù)據(jù)均勻分發(fā)到各個(gè)Reducer節(jié)點(diǎn),較好利用MapReduce集群并行計(jì)算性能.在數(shù)據(jù)傾斜場景下,哈希分區(qū)分割數(shù)據(jù)集時(shí)并沒有考慮數(shù)據(jù)的具體情況,經(jīng)過哈希分區(qū)之后可能導(dǎo)致某個(gè)或某幾個(gè)Reducer節(jié)點(diǎn)處理大量數(shù)據(jù),而個(gè)別Reducer節(jié)點(diǎn)處理完少量數(shù)據(jù)之后處于閑等待狀態(tài),因此無法充分利用MapReduce集群并行計(jì)算能力.

本文針對ReduceSideJoin在數(shù)據(jù)傾斜場景下的性能瓶頸問題,設(shè)計(jì)并實(shí)現(xiàn)統(tǒng)計(jì)傾斜輪詢分區(qū)算法(CountSkewPollingRepartitionJoin,以下簡稱CSPRJ).在本文,我們主要描述CSPRJ算法的核心思想,而關(guān)于MapReduce框架的具體實(shí)現(xiàn)過程請查閱文獻(xiàn)[13].CSPRJ算法核心思想包含兩部分:統(tǒng)計(jì)傾斜與輪詢分區(qū).

4.1 統(tǒng)計(jì)傾斜

在Map階段對分析處理的記錄進(jìn)行統(tǒng)計(jì)傾斜信息.為此,定義3個(gè)全局計(jì)數(shù)器recordcounter、joinkeycounter、joinkey(這3個(gè)計(jì)數(shù)器分別代表整個(gè)作業(yè)進(jìn)行連接操作的記錄數(shù)、連接鍵數(shù)量、每個(gè)連接鍵對應(yīng)記錄數(shù)量),負(fù)責(zé)對記錄的信息進(jìn)行統(tǒng)計(jì).

首先,在Mapper節(jié)點(diǎn)執(zhí)行setup函數(shù),利用Hadoop的DistributedCache機(jī)制把連接屬性加載到Mapper節(jié)點(diǎn)緩存中;然后,執(zhí)行map函數(shù)對輸入分片記錄進(jìn)行解析,并判斷緩存中是否存在該連接屬性,如果存在則計(jì)數(shù)器進(jìn)行計(jì)數(shù)并進(jìn)行相應(yīng)處理,否則過濾掉該無效數(shù)據(jù),以減少網(wǎng)絡(luò)I/O傳輸與CPU計(jì)算開銷.統(tǒng)計(jì)傾斜流程可表示如圖1所示.

4.2 輪詢分區(qū)

在Shuffle階段對傾斜數(shù)據(jù)采用輪詢分區(qū)算法進(jìn)行分區(qū).為此,在處理數(shù)據(jù)時(shí)通過計(jì)算Map階段統(tǒng)計(jì)的計(jì)數(shù)器并判斷所處理的記錄是否屬于傾斜數(shù)據(jù).如果該條記錄不屬于傾斜數(shù)據(jù),則采用hashpartition算法對該條記錄進(jìn)行分區(qū),否則采用自定義輪詢函數(shù):

(key%reducenum+key/reducenum)%reducenum)

圖1 統(tǒng)計(jì)傾斜Fig.1 Count skew

對傾斜記錄進(jìn)行分區(qū).經(jīng)過輪詢函數(shù)處理將傾斜數(shù)據(jù)輪詢分發(fā)到不同的Reducer節(jié)點(diǎn),使各個(gè)Reducer節(jié)點(diǎn)處理的數(shù)

據(jù)量基本均衡,以充分利用MapReduce集群并行計(jì)算能力.輪詢分區(qū)流程如圖2所示.

圖2 輪詢分區(qū)Fig.2 Polling repartition

4.3 CSPRJ算法實(shí)現(xiàn)與執(zhí)行流程

CSPRJ算法計(jì)算框架與執(zhí)行流程可表示如圖3所示.

圖3 CSPRJ算法計(jì)算框架與執(zhí)行流程Fig.3 CSPRJ Algorithm Computing Framework and Execution Flow

基于4.1,4.2節(jié)的統(tǒng)計(jì)傾斜與輪詢分區(qū)思想,本節(jié)給出CSPRJ算法具體實(shí)現(xiàn)過程.

在Map階段:

1)基于4.1節(jié)的思想對輸入分片信息進(jìn)行采集,統(tǒng)計(jì)傾斜數(shù)據(jù)及過濾無法進(jìn)行連接操作的數(shù)據(jù);

2)對連接屬性添加標(biāo)簽組成combinekey作為鍵,并以,value>形式輸出.

在Shuffle階段:

1)基于4.2節(jié)的思想對傾斜數(shù)據(jù)采用輪詢分區(qū)算法,否則采用哈希分區(qū)算法對數(shù)據(jù)進(jìn)行分區(qū);

2)采用combinekey.tag字段對同一分區(qū)中的數(shù)據(jù)進(jìn)行排序,使分區(qū)中的數(shù)據(jù)以表為單位進(jìn)行排序,即一張表的數(shù)據(jù)始終排在另一張表前面;

3)采用combinekey.key對同一分區(qū)中的相關(guān)數(shù)據(jù)進(jìn)行分組,并以,list>形式發(fā)送給Reducer節(jié)點(diǎn).

在Reduce階段:

1)對combinekey相應(yīng)的list數(shù)據(jù)集進(jìn)行解析并緩存其中一張表的數(shù)據(jù),然后使用緩存中的數(shù)據(jù)與list中剩余數(shù)據(jù)集進(jìn)行笛卡爾連接查詢操作.

CSPRJ算法核心偽代碼描述如下所示:

Map階段:

輸入:Tablec,Tableo

輸出:,value>

Setup函數(shù)執(zhí)行①中語句塊

① DistributedCache(joinkey)

Map函數(shù)執(zhí)行②～⑦中語句塊

② For each MapInputSplitRecord

③ Decode(MapInputSplitRecord)

④ If(!DistributedCache().contains(joinkey.key))

Return;

End If

⑤ If(MapInputSplitRecord∈Tablec)

joinkeycounter++

combinekey

value(value+tag11

End If

⑥ If(MapInputSplitRecord∈Tableo)

recordcounter++

joinkey.put(key,counter++)

combinekey

value(value+tag22

End If

⑦ Emit,value>

End For

Shuffle階段:

Partition函數(shù)執(zhí)行如下語句塊

輸入:Partition(,value>)

①If(joinkey.get(combinekey.key) <(recordcounter / joinkeycounter))

hashcode(hash_func(combinekey.key)

Return hashcode % reducenum

② Else

Return ((combinekey.key % reducenum + combinekey.key / reducenum) % reducenum)

5 實(shí)驗(yàn)與結(jié)果分析

5.1 查詢用例描述

TPC-H[17]基準(zhǔn)數(shù)據(jù)集是查詢與事務(wù)處理常用性能測試數(shù)據(jù)集.本文以TPC-H中CUSTOMER和ORDERS兩張表作為連接查詢表,分別使用CUSTOMER表的custkey、custname字段和ORDERS表的custkey、clerk字段,兩張表通過字段custkey進(jìn)行連接.本文實(shí)驗(yàn)SQL查詢用例描述如下所示:

SELECT CUSTOMER.name,ORDERS.clerk

FROM CUSTOMER,ORDERS

WHERE CUSTOMER.custkey = ORDERS.custkey;

5.2 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

實(shí)驗(yàn)集群環(huán)境包括5個(gè)節(jié)點(diǎn),其中一個(gè)主控節(jié)點(diǎn),4個(gè)計(jì)算節(jié)點(diǎn).每個(gè)節(jié)點(diǎn)都配有雙核Intel(R) Xeon(R) CPU,主頻2.53GHz,4G內(nèi)存,500G存儲磁盤;節(jié)點(diǎn)間通過百兆內(nèi)部局域網(wǎng)互聯(lián);操作系統(tǒng)為Red Hat Linux 6.5.Hadoop版本為Hadoop2.6.4;實(shí)驗(yàn)數(shù)據(jù)集使用TPC-H中的CUSTOMER和ORDERS兩張表.TPC-H數(shù)據(jù)集是嚴(yán)格均勻的,本文根據(jù)實(shí)驗(yàn)設(shè)定對數(shù)據(jù)集進(jìn)行處理,設(shè)置多種傾斜率,數(shù)據(jù)連接率設(shè)定為80%(其中連接率約定為連接數(shù)據(jù)占總數(shù)據(jù)的百分比).實(shí)驗(yàn)測試數(shù)據(jù)如表1所示.

5.3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)采用MapReduce默認(rèn)分片大小,即128MB;設(shè)定Reduce分區(qū)數(shù)量為8;本文主要從兩個(gè)方面衡量算法性能:①不同傾斜率下連接查詢性能;②連接查詢中Map、Reduce的時(shí)間消耗.

5.3.1 不同傾斜率下連接查詢性能

實(shí)驗(yàn)環(huán)境與測試數(shù)據(jù)詳見5.2節(jié).為了客觀準(zhǔn)確評價(jià)SRJ、IRJ、WFIRJ與本文提出的CSPRJ算法性能,本節(jié)對數(shù)據(jù)連接率設(shè)定為80%,CUSTOMER表數(shù)據(jù)量固定為2萬條,ORDERS表數(shù)據(jù)量從2500萬條漸增至17500萬條,數(shù)據(jù)傾斜率分別設(shè)定為0、0.4和0.8三組,實(shí)驗(yàn)結(jié)果如圖4所示.從圖4可以得出如下分析.

表1 實(shí)驗(yàn)數(shù)據(jù)
Table 1 Experimental data

1)圖4(a)顯示數(shù)據(jù)均勻場景下,數(shù)據(jù)分發(fā)到各Reducer節(jié)點(diǎn)的數(shù)據(jù)量大致均衡,因此四種算法性能差異并不大;總體而言,WFIRJ與CSPRJ對無效數(shù)據(jù)進(jìn)行過濾,減少部分網(wǎng)絡(luò)I/O傳輸與CPU計(jì)算開銷,性能稍好.

2)圖4(b)、圖4(c)當(dāng)傾斜率為0.4與0.8時(shí),數(shù)據(jù)發(fā)生傾斜.SRJ分別只能進(jìn)行5組與3組實(shí)驗(yàn),這是因?yàn)閿?shù)據(jù)傾斜導(dǎo)致某個(gè)或某幾個(gè)Reducer節(jié)點(diǎn)需要緩存大量數(shù)據(jù)從而導(dǎo)致OOM異常;IRJ與WFIRJ在一定程度上避免了OOM異常,但當(dāng)數(shù)據(jù)發(fā)生傾斜時(shí),還是無法避免某個(gè)或某幾個(gè)Reducer節(jié)點(diǎn)處理大量數(shù)據(jù)的情況;WFIRJ與IRJ主要區(qū)別在于,WFIRJ在Map階段對不能進(jìn)行連接的無效數(shù)據(jù)進(jìn)行了過濾,但WFIRJ并沒有解決數(shù)據(jù)傾斜導(dǎo)致負(fù)載不均勻問題.

1)本文設(shè)計(jì)與實(shí)現(xiàn)的CSPRJ不僅避免了OOM異常、過濾無效數(shù)據(jù),而且經(jīng)過Map階段統(tǒng)計(jì)傾斜、Shuffle階段輪詢分區(qū),保證數(shù)據(jù)基本均勻分發(fā)到各個(gè)Reducer節(jié)點(diǎn),實(shí)現(xiàn)MapReduce集群節(jié)點(diǎn)間負(fù)載均衡、較好利用其并行計(jì)算特性.

圖4 不同傾斜率下連接查詢性能Fig.4 Join query performance under different skew rates

5.3.2 連接查詢中Map、Reduce時(shí)間消耗

在5.3.1節(jié)中對SRJ、IRJ、WFIRJ、CSPRJ這四種算法進(jìn)行了實(shí)驗(yàn)并給出較為詳細(xì)分析,本節(jié)將對上述四種算法在MapReduce中兩個(gè)核心操作Map和Reduce的性能評價(jià)與分析.為了對上述四種算法進(jìn)行客觀評價(jià)與分析,本節(jié)采用實(shí)驗(yàn)條件與5.3.1節(jié)相同,實(shí)驗(yàn)結(jié)果如圖5所示.從圖5可以得出如下分析:

1)由于SRJ在Map階段沒有對數(shù)據(jù)進(jìn)行額外預(yù)處理,所以不管數(shù)據(jù)是否傾斜SRJ在Map階段所消耗時(shí)間最少;而IRJ、WFIRJ和CSPRJ在Map階段對數(shù)據(jù)都做了相應(yīng)預(yù)處理損失了一些性能,其中WFIRJ和CSPRJ在Map階段對不能進(jìn)行連接的無效數(shù)據(jù)進(jìn)行了過濾,減少部分?jǐn)?shù)據(jù)寫磁盤操作,因此相對于IRJ,WFIRJ與CSPRJ在Map階段性能比IRJ略好.

2)本文所述四種算法在Map階段對數(shù)據(jù)進(jìn)行不同處理,從而導(dǎo)致在Reduce階段表現(xiàn)出不同性能.如圖5(a)所示,在數(shù)據(jù)均勻場景下這四種算法各個(gè)Reducer節(jié)點(diǎn)負(fù)載均衡,但相對于其他三種算法,SRJ在Reduce階段緩存所有進(jìn)行連接查詢的數(shù)據(jù),故性能相對較差;如圖5(b)、圖5(c)所示,當(dāng)數(shù)據(jù)發(fā)生傾斜時(shí),SRJ算法性能下降最快,并且由于SRJ在Reduce階段對所有數(shù)據(jù)進(jìn)行緩存從而導(dǎo)致OOM異常,無法得到正確結(jié)果;IRJ和WFIRJ有效解決SRJ在Reduce階段潛在的OOM問題,但當(dāng)數(shù)據(jù)發(fā)生傾斜時(shí),還是無法避免Reducer節(jié)點(diǎn)負(fù)載不均勻問題,所以當(dāng)數(shù)據(jù)發(fā)生傾斜時(shí),IRJ和WFIRJ性能都有不同程度下降.

3)針對數(shù)據(jù)傾斜導(dǎo)致各個(gè)Reducer節(jié)點(diǎn)負(fù)載不均,影響MapReduce集群并行性能問題.本文設(shè)計(jì)實(shí)現(xiàn)的CSPRJ有效解決了這個(gè)問題.從圖5(a)、圖5(b)、圖5(c)可以發(fā)現(xiàn),不管數(shù)據(jù)是否發(fā)生傾斜,CSPRJ均能保證各個(gè)Reducer節(jié)點(diǎn)達(dá)到基本負(fù)載均衡,充分利用MapReduce框架并行計(jì)算能力,提高連接查詢性能.

6 結(jié)束語

數(shù)據(jù)傾斜在海量數(shù)據(jù)分析處理中普遍存在,本文主要針對數(shù)據(jù)傾斜場景下連接查詢算法研究.通過分析SRJ、IRJ和WFIRJ等傳統(tǒng)經(jīng)典MapReduce并行計(jì)算框架連接查詢算法及其相應(yīng)適用場景與性能瓶頸;進(jìn)而,基于統(tǒng)計(jì)傾斜與輪詢分區(qū)兩個(gè)核心思想,設(shè)計(jì)并實(shí)現(xiàn)基于數(shù)據(jù)傾斜的統(tǒng)計(jì)傾斜輪詢分區(qū)連接算法.實(shí)驗(yàn)結(jié)果表明,本文提出的算法能有效處理數(shù)據(jù)傾斜場景下海量數(shù)據(jù)連接查詢,且在現(xiàn)實(shí)應(yīng)用場景中得到應(yīng)用并取得較好性能提升.本文的后續(xù)工作將從索引機(jī)制的研究展開,借鑒基于B樹、Hash等算法優(yōu)化提高M(jìn)apReduce連接查詢性能.

[1] Liu Xian-cong,Song Bin.Hadoop-based mass data TCP packet reassembly technology[J].Computer Engineering,2016,42(10):113-117.

[2] Chen J,Chen H,Wan X,et al.MR-ELM:a MapReduce-based framework for large-scale ELM training in big data era[J].Neural Computing and Applications,2016,27(1):101-110.

[3] Li R,Hu H,Li H,et al.MapReduce parallel programming model:a state-of-the-art survey[J].International Journal of Parallel Programming,2016,44(4):832-866.

[4] Blanas S,Patel J M,Ercegovac V,et al.A comparison of join algorithms for log processing in MapReduce[C].Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,ACM,2010:975-986.

[5] Vernica R,Carey M J,Li C.Efficient parallel set-similarity joins using MapReduce[C].ACM SIGMOD International Conference on Management of Data,SIGMOD 2010,Indianapolis,Indiana,USA,June,2010:495-506.

[6] Afrati F N,Ullman J D.Optimizing multiway joins in a Map-Reduce environment[J].IEEE Transactions on Knowledge & Data Engineering,2011,23(9):1282-1298.

[7] Hui Sun.Join processing and optimizing on large DataSets based on Hadoop framework[D].Nanjing:Nanjing University of Posts and Telecommunications,2013.

[8] Zhao Yan-rong,Wang Wei-ping,Meng Dan,et al.Efficient join query processing algorithm CHMJ based on Hadoop[J].Journal of Software,2012,23(8):2032-2041.

[9] Yang H C,Dasdan A,Hsiao R L,et al.Map-reduce-merge:simplified relational data processing on large clusters[C].ACM SIGMOD International Conference on Management of Data,ACM,2007:1029-1040.

[10] Jiang D,Tung A K H,Chen G.Map-join-reduce:toward scalable and efficient data analysis on large clusters[J].IEEE Transactions on Knowledge & Data Engineering,2011,23(9):1299-1311.

[11] Hungchih Yang,Parker D S.Traverse:simplified indexing on large map-reduce-merge clusters[C].Database Systems for Advanced Applications,International Conference,DASFAA 2009,Brisbane,Australia,April 21-23,Proceedings,2009:308-322.

[12] Abouzeid A,Bajda-Pawlikowski K,Abadi D,et al.HadoopDB:an architectural hybrid of MapReduce and DBMS technologies for analytical workloads[J].Proceedings of the Vldb Endowment,2009,2(1):922-933.

[13] Melorose J,Perroy R,Careas S.Hadoop definitive guide[M].Hadoop:The Definitive Guide,Yahoo! Press,2015:1-4.

[14] Vohra D.Apache hive[M].Practical Hadoop Ecosystem,Apress,2016.

[15] Eldawy A,Mokbel M F.SpatialHadoop:a MapReduce framework for spatial data[C].IEEE,International Conference on Data Engineering,IEEE,2016:1352-1363.

[16] Lin Y,Agrawal D,Chen C,et al.Llama:leveraging columnar storage for scalable join processing in the MapReduce framework[C].ACM SIGMOD International Conference on Management of Data,SIGMOD 2011,Athens,Greece,2011:961-972.

[17] Chiba T,Onodera T.Workload characterization and optimization of TPC-H queries on apache spark[C].IEEE International Symposium on Performance Analysis of Systems and Software,IEEE Computer Society,2016:112-121.