張敬偉，尚宏佳，錢俊彥，周 萍，楊 青+

1.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

2.桂林電子科技大學(xué) 廣西云計(jì)算與大數(shù)據(jù)協(xié)同創(chuàng)新中心，廣西 桂林 541004

3.桂林電子科技大學(xué) 廣西自動(dòng)檢測(cè)技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

非均勻數(shù)據(jù)分布下的MapReduce連接查詢算法優(yōu)化*

張敬偉1,2，尚宏佳1，錢俊彥1，周 萍3，楊 青3+

1.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

2.桂林電子科技大學(xué) 廣西云計(jì)算與大數(shù)據(jù)協(xié)同創(chuàng)新中心，廣西 桂林 541004

3.桂林電子科技大學(xué) 廣西自動(dòng)檢測(cè)技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

MapReduce分布式計(jì)算框架有助于提升大規(guī)模數(shù)據(jù)連接查詢的效率，但當(dāng)連接屬性分布不均勻時(shí)，其簡(jiǎn)單的散列策略容易導(dǎo)致計(jì)算節(jié)點(diǎn)間負(fù)載不均衡，影響作業(yè)的整體性能。針對(duì)連接查詢操作中的數(shù)據(jù)傾斜問題，研究了MapReduce框架下大規(guī)模數(shù)據(jù)連接查詢操作的優(yōu)化算法。首先對(duì)經(jīng)典的改進(jìn)重分區(qū)連接查詢算法進(jìn)行實(shí)驗(yàn)分析，研究了傳統(tǒng)MapReduce計(jì)算框架下連接查詢操作的執(zhí)行流程，找出了基于MapReduce計(jì)算框架的連接查詢算法在數(shù)據(jù)分布不均勻時(shí)的性能瓶頸；進(jìn)而提出了組合分割平衡分區(qū)優(yōu)化策略，設(shè)計(jì)并實(shí)現(xiàn)了基于組合分割平衡分區(qū)優(yōu)化策略的改進(jìn)型連接查詢算法。實(shí)驗(yàn)結(jié)果表明，提出的優(yōu)化策略在大規(guī)模數(shù)據(jù)的連接查詢處理上很好地解決了數(shù)據(jù)傾斜帶來的性能影響，具有好的時(shí)間性能和可擴(kuò)展性。

連接查詢；MapReduce；數(shù)據(jù)傾斜

1 引言

多樣化的應(yīng)用促進(jìn)了數(shù)據(jù)的快速積累，GB、TB級(jí)的數(shù)據(jù)分析已成為常態(tài)。在互聯(lián)網(wǎng)領(lǐng)域，全球最大中文搜索引擎百度，收錄了全世界萬億個(gè)網(wǎng)頁，數(shù)據(jù)總量接近1 000 PB（http://chgcx.sirt.edu.cn/a/2015/ 12/06/2015120619241012299.html）。在零售業(yè)，沃爾瑪每小時(shí)都會(huì)積累2.5 PB的消費(fèi)數(shù)據(jù)（http://news. hexun.com/2016-05-13/183843576.html）。在金融行業(yè)，國內(nèi)“銀聯(lián)”銀行卡發(fā)行量接近40億張，每天需處理超過600億次交易，年新增的數(shù)據(jù)量也達(dá)到數(shù)十PB。上述的大規(guī)模數(shù)據(jù)及其分析應(yīng)用中，連接查詢操作是最頻繁使用的算子之一，連接查詢操作的性能對(duì)大規(guī)模數(shù)據(jù)分析效率具有重要影響。

MapReduce計(jì)算架構(gòu)具有較好的可擴(kuò)展性、高可用性以及容錯(cuò)性，被廣泛地應(yīng)用于大規(guī)模數(shù)據(jù)分析相關(guān)工作中。然而，大規(guī)模數(shù)據(jù)中經(jīng)常會(huì)出現(xiàn)數(shù)據(jù)分布不均勻的情況，采用MapReduce計(jì)算框架的連接查詢操作并不總是十分有效，會(huì)導(dǎo)致各計(jì)算節(jié)點(diǎn)負(fù)載不均衡，降低連接查詢操作效率，影響大規(guī)模數(shù)據(jù)分析性能。因此，本文將致力解決大規(guī)模數(shù)據(jù)連接操作過程中數(shù)據(jù)分布不均勻?qū)е伦鳂I(yè)性能下降的問題，提升大規(guī)模數(shù)據(jù)連接查詢的效率。

2 相關(guān)工作

連接查詢操作是關(guān)系型數(shù)據(jù)庫的核心操作算子，在日志分析、聯(lián)機(jī)分析處理等領(lǐng)域也被頻繁使用，大規(guī)模數(shù)據(jù)的連接查詢需借助MapReduce計(jì)算框架來提升性能。目前，針對(duì)MapReduce計(jì)算框架下的連接查詢操作及其優(yōu)化工作可歸納為以下3類。

（1）基于傳統(tǒng)MapReduce框架的連接優(yōu)化研究。該類研究不需要對(duì)數(shù)據(jù)重新進(jìn)行組織，實(shí)現(xiàn)過程也較為簡(jiǎn)單，但應(yīng)對(duì)復(fù)雜連接查詢操作時(shí)，往往需要多個(gè)連續(xù)的MapReduce作業(yè)，執(zhí)行過程較為復(fù)雜。文獻(xiàn)[1]設(shè)計(jì)了兩表等值連接的標(biāo)準(zhǔn)重分區(qū)連接算法，在云數(shù)據(jù)管理系統(tǒng)中有較好的應(yīng)用，但當(dāng)數(shù)據(jù)量較大時(shí)，Reduce階段可能會(huì)出現(xiàn)內(nèi)存溢出。文獻(xiàn)[2]為了解決標(biāo)準(zhǔn)重分區(qū)連接算法內(nèi)存消耗較大的問題，設(shè)計(jì)了改進(jìn)標(biāo)準(zhǔn)重分區(qū)連接算法，一定程度降低了Reduce階段對(duì)內(nèi)存容量的要求。文獻(xiàn)[1]設(shè)計(jì)了當(dāng)兩表數(shù)據(jù)量相差很大時(shí)，僅需一個(gè)無Reduce階段的MapReduce作業(yè)且具有很高效率的廣播連接算法，但當(dāng)兩張表數(shù)據(jù)量都較大時(shí)，Map階段可能會(huì)出現(xiàn)內(nèi)存溢出。文獻(xiàn)[2]在廣播算法的基礎(chǔ)上設(shè)計(jì)了半連接算法，對(duì)較小表進(jìn)行過濾，減少了廣播過程中數(shù)據(jù)傳輸量和Map階段的內(nèi)存消耗，但需連續(xù)的3個(gè)作業(yè)才能完成，執(zhí)行過程較為復(fù)雜。文獻(xiàn)[2]設(shè)計(jì)了分片半連接算法，更細(xì)粒度地對(duì)較小表進(jìn)行過濾，進(jìn)一步減少了廣播過程中數(shù)據(jù)傳輸量和Map階段的內(nèi)存消耗，但同樣存在執(zhí)行過程較為復(fù)雜的不足。文獻(xiàn)[3]設(shè)計(jì)了冗余重分區(qū)算法來處理兩表非等值連接，利用二維矩陣較為簡(jiǎn)潔地完成了復(fù)雜的非等值連接操作，但在數(shù)據(jù)混洗階段網(wǎng)絡(luò)傳輸代價(jià)較大。文獻(xiàn)[4]設(shè)計(jì)了兩表相似度連接的算法，濾掉不可能成為最終結(jié)果的數(shù)據(jù)，有效地減少了網(wǎng)絡(luò)傳輸代價(jià)，但其應(yīng)用范圍僅僅限于文本字符串的相似性連接。文獻(xiàn)[5]設(shè)計(jì)了利用一個(gè)MapReduce作業(yè)處理星型連接與鏈?zhǔn)竭B接的多表等值連接算法，很大程度地簡(jiǎn)化了實(shí)現(xiàn)多表連接操作的復(fù)雜性，但隨著連接表數(shù)目的增加，其中間數(shù)據(jù)量將急劇增加。文獻(xiàn)[6]提出了網(wǎng)絡(luò)感知多路連接算法，在多路連接方面具有較高效率，但僅適用于兩張大表和多個(gè)放在同一個(gè)Reducer節(jié)點(diǎn)的小表，且兩張大表之間必須有連接屬性。文獻(xiàn)[7]設(shè)計(jì)了基于數(shù)據(jù)本地化計(jì)算的連接查詢處理算法，一定程度地提高了連接查詢效率。

