并行隨機抽樣貪心算法分區(qū)的MapReduce負載均衡研究

黃偉建 賈孟玉 黃亮

摘? 要： 針對傳統(tǒng)MapReduce環(huán)境下Hash分區(qū)處理偏差數(shù)據(jù)時存在效率低下負載不均衡問題，采用兩階段分區(qū)，即基于并行相似隨機抽樣貪心算法分區(qū)。該抽樣是基于Hadoop隨機抽樣在給定樣本比率或特定置信度下的誤差范圍內(nèi)快速且低錯誤率的預(yù)測key分布結(jié)果。優(yōu)點在于利用MapReduce框架的并行性減少抽樣開銷成本，并采用一種評估模型來確定合適的抽樣率，達到減少抽樣開銷成本和提高抽樣準確性的目的。結(jié)合貪心算法分區(qū)代替Hadoop平臺默認的Hash分區(qū)算法來劃分中間數(shù)據(jù)，實現(xiàn)MapReduce負載均衡。Matlab實驗仿真結(jié)果表明，并行隨機抽樣貪心算法分區(qū)無論從負載均衡還是執(zhí)行時間上都優(yōu)于原生Hadoop中Hash分區(qū)算法。

關(guān)鍵詞： MapReduce; 負載均衡; 貪心算法分區(qū); 并行隨機抽樣; 分區(qū)建模; 對比驗證

Abstract： In allusion to inefficiency and load imbalance in the traditional MapReduce environment when the Hash partitioning is used to process the bias data， the two?stage partitioning algorithm?greedy partitioning based on the parallel similarity random sampling is adopted. This sampling is based on Hadoop random sampling to predict key distribution results with fast and low error rate throughout the error range of the given sample ratio or the specific confidence coefficient. The advantage of this sampling way is that the overhead costs of sampling are reduced by means of the parallelism of MapReduce framework， and the appropriate sampling rate is determined with an evaluation model to reduce the overhead cost of sampling and improve the sampling′s accuracy. The intermediate data is divided by using the greedy algorithm partitioning to replace the default Hash partitioning algorithm of Hadoop platform， so as to realize the MapReduce load balancing. The Matlab simulation results show that the greedy partitioning algorithm based on the parallel sampling is superior to the Hash partitioning algorithm in the native Hadoop in terms of load balancing and execution time.

Keywords： MapReduce; load balancing; greedy algorithm partitioning; parallel random sampling; partitioning modeling; comparison validation

0? 引? 言

目前，兩階分區(qū)（抽樣和分區(qū)）是一種解決MapReduce處理偏差數(shù)據(jù)時存在Redcue負載不均衡問題的簡單且高效的算法。文獻[1]研究抽樣過程影響開銷與成本的各種因素，如準確率、節(jié)點個數(shù)、樣本規(guī)模，并給出理論證明，為兩階段分區(qū)提供了理論支撐。有學(xué)者提出用貪心算法代替Hash算法，但其抽樣采用普通系統(tǒng)抽樣，當(dāng)抽樣率到達一定閾值時抽樣開銷成本會影響MapReduce整體性能[2]。文獻[3?4]缺乏有效估計數(shù)據(jù)分布的預(yù)處理。然而很少學(xué)者在抽樣過程中考慮抽樣結(jié)果準確性和抽樣帶來的開銷成本問題，所以有必要對此問題進行研究。

于是在上述學(xué)者研究的基礎(chǔ)上對抽樣分區(qū)進行優(yōu)化，采用一種argMin函數(shù)方法來解決抽樣開銷和結(jié)果準確性之間的平衡問題。本文將針對數(shù)據(jù)傾斜問題提出一種并行相似隨機抽樣貪心算法分區(qū)來實現(xiàn)Reduce負載均衡。Matlab實驗仿真結(jié)果表明，該算法在處理數(shù)據(jù)傾斜問題上能進一步優(yōu)化執(zhí)行時間和實現(xiàn)負載均衡。

1? 并行隨機抽樣貪心算法分區(qū)模型

采用兩階段分區(qū)，第一階段利用MapRedcue框架進行并行抽樣預(yù)測Key分布制定分區(qū)方法，如圖1所示。

第二階段將貪心算法分區(qū)代替Hash分區(qū)運行MapReduce工作，如圖2所示。

2? 隨機抽樣率選擇

本文提出一種評估模型，以更好地選擇適當(dāng)?shù)某闃勇蕘頊p少開銷，并全面考慮這些受影響的因素。評估模型公式如下：

式中：函數(shù)[fi（Ei，Di，Vi）]綜合考慮抽樣效果，以及時間成本和變化;[α，β]和[γ]是反映這些受影響因素重要性的權(quán)重系數(shù)。

