李立現(xiàn)　屈曉平　高琴琴

摘要：大數(shù)據(jù)主要有四個(gè)典型特征：海量、多樣性、高速、易變。連接算法優(yōu)化是大數(shù)據(jù)熱點(diǎn)問題之一，2010年以來，數(shù)據(jù)庫頂級(jí)會(huì)議ICDE，Sigmod和VLDB每年都有專門的文章研究基于MapReduce的連接算法優(yōu)化。依據(jù)連接條件主要可以分為等值連接法、數(shù)據(jù)傾斜時(shí)連接法和任意連接法，分析三種數(shù)據(jù)連接方法，介紹三種連接算法設(shè)計(jì)和優(yōu)化方式，并針對(duì)基于BloomFilter等值連接設(shè)計(jì)和優(yōu)化做了和二階段法和三階段法的實(shí)驗(yàn)分析。兩表等值連接，數(shù)據(jù)量較大時(shí)，采用基于BloomFilter等值連接方式會(huì)在一定范圍減少算法執(zhí)行時(shí)間，提高數(shù)據(jù)連接效率。

關(guān)鍵詞：云計(jì)算；大數(shù)據(jù)集；等值連接；任意連接

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）13-0219-02

Abstract： Big data mainly has four typical characteristics： mass， diversity， high speed， easy to change.Connection algorithm optimization is one of the big data issues， since 2010， the database top meeting ICDE Sigmod and VLDB every year have special article studies connection efficiency optimization algorithm based on graphs.According to the connecting conditions are equivalent connecting method， the data skew links and any link method， analyzes the three methods of data connection， introduce three kinds of connection algorithm design and optimization method， and based on BloomFilter contour connection design and optimization done and two stage method and experimental analysis of three phase method.Equal join two tables， large amount of data， based on BloomFilter equivalent connections will be reduced in a certain range algorithm execution time， improve the efficiency of data connection.

Key words： Cloud Computing； Big Data ； Equi-join； [θ]Join

根據(jù)參考材料[1]中統(tǒng)計(jì)顯示全部企業(yè)的信息每天高達(dá) 2.2ZB存儲(chǔ)量，其中大型企業(yè)平均每天可以產(chǎn)生10WTB的信息量，而中小企業(yè)平均每天可以產(chǎn)生 563TB 的數(shù)據(jù)量。大數(shù)據(jù)主要有四個(gè)典型特征：海量、多樣性、高速、易變[1-5]。連接算法優(yōu)化是大數(shù)據(jù)熱點(diǎn)問題之一，2010年以來，數(shù)據(jù)庫頂級(jí)會(huì)議ICDE，Sigmod和VLDB每年都有專門的文章研究基于MapReduce的連接算法效率優(yōu)化[6-10]。研究基于MapReduce的連接算法并優(yōu)化其效率是大數(shù)據(jù)在云平臺(tái)下能夠快速處理的關(guān)鍵。依據(jù)連接條件，目前主要連接算法主要體現(xiàn)在以下三個(gè)方面：等值連接算法的設(shè)計(jì)與優(yōu)化，數(shù)據(jù)傾斜時(shí)的連接算法的設(shè)計(jì)與優(yōu)化，任意連接算法的設(shè)計(jì)與優(yōu)化[11-15]。

1 大數(shù)據(jù)集連接算法

近年來，大數(shù)據(jù)領(lǐng)域中最常用的一個(gè)并行框架是MapReduce，MapReduce為許多大型公司尤其是互聯(lián)網(wǎng)公司處理業(yè)務(wù)需求，基于MapReduce設(shè)計(jì)的Hive是現(xiàn)在市場(chǎng)主流的分布式數(shù)據(jù)倉(cāng)庫[14]。程序設(shè)計(jì)人員在進(jìn)行任務(wù)查詢時(shí)，數(shù)據(jù)倉(cāng)庫Hive內(nèi)部連接操作是最占時(shí)間的，因而數(shù)據(jù)連接算法的設(shè)計(jì)和優(yōu)化就成為目前的熱點(diǎn)和關(guān)鍵技術(shù)。

1.1等值連接算法