（2）基于改進(jìn)MapReduce框架的連接優(yōu)化研究。該類研究從集群層面對(duì)MapReduce計(jì)算框架進(jìn)行改進(jìn)，減少了連接查詢過程中MapReduce作業(yè)的數(shù)目和中間數(shù)據(jù)量，但增加了算法的實(shí)現(xiàn)難度。文獻(xiàn)[8]設(shè)計(jì)了Map-Reduce-Merge新型編程框架，在Reduce階段后面附加一個(gè)Merge操作，加強(qiáng)了原有的Map-Reduce計(jì)算框架，可以方便地實(shí)現(xiàn)關(guān)系數(shù)據(jù)庫中的連接和笛卡爾積操作。文獻(xiàn)[9]將索引結(jié)構(gòu)引入到Map-Reduce-Merge計(jì)算框架上，借助索引技術(shù)在Map-Reduce-Merge上實(shí)現(xiàn)數(shù)據(jù)剪枝預(yù)處理，縮小了待處理數(shù)據(jù)空間。文獻(xiàn)[10]設(shè)計(jì)了Map-Join-Reduce的編程模型，在Map和Reduce之間增加一個(gè)Join操作，從多個(gè)數(shù)據(jù)源讀取數(shù)據(jù)，利用一個(gè)MapReduce作業(yè)就可以完成多表連接操作。文獻(xiàn)[11]為MapReduce增加了一個(gè)全局節(jié)點(diǎn)，用于接收、存儲(chǔ)和更新少量的全局信息，對(duì)Mapper生成的中間結(jié)果進(jìn)行過濾，減少了混洗代價(jià)和網(wǎng)絡(luò)傳輸。

（3）基于數(shù)據(jù)索引的連接優(yōu)化研究。該類研究利用索引對(duì)數(shù)據(jù)進(jìn)行有效過濾，一定程度地提高了連接查詢的效率，但需要對(duì)數(shù)據(jù)進(jìn)行重新組織。文獻(xiàn)[12]在Hadoop和Hive的基礎(chǔ)上，設(shè)計(jì)了HadoopDB系統(tǒng)，充分利用傳統(tǒng)關(guān)系型數(shù)據(jù)庫中的索引及查詢優(yōu)化機(jī)制提高連接查詢的效率，但其索引的容錯(cuò)性較弱。文獻(xiàn)[13]利用MapReduce提供的用戶自定義函數(shù)構(gòu)建索引設(shè)計(jì)了Hadoop++系統(tǒng)，使用寄宿索引技術(shù)提高數(shù)據(jù)查詢和連接效率，但其索引構(gòu)建代價(jià)較高。文獻(xiàn)[14]針對(duì)Hadoop++建立索引代價(jià)較高的不足，提出了HAIL，給每個(gè)文件的不同備份建立相應(yīng)的索引，提高數(shù)據(jù)查詢和連接的效率。文獻(xiàn)[15]基于垂直分組設(shè)計(jì)了多表連接的混合系統(tǒng)Llama，將多表連接查詢分解為無數(shù)據(jù)耦合的多個(gè)子查詢，大大地減少了MapReduce作業(yè)數(shù)。文獻(xiàn)[16]提出了CoHadoop系統(tǒng)，改變副本放置策略來提高數(shù)據(jù)連接查詢效率，但不具有普遍適用性。文獻(xiàn)[17]提出了Tenzing系統(tǒng)，在MapReduce框架上融合了ColumnIO、BigTable、GFS、MySQL等系統(tǒng)實(shí)現(xiàn)對(duì)SQL的支持，對(duì)底層數(shù)據(jù)進(jìn)行數(shù)據(jù)過濾和數(shù)據(jù)索引，提高連接查詢效率。

上述研究工作均致力于基于MapReduce計(jì)算框架的大規(guī)模數(shù)據(jù)連接操作及其優(yōu)化，優(yōu)化出發(fā)點(diǎn)均在集群層面上，對(duì)數(shù)據(jù)分布不均勻給大規(guī)模數(shù)據(jù)連接查詢操作帶來的影響考慮不夠充分。本文將充分研究數(shù)據(jù)不均勻分布對(duì)大規(guī)模數(shù)據(jù)連接效率的影響及優(yōu)化，最大程度地提升數(shù)據(jù)連接查詢的性能，進(jìn)而提高大規(guī)模數(shù)據(jù)分析的效率。

3 連接查詢

連接查詢?cè)跀?shù)據(jù)分析中非常重要，也是關(guān)系數(shù)據(jù)庫中最主要的操作之一，主要包括內(nèi)連接、外連接和交叉連接等。由于內(nèi)連接較常用，本文圍繞內(nèi)連接展開研究。

3.1 問題的描述

TPC-H基準(zhǔn)數(shù)據(jù)集是查詢和事務(wù)處理常用性能測(cè)試數(shù)據(jù)集[18]，為了簡(jiǎn)化描述且不失一般性，以TPCH中CUSTOMER和ORDERS兩張表的連接查詢操作為例，設(shè)計(jì)連接查詢用例，本文研究的連接查詢算法將圍繞該查詢用例進(jìn)行討論。給定關(guān)系表CUSTOMER和ORDERS，其中表CUSTOMER包含屬性custkey、custname等，表ORDERS包含屬性orderkey、custkey等；兩表通過屬性custkey進(jìn)行連接，CR和CS分別表示表CUSTOMER和ORDERS相關(guān)的選擇條件，查詢用例的SQL描述如下：

SELECT ORDERS.orderkey,CUSTOMER.custname

FROM ORDERS INNER JOIN CUSTOMER

ON ORDERS.custkey=CUSTOMER.custkey

WHERE CRAND CS

3.2 問題的定義

設(shè)參加連接查詢的兩張表分別為R和S，R約定為主表，S約定為從表，ri和si分別為R和S的屬性，nr和ns分別為R和S的屬性個(gè)數(shù)，則表R和S的屬性集合R′和S′可表示為：

其中，屬性x∈R′∩S′,y∈R′,z∈S′。不失一般性，連接條件約定為R.x=S.x；查詢條件約定為CR和CS；投影屬性約定為P；連接操作可以描述為σR.x=S.x(R×S)；投影操作可以描述為πP(R×S)。本文的連接查詢可以定義為：

上述給出的SQL查詢用例的關(guān)系代數(shù)表達(dá)式如下：

4 連接查詢算法

首先基于傳統(tǒng)MapReduce計(jì)算框架，實(shí)現(xiàn)了改進(jìn)重分區(qū)連接查詢（improved repartition join query，IRJQ）算法并展開實(shí)驗(yàn)分析；接著，針對(duì)IRJQ算法在數(shù)據(jù)分布不均勻下各計(jì)算節(jié)點(diǎn)負(fù)載不均衡導(dǎo)致效率低下的問題，設(shè)計(jì)了組合分割平衡分區(qū)優(yōu)化策略（combination and division partition strategy，CDPS），進(jìn)而實(shí)現(xiàn)了基于組合分割平衡分區(qū)優(yōu)化策略的改進(jìn)型連接查詢算法（IRJQ+CDPS）。

4.1 基于傳統(tǒng)MapReduce連接查詢算法

改進(jìn)重分區(qū)連接查詢算法是借助于傳統(tǒng)Map-Reduce計(jì)算框架連接查詢操作的一種典型實(shí)現(xiàn)方式，該算法僅僅需要一個(gè)MapReduce作業(yè)就能完成連接查詢操作，特別是在Reduce端較小內(nèi)存消耗，使得它被廣泛地應(yīng)用于大規(guī)模數(shù)據(jù)分析中。在Map階段完成對(duì)連接屬性的解析和標(biāo)記，以HashPartition為核心完成Shuffle過程，在Reduce階段完成連接操作。圖1給出了IRJQ算法的計(jì)算框架和執(zhí)行流程。

