MapReduce模型中基于直方圖的數據均衡算法

周渭博, 鐘勇, 王陽,2

1.中國科學院成都計算機 應用研究所, 四川 成都　610041;2.中國科學院大學, 北京　100049;3.成都崇信大數據服務有限公司, 四川 成都　611230

隨著信息技術的發展,人們正在以前所未有的速度生產和消費各種各樣的數據,面對海量數據的不斷增長,傳統的數據存儲和計算模型無法滿足需求,分布式系統得到了長足發展,其中Apache開源的Hadoop[1]以其高可靠和低成本優勢,迅速成為業內廣泛采用的分布式解決方案。

MapReduce模型[2]是Hadoop的核心計算框架,分為Map和Reduce 2個階段:Map階段完成原始數據的并行計算,產生中間數據;Reduce階段讀取中間數據并計算得到最終結果。其性能取決于數據分布狀態[3],數據分布比較均衡,性能就比較高,一旦出現數據傾斜,性能就會降低,因此研究MapReduce模型中數據分布狀態,對提升整個分布式計算的性能有很重要的意義。

本文通過構建數據塊直方圖、存儲節點直方圖和文件直方圖的方式來描述MapReduce模型中的數據分布狀態,判斷是否存在數據傾斜,并利用貪心策略,通過數據塊交換的方法,在不改變每個存儲節點存儲量的條件下,使數據的分布趨于均衡。

1　相關研究

1.1　直方圖

在統計學領域,直方圖常用于描述數據的分布狀態,一般用橫軸表示數據類型或數據范圍,縱軸用一系列高度不等的縱向條紋或線段表示數據的分布情況。直方圖描述的數據分布狀態可以為分布式并行計算的效率優化奠定基礎[4-5],文獻[6]中利用元組抽樣方法提出基于MapReduce的小波直方圖構建算法,文獻[7]中提出了基于MapReduce的maxdiff直方圖的構建方法,文獻[8]中對MapReduce框架進行擴展,在map( )函數之前和reduce( )函數之后分別增加了數據的采樣和統計,對基于MapReduce的等寬和等深直方圖構建算法進行了改進。

上述基于MapReduce的直方圖構建算法的核心思想是將文件中的原始數據在Map階段計算并轉換成對的形式,然后通過Hash分區將對傳輸到相應的Reduce節點,最后在Reduce節點上進行直方圖的構建,這必然會出現Map節點與Reduce節點間數據傳輸量大的問題。盡管很多改進算法能夠降低Map節點與Reduce節點間的數據傳輸量,但仍然無法從根本上解決該問題。

1.2　數據均衡

MapReduce的計算過程中可能出現2個方面的性能瓶頸:Map階段并行計算時間受到負載重的Map任務制約;Reduce階段計算時間受到負載重的Reduce任務制約。文獻[9]中分析了原因:Map階段是由于原始數據分布不均衡,導致某一個(或某一些)Map任務處理的數據量遠多于其他Map任務;Reduce階段是由于數據內容本身的傾斜和Hadoop默認Hash分區方法不合理,導致某一個(或某一些)Reduce任務的數據處理量遠多于其他Reduce任務。

Map階段的數據傾斜與數據內容息息相關,而數據內容是數據自身的屬性,是無法改變的,因此目前大量的研究集中在Reduce階段對中間數據的分區方法改進上。例如:文獻[10-11]中提出基于元組的采樣策略,文獻[12-13]中提出基于數據塊的采用策略,其思路都是先采樣后調整分區;文獻[14]中提出了一種增量式分區策略,通過多輪遞增機制實現Reduce端數據平衡。

基于以上研究現狀,本文嘗試通過改進的基于MapReduce模型的數據直方圖并行構造算法完成對Map階段的數據傾斜進行度量和判定的工作,并在此基礎上通過數據均衡算法對其存在的數據傾斜問題進行改進和優化。

2　直方圖構造算法

針對MapReduce模型中直方圖數據傳輸量大的問題,本文通過計算分組、計算頻率和、傳輸直方圖信息等過程實現基于MapReduce的數據直方圖的并行構建,從根本上解決了Map節點與Reduce節點間的數據傳輸量大的問題。

