陳軍

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

隨著大數(shù)據(jù)時(shí)代的到來，以MapReduce和Spark為代表的分布式計(jì)算框架在大數(shù)據(jù)處理中發(fā)揮了重要作用。連接與過濾、排序、聚合等都是常用的數(shù)據(jù)庫查詢操作，相比外連接等非等值連接，等值連接更為常用。針對(duì)分布式平臺(tái)分布式存儲(chǔ)和計(jì)算的特點(diǎn)，對(duì)等值連接無關(guān)連接元組占用shuffle資源、等值連接數(shù)據(jù)傾斜等問題進(jìn)行優(yōu)化具有重要意義。

1 常見等值連接方法

1.1 M ap-sid e Join

在大表和小表等值連接操作中，若小表可以加載到內(nèi)存中，則可將小表廣播到各個(gè)分布式節(jié)點(diǎn)中，從而避免shuffle、reduce等過程，效率較高。在Map Reduce上借助Distributed Cache實(shí)現(xiàn)的了Map-side Join。在Spark中的BroadcastJoin提供了與此類似的功能，通常情況下表廣播的默認(rèn)閾值為10M，可通過spark.sql.au?to Broadcast Join Threshold進(jìn)行設(shè)置，若設(shè)為-1表示禁用Broadcast Join。

1.2 Reduce-sid e Join

當(dāng)兩表均較大時(shí)，兩表均無法放入內(nèi)存，這就需要map端根據(jù)連接key值的hash值進(jìn)行分區(qū)，將key值相同的點(diǎn)存放到同一節(jié)點(diǎn)中，然后在reduce端對(duì)收到的數(shù)據(jù)進(jìn)行等值連接操作。該方法實(shí)現(xiàn)簡(jiǎn)單，適用場(chǎng)景較廣，但由于中間涉及大量的shuffle操作，還存在著數(shù)據(jù)傾斜等問題，效率不高。在Spark中的HashJoin實(shí)現(xiàn)方法與之類似。

2 元組過濾技術(shù)

2.1 問題描述

在兩表進(jìn)行等值連接時(shí)，兩表中都可能存在著大量無最終連接結(jié)果的元組，它們也參與到shuffle過程中，從造成網(wǎng)絡(luò)資源的浪費(fèi)。傳統(tǒng)數(shù)據(jù)庫中提取連接屬性進(jìn)行過濾的方法，也存在著在分布式環(huán)境中連接屬性數(shù)據(jù)量較大，無法放入所有節(jié)點(diǎn)內(nèi)存中的問題。采用元組過濾技術(shù)事先將無最終連接結(jié)果的元組過濾掉，將極大提高等值連接操作的效率。

2.2 位圖（B itmap）

大數(shù)據(jù)處理中所說的位圖技術(shù)不同于圖像學(xué)中的概念，它用一個(gè)比特位表示一個(gè)整型數(shù)的存在與否，1表示存在，0表示不存在，對(duì)于一個(gè)int數(shù)字通常需要占用32位，而位圖僅需占用1位，所以極大地節(jié)省了存儲(chǔ)空間。文獻(xiàn)[1]在Map Reduce中運(yùn)用位圖技術(shù)將兩表的連接屬性壓縮生成“背景文件”，然后利用Hadoop的Distributed Cache傳輸?shù)礁鱾€(gè)節(jié)點(diǎn)，并載入內(nèi)存，在map階段實(shí)現(xiàn)了部分無最終連接結(jié)果的元組的過濾，但過濾效果不夠好。

適用場(chǎng)景：在判斷整型數(shù)是否存在時(shí)，位圖能極大節(jié)省存儲(chǔ)空間，但不適用于對(duì)字符串等的操作，且過濾判斷情況分類較少，應(yīng)用范圍窄。

2.3 布隆過濾器（Bloom F ilter）

圖1 布隆過濾器示例

布隆過濾器可以看成位圖的擴(kuò)展，它是1970年由布隆提出來的一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。但這個(gè)判斷有一定誤差的。這個(gè)誤差體現(xiàn)為假陽性（false negative），即屬于這個(gè)集合的元素，一定會(huì)被判為屬于，但有可能會(huì)把本不屬于這個(gè)集合的元素誤判為屬于。如圖1中所示，用a到g生成的布隆過濾器中，a的3個(gè)哈希值均為1，則判定a可能在其中，若x的3個(gè)哈希值不全為1，則x必定不在其中。在分布式平臺(tái)等值連接中如果將布隆過濾器用作連接屬性的過濾，那么誤判的元組雖然會(huì)參與到shuffle中，但不影響最終結(jié)果的正確性。文獻(xiàn)[2]在Map Reduce中，采用兩階段和三階段兩種方法，對(duì)兩表的連接屬性進(jìn)行去重，然后分別生成兩個(gè)布隆過濾器，再將二者進(jìn)行與操作，合并生成最終的布隆過濾器。再將布隆過濾器廣播到各個(gè)節(jié)點(diǎn)，取得了較好的過濾效果。文獻(xiàn)[3]在Spark平臺(tái)下，運(yùn)用Spark本身自帶的RDD相關(guān)操作生成了用于過濾的布隆過濾器，并廣播到各節(jié)點(diǎn)內(nèi)存當(dāng)中，實(shí)現(xiàn)了較好的過濾效果。