IRJQ算法的運(yùn)行過程主要分為Map、Shuffle和Reduce共3個(gè)階段。其中Map階段完成兩表的連接屬性的解析和標(biāo)記操作，以及查詢屬性的解析；Shuffle階段負(fù)責(zé)相同hash值分組從Map端到Reduce端的傳遞；Reduce階段則將來自不同表的連接屬性和查詢值進(jìn)行連接。

Fig.1 Computation framework and implementation process of IRJQ algorithm圖1 IRJQ算法的計(jì)算框架和執(zhí)行流程

4.1.1 Map階段的屬性提取和標(biāo)記過程

MapTaski任務(wù)獲取輸入分片InputSpliti，讀取Input-Spliti中源表屬性和所有記錄。對(duì)記錄MapRecordij根據(jù)不同的源表屬性，解析出對(duì)應(yīng)的連接屬性join_keyij和查詢屬性query_valueij。在連接屬性join_keyij前加上源表標(biāo)記tag組成復(fù)合連接屬性composite_keyij，將＜composite_keyij，query_valueij＞以key/value形式輸出，完成屬性提取和標(biāo)記。

如果輸入分片InputSpliti來自O(shè)RDERS表，從MapRecordij中解析出custkeyij和orderkeyij，在custkeyij的前面加一個(gè)數(shù)字“1”組成復(fù)合的輸出鍵“1”+custkeyij，將＜“1”+custkeyij，orderkeyij＞以key/value鍵值對(duì)的形式輸出，完成對(duì)記錄中屬性的提取和標(biāo)記過程。同樣，如果輸入分片InputSpliti來自CUSTOMER表，從MapRecordij解析出custkeyij和custnameij，在custkeyij的前面加一個(gè)數(shù)字“0”組成復(fù)合的輸出鍵“0”+custkeyij，以key/value鍵值對(duì)的形式將＜“0”+custkeyij，custnameij＞輸出。其中，在來自于CUSTOMER表中記錄的連接屬性custkeyij前面加標(biāo)記“0”，而來自于ORDERS表中記錄的連接屬性custkeyij前面加標(biāo)記“1”，是為了在Shuffle過程中，使得CUSTOMER表中記錄排在ORDERS表中記錄的前面，這樣在Reduce階段只用緩存CUSTOMER表中的記錄，減少Reduce階段對(duì)內(nèi)存的消耗。其算法描述如下：

算法1屬性解析和標(biāo)記算法

4.1.2 Shuffle階段的哈希分區(qū)過程

當(dāng)所有輸入分片完成屬性的提取和標(biāo)記后，需要將分組劃分到合適的分區(qū)，以保證各Reducer節(jié)點(diǎn)擁有相等的分組數(shù)目。在傳統(tǒng)MapReduce框架中對(duì)分組的劃分過程是以HashPartition為核心完成的，讀取分組Groupi中的連接屬性join_keyi，計(jì)算連接屬性join_keyi對(duì)應(yīng)的哈希值HashCodei，將HashCodei和分區(qū)的數(shù)目做取余運(yùn)算得到對(duì)應(yīng)的分區(qū)PartitionNumi。其中，連接屬性join_keyi一般是以字符串的形式出現(xiàn)，為了保證所分區(qū)擁有相等數(shù)目的分組，連接屬性join_keyi的哈希值HashCodei計(jì)算策略較為重要，默認(rèn)情況下使用JDK中String類的hashcode（）方法。計(jì)算字符串join_keyi的長度length，讀取字符串join_ keyi在內(nèi)存中的存儲(chǔ)地址并保存在字符數(shù)組val[]中，最后做一個(gè)length次的迭代運(yùn)算HashCodei=31*h+ val[i++]得到哈希值HashCodei，即為對(duì)應(yīng)的分區(qū)。其算法描述如下：

算法2哈希分區(qū)算法

4.1.3 Reduce階段的連接過程

ReduceTaski任務(wù)從多個(gè)MapTask的本地磁盤中拉取屬于自己的中間數(shù)據(jù)，將數(shù)據(jù)進(jìn)行排序、分組和合并等操作，得到多個(gè)分組組成的集合GroupSeti。分組Groupij中的記錄以＜composite_key，query_value_ List＞鍵和多個(gè)值組成的序列對(duì)形式存在，且每一個(gè)分組內(nèi)所有來自于CUSTOMER的記錄都排在來自O(shè)RDERS表的記錄之前。對(duì)分組Groupij中的記錄ReduceRecordp，讀取復(fù)合連接屬性composite_keyp，從復(fù)合連接屬性composite_keyp中解析出連接屬性join_ keyp和源表標(biāo)記tag，遍歷查詢屬性的序列query_ value_Listp。

如果tag為“0”，表明該記錄來自于CUSTOMER表，將查詢屬性序列query_value_Listp中的每一個(gè)cust_query_valueq分別和連接屬性join_keyp以＜join_ keyp，cust_query_valueq＞鍵值對(duì)的形式保存于緩存集合ReduceBufferi中。如果tag為“1”，表明該記錄來自于ORDERS表，對(duì)序列query_value_Listp中的各查詢屬性order_query_valueq分別在緩存集合ReduceBufferi中查詢其連接屬性join_keyp是否存在。如果存在，就從緩存集合ReduceBufferi中讀取該連接屬性join_ keyp對(duì)應(yīng)的查詢屬性cust_query_valueq，并將＜o(jì)rder_ query_valueq，cust_query_valueq＞以鍵值對(duì)的形式輸出；如果緩存ReduceBufferi中查詢其連接屬性join_ keyp不存在，則讀取序列query_value_Listp中的下一條查詢記錄order_query_value(q+1)，直到序列query_ value_Listp中的所有記錄遍歷完成。其算法描述如下：

算法3連接查詢算法

4.1.4 算法性能分析

實(shí)驗(yàn)平臺(tái)環(huán)境和實(shí)驗(yàn)數(shù)據(jù)集詳細(xì)見5.1節(jié)，實(shí)驗(yàn)的評(píng)價(jià)標(biāo)準(zhǔn)為整個(gè)作業(yè)運(yùn)行時(shí)間。連接條件定義為CUSTOMER.custkey=ORDERS.custkey，實(shí)驗(yàn)采用測(cè)試用例SQL描述如下：

SELECT ORDERS.orderkey，CUSTOMER.custname

FROM ORDERS INNER JOIN CUSTOMER

ON CUSTOMER.custkey=ORDERS.custkey

為了較全面評(píng)估IRJQ算法的性能，將CUSTOMER的連接率設(shè)定為0.1%、20%和50%，ORDERS數(shù)據(jù)的傾斜率設(shè)定為0.2、0.5和0.8。其中，連接率定義為CUSTOMER中有購買記錄的用戶所占的比率；傾斜率定義為某一分組數(shù)據(jù)量在整個(gè)數(shù)據(jù)集中所占的比率。

實(shí)驗(yàn)1數(shù)據(jù)傾斜時(shí)不同連接率下IRJQ算法時(shí)間性能分析。固定CUSTOMER表中的數(shù)據(jù)量，不斷增加ORDERS中的數(shù)據(jù)量，對(duì)比分析IRJQ算法在數(shù)據(jù)傾斜時(shí)不同連接率下的時(shí)間性能。其中，CUSTOMER中記錄數(shù)目固定為8 000萬條，連接率分別取0.1%、20%和50%；ORDERS中的記錄數(shù)目分別取10億、20億、30億、40億、50億、60億、70億和80億，傾斜率分別取0.2、0.5和0.8。實(shí)驗(yàn)結(jié)果如圖2所示。

實(shí)驗(yàn)結(jié)果表明，ORDERS中的連接屬性不均勻分布對(duì)IRJQ算法時(shí)間性能影響較大，隨著ORDERS中的數(shù)據(jù)量及傾斜率增大，其時(shí)間性能大幅度下降。這主要是因?yàn)閭鹘y(tǒng)MapReduce框架為了保證所有的分區(qū)有相同數(shù)目的分組，以哈希分區(qū)策略完成對(duì)分組的劃分。