在函數(shù)[fi]中，[Ei]表示當(dāng)抽樣率設(shè)置為[i]時的抽樣效果，文中側(cè)重于5倍不同的抽樣率：10%，25%，50%，75%，100%。因此[1≤i≤SN]，[SN]表示不同的抽樣率的數(shù)量，這里[SN]=5。[Ei]具體表示為當(dāng)前采用的百分比與整個輸入數(shù)據(jù)集的CoV（變異系數(shù)）值序列之間的差異的抽樣效果。

式中：[covi，j]表示當(dāng)抽樣率為i時第j次抽樣實驗的CoV值，即錯誤率值;[N]為重復(fù)的實驗次數(shù)。例如[cov5，j]為抽樣率為100%時的CoV值。平均抽樣時間[Di]為：

式中：[di，j]表示在抽樣率[i]和[j]次抽樣實驗執(zhí)行的時間，[1≤i≤SN]，[1≤j≤N];[SN]表示不同的抽樣率的數(shù)量。由于本文的集群組件性能是不同的，因此在并行抽樣存在計算時間的變化。為了考慮這個因素，本文使用式（4）來計算變化，在抽樣率[i]下用[Vi]表示為：

在實驗中進行Sort和Grep基準測試，分別采用不同的抽樣率，每組實驗重復(fù)進行10次，在95%的置信區(qū)間根據(jù)不同抽樣率對應(yīng)的時間，簡單地假設(shè)效率、成本、變化權(quán)重系數(shù)相同，則[α=β=γ=1]。計算其結(jié)果如表1所示。

從表1可以看出，隨著抽樣率的提高，數(shù)據(jù)準確性在提高，Di即抽樣耗費的時間也隨之增高。具體來講，在10%抽樣率的實驗中，Ei的值遠大于抽樣率為100%的實驗組。抽樣率會縮短抽樣時間，但無法證明輸入數(shù)據(jù)的分布準確性。由表1得出在并行抽樣中，在95%置信區(qū)間抽樣率為25%是抽樣率最合適的選擇。

3? 抽樣貪心算法分區(qū)思想

貪心算法分區(qū)思想是把所有的Reduce抽象為一個整體，每個Reduce獲得平均值負載則為子問題。

找出整體當(dāng)中局部的最優(yōu)解，并且將所有的這些局部最優(yōu)解合起來形成整體上的一個最優(yōu)解。貪心算法思想是根據(jù)抽樣數(shù)據(jù)預(yù)測Key分布結(jié)果，求取每個Reduce負載平均值，然后為每個Reduce分配接近平均值的負載，從而達到整體的負載均衡。具體算法流程圖如圖3所示。

4? 實驗過程與結(jié)果分析

4.1? 實驗環(huán)境

本文使用虛擬機軟件為VMware Workstation 8.0.4 build?744019，虛擬機操作系統(tǒng)是CentOS?6.5，設(shè)置為單核，2 GB內(nèi)存，Java開發(fā)工具版本使用JDK?1.8.0_102;Hadoop版本為2.8.1，采用zookeeper?3.4.6組件為實驗平臺。本實驗集群包括1個NameNode和3個DataNode，其中節(jié)點可以相互通信。

4.2? 實驗過程

本文數(shù)據(jù)集是真實的網(wǎng)頁數(shù)據(jù)，利用爬蟲技術(shù)得到了紅帽官方網(wǎng)站的數(shù)據(jù)并將其轉(zhuǎn)化為鍵值對。其記錄大小為128 MB～2 GB。

1） 抽樣參數(shù)設(shè)置

原數(shù)據(jù)大小為652 MB，記錄為13 491 498條，經(jīng)上文分析得出合適的抽樣率為0.25%，置信區(qū)間為0.95，錯誤率為0.07%，Reduce個數(shù)為5。

2） 抽樣結(jié)果和分析

抽樣平均花費時間為46.21 s。原數(shù)據(jù)Key類型總數(shù)為53 070 602，樣本Key類型總數(shù)為10 373 686，經(jīng)過實驗結(jié)果表明，所抽取樣本在45個Key類型與原數(shù)據(jù)類型中樣本原數(shù)據(jù)相似比例近似為0.195 5。

這充分說明本文提出的并行隨機抽樣數(shù)據(jù)的有效性，即正確反映原數(shù)據(jù)的分布規(guī)律，為接下來分區(qū)提供有效且準確的Key分布信息。

3） 抽樣準確率分析

為了驗證抽樣率的準確性，本文采取不同抽樣來觀察抽樣的準確性。不同規(guī)模的數(shù)據(jù)集所需要樣本規(guī)模是相同的，當(dāng)樣本規(guī)模增長到一個不大的閾值時，準確率的增長將非常緩慢，并在一個接近于1的值上趨于平穩(wěn)[1]。

