黃偉建 賈孟玉 黃亮

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

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

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

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

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

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

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

2? 隨機(jī)抽樣率選擇

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

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

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

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

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

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

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

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

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

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

4? 實(shí)驗(yàn)過程與結(jié)果分析

4.1? 實(shí)驗(yàn)環(huán)境

本文使用虛擬機(jī)軟件為VMware Workstation 8.0.4 build?744019，虛擬機(jī)操作系統(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組件為實(shí)驗(yàn)平臺。本實(shí)驗(yàn)集群包括1個(gè)NameNode和3個(gè)DataNode，其中節(jié)點(diǎn)可以相互通信。

4.2? 實(shí)驗(yàn)過程

本文數(shù)據(jù)集是真實(shí)的網(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，錯(cuò)誤率為0.07%，Reduce個(gè)數(shù)為5。

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

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

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

3） 抽樣準(zhǔn)確率分析

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

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

4.3? 實(shí)驗(yàn)結(jié)果對比圖

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

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

5? 結(jié)? 語

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

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

參考文獻(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負(fù)載均衡貪心算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33（9）：2656?2659.

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

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

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

[6] 李娜，余省威.云計(jì)算環(huán)境下多服務(wù)器多分區(qū)數(shù)據(jù)的高效挖掘方法設(shè)計(jì)[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負(fù)載不均衡算法[D].淮南：安徽理工大學(xué)，2017.

[9] 張?jiān)Q，蔣建波，陸佳煒，等.面向MapReduce的迭代式數(shù)據(jù)均衡分區(qū)策略[J].計(jì)算機(jī)學(xué)報(bào)，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.