假設(shè)ORDERS共有m條記錄，傾斜率為α，且傾斜分組數(shù)目為1；CUSTOMER共有n條記錄，連接率為β；Reduce階段共有k個(gè)分區(qū)。則每個(gè)分區(qū)的分組數(shù)目為，傾斜分組中的記錄數(shù)目為m×α，非傾斜分組中的記錄數(shù)目約為，傾斜分區(qū)中的記錄數(shù)目約為，非傾斜分區(qū)中的記錄數(shù)目約為，傾斜分區(qū)與非傾斜分區(qū)間的記錄數(shù)目差約為?？梢院芮宄乜闯?，隨著ORDERS中記錄數(shù)目m或者傾斜率α的增加，傾斜分組的記錄數(shù)目m×α變得越來越大，傾斜分組和非傾斜分組間的數(shù)據(jù)量差也會(huì)越來越大。當(dāng)α→1或者m→∞時(shí)，，即ORDERS中數(shù)據(jù)分布嚴(yán)重不均勻或者數(shù)據(jù)量較大會(huì)導(dǎo)致多個(gè)分區(qū)間的數(shù)據(jù)量相差巨大，造成Reduce階段負(fù)載嚴(yán)重不均衡，最終影響整個(gè)作業(yè)的時(shí)間性能。

4.2 基于改進(jìn)型MapReduce連接查詢算法

IRJQ算法在數(shù)據(jù)分布均勻的情況下?lián)碛休^好的時(shí)間性能和穩(wěn)定性，然而當(dāng)數(shù)據(jù)分布不均勻時(shí)，Reduce階段會(huì)因?yàn)槎鄠€(gè)分組數(shù)據(jù)量相差較大導(dǎo)致負(fù)載不平衡，嚴(yán)重影響了算法的時(shí)間性能和穩(wěn)定性。針對(duì)IRJQ算法的這種不足，本文設(shè)計(jì)和實(shí)現(xiàn)了組合分割平衡分區(qū)優(yōu)化策略，形成MapReduce計(jì)算框架下基于組合分割平衡分區(qū)優(yōu)化策略的改進(jìn)型連接查詢算法（IRJQ+CDPS）。圖3給出了IRJQ+CDPS算法的計(jì)算框架和執(zhí)行流程。

IRJQ+CDPS算法以改進(jìn)重分區(qū)連接查詢算法為基礎(chǔ)，分為3個(gè)階段Map、Shuffle和Reduce。Map和Reduce階段同IRJQ算法一致，其核心改進(jìn)體現(xiàn)在Shuffle過程中的組合分割平衡分區(qū)優(yōu)化策略，保證了在數(shù)據(jù)傾斜時(shí)Reduce階段的負(fù)載均衡。

4.2.1 ORDERS表連接屬性頻率分布統(tǒng)計(jì)

Fig.2 Time performance comparison of IRJQ algorithm under skewed data圖2 數(shù)據(jù)傾斜下IRJQ算法時(shí)間性能對(duì)比分析

為了解決數(shù)據(jù)傾斜導(dǎo)致連接算法時(shí)間性能下降的不足，本文對(duì)嚴(yán)重傾斜的連接屬性分組采用分割分區(qū)策略，不嚴(yán)重或不傾斜的連接屬性分組采用組合分區(qū)策略。其中，首先需要解決的問題就是要得到ORDERS表中連接屬性的頻率分布情況。該過程由一個(gè)獨(dú)立的MapReduce作業(yè)完成，MapTaski任務(wù)獲取對(duì)應(yīng)的輸入分片inputspliti，讀取記錄MapRecordij，解析出MapRecordij的連接屬性join_keyij，然后將＜join_ keyij，1＞以key/value的形式輸出到對(duì)應(yīng)的分組中。多個(gè)擁有不同連接屬性的分組經(jīng)過Shuffle過程的分區(qū)操作，被從Map端傳送到Reduce端。這里使用的分區(qū)策略是MapReduce計(jì)算框架默認(rèn)的哈希分區(qū)策略。ReduceTaski任務(wù)對(duì)來自多個(gè)Map端的分組進(jìn)行排序、分組和合并等操作得到對(duì)應(yīng)的分區(qū)，讀取分組Groupi的連接屬性join_keyij和value_Listij。其中value_ Listij為從Map階段傳送過來的具有相同連接屬性的多個(gè)“1”組成的序列，將value_Listij中所有的“1”求和得到對(duì)應(yīng)連接屬性join_keyij的頻率frequencyij。最后將＜join_keyij，frequencyij＞以key/value的形式輸出，完成對(duì)ORDERS表中連接屬性出現(xiàn)頻率的統(tǒng)計(jì)。

Fig.3 Computation framework and implementation process of CDPS+IRJQ algorithm圖3 IRJQ+CDPS算法的計(jì)算框架和執(zhí)行過程

4.2.2 嚴(yán)重傾斜分區(qū)和不嚴(yán)重或不傾斜分區(qū)劃分

在得到了ORDERS表中連接屬性的頻率分布后，一個(gè)非常重要的問題就是如何準(zhǔn)確地找到那些連接屬性嚴(yán)重傾斜的分組。一個(gè)常見的方法就是計(jì)算所有連接屬性分組中key/value鍵值對(duì)數(shù)目的平均值A(chǔ)VG，每個(gè)分組通過和平均值A(chǔ)VG的比較來確認(rèn)是否嚴(yán)重傾斜。如果某個(gè)分組中key/value鍵值對(duì)數(shù)目小于平均值A(chǔ)VG，那么就認(rèn)為該分組為不嚴(yán)重或不傾斜分組，將對(duì)其采用組合分區(qū)策略；同樣，如果某個(gè)分組中key/value鍵值對(duì)數(shù)目大于或等于平均值A(chǔ)VG，那么就認(rèn)為該分組為嚴(yán)重傾斜分組，將對(duì)其采用分割分區(qū)策略。所有分組的key/value鍵值對(duì)數(shù)目平均值A(chǔ)VG計(jì)算方式如下：

其中，|Groupi|表示第i個(gè)分組中key/value鍵值對(duì)的數(shù)目；m表示分組Group的個(gè)數(shù)。很明顯，key/value鍵值對(duì)數(shù)目的平均值A(chǔ)VG決定了分組是否嚴(yán)重傾斜。如果嚴(yán)重傾斜分組太多，AVG也會(huì)變得更接近嚴(yán)重傾斜分組，從而保證了較為準(zhǔn)確地劃分出嚴(yán)重傾斜分組和不嚴(yán)重或不傾斜分組。

4.2.3 組合分割平衡分區(qū)優(yōu)化策略

針對(duì)數(shù)據(jù)分布不均勻?qū)е碌膬A斜問題，將那些不嚴(yán)重傾斜或不傾斜連接屬性的分組，組合成較大的分組，然后再將組合后的大分組劃分到各Reducer節(jié)點(diǎn)中，而那些嚴(yán)重傾斜連接屬性的分組等劃分到各Reducer節(jié)點(diǎn)中。

不嚴(yán)重傾斜或不傾斜屬性分組的組合分區(qū)策略，根據(jù)每個(gè)分組中數(shù)據(jù)量的大小組合成較大的分組，在組合過程中最大程度地保證組合后的多個(gè)大分組數(shù)據(jù)量大致相等，然后將組合后的分組分別傳遞到Reduce端，使所有的Reduce端具有近似相等的負(fù)載量，達(dá)到負(fù)載均衡的目的。這種組合分區(qū)策略是典型NP難解問題，采用啟發(fā)式的方法得到次優(yōu)解，即優(yōu)先分配較大分組，接著在剩下的分組中選擇數(shù)據(jù)量最多的分組分配到負(fù)載最小的分區(qū)上。根據(jù)每個(gè)分組{G1,G2,…,Gm}的數(shù)據(jù)量大小進(jìn)行降序排列；然后，將前n個(gè)分組分配給{r1,r2,…,rn}n個(gè)Reducer節(jié)點(diǎn)，這樣rn的負(fù)載量最小；接著，選擇{r1,r2,…,rn}中當(dāng)前負(fù)載量最小的ri，將Gn+1分配給ri；重復(fù)上一步，依次將Gj分配給負(fù)載量最小的ri，只到所有的分組分配完成，達(dá)到Reduce階段的負(fù)載均衡。