2.1　相關定義

橫看成嶺側成峰,遠近高低各不同。我們在看待事物的時候,如果角度不同,往往會得到不同的結果。對于數據來說,具有同樣的道理。數據本身是有具有維度的,同樣的數據從不同的維度進行觀察往往也會得到不同的結果。在具體的數據應用場景中,通常是針對某一個(或某幾個)具體的數據維度進行數據分析,不失一般性,本文假設一個數據文件datafile中含有mass條記錄,存儲于分布式系統中,并據此進行數學定義:

定義1數據文件datafile中的若干條記錄中均包含某一方面的信息,提取該信息片段,并將其定義為數據維度D,設其對應的值域為R,且其取值可通過計算轉化為數值域R*。

例如在分析Log4j產生的海量日志文件時,其日志級別主要是FATAL、ERROR、WARN、INFO和DEBUG,我們可以將該日志文件作為datafile,在其數據維度D(級別Level)上,值域R為{FATAL,ERROR,WARN,INFO,DEBUG},并可以進一步將其轉換成數值域R*為{1, 2, 3, 4, 5}。

定義2數據文件datafile中的每條記錄在值域R(或數值域R*)上都對應著一個值,設為x,用f(x)表示datafile中所有記錄取值為x的頻率值;另設Gi為該文件的第i個分組,則可以進一步定義當x∈Gi時,datafile中所有記錄在該分組范圍內的頻率和。

y=f(x),x∈Gi

(1)

定義3以Gi為橫坐標軸,處于該范圍內的頻率和f(x)為縱坐標軸,建立數據文件datafile在數據維度D上對應的直方圖H,其數學表達式為:

H={,i∈[1,N],x∈Gi}

(2)

式中,N為分組數。

2.2　算法描述

Step1計算分組

直方圖橫坐標軸的核心是計算文件在數據維度D的對應值域R(或數值域R*)的范圍或類型,并據此進行分組,所有并行構造直方圖的Map節點必須有統一的分組。根據應用條件的不同,本文提出3種確定直方圖橫坐標范圍或類型的方法:

1) 如果文件在數據維度D的對應值域R(或數值域R*)的范圍已知,可以根據經驗快速分組。比如:在分析某文件的時間維度上,可以得到每天、每周、每月或每年的統計分析結果,那么其數值域可以相應的設置為1～24,1～7,1～31或1～12等。

2) 如果文件在數據維度D的對應值域R(或數值域R*)的范圍未知,且相關數據維度的類型不明確,可以先在Map節點上采用相同的標準對數據塊進行并行聚類,再根據分類情況在Reduce節點上統計所有的分類。比如:對微博數據中用戶關注的領域進行分析時,可以先在Map節點并行執行領域聚類計算,再通過Reduce節點合并統計出整個文件所有用戶關注的全部領域。

3) 如果文件在數據維度D的對應值域R(或數值域R*)的范圍未知,且數據分布不清楚,可以在各Map節點通過各自的map task計算每個數據塊的最大值和最小值,然后將所有數據塊對應的最大值和最小值傳輸到一個Reduce節點,計算出全局最大值和全局最小值,再據此進行分組。比如:在分析高中在校學生身高數據時,就可以使用該方法來確定直方圖的橫坐標軸。

Step2計算頻率和

直方圖縱坐標軸的核心是計算每個分組對應的頻率和。由于數據文件被劃分成若干個數據塊分布式存儲,因此在計算頻率和的過程中,本文以數據塊為單位進行計算,可以獲得每個數據塊在每個橫坐標分組范圍內的頻率和。

Step3構造數據塊直方圖

根據直方圖橫坐標軸的分組信息和縱坐標軸的頻率和信息,可以在Map節點上并行的構造出所有的數據塊直方圖。

Step4傳輸數據塊直方圖信息

Map節點并行構造出的數據塊直方圖無法直接傳輸到Reduce節點上,須將其轉化成對的形式,本文采用的形式傳輸一個數據塊的數據直方圖信息。

Step5構造文件直方圖