缺少索引支持的MapReduce并行計(jì)算框架，如果需要處理一個(gè)或多個(gè)數(shù)據(jù)集，就需要MapReduce在系統(tǒng)內(nèi)全部加載相應(yīng)的數(shù)據(jù)集中的數(shù)據(jù)，先是需要map函數(shù)處理，接者是使用網(wǎng)絡(luò)發(fā)送給reduce端，并且相應(yīng)的處理操作要在reduce端進(jìn)行，最后在HDFS中存放最終結(jié)果[14]。比如在R連接S時(shí)，設(shè)定數(shù)據(jù)集R的大小為r，數(shù)據(jù)集S的大小為s，reduce端接全部收來自map發(fā)送的兩個(gè)數(shù)據(jù)集，在網(wǎng)絡(luò)傳輸shuffle階段時(shí)間代價(jià)記為C（r + s），這里的C我們?cè)O(shè)定為一個(gè)整數(shù)。假設(shè)我們選取連接選擇率（0.1）較小的R和S，可以獲知在shuffle階段只需要發(fā)送的數(shù)據(jù)量是0.1C（r + s），消減了原來網(wǎng)絡(luò)傳輸量的9/10，尤其在集群環(huán)境 Hadoop中，同一時(shí)刻會(huì)處理很多數(shù)據(jù)，在有限的網(wǎng)絡(luò)寬帶資源下，不但可以提高算法的運(yùn)行效率，而且在Hadoop系統(tǒng)中也可以提高整體的吞吐量，優(yōu)化的等值連接算法對(duì)網(wǎng)絡(luò)傳輸?shù)膬?yōu)化是十分重要[15]。

1.2數(shù)據(jù)傾斜時(shí)的連接算法

在數(shù)據(jù)通常的分析處理中，常常會(huì)有某個(gè)值或者某些值出現(xiàn)的頻率很高，遠(yuǎn)遠(yuǎn)高于其他數(shù)值出現(xiàn)頻率，數(shù)據(jù)的這種現(xiàn)象我們稱之為數(shù)據(jù)傾斜或者傾斜的數(shù)據(jù)，比如某個(gè)論壇上，發(fā)帖數(shù)目方面活躍用戶要遠(yuǎn)遠(yuǎn)高于非活躍用戶，或者數(shù)據(jù)丟失情況下，日志收集中常常使用空值（NULL），從而導(dǎo)致多次出現(xiàn)（NULL） [14]。在連接查詢中兩表或者多表會(huì)遵循哈希函數(shù)的規(guī)則，在同一節(jié)點(diǎn)上分配相同的數(shù)值，這樣就會(huì)使得在的節(jié)點(diǎn)上傾斜數(shù)據(jù)要非常明顯的數(shù)據(jù)增多，尤其在并行環(huán)境的運(yùn)行條件下，reduce端的負(fù)載會(huì)因傾斜的數(shù)據(jù)而造成不均衡，形成“長(zhǎng)板效應(yīng)”，大部分reduce節(jié)點(diǎn)執(zhí)行時(shí)間很短，一個(gè)或幾個(gè)節(jié)點(diǎn)執(zhí)行時(shí)間較長(zhǎng)，導(dǎo)致整個(gè)MapReduce程序在較長(zhǎng)的時(shí)間運(yùn)行[16]。所以，深入研究并優(yōu)化數(shù)據(jù)傾斜時(shí)的兩表或者多表連接算法的效率是提高大數(shù)據(jù)處理的關(guān)鍵。

1.3任意連接算法

任意連接是數(shù)據(jù)庫中一種關(guān)系運(yùn)算方式，又可以稱之為[θ]連接，關(guān)系運(yùn)算符主要包括<、[≤、=、≥、>]等，等值連接只是其中特殊一種方式，現(xiàn)在相對(duì)等值連接，任意連接具有更普遍的意義[16]。以兩個(gè)企業(yè)商品數(shù)據(jù)集句R（A，B）和S（B，C）為例，設(shè)定屬性B是商品入庫時(shí)間，A表示第一個(gè)企業(yè)的商品名字，C表示第二個(gè)企業(yè)商品名字，S.B>R.B為其對(duì)應(yīng)的連接條件，數(shù)據(jù)倉(cāng)庫Hive在設(shè)定條件下不能有效的支持[θ]連接，由于reduce端接收的來自map階段產(chǎn)生key-value鍵值對(duì)形式的數(shù)據(jù)時(shí)間，不能提前獲得兩個(gè)數(shù)據(jù)集中的準(zhǔn)確的數(shù)據(jù)分布信息，如果其中一個(gè)數(shù)據(jù)集不是對(duì)全部節(jié)點(diǎn)廣播，其他數(shù)據(jù)集遵循哈希分配在相應(yīng)節(jié)點(diǎn)上，就會(huì)導(dǎo)致不易確定連接屬性B在R和S中哪些是適合連接條件，之后必須在每個(gè)節(jié)點(diǎn)做出相應(yīng)的連接判斷，這樣shuffle階段必然加大網(wǎng)絡(luò)傳輸量[14]。可見有效設(shè)計(jì)和實(shí)現(xiàn)在MapReduce環(huán)境下兩表和多表連接算法是影響到大數(shù)據(jù)處理效率。

2 連接算法優(yōu)化

2.1等值連接算法優(yōu)化