嚴(yán)重傾斜連接屬性分組的分割分區(qū)策略，組合分區(qū)策略應(yīng)對(duì)傾斜不是很嚴(yán)重的分組時(shí)往往具有較好的負(fù)載均衡效果，當(dāng)面對(duì)那些嚴(yán)重傾斜的分組時(shí)，有些較大分組數(shù)據(jù)量的大小要比其他多個(gè)較小分組組合之后的數(shù)據(jù)量還要大，從而導(dǎo)致無論怎么分配組合都無法達(dá)到在Reduce端的負(fù)載均衡，離人們所期望的效果相差甚遠(yuǎn)。假設(shè)GSet={G1,G2,G3,G4,G5}= {2 000,700,360,150,80},PSet={P1,P2,P3}，使用組合分區(qū)策略：{G1→P1},{G2→P2},{G3→P3}，接下來即使把G4、G5都分配到P3上也達(dá)不到負(fù)載平衡。但是，可以將這些嚴(yán)重傾斜連接屬性分組等劃分成n份，將這n等份分別發(fā)到n個(gè)分區(qū)中，在Reduce端就可以得到一個(gè)比較好的負(fù)載平衡效果。

算法4組合分割平衡分區(qū)優(yōu)化算法

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

在大規(guī)模數(shù)據(jù)分析過程中，數(shù)據(jù)分布不均勻?qū)B接查詢操作的性能有非常大的影響。本文設(shè)計(jì)和實(shí)現(xiàn)了IRJQ+CDPS算法和IRJQ算法，并以實(shí)驗(yàn)的方式對(duì)兩者的時(shí)間性能和Reduce階段最大負(fù)載量進(jìn)行對(duì)比與分析。

5.1 實(shí)驗(yàn)平臺(tái)環(huán)境和數(shù)據(jù)集

實(shí)驗(yàn)平臺(tái)由16臺(tái)高性能服務(wù)器構(gòu)成，1臺(tái)設(shè)為主控節(jié)點(diǎn)，15臺(tái)設(shè)為計(jì)算節(jié)點(diǎn)，分布在兩個(gè)機(jī)架上面，每個(gè)機(jī)架有獨(dú)立的路由器。每個(gè)節(jié)點(diǎn)配有2個(gè)處理核心，2.4 GHz主頻，8 GB內(nèi)存和1.5 TB的本地存儲(chǔ)磁盤，操作系統(tǒng)為Red Hat Linux 5.6。使用Hadoop 1.1.2版本的系統(tǒng)作為集群環(huán)境，每個(gè)節(jié)點(diǎn)配置2個(gè)MapTask任務(wù)和2個(gè)ReduceTask任務(wù)，HDFS的塊大小設(shè)定為128 MB，每一個(gè)數(shù)據(jù)塊的副本數(shù)設(shè)置為3，其他各項(xiàng)參數(shù)均采用默認(rèn)設(shè)置。

使用TPC-H基準(zhǔn)測(cè)試集生成工具產(chǎn)生用于連接查詢操作實(shí)驗(yàn)的數(shù)據(jù)集，并采用其中的CUSTOMER和ORDERS兩個(gè)數(shù)據(jù)表來做連接操作。其中，CUSTOMER表中的數(shù)據(jù)量分別取1 000萬條、2 000萬條、3 000萬條、4 000萬條、5 000萬條、6 000萬條、7 000條和8 000萬條；ORDERS中數(shù)據(jù)量分別取10億條、20億條、30億條、40億條、50億條、60億條、70億條和80億條。為了更好地評(píng)估IRJQ+CDPS算法的性能，將ORDERS數(shù)據(jù)傾斜率設(shè)定為0.2、0.5和0.8。

實(shí)驗(yàn)的評(píng)價(jià)標(biāo)準(zhǔn)為時(shí)間性能和Reduce端最大負(fù)載量。其中，時(shí)間性能簡(jiǎn)單設(shè)定為整個(gè)作業(yè)運(yùn)行的總時(shí)間；Reduce端的最大負(fù)載量設(shè)定為所有分區(qū)中最大那個(gè)分區(qū)的數(shù)據(jù)量。

5.2 實(shí)驗(yàn)與結(jié)果

為了和帶有區(qū)間范圍的連接查詢和低選擇性的連接查詢相區(qū)分，將一般性連接查詢定義為全表范圍的連接查詢。

5.2.1 全表范圍的連接查詢對(duì)比實(shí)驗(yàn)

對(duì)兩種連接查詢算法全表范圍連接查詢的性能進(jìn)行對(duì)比分析，連接條件設(shè)定為CUSTOMER.custkey=ORDERS.custkey，測(cè)試用例SQL描述如下：

SELECT ORDERS.orderkey，CUSTOMER.custname

FROM ORDERS INNER JOIN CUSTOMER

ON CUSTOMER.custkey=ORDERS.custkey

實(shí)驗(yàn)2全表范圍連接查詢的不同傾斜率下時(shí)間性能對(duì)比實(shí)驗(yàn)。固定ORDERS表中數(shù)據(jù)量，不斷增加CUSTOMER中的數(shù)據(jù)量，對(duì)比分析IRJQ算法和IRJQ+CDPS算法在全表范圍連接查詢的不同傾斜率下的時(shí)間性能。其中，CUSTOMER中記錄數(shù)固定為8 000萬條，連接率為100%；ORDERS中記錄數(shù)分別取10億、20億、30億、40億、50億、60億、70億和80億，傾斜率分別取0.2、0.5和0.8。實(shí)驗(yàn)結(jié)果如圖4所示。

實(shí)驗(yàn)結(jié)果表明，當(dāng)ORDERS中數(shù)據(jù)量較少時(shí)，IRJQ算法擁有較好的時(shí)間性能；隨著ORDERS中數(shù)據(jù)量的增加，IRJQ算法的時(shí)間性能快速下降，而IRJQ+CDPS算法的時(shí)間性能逐步轉(zhuǎn)好；當(dāng)ORDERS中數(shù)據(jù)量增加到一定程度，IRJQ+CDPS算法擁有非常好的時(shí)間性能，且整個(gè)過程中IRJQ+CDPS算法擁有較好的穩(wěn)定性。這主要是因?yàn)镮RJQ+CDPS算法相對(duì)于IRJQ算法較為復(fù)雜，當(dāng)ORDERS中數(shù)據(jù)量較少時(shí)，數(shù)據(jù)分布不均勻?qū)е碌腞educe階段的負(fù)載不均衡不是很明顯，IRJQ+CDPS算法負(fù)載均衡優(yōu)化策略帶來的時(shí)間性能優(yōu)勢(shì)相對(duì)于復(fù)雜的執(zhí)行流程帶來額外的時(shí)間開銷還是太小；隨著ORDERS中數(shù)據(jù)量的增加，數(shù)據(jù)分布不均勻?qū)е碌腞educe階段的負(fù)載不均衡越來越明顯，復(fù)雜的執(zhí)行流程帶來額外的時(shí)間開銷相對(duì)于IRJQ+CDPS算法優(yōu)化策略帶來的時(shí)間性能優(yōu)勢(shì)可以忽略不計(jì)，IRJQ+CDPS算法的時(shí)間性能優(yōu)勢(shì)也越來越明顯。

實(shí)驗(yàn)3全表范圍連接查詢的不同傾斜率下Reduce階段最大負(fù)載量對(duì)比實(shí)驗(yàn)。固定ORDERS中的數(shù)據(jù)量，不斷增加CUSTOMER中的數(shù)據(jù)量，對(duì)比分析IRJQ算法和IRJQ+CDPS算法在全表范圍連接查詢的不同傾斜率下Reduce階段的最大負(fù)載量。其中，CUSTOMER中記錄數(shù)目固定為8 000萬條，連接率為100%；ORDERS中記錄數(shù)目分別取10億、20億、30億、40億、50億、60億、70億和80億，傾斜率分別取0.2、0.5和0.8。實(shí)驗(yàn)結(jié)果如圖5所示。

