分布式平臺等值連接優化技術分析

陳軍

（四川大學計算機學院，成都610065）

0 引言

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

1 常見等值連接方法

1.1 M ap-sid e Join

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

1.2 Reduce-sid e Join

當兩表均較大時，兩表均無法放入內存，這就需要map端根據連接key值的hash值進行分區，將key值相同的點存放到同一節點中，然后在reduce端對收到的數據進行等值連接操作。該方法實現簡單，適用場景較廣，但由于中間涉及大量的shuffle操作，還存在著數據傾斜等問題，效率不高。在Spark中的HashJoin實現方法與之類似。

2 元組過濾技術

2.1 問題描述

在兩表進行等值連接時，兩表中都可能存在著大量無最終連接結果的元組，它們也參與到shuffle過程中，從造成網絡資源的浪費。傳統數據庫中提取連接屬性進行過濾的方法，也存在著在分布式環境中連接屬性數據量較大，無法放入所有節點內存中的問題。采用元組過濾技術事先將無最終連接結果的元組過濾掉，將極大提高等值連接操作的效率。

2.2 位圖（B itmap）

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

適用場景：在判斷整型數是否存在時，位圖能極大節省存儲空間，但不適用于對字符串等的操作，且過濾判斷情況分類較少，應用范圍窄。

2.3 布隆過濾器（Bloom F ilter）

圖1 布隆過濾器示例

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

適合場景：當表連接屬性非外鍵（重復率較高）、寬表（所含的列較多不便于進行廣播操作）、符合連接要求的元組數較少時過濾效果好，但用兩表共有連接屬性生成布隆過濾器需要一定預處理時間，bloomfilter本身的廣播也會戰用一定的網絡資源。

3 數據傾斜處理

3.1 問題描述

一個任務的最終完成時間，是由完成時間最長的子任務所決定的。根據帕內托法則（又稱80-20法則）現實生活中的數據大多是不均衡的。在等值連接中，如果采用簡單的哈希分區方法，值相同的數據將分配到同一節點，造成最終完成時間的延長。

3.2 基于采樣或統計的重分區

在采樣或統計的基礎上，針對數值分布特點進行重新分區可有效解決數據傾斜問題。文獻[3]提出了簡單分區和虛擬節點分區。簡單分區在傾斜數據周邊劃分更多的分區，但無法解決單一數值極度傾斜，數量超過分區大小的情形，虛擬節點分區可有效解決這個問題。

適用場景：采樣速度快，精度低，統計成本高，精度好，要依據需求選擇合理的方法為分區提供依據。

3.3 統計直方圖（H ist ogram）

圖2 直方圖示例

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

適用場景：當兩表中傾斜值不同時，可有效減少數據廣播復制量，但對兩表中傾斜值相同的情況廣播復制數據量較大，實現效果較差。

4 結語

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

參考文獻：

[1]孫惠.基于Hadoop框架的大數據集連接優化算法[D].南京郵電大學,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大表等值連接的優化及其在網絡流量數據分析的應用研究[D].華南理工大學,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的數據傾斜連接算法[J].計算機科學,2016,43（9）:27-31.