大數(shù)據(jù)連接算法分析

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

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：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)計顯示全部企業(yè)的信息每天高達 2.2ZB存儲量，其中大型企業(yè)平均每天可以產(chǎn)生10WTB的信息量，而中小企業(yè)平均每天可以產(chǎn)生 563TB 的數(shù)據(jù)量。大數(shù)據(jù)主要有四個典型特征：海量、多樣性、高速、易變[1-5]。連接算法優(yōu)化是大數(shù)據(jù)熱點問題之一，2010年以來，數(shù)據(jù)庫頂級會議ICDE，Sigmod和VLDB每年都有專門的文章研究基于MapReduce的連接算法效率優(yōu)化[6-10]。研究基于MapReduce的連接算法并優(yōu)化其效率是大數(shù)據(jù)在云平臺下能夠快速處理的關鍵。依據(jù)連接條件，目前主要連接算法主要體現(xiàn)在以下三個方面：等值連接算法的設計與優(yōu)化，數(shù)據(jù)傾斜時的連接算法的設計與優(yōu)化，任意連接算法的設計與優(yōu)化[11-15]。

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

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

1.1等值連接算法

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

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

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

1.3任意連接算法

任意連接是數(shù)據(jù)庫中一種關系運算方式，又可以稱之為[θ]連接，關系運算符主要包括<、[≤、=、≥、>]等，等值連接只是其中特殊一種方式，現(xiàn)在相對等值連接，任意連接具有更普遍的意義[16]。以兩個企業(yè)商品數(shù)據(jù)集句R（A，B）和S（B，C）為例，設定屬性B是商品入庫時間，A表示第一個企業(yè)的商品名字，C表示第二個企業(yè)商品名字，S.B>R.B為其對應的連接條件，數(shù)據(jù)倉庫Hive在設定條件下不能有效的支持[θ]連接，由于reduce端接收的來自map階段產(chǎn)生key-value鍵值對形式的數(shù)據(jù)時間，不能提前獲得兩個數(shù)據(jù)集中的準確的數(shù)據(jù)分布信息，如果其中一個數(shù)據(jù)集不是對全部節(jié)點廣播，其他數(shù)據(jù)集遵循哈希分配在相應節(jié)點上，就會導致不易確定連接屬性B在R和S中哪些是適合連接條件，之后必須在每個節(jié)點做出相應的連接判斷，這樣shuffle階段必然加大網(wǎng)絡傳輸量[14]?？梢娪行гO計和實現(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進行多表和兩表的等值連接算法設計，獲得各種算法在不同的數(shù)據(jù)集下的連接處理效率；第三步，進行對算法進行建模，任意數(shù)據(jù)集實驗分析出選擇一個最佳的等值連接方案。

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

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

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

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

3 基于BloomFilter的等值連接實驗分析

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

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

4 結束語

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

參考文獻：

[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] 王珊， 王會舉， 覃雄派， 周烜， 架構大數(shù)據(jù)：挑戰(zhàn)，現(xiàn)狀與展望計算機學報，2011，34（10）：1741-1752.

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

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

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

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

[11] 張凱. 視頻運動檢測算法的研究和分析[J]. 遼寧工學院學報， 2007（1）.

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

[13] 彭輔權， 金蒼宏， 明暉. MapReduce中Shuffle優(yōu)化勾重構[D]. 杭州： 浙江大學計算機學院， 2012.

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

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

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