實(shí)驗(yàn)結(jié)果表明，在整個(gè)實(shí)驗(yàn)過程中，與IRJQ算法相比，IRJQ+CDPS算法在Reduce階段的最大負(fù)載量一直較低；并且隨著ORDERS中數(shù)據(jù)量和傾斜率的增大，IRJQ+CDPS算法的這種負(fù)載均衡優(yōu)勢(shì)越來越明顯。這主要是因?yàn)镮RJQ算法在Shuffle階段采用的是哈希分區(qū)，只能保證Reduce階段多個(gè)分區(qū)間擁有相等的分組數(shù)，而無法保證每個(gè)分組擁有相等的數(shù)據(jù)量，更加無法保證Reduce階段的負(fù)載均衡；而IRJQ+CDPS算法在Shuffle階段采用了組合分割平衡分區(qū)優(yōu)化策略，對(duì)不嚴(yán)重或不傾斜的分組采用組合分區(qū)策略，嚴(yán)重傾斜的分組采用分割策略，每個(gè)分組擁有近似相等的數(shù)據(jù)量，很好地保證了Reduce階段的負(fù)載均衡。

Fig.4 Time performance comparison of full-join queries under different data skewed rates圖4 不同傾斜率下全表連接查詢時(shí)間性能對(duì)比

5.2.2 帶有區(qū)間范圍的連接查詢對(duì)比實(shí)驗(yàn)

對(duì)兩種連接查詢算法帶有區(qū)間范圍連接查詢的性能進(jìn)行對(duì)比分析，連接條件設(shè)定為CUSTOMER. custkey=ORDERS.custkey，選擇條件設(shè)定為207 290＜CUSTOMER.custkey＜291050，測(cè)試用例SQL描述如下：

SELECT ORDERS.orderkey,CUSTOMER.custname

FROM ORDERS INNER JOIN CUSTOMER

ON CUSTOMER.custkey=ORDERS.custkey

WHERE 207290＜CUSTOMER.custkey＜291050

實(shí)驗(yàn)4帶有區(qū)間范圍連接查詢的不同傾斜率下時(shí)間性能對(duì)比實(shí)驗(yàn)。固定ORDERS表中的數(shù)據(jù)量，不斷增加CUSTOMER中的數(shù)據(jù)量，對(duì)比分析IRJQ算法和IRJQ+CDPS算法在帶有區(qū)間范圍連接查詢的不同傾斜率下的時(shí)間性能。其中，CUSTOMER中記錄數(shù)固定為8 000萬條，連接率為100%；ORDERS中記錄數(shù)分別取10億、20億、30億、40億、50億、60億、70億和80億，傾斜率分別取0.2、0.5和0.8。實(shí)驗(yàn)結(jié)果如圖6所示。

Fig.5 Maximum load of Reduce comparison for full-join queries under different data skewed rates圖5 不同傾斜率下全表連接查詢Reduce端最大負(fù)載量對(duì)比

Fig.6 Time performance comparison of range queries under different data skewed rates圖6 不同傾斜率下范圍查詢時(shí)間性能對(duì)比

實(shí)驗(yàn)結(jié)果同實(shí)驗(yàn)2類似，當(dāng)ORDERS中數(shù)據(jù)量較少時(shí)，IRJQ算法擁有較好的時(shí)間性能；隨著ORDERS中數(shù)據(jù)量的增加，IRJQ算法的時(shí)間性能快速下降，而IRJQ+CDPS算法的時(shí)間性能逐步轉(zhuǎn)好；當(dāng)ORDERS中數(shù)據(jù)量達(dá)到一定程度時(shí)，IRJQ+CDPS算法擁有非常好的時(shí)間性能，且整個(gè)過程中IRJQ+CDPS算法擁有較好的穩(wěn)定性。同時(shí)，相比于實(shí)驗(yàn)2，實(shí)驗(yàn)4中的IRJQ+CDPS算法的組合分割平衡分區(qū)策略帶來的時(shí)間性能優(yōu)勢(shì)稍微降低。這主要是因?yàn)?，相比于全表范圍的連接查詢，帶有區(qū)間范圍連接查詢的查詢范圍較小，相同的輸入數(shù)據(jù)量下，Reduce階段需要緩存的數(shù)據(jù)量較小，一定程度減少了數(shù)據(jù)分布不均勻?qū)φ麄€(gè)連接查詢算法時(shí)間性能的影響。

實(shí)驗(yàn)5帶有區(qū)間范圍連接查詢的不同傾斜率下Reduce階段最大負(fù)載量對(duì)比實(shí)驗(yàn)。固定ORDERS表中的數(shù)據(jù)量，不斷增加CUSTOMER中的數(shù)據(jù)量，對(duì)比分析IRJQ算法和IRJQ+CDPS算法在不同傾斜率下Reduce階段的最大負(fù)載量。其中，CUSTOMER中記錄數(shù)固定為8 000萬條，連接率為100%；ORDERS中記錄數(shù)分別取10億、20億、30億、40億、50億、60億、70億和80億，傾斜率分別取0.2、0.5和0.8。實(shí)驗(yàn)結(jié)果如圖7所示。

實(shí)驗(yàn)結(jié)果同實(shí)驗(yàn)3類似，在整個(gè)實(shí)驗(yàn)過程中，IRJQ+CDPS算法在Reduce階段的最大負(fù)載量一直較低，并且隨著ORDERS中數(shù)據(jù)量和傾斜率的增大，IRJQ+CDPS算法的這種負(fù)載均衡優(yōu)勢(shì)越來越明顯。這主要是因?yàn)?，IRJQ算法在Shuffle階段采用的是哈希分區(qū)，在數(shù)據(jù)分布不均勻時(shí)，只能保證Reduce階段多個(gè)分區(qū)間擁有相等的分組數(shù)，而無法保證每個(gè)分組有相等的數(shù)據(jù)量，更加無法保證Reduce階段的負(fù)載均衡；而IRJQ+CDPS算法在Shuffle階段采用了組合分割平衡分區(qū)優(yōu)化策略，每個(gè)分組擁有近似相等的數(shù)據(jù)量，很好地保證了Reduce階段的負(fù)載均衡。

5.2.3 低選擇性的連接查詢對(duì)比實(shí)驗(yàn)

對(duì)兩種連接查詢算法低選擇性連接查詢的性能進(jìn)行對(duì)比分析，連接條件設(shè)定為CUSTOMER.custkey=ORDERS.custkey，選擇條件設(shè)定為CUSTOMER. custkey=23 698，測(cè)試用例SQL描述如下：

SELECT ORDERS.orderkey，CUSTOMER.custname

FROM ORDERS INNER JOIN CUSTOMER

ON CUSTOMER.custkey=ORDERS.custkey

WHERE CUSTOMER.custkey=23698

實(shí)驗(yàn)6低選擇性連接查詢的不同傾斜率下時(shí)間性能對(duì)比實(shí)驗(yàn)。固定ORDERS表中的數(shù)據(jù)量，不斷增加CUSTOMER中的數(shù)據(jù)量，對(duì)比分析IRJQ算法和IRJQ+CDPS算法在低選擇性連接查詢的不同傾斜率下的時(shí)間性能。其中，CUSTOMER中記錄數(shù)固定為8 000萬條，連接率為100%；ORDERS中記錄數(shù)分別取10億、20億、30億、40億、50億、60億、70億和80億，傾斜率分別取0.2、0.5和0.8。實(shí)驗(yàn)結(jié)果如圖8所示。

實(shí)驗(yàn)結(jié)果同實(shí)驗(yàn)4類似，當(dāng)ORDERS中數(shù)據(jù)量較少時(shí)，IRJQ算法擁有較好的時(shí)間性能；隨著ORDERS中數(shù)據(jù)量的增加，IRJQ算法的時(shí)間性能快速下降，而IRJQ+CDPS算法的時(shí)間性能逐步轉(zhuǎn)好；當(dāng)ORDERS中數(shù)據(jù)量達(dá)到一定程度時(shí)，IRJQ+CDPS算法擁有非常好的時(shí)間性能，且整個(gè)過程中IRJQ+CDPS算法擁有較好的穩(wěn)定性。同時(shí)，相比于實(shí)驗(yàn)4，實(shí)驗(yàn)6中的IRJQ+CDPS算法的平衡分區(qū)帶來的時(shí)間性能優(yōu)勢(shì)有所降低。這是主要是因?yàn)?，相比于帶有區(qū)間范圍的連接查詢，低選擇性連接查詢的查詢范圍較小，相同的輸入數(shù)據(jù)量下，Reduce階段需要緩存的數(shù)據(jù)量較小，一定程度減少了數(shù)據(jù)分布不均勻?qū)φ麄€(gè)連接查詢算法時(shí)間性能的影響。