在大數(shù)據(jù)處理分析中，較為突出的是多表和兩表的等值連接，改善等值連接算法可以較大提高數(shù)據(jù)處理效率，所以可以引入BloomFilter優(yōu)化等值連接算法[14]。第一步，利用MapReduce快速高效生成BlooomFilter；第二步，基于BloomFilter進(jìn)行多表和兩表的等值連接算法設(shè)計(jì)，獲得各種算法在不同的數(shù)據(jù)集下的連接處理效率；第三步，進(jìn)行對(duì)算法進(jìn)行建模，任意數(shù)據(jù)集實(shí)驗(yàn)分析出選擇一個(gè)最佳的等值連接方案。

2.2 數(shù)據(jù)傾斜時(shí)的等值連接算法優(yōu)化

MapReduce環(huán)境中，在使用基于Hadoop默認(rèn)分區(qū)方法，傾斜的數(shù)據(jù)集會(huì)造成reduce端的數(shù)據(jù)集合傾斜，處理數(shù)據(jù)數(shù)量隨著各個(gè)reduce端發(fā)生改變，使得整個(gè)MapReduce程序降低了執(zhí)行效率[14]。在實(shí)際使用中，經(jīng)常出現(xiàn)傾斜的數(shù)據(jù)，所以要優(yōu)化傾斜數(shù)據(jù)連接是十分必要的，第一步，利用Maxdiff直方圖技術(shù)，獲得屬性B在R中傾斜元素的集合Rskew和數(shù)據(jù)集S中傾斜元素的集合Sskew；第二部，map函數(shù)將Rskew和Sskew中的數(shù)據(jù)隨機(jī)發(fā)給reduce端，發(fā)送方式為key-value鍵值對(duì)形式；第三步，reduce函數(shù)接收，輸出到HDFS中。

2.3多表[θ]連接算法優(yōu)化

[θ]連接比等值連接更為普遍，具有豐富的語義，更適合一般化的查詢需求。MapReduce平臺(tái)上，[θ]連接算法不容易實(shí)現(xiàn)，因而優(yōu)化多表的[θ]連接算法是提高大數(shù)據(jù)分析處理的關(guān)鍵[14]。第一步，定義R1連接R2連接…連接 Rn連接方案的連接圖；第二步，連接策略：在數(shù)據(jù)集對(duì)應(yīng)的查詢連接圖，確定劃分，每個(gè)劃分的每個(gè)子圖都對(duì)應(yīng)一個(gè)連接策略，第三步，函數(shù)estimatedCost給出基于MapReduce的多表任意連接效率最好方案。

3 基于BloomFilter的等值連接實(shí)驗(yàn)分析

第三節(jié)介紹了三種優(yōu)化方法，這里就等值連接優(yōu)化算法兩表連接進(jìn)行實(shí)驗(yàn)分析。第一步，基于 MapReduce 的 BloomFilter 建立算法，對(duì)連接屬性進(jìn)行預(yù)先過濾，篩除掉對(duì)最終結(jié)果沒有影響的數(shù)據(jù)元素，消減后續(xù)階段shuffle的網(wǎng)絡(luò)傳輸量，提高數(shù)據(jù)連接效率，這里分別就基于BloomFilter的改進(jìn)法，兩階段法和三階段法[14]。假設(shè)R（A，B）和S（B，C）兩個(gè)數(shù)據(jù)集每個(gè)都包含了兩個(gè)屬性，每個(gè)屬性值是通過隨機(jī)生成的1到1000000范圍內(nèi)的整數(shù)，并且R（A，B）和S（B，C）數(shù)據(jù)集數(shù)目相等。實(shí)驗(yàn)主要驗(yàn)證兩個(gè)方面的改變，一是數(shù)據(jù)集R和S中數(shù)據(jù)數(shù)目的大小，二是數(shù)據(jù)集R和S的屬性B的連接選擇率，我們定義連接選擇率如下：符合設(shè)定連接條件的屬性的值在數(shù)據(jù)集中所占比例，比如選擇率是0.1，表示有10%的數(shù)據(jù)集R或者S 中元組需要進(jìn)行連接操作。

如圖1所示的實(shí)驗(yàn)結(jié)果，數(shù)據(jù)數(shù)量在5千萬以下時(shí)，Improved Repartition Join算法的效率要低于兩階段法和三階段法，試驗(yàn)中優(yōu)化算法在運(yùn)行中創(chuàng)建BloomFilter并增加了MapReduce輪數(shù)，所以增加了時(shí)間消耗。當(dāng)數(shù)據(jù)量逐步增大到5千萬以上時(shí)間，優(yōu)化算法可以利用BloomFilter過濾掉很多無用數(shù)據(jù)，減少shuffle階段網(wǎng)絡(luò)傳輸量和reduce階段的處理時(shí)間，優(yōu)化算法效率就大大高于標(biāo)準(zhǔn)算法。實(shí)驗(yàn)對(duì)比分析，連接屬性選擇率小于1%時(shí)，兩階段法的效率要比三階段法差，是由于第三階段和三階段法的第二階段不需要shuffle過程和reduce過程，僅僅包含map過程，從而較大消減算法運(yùn)行時(shí)間。在逐步增加到一定數(shù)目的數(shù)據(jù)集時(shí)，三階段法的第二階段產(chǎn)生的數(shù)據(jù)集Si會(huì)增加很大，傳輸Si到全部的map中，會(huì)浪費(fèi)很多時(shí)間，因而兩階段法的運(yùn)行效率要高于三階段法。