當所有數據塊的直方圖信息都傳輸到一個Reduce節點上,該Reduce節點將所有數據塊對應的對中key值相同的進行分組,并依次將對應的value值進行累加操作,得到新對,進而構造出整個數據文件的數據直方圖。

基于MapReduce的直方圖并行構造過程如圖1所示:

圖1　直方圖并行構造過程

3　基于直方圖的數據均衡算法

數據直方圖可以描述出在某一數據維度D上,文件在分布式系統中各個存儲節點上的分布情況,根據該分布情況,我們可以提取出相關的數學模型。

3.1　相關定義

定義4設數據文件datafile被劃分成n個block,每個block在建立數據直方圖時劃分成m個組,則該文件中所有block的數據直方圖信息可以使用以下矩陣A來表達:

(3)

式中,該矩陣的第i行表示第i個block對應的數據直方圖的信息,第j列表示數據直方圖的第j個分組,數值aij表示第i個block在其第j個分組組距值范圍內的頻率和信息。

由于數據文件在劃分成block時是采用固定大小劃分的,忽略末尾block差異性,可以得到以下約束條件:

(4)

上述矩陣A及其約束條件可以看作是基于數據塊的文件直方圖的一種數學表達。

如果將這n個block分布存儲于N個存儲節點上(n?N),在不改變每個存儲節點存儲容量的條件下,要想每個分組的頻率和都盡量達到均衡分布,問題就轉變成在含有約束條件的矩陣A中將n個行向量,分成N份,使得每一份中m個分量上的值(或累加值)趨近于相等,問題的本質是在不改變數據塊內容以及每個節點數據塊數量的前提下,尋找一個數據塊均衡分布的全局最優解。

定義5節點均衡向量Aavg

將n個block均衡的分配到N個節點上,則每個節點上的節點均衡值可以定義成一個節點均衡向量:

(5)

定義6組合矩陣Ak

矩陣Ak中的行向量與均衡向量之間的相似性的度量標準很多,比如:歐氏距離、曼哈頓距離、馬氏距離、夾角余弦等,考慮到本文提出的數據均衡算法關注的重點在于每個存儲節點上相關分量的頻率和是否相等,偏重于數值大小的比較,因此本文選用歐式距離作為向量間相似度的衡量標準。

(6)

定義7文件均衡偏差值df。將所有存儲節點中的block所構成的行向量與均衡向量之間的距離累加值定義為文件均衡偏差值。

df=d1+d2+…+dN

(7)

3.2　算法描述

本文提出的數據均衡算法是在不改變所有節點已經分配block數量的情況下,通過各個節點間block的調整和交換,實現數據內容方面的均衡。因此,確定每個節點存儲了多少個block是本算法的前提條件。

例如表1是一個被劃分成14個block的文件,該文件被分布到5個節點上,其每個節點block分布數量信息如表1所示。

表1　節點中block分布數量

根據block直方圖信息和block分布數量信息,本文提出基于數據直方圖的數據均衡算法,具體過程如下:

Step1計算節點均衡向量Aavg;

Step2構造組合矩陣Ak;

Step3計算向量距離;

計算矩陣Ak中所有行向量與節點均衡向量之間的距離;

Step4根據距離大小分配block。

從組合矩陣Ak中選擇d值最小的N個互不相關的行向量,并將組成該行向量的若干個block分配到同一個存儲節點上。

算法:

Input: matrixAand block distribution quantity

Output: block distribution information

1.Aavg[group]←A[n][group];

2.whileAis not null andn>k

∥Take anykrows data from matrixA

∥and accumulate into one row into matrixAk

3.Ak[i][group]←A[n][group];

∥Mark thekrows subscript composed of

∥Ak[i][group] from matrixA

4.Index[i][k]←1…k;

5.di←|Ak[i][group]-Aavg[group]|;

6.min ←di;∥Search minimum value indi

∥Findkrows data from matrixA

7.A[Index[i][0]][group]…A[Index[i][k]][group];

∥Delete thekrows data from matrixA

8.A[n-k][group]←A[n][group];

9.n=n-k;

10.end while

4　實驗驗證

4.1　實驗設計

