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

黃偉建 賈孟玉 黃亮

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

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

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? 引? 言

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

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

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

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

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

2? 隨機抽樣率選擇

本文提出一種評估模型，以更好地選擇適當的抽樣率來減少開銷，并全面考慮這些受影響的因素。評估模型公式如下：

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

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

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

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

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

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

3? 抽樣貪心算法分區思想

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

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

4? 實驗過程與結果分析

4.1? 實驗環境

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

4.2? 實驗過程

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

1） 抽樣參數設置

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

2） 抽樣結果和分析

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

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

3） 抽樣準確率分析

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

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

4.3? 實驗結果對比圖

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

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

5? 結? 語

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

實驗結果表明，并行相似隨機抽樣貪心算法分區不僅解決了采樣抽樣結果準確性和抽樣帶來的開銷成本問題，整體分區算法在任務執行時間和Reduce負載均衡方面都優于傳統Hash算法分區。在接下來的工作中會將該算法應用到真實的系統環境中，來體現該算法的實用性。

參考文獻

[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].計算機應用研究，2016，33（9）：2656?2659.

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

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

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

[6] 李娜，余省威.云計算環境下多服務器多分區數據的高效挖掘方法設計[J].現代電子技術，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].淮南：安徽理工大學，2017.

[9] 張元鳴，蔣建波，陸佳煒，等.面向MapReduce的迭代式數據均衡分區策略[J].計算機學報，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.