4 結(jié)束語

簡(jiǎn)單介紹了根據(jù)連接條件分類的三種方法： 等值連接法、數(shù)據(jù)傾斜時(shí)連接法和任意連接法，說明了這三種方法各自的特點(diǎn)，指出了各自所適用的數(shù)據(jù)范圍，并且對(duì)比了兩表和多表下三種連接算法。重點(diǎn)基于BloomFilter等值連接實(shí)驗(yàn)的進(jìn)行詳細(xì)分析。分別采用二階段、三階段和基于BloomFilter的兩表等值連接進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)表明，兩表等值連接，數(shù)據(jù)量較大時(shí)，采用基于BloomFilter等值連接方式會(huì)在一定范圍減少算法執(zhí)行時(shí)間，提高數(shù)據(jù)連接效率。

參考文獻(xiàn)：

[1] http：//www.enet.com.cn/cio/zhuanti/2012/bigdata.

[2] Randal E. B. ， Randy H. K. ， Edward D. L. ， Big-Data Computing： Creating revolutionaryBreakth

roughs in commerce， science and society[R]. http：//www.cra.org/ccc/files/docs/iiiit/Big-Data.pdf.

[3] James M. ， Michael C. ， Brad B. ，Jacques B” Big data： The next frontier for innovation， compe-

tition， and productivity[R]， http：//www.mckinsey.com/Insights/MGI/Research/Technology-and-

Innovation/Big-data-The-next-frontier-for-innovation

[4] The digital universe in 2020： big data， bigger digital shadows， and biggest growth in the far

east[EB/OL]. http：//www.emc.com/collateral/analyst-reports/idc-the-digitaluniverse-in-2020.pdf.

[5] Ibrahim S， Hai J， et al. Handling Partitioning Skew in MapReduce using LEEN[J]. Peer-to-

PeerNetworking and Applications， 2013， 409-424.

[6] 王珊， 王會(huì)舉， 覃雄派， 周烜， 架構(gòu)大數(shù)據(jù)：挑戰(zhàn)，現(xiàn)狀與展望計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1741-1752.

[7] 丁琳琳， 信俊昌， 王國(guó)仁， 黃山.基于Map-Reduce的海量數(shù)據(jù)高效Skyline查詢處理[J]. 計(jì)算機(jī)學(xué)報(bào)， 2011， 34（10）： 1785-1796.

[8] 李建江， 崔健， 王聃，等. MapReduce 并行編程模型研究綜述[J]. 電子學(xué)報(bào)， 2012， 39（11）： 2635-2642.

[9] 彌艷金. MapReduce模型在Hadoop平臺(tái)下實(shí)現(xiàn)作業(yè)調(diào)度算法的研究和改進(jìn)[D]. 華南理工大學(xué)碩士論文， 2011.

[10] 李成華， 張新訪， 金海，等.Map Reduce：新型的分布式并行計(jì)算編程模型[J]. 計(jì)算機(jī)工程與科學(xué)， 2011（03）.

[11] 張凱. 視頻運(yùn)動(dòng)檢測(cè)算法的研究和分析[J]. 遼寧工學(xué)院學(xué)報(bào)， 2007（1）.

[12] 李鑫. Hadoop框架的擴(kuò)展和性能調(diào)[D]. 西安：西安建筑科技大學(xué)碩士論文， 2012（05）.

[13] 彭輔權(quán)， 金蒼宏， 明暉. MapReduce中Shuffle優(yōu)化勾重構(gòu)[D]. 杭州： 浙江大學(xué)計(jì)算機(jī)學(xué)院， 2012.

[14] 張常淳. 基于MapReduce的大大數(shù)據(jù)算法的設(shè)計(jì)與優(yōu)化[D]. 中國(guó)科學(xué)技術(shù)大學(xué)博士論文， 2014.

[15] 孫慧. 基于hadhoop框架的大數(shù)據(jù)集連接優(yōu)化算法[D]. 南京郵電大學(xué)碩士論文， 2013.

[16] 郭騏愷. 基于MapReduce的連接方法研究[D]. 吉林大學(xué)碩士論文， 2014.