經(jīng)實驗證明抽樣率在0.25%以后準確率的增長趨于緩慢，但隨著抽樣率的增加時間在增長，時間的增長速度遠遠超過準確率的提高速度。于是0.25%的抽樣證明是有效可行的，并且并行隨機抽樣比普通隨機抽樣時間大大減少。

4.3? 實驗結(jié)果對比圖

以WordCount為實例，進行實驗，分別比較默認的Hash、群集拆分和貪心算法分區(qū)。從運行時間和Reduce負載均衡兩個角度比較3種算法的優(yōu)劣數(shù)據(jù)集抽樣率為0.25，數(shù)據(jù)集為1.02 GB，Reduce個數(shù)為15，本文分區(qū)算法中群集拆分和貪心算法分區(qū)抽樣時間、抽樣率是相同的。3種分區(qū)算法執(zhí)行時間對比圖如圖4所示。Reduce負載數(shù)量對比圖如圖5所示。

實驗結(jié)果表明，數(shù)據(jù)集在500 MB左右時，3種分區(qū)算法執(zhí)行時間相差甚少，Reduce負載也相對均衡。但隨著數(shù)據(jù)集的增大，貪心算法優(yōu)于兩者，Hash分區(qū)算法不均衡，群集拆分負載相對平均值偏差較貪心算法波動幅度大。由此可見，在時間效率和負載均衡兩個方面，抽樣分區(qū)優(yōu)于一次性Hash分區(qū)，并行相似抽樣貪心分區(qū)優(yōu)于群集拆分分區(qū)。

5? 結(jié)? 語

本文采用一種基于并行相似隨機抽樣貪心算法來解決傳統(tǒng)Hash分區(qū)處理偏斜數(shù)據(jù)存在負載不均衡問題，提出一種評估模型來選擇合適的抽樣百分百來減少抽樣時間和準確率對MapReduce性能帶來的影響，根據(jù)抽樣結(jié)果使用貪心算法分區(qū)實現(xiàn)負載均衡。

實驗結(jié)果表明，并行相似隨機抽樣貪心算法分區(qū)不僅解決了采樣抽樣結(jié)果準確性和抽樣帶來的開銷成本問題，整體分區(qū)算法在任務(wù)執(zhí)行時間和Reduce負載均衡方面都優(yōu)于傳統(tǒng)Hash算法分區(qū)。在接下來的工作中會將該算法應(yīng)用到真實的系統(tǒng)環(huán)境中，來體現(xiàn)該算法的實用性。

參考文獻

[1] XU Y J， QU W Y， LI Z Y， et al. Balancing reducer workload for skewed data using sampling?based partitioning [J]. Computers & electrical engineering， 2014， 40（2）： 675?687.

[2] 劉朵，曾鋒，陳志剛，等.Hadoop平臺中一種Reduce負載均衡貪心算法[J].計算機應(yīng)用研究，2016，33（9）：2656?2659.

[3] 陶永才，丁雷道，石磊，等.MapReduce在線抽樣分區(qū)負載均衡研究[J].小型微型計算機系統(tǒng)，2017，38（2）：238?242.

[4] 王誠，李奇源.基于貪心算法的一致性哈希負載均衡優(yōu)化[J].南京郵電大學(xué)學(xué)報（自然科學(xué)版），2018，38（3）：89?97.

[5] 宛婉，周國祥.Hadoop平臺的海量數(shù)據(jù)并行隨機抽樣[J].計算機工程與應(yīng)用，2014，50（20）：115?118.

[6] 李娜，余省威.云計算環(huán)境下多服務(wù)器多分區(qū)數(shù)據(jù)的高效挖掘方法設(shè)計[J].現(xiàn)代電子技術(shù)，2017，40（10）：43?45.

[7] LIU G P， ZHU X M， WANG J， et al. SP?partitioner： a novel partition method to handle intermediate data skew in spark streaming [J]. Future generation computer systems， 2018， 86： 1054?1063.

[8] 羅永青.基于Key值解決MapReduce中Reduce負載不均衡算法[D].淮南：安徽理工大學(xué)，2017.

[9] 張元鳴，蔣建波，陸佳煒，等.面向MapReduce的迭代式數(shù)據(jù)均衡分區(qū)策略[J].計算機學(xué)報，2019，42（8）：1873?1885.

[10] LU W， CHEN L， WANG L Q， et al. NPIY： a novel partitioner for improving mapreduce performance [J]. Journal of visual languages & computing， 2018， 46： 1?11.

[11] BERLI?SKA J， DROZDOWSKI M. Comparing load?balancing algorithms for mapreduce under Zipfian data skews [J]. Parallel computing， 2018， 72： 14?28.