實(shí)驗(yàn)7低選擇性連接查詢的不同傾斜率下Reduce階段最大負(fù)載量對(duì)比實(shí)驗(yàn)。固定ORDERS表中的數(shù)據(jù)量，不斷增加CUSTOMER中的數(shù)據(jù)量，對(duì)比分析IRJQ算法和IRJQ+CDPS算法在低選擇性連接查詢的不同傾斜率下Reduce階段的最大負(fù)載量。其中，CUSTOMER中記錄數(shù)固定為8 000萬條，連接率為100%；ORDERS中記錄數(shù)分別取10億、20億、30億、40億、50億、60億、70億和80億，傾斜率分別取0.2、0.5和0.8。實(shí)驗(yàn)結(jié)果如圖9所示。

Fig.7 Maximum load of Reduce comparison for range queries under different data skewed rates圖7 不同傾斜率下范圍查詢Reduce端最大負(fù)載量對(duì)比

實(shí)驗(yàn)結(jié)果同實(shí)驗(yàn)5類似，在整個(gè)實(shí)驗(yàn)過程中，IRJQ+CDPS算法在Reduce階段的最大負(fù)載量一直較低，并且隨著ORDERS中數(shù)據(jù)量和傾斜率的增大，IRJQ+CDPS算法的這種負(fù)載均衡優(yōu)勢(shì)越來越明顯。這主要是因?yàn)?，IRJQ算法在Shuffle階段采用的是哈希分區(qū)，在數(shù)據(jù)分布不均勻時(shí)，只能保證Reduce階段多個(gè)分區(qū)間擁有相等的分組數(shù)，而無法保證每個(gè)分組有相等的數(shù)據(jù)量，更加無法保證Reduce階段的負(fù)載均衡；而IRJQ+CDPS算法在Shuffle階段采用了組合分割平衡分區(qū)優(yōu)化策略，每個(gè)分組擁有近似相等的數(shù)據(jù)量，很好地保證了Reduce階段的負(fù)載均衡。

Fig.8 Time performance comparison of low-join-rate queries under different data skewed rates圖8 不同傾斜率下低連接率查詢時(shí)間性能對(duì)比

Fig.9 Maximum load of Reduce comparison for low-join-rate queries under different data skewed rates圖9 不同傾斜率下低連接率查詢Reduce端最大負(fù)載量對(duì)比

5.3 結(jié)果分析

從上面的實(shí)驗(yàn)結(jié)果中可以看到，不論是在全局范圍的連接查詢操作，還是帶有區(qū)間范圍的連接查詢操作，亦或是低選擇性連接查詢操作，相對(duì)于IRJQ算法，IRJQ+CDPS算法在時(shí)間性能和Reduce端最大負(fù)載量兩方面均具有非常大的優(yōu)勢(shì)。

在時(shí)間復(fù)雜度方面，當(dāng)ORDERS中數(shù)據(jù)量較少時(shí)，IRJQ算法擁有較好的時(shí)間性能；隨著ORDERS表中數(shù)據(jù)量的增加，IRJQ算法的時(shí)間性能快速下降，而IRJQ+CDPS算法的時(shí)間性能逐步轉(zhuǎn)好；當(dāng)ORDERS表中數(shù)據(jù)量達(dá)到一定程度時(shí)，IRJQ+CDPS算法擁有較好的時(shí)間性能。這主要是因?yàn)?，IRJQ+CDPS算法相對(duì)于IRJQ算法較為復(fù)雜，當(dāng)ORDERS中數(shù)據(jù)量較少時(shí)，數(shù)據(jù)分布不均勻?qū)е碌腞educe階段的負(fù)載不均衡不是很明顯，IRJQ+CDPS算法的優(yōu)化策略帶來的時(shí)間性能優(yōu)勢(shì)相對(duì)于復(fù)雜的執(zhí)行流程帶來額外的時(shí)間開銷還是太?。浑S著ORDERS中數(shù)據(jù)量的增加，數(shù)據(jù)分布不均勻?qū)е碌腞educe階段的負(fù)載不均衡不是越來越明顯，復(fù)雜的執(zhí)行流程帶來額外的時(shí)間開銷相對(duì)于IRJQ+CDPS算法的優(yōu)化策略帶來的時(shí)間性能優(yōu)勢(shì)可以忽略不計(jì)，IRJQ+CDPS算法的時(shí)間性能優(yōu)勢(shì)也越來越明顯。

在Reduce端的最大負(fù)載量方面，整個(gè)實(shí)驗(yàn)過程中，IRJQ+CDPS算法在Reduce階段的最大負(fù)載量一直較低，并且隨著ORDERS中數(shù)據(jù)量和傾斜率的增大，IRJQ+CDPS算法的這種負(fù)載均衡優(yōu)勢(shì)越來越明顯。這主要是因?yàn)?，IRJQ算法在Shuffle階段采用的是哈希分區(qū)，在數(shù)據(jù)分布不均勻時(shí)，只能保證Reduce階段多個(gè)分區(qū)間擁有相等的分組數(shù)，而無法保證每個(gè)分組有相等的數(shù)據(jù)量，更加無法保證Reduce階段的負(fù)載均衡；而IRJQ+CDPS算法在Shuffle階段采用了組合分割平衡分區(qū)優(yōu)化策略，很好地保證了Reduce階段的負(fù)載均衡。

6 小結(jié)

連接查詢是大規(guī)模數(shù)據(jù)分析的核心操作算子之一，數(shù)據(jù)傾斜在大規(guī)模數(shù)據(jù)分析中普遍存在，且對(duì)借助于MapReduce計(jì)算框架的連接查詢算法的效率具有較大影響。本文主要針對(duì)連接查詢操作中的數(shù)據(jù)傾斜問題，研究MapReduce框架下大規(guī)模數(shù)據(jù)連接查詢操作的優(yōu)化算法。首先，以較為常見的改進(jìn)重分區(qū)連接查詢算法為例，研究借助于傳統(tǒng)MapReduce計(jì)算框架連接查詢操作的執(zhí)行流程，找出基于Map-Reduce計(jì)算框架連接算法在數(shù)據(jù)分布不均勻時(shí)的性能瓶頸；進(jìn)而，提出了組合分割平衡分區(qū)優(yōu)化策略，形成了MapReduce計(jì)算框架下基于組合分割平衡分區(qū)優(yōu)化策略的改進(jìn)型連接查詢算法。實(shí)驗(yàn)結(jié)果表明，提出的優(yōu)化策略在大規(guī)模數(shù)據(jù)連接查詢處理上很好地解決了數(shù)據(jù)傾斜對(duì)其性能的影響，具有較好的時(shí)間性能和可擴(kuò)展性。

[1]Olston C,Reed B,Srivastava U,et al.Pig a not-so-foreign language for data processing[C]//Proceedings of the 2008 International Conference on Management of Data,Vancouver, Canada,Jun 9-12,2008.New York:ACM,2008:1099-1110.

[2]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,Indianapolis,USA,Jun 6-11, 2010.New York:ACM,2010:975-986.