為了驗證算法的正確性和優越性,利用虛擬機搭建一個由7個節點構成的Hadoop集群進行測試。整個Hadoop集群由2個NameNode節點和5個DataNode節點組成,其中每個節點均為內存512MB,硬盤8GB,操作系統為CentOS 6.5,Hadoop版本為2.6.0,修改并設置block大小為256 kB,副本數為1。

Step1采用構造數據直方圖的算法構造整個數據文件的數據直方圖。將包含1 223 348個隨機數的大小為3.5 MB的數據文件datafile.txt存儲到實驗中搭建的Hadoop集群中,設置分組數為5,構建數據塊數據直方圖和整個文件數據直方圖,分析數據傾斜狀態,并對比直方圖構造算法的數據傳輸量。

Step2根據整個文件的數據直方圖和每個數據塊(block)的數據直方圖的相關信息,采用隨機分配和基于數據直方圖的數據均衡算法進行分配2種方案,對比其文件均衡偏差值,并根據節點數據直方圖分析其數據傾斜狀態。

4.2　實驗結果及分析

4.2.1直方圖分析

由于實驗集群中block大小被設置為256 kB,因此實驗中的數據文件被劃分成14個block,每個block對應的分組和每組頻率和的統計信息如表2所示:

表2　block統計信息

通過表2可以直接構建出每個block的數據直方圖,如圖2所示:

圖2　block數據直方圖

所有block數據直方圖的信息在Reduce節點合并統計后,得到整個文件的數據直方圖,如圖3所示:

圖3　file數據直方圖

通過block的數據直方圖(見圖2)可以看出:多個block之間的數據分布差異明顯;通過整個文件的數據直方圖(見圖3)可以看出:整個文件的數據內容本身分布不均衡,第3個分組的數據量明顯偏多,第1個分組和第5個分組的數據量明顯偏少。

算法數據傳輸量分析:如果采用傳統的直方圖構建算法,需要將3.5 MB的數據在Map端處理成120多萬個對,然后傳輸到Reduce端,通過對合并來完成文件直方圖的構建;而采用本文提出的改進算法只需要傳輸14個數據塊共70個對的統計信息,就可以在Reduce端快速建立整個文件的直方圖,而且還可以同時完成數據塊直方圖的構建和該文件在某一存儲節點上數據直方圖的構建。

4.2.2數據均衡分析

將14個block分布到5個存儲節點上,假設block分布情況為:4個三block節點,1個雙block節點,對比2種block分布算法。

方案1隨機分布算法

表3　隨機算法block分布狀態

圖4　隨機算法節點直方圖

文件均衡偏差:df=137 467.08

方案2數據均衡算法

表4　均衡算法block分布狀態

圖5　均衡算法節點直方圖

文件均衡偏差:df=81 290.32

圖4和圖5中的nodeEV表示節點期望值,通過

nodeEV與node1～node5的對比可以看出:采用隨機block分布算法,node1～node5節點之間以及節點與nodeEV之間直方圖差異比較明顯;而采用數據均衡算法,node1～node5節點之間直方圖差異比較小,而且基本上與nodeEV的直方圖分布很接近,因此采用數據均衡算法比采用隨機block分布算法具有更好的數據均衡效果。

經過不同數據多次實驗驗證,采用數據均衡算法比采用隨機block分布算法在文件均衡偏差值上可以有較大幅度的提高(本文實驗結果提高了40.87%)。

5　結　論

本文針對MapReduce并行計算框架中出現的中間數據的數據傾斜問題,提出了一種基于直方圖的數據均衡算法,該算法通過構建數據塊直方圖的形式來分析數據傾斜問題,并定義文件均衡偏差值對數據傾斜程度進行度量,進而通過交換節點中存儲的數據塊的方式,在保證所有節點存儲容量不變的條件下,降低文件均衡偏差值。經過不同數據多次實驗驗證,該算法比隨機block分布算法具有更好的均衡效果。

同時也要指出,本文提出基于直方圖的數據均衡算法在計算過程中采用了貪心策略,該策略并不保證能夠找到數據均衡分布的全局最優解,但是可以找到一個全局最優解的很好的近似解,因此在工程上具有極大的應用價值。