適合場(chǎng)景：當(dāng)表連接屬性非外鍵（重復(fù)率較高）、寬表（所含的列較多不便于進(jìn)行廣播操作）、符合連接要求的元組數(shù)較少時(shí)過濾效果好，但用兩表共有連接屬性生成布隆過濾器需要一定預(yù)處理時(shí)間，bloomfilter本身的廣播也會(huì)戰(zhàn)用一定的網(wǎng)絡(luò)資源。

3 數(shù)據(jù)傾斜處理

3.1 問題描述

一個(gè)任務(wù)的最終完成時(shí)間，是由完成時(shí)間最長(zhǎng)的子任務(wù)所決定的。根據(jù)帕內(nèi)托法則（又稱80-20法則）現(xiàn)實(shí)生活中的數(shù)據(jù)大多是不均衡的。在等值連接中，如果采用簡(jiǎn)單的哈希分區(qū)方法，值相同的數(shù)據(jù)將分配到同一節(jié)點(diǎn)，造成最終完成時(shí)間的延長(zhǎng)。

3.2 基于采樣或統(tǒng)計(jì)的重分區(qū)

在采樣或統(tǒng)計(jì)的基礎(chǔ)上，針對(duì)數(shù)值分布特點(diǎn)進(jìn)行重新分區(qū)可有效解決數(shù)據(jù)傾斜問題。文獻(xiàn)[3]提出了簡(jiǎn)單分區(qū)和虛擬節(jié)點(diǎn)分區(qū)。簡(jiǎn)單分區(qū)在傾斜數(shù)據(jù)周邊劃分更多的分區(qū)，但無法解決單一數(shù)值極度傾斜，數(shù)量超過分區(qū)大小的情形，虛擬節(jié)點(diǎn)分區(qū)可有效解決這個(gè)問題。

適用場(chǎng)景：采樣速度快，精度低，統(tǒng)計(jì)成本高，精度好，要依據(jù)需求選擇合理的方法為分區(qū)提供依據(jù)。

3.3 統(tǒng)計(jì)直方圖（H ist ogram）

圖2 直方圖示例

直方圖，又被稱為質(zhì)量分布圖，是由一系列高度不等的縱向條表示數(shù)據(jù)分布的情況的統(tǒng)計(jì)報(bào)告圖。統(tǒng)計(jì)直方圖可以使我們了解等值連接屬性的鍵值分布情況，從而為下一步的傾斜處理打下基礎(chǔ)。文獻(xiàn)[5]在獲取了連接屬性的統(tǒng)計(jì)直方圖的基礎(chǔ)上，將兩表的連接屬性劃分為三組相互對(duì)應(yīng)的集合，分別采用隨機(jī)分發(fā)、廣播復(fù)制、Hash分發(fā)的策略，避免了數(shù)據(jù)傾斜。

適用場(chǎng)景：當(dāng)兩表中傾斜值不同時(shí)，可有效減少數(shù)據(jù)廣播復(fù)制量，但對(duì)兩表中傾斜值相同的情況廣播復(fù)制數(shù)據(jù)量較大，實(shí)現(xiàn)效果較差。

4 結(jié)語

本文介紹了基于當(dāng)前主流分布式計(jì)算框架Map Reduce和Spark的常見等值連接方法BroadcastJoin、Reduce-side Join。針對(duì)元組過濾技術(shù)介紹了BitMap和Bloom filter在獲取等值連接相關(guān)表的連接屬性并過濾掉無最終連接結(jié)果元組時(shí)的運(yùn)用。針對(duì)數(shù)據(jù)傾斜問題分別介紹了基于采樣或統(tǒng)計(jì)的重分區(qū)和基于直方圖的數(shù)據(jù)傾斜處理等方法。等值連接元組過濾和數(shù)據(jù)傾斜問題比較復(fù)雜，沒有完全通用的方案，應(yīng)根據(jù)數(shù)據(jù)特點(diǎn)，結(jié)合各種技術(shù)的優(yōu)缺點(diǎn)，綜合衡量，選擇適合的等值連接方法。

參考文獻(xiàn)：

[1]孫惠.基于Hadoop框架的大數(shù)據(jù)集連接優(yōu)化算法[D].南京郵電大學(xué),2013.

[2]Zhang C,Wu L,Li J.Efficient Processing Distributed Joins with Bloom filter Using Mapreduce[J].International Journal of Grid&Distributed Computing,2013,6:43-58.

[3]周思偉.Spark大表等值連接的優(yōu)化及其在網(wǎng)絡(luò)流量數(shù)據(jù)分析的應(yīng)用研究[D].華南理工大學(xué),2015.

[4]Atta F,Viglas SD,NiaziS.SAND Join—ASkew Handling Join Algorithm for Google'sMap Reduce Framework[C].Multitopic Conference.IEEE,2011:170-175.

[5]梁俊杰,何利民.基于Map Reduce的數(shù)據(jù)傾斜連接算法[J].計(jì)算機(jī)科學(xué),2016,43（9）:27-31.