[3]Okcan A,Riedewald M.Processing theta-joins using Map-Reduce[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data,Athens,Greece, Jun 12-16,2011.New York:ACM,2011:949-960.

[4]Vernica R,Carey M J,Li Chen.Efficient parallel set similarity joins using MapReduce[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indianapolis,USA,Jun 6-10,2010.New York:ACM,2010: 495-506.

[5]Afrati F N,Ullman J D.Optimizing multiway joins in a Map Reduce environment[C]//Proceedings of the 13th International Conference on Extending Database Technology,Lausanne,Switzerland,Mar 22-26,2010.New York:ACM,2011: 1282-1298.

[6]Slagter K,Hsu C H,Chung Y C,et al.SmartJoin:a networkaware multiway join for MapReduce[J].Cluster Computing, 2014,17(3):629-641.

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

[8]Yang H C,Dasdan A,Hsiao R L,et al.Map-Reduce-Merge: simplified relational data processing on large clusters[C]// Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data,Beijing,Jun 11-14,2007. New York:ACM,2007:1029-1040.

[9]Yang H C,Parker D S.Traverse:simplified indexing on large Map-Reduce-Merge clusters[C]//LNCS 5463:Proceedings of the 14th International Conference on Database Systems for Advanced Applications,Brisbane,Australia,Apr 21-23, 2009.Berlin,Heidelberg:Springer,2009:308-322.

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

[11]Ding Linlin,Wang Guoren,Xin Junchang,et al.ComMap Reduce:an improvement of MapReduce with lightweight communication mechanisms[C]//LNCS 7239:Proceedings of the 17th International Conference on Database Systems for Advanced Applications,Busan,Korea,Apr 15-19,2012.Berlin,Heidelberg:Springer,2012:150-168.

[12]Abouzeid A,Bajda-Pawlikowski K,Abadi D,et al.Hadoop-DB:an architectural hybrid of MapReduce and DBMS technologies for analytical workloads[C]//Proceedings of the 35th International Conference on Very Large Data Bases,Lyon, France,Aug 24-28,2009.NewYork:ACM,2009:922-933.

[13]Dittrich J,Quiané-Ruiz J A,Jindal A,et al.Hadoop++:making a yellow elephant run like a cheetah(without it evenoticing) [C]//Proceedings of the 36th International Conference on Very Large Data Bases,Singapore,Sep 13-17,2010.New York:ACM,2010:515-529.

[14]Dittrich J,Quiané-Ruiz J A,Richter S,et al.Only aggressive elephants are fast elephants[C]//Proceedings of the 38th International Conference on Very Large Data Bases,Istanbul, Turkey,Aug 27-31,2012.NewYork:ACM,2012:1591-1602.

[15]Lin Yuting,Agrawal D,Chen Chen,et al.Llama:leveraging columnar storage for scalable join processing in the Map-Reduce framework[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, Athens,Greece,Jun 12-16,2011.New York:ACM,2011: 961-972.

[16]Zhang Yanfeng,Gao Qixin,Gao Lixin,et al.Priter:a distributed framework for prioritized iterative computations [C]//Proceedings of the 2nd ACM Symposium on Cloud Computing,Cascais,Portugal,Oct 26-28,2011.New York: ACM,2011:1-13.

[17]Chattopadhyay B,Lin Liang,Liu Weiran,et al.Tenzing a SQL implementation on the MapReduce framework[C]//Proceedings of the 37th International Conference on Very Large Data Bases,Seattle,USA,Aug 29-Sep 3,2011.New York: ACM,2011:1318-1327.

[18]Zhu Haitong.Efficient star join for column-oriented data store in the MapReduce environment[D].Shanghai:East China Normal University,2012.

附中文參考文獻(xiàn)：

[7]趙彥榮,王偉平,孟丹,等.基于Hadoop的高效連接查詢處理算法[J].軟件學(xué)報(bào),2012,23(8):2032-2041.

[18]祝海通.MapReduce環(huán)境中基于列存儲(chǔ)的一種高效的星型連接方法[D].上海:華東師范大學(xué),2012.

ZHANG Jingwei was born in 1977.He received the Ph.D.degree from East China Normal University in 2012. Now he is an associate professor at Guilin University of Electronic Technology,and the member of CCF.His research interests include Web data analysis and management,query optimization technologies,massive data management and storage,etc.

張敬偉（1977—），男，山東蓬萊人，2012年于華東師范大學(xué)獲得博士學(xué)位，現(xiàn)為桂林電子科技大學(xué)計(jì)算機(jī)與信息安全學(xué)院副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)閃eb數(shù)據(jù)分析與管理，查詢優(yōu)化技術(shù)，海量數(shù)據(jù)管理和存儲(chǔ)等。

SHANG Hongjia was born in 1989.He is an M.S.candidate at School of Computer and Information Security,Guilin University of Electronic Technology.His research interests include database technology and distributed computing,etc.

尚宏佳（1989—），男，湖北隨州人，桂林電子科技大學(xué)計(jì)算機(jī)與信息安全學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫技術(shù)，分布式計(jì)算等。

QIAN Junyan was born in 1973.He received the Ph.D.degree from Southeast University in 2008.Now he is a professor at Guilin University of Electronic Technology,and the senior member of CCF.His research interests include software engineering,program analysis and verification,information security and VLSI fault tolerance technologies,etc.

錢俊彥（1973—），男，浙江嵊縣人，2008年于東南大學(xué)獲得博士學(xué)位，現(xiàn)為桂林電子科技大學(xué)計(jì)算機(jī)與信息安全學(xué)院教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)檐浖こ?，程序分析與驗(yàn)證，信息安全，VLSI容錯(cuò)技術(shù)等。

ZHOU Ping was born in 1961.She is a professor at Guilin University of Electronic Technology.Her research interests include speech signal processing and intelligent control,etc.

周萍（1961—），女，河北唐山人，桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院教授，主要研究領(lǐng)域?yàn)檎Z音信號(hào)處理，智能控制等。

YANG Qing was born in 1976.She is an associate professor at Guilin University of Electronic Technology.Her research interests include massive data management and large-scale intelligent information processing,etc.

楊青（1976—），女，廣西恭城人，桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院副教授，主要研究領(lǐng)域?yàn)楹Ａ繑?shù)據(jù)管理，大規(guī)模智能信息處理等。

Join Query Optimization Based on MapReduce under Skewed Data*

ZHANG Jingwei1,2,SHANG Hongjia1,QIAN Junyan1,ZHOU Ping3,YANG Qing3+
1.Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China
2.Guangxi Cooperative Innovation Center of Cloud Computing and Big Data,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China
3.Guangxi Key Laboratory of Automatic Measurement Technology and Instrument,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China

+Corresponding author:E-mail:gtyqing@hotmail.com

ZHANG Jingwei,SHANG Hongjia,QIAN Junyan,et al.Join query optimization based on MapReduce under skewed data.Journal of Frontiers of Computer Science and Technology,2017,11(5)：752-767.

MapReduce,a classic distributed computing environment,can improve the performance of join query on large-scale data,but when the join attributes do not follow a uniform distribution,the pure hash strategy in traditional MapReduce will lead to load imbalance over computing nodes,which will reduce the performance of overall task.Aiming at the data skew problem in the join query,this paper studies the join query optimization based on MapReduce computing framework.Firstly,this paper conducts experimental analysis for the improved repartitioning join query algorithm,studies the execution phases of join query based on traditional MapReduce computing framework,and finds the performance bottlenecks of join query on MapReduce computing framework when data do not follow a uniform distribution.Based on the above,this paper designs and implements an improved join query optimization algorithm,which is based on an execution strategy by integrating the combination segmentation method and equilibrium partitioning method.The experimental results show that the proposed optimization method provides a good solution for distributed join query on large-scale skewed datasets,and presents an excellent time performance and scalability.

join query;MapReduce;skewed data

10.3778/j.issn.1673-9418.1604022

A

TP311.130

*The National Natural Science Foundation of China under Grant Nos.U1501252,61363005,61462017(國家自然科學(xué)基金);the Natural Science Foundation of Guangxi under Grant Nos.2014GXNSFAA118353,2014GXNSFAA118390，2014GXNSFDA118036(廣西自然科學(xué)基金);the High Level Innovation Team of Colleges and Universities in Guangxi and Outstanding Scholars Program Funding (廣西高等學(xué)校高水平創(chuàng)新團(tuán)隊(duì)及卓越學(xué)者計(jì)劃);the Program of Guangxi Cooperative Innovation Center of Cloud Computing and Big Data(廣西云計(jì)算與大數(shù)據(jù)協(xié)同創(chuàng)新中心基金項(xiàng)目);the Guangxi Cooperative Innovation Center of IOT and Industrialization (廣西物聯(lián)網(wǎng)技術(shù)與產(chǎn)業(yè)化推進(jìn)協(xié)同創(chuàng)新中心資助項(xiàng)目).

Received 2016-04,Accepted 2016-06.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-06-27,http://www.cnki.net/kcms/detail/11.5602.TP.20160627.0929.006.html