黃偉建 賈孟玉 黃亮

摘 ?要： 傳統(tǒng)MapReduce在處理傾斜數(shù)據(jù)時(shí)會(huì)造成負(fù)載不均衡，降低MapReduce框架的執(zhí)行效率。雖然利用貪心算法分區(qū)減輕了MapReduce應(yīng)用中的數(shù)據(jù)傾斜，但是忽略了Reduce異構(gòu)性，因?yàn)镸apReduce的計(jì)算環(huán)境通常是異構(gòu)的，即使中間數(shù)據(jù)沒有傾斜，由于計(jì)算能力不同，任務(wù)在不同節(jié)點(diǎn)上的執(zhí)行時(shí)間也是不同的。為了避免異構(gòu)性導(dǎo)致Reduce性能下降的問題，提出一種在異構(gòu)環(huán)境下動(dòng)態(tài)平滑加權(quán)輪詢調(diào)度算法。該算法根據(jù)節(jié)點(diǎn)的計(jì)算能力和數(shù)據(jù)本地性這兩個(gè)因素選取Reduce計(jì)算節(jié)點(diǎn)來提高Reduce任務(wù)執(zhí)行效率，還進(jìn)一步將優(yōu)化后的框架用于并行圖像處理。實(shí)驗(yàn)結(jié)果表明，動(dòng)態(tài)平滑加權(quán)輪詢調(diào)度算法減少了Reduce跨節(jié)點(diǎn)傳輸?shù)木W(wǎng)絡(luò)帶寬，同時(shí)也減少了Reduce任務(wù)的執(zhí)行時(shí)間。

關(guān)鍵詞： Reduce任務(wù)調(diào)度; 負(fù)載均衡; 異構(gòu)集群; 平滑加權(quán)輪詢算法; 節(jié)點(diǎn)選取; 并行圖像處理

中圖分類號(hào)： TN911.1?34; TP311 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2020）23?0139?04

Abstract： The traditional MapReduce framework may cause load imbalance when it is used to process skewed data， which can reduce the execution efficiency of the MapReduce framework. Although the application of the greedy algorithm partitioning can alleviate data skew in MapReduce applications， Reduce heterogeneity is ignored， because the computing environment of MapReduce is usually heterogeneous. Even if the intermediate data is not skewed， the execution time of tasks on different nodes is different due to different computing power. In order to avoid Reduce performance degradation caused by the heterogeneity， a dynamic smoothing algorithm of weighted polling scheduling in the heterogeneous environment is put forward. The algorithm is used to select the Reduce computing nodes according to the two factors of the node computing power and data locality， and improve the execution efficiency of Reduce tasks. The optimized framework is adopted for parallel image processing. The experimental results show that the dynamic smoothing weighted polling scheduling algorithm can reduce the network bandwidth of Reduce transmission across nodes and decrease the Reduce task execution time.

Keywords： Reduce task scheduling; load balancing; heterogeneous cluster; smooth weighted polling algorithm; node selection; parallel image processing

0 ?引 ?言

隨著互聯(lián)網(wǎng)的普及以及信息和數(shù)據(jù)的迅猛發(fā)展，每天都會(huì)產(chǎn)生大量的數(shù)據(jù)，Yahoo、Facebook、百度、中國移動(dòng)研究院、淘寶還有社交網(wǎng)絡(luò)領(lǐng)域，并行圖像處理等都利用Hadoop集群進(jìn)行各種信息的加工處理。處理大數(shù)據(jù)的現(xiàn)實(shí)需求促進(jìn)了云計(jì)算的更多學(xué)術(shù)研究。

Hadoop是一種處理海量數(shù)據(jù)的軟件框架，主要包含分布式文件系統(tǒng)（HDFS）和分布式計(jì)算框架（MapReduce）兩部分。數(shù)據(jù)傾斜、集群異構(gòu)、數(shù)據(jù)傳輸是影響作業(yè)的執(zhí)行效率和資源利用率的三大重要問題。文獻(xiàn)[1]采用兩階段分區(qū)降低了Map輸出結(jié)果的不均衡性。文獻(xiàn)[2]提出動(dòng)態(tài)放置文件策略來提高Reduce階段的I/O性能。文獻(xiàn)[3]提出LoNARS算法來減少Reduce任務(wù)過程中的數(shù)據(jù)傳輸。但是在異構(gòu)環(huán)境下，以上算法執(zhí)行時(shí)間上沒有太大的提高。由于忽略Reduce節(jié)點(diǎn)計(jì)算能力的差異性，從而導(dǎo)致任務(wù)的執(zhí)行效率降低，節(jié)點(diǎn)之間的跨數(shù)據(jù)傳輸增大了網(wǎng)絡(luò)通信開銷，進(jìn)一步降低了Reduce任務(wù)在異構(gòu)環(huán)境下的執(zhí)行效率。為了避免異構(gòu)性導(dǎo)致的性能下降，本文采用動(dòng)態(tài)平滑加權(quán)輪詢算法，根據(jù)Reduce節(jié)點(diǎn)的計(jì)算能力和Reduce執(zhí)行任務(wù)時(shí)數(shù)據(jù)的本地性這兩個(gè)因素選取Reduce節(jié)點(diǎn)，提高異構(gòu)環(huán)境中Reduce任務(wù)的執(zhí)行效率。

1 ?平滑加權(quán)輪詢調(diào)度算法

1.1 ?節(jié)點(diǎn)計(jì)算能力

節(jié)點(diǎn)的計(jì)算能力是指節(jié)點(diǎn)處理任務(wù)的效率。節(jié)點(diǎn)在處理任務(wù)時(shí)可以分為快節(jié)點(diǎn)和慢節(jié)點(diǎn)。任務(wù)如果都分配在快節(jié)點(diǎn)上執(zhí)行，節(jié)點(diǎn)執(zhí)行效率極高，應(yīng)充分利用快節(jié)點(diǎn)計(jì)算能力超出部分，縮短任務(wù)執(zhí)行時(shí)間，協(xié)助慢節(jié)點(diǎn)提高任務(wù)并行度。所以異構(gòu)環(huán)境下節(jié)點(diǎn)的計(jì)算差異性會(huì)對(duì)整個(gè)任務(wù)的執(zhí)行效率有很大的影響。

Hadoop集群通常是異構(gòu)的。為了獲得Reduce計(jì)算能力，即在每個(gè)DataNode上運(yùn)行監(jiān)聽器。為了顯著減少異構(gòu)引起的轉(zhuǎn)移開銷，在選擇Reduce任務(wù)的計(jì)算節(jié)點(diǎn)時(shí)，鑒于數(shù)據(jù)的本地性原則，應(yīng)該考慮Reduce所在節(jié)點(diǎn)數(shù)據(jù)量大的機(jī)器，同一機(jī)器的數(shù)據(jù)傳輸率遠(yuǎn)高于跨機(jī)器的數(shù)據(jù)傳輸[3]。每個(gè)DataNode中的容量監(jiān)控器在分區(qū)抽樣開始運(yùn)行時(shí)持續(xù)監(jiān)視采樣的輸入數(shù)據(jù)，并在一段時(shí)間內(nèi)獲取Reduce監(jiān)控?cái)?shù)據(jù)量[dataj（1≤j≤n）]，這里[n]表示Reduce的個(gè)數(shù)。在此基礎(chǔ)上，計(jì)算該監(jiān)聽器的計(jì)算能力[pi]，由式（1）可得，容量監(jiān)聽器任務(wù)通過心跳消息將所有Reduce的計(jì)算能力[pi]發(fā)送到節(jié)點(diǎn)選擇器中。

本文利用zookeeper技術(shù)監(jiān)聽節(jié)點(diǎn)任務(wù)，以任務(wù)的平均處理速度代表其計(jì)算能力，節(jié)點(diǎn)的計(jì)算能力為：

[pi=1nj=1ndatajcostj] （1）

式中：[pi]表示第[i]個(gè)節(jié)點(diǎn)的計(jì)算能力;[dataj（1≤j≤n）]表示第[i]節(jié)點(diǎn)上已經(jīng)處理的第[j]個(gè)任務(wù)的數(shù)據(jù);[costj]表示第[j]個(gè)任務(wù)的執(zhí)行時(shí)間。

1.2 ?算法涉及的變量

節(jié)點(diǎn)理想狀態(tài)下的選擇是同時(shí)滿足本地性和硬件配置最高，但在實(shí)際應(yīng)用過程中，數(shù)據(jù)分布和節(jié)點(diǎn)性能是不能確定的，綜合這兩方面因素，本文提出一種新的選擇計(jì)算節(jié)點(diǎn)策略。綜合考慮任務(wù)所需數(shù)據(jù)的傳輸時(shí)間和任務(wù)執(zhí)行時(shí)間，用這兩個(gè)因素之和作為平滑加權(quán)輪詢算法的權(quán)重值。算法涉及的變量如下。

[Rdatai]表示第[i]個(gè)節(jié)點(diǎn)上監(jiān)聽的數(shù)據(jù)量;在Reduce任務(wù)執(zhí)行過程中用[dS]表示Reduce跨節(jié)點(diǎn)傳輸數(shù)據(jù)量的大小。則[dS]為：

1.3 ?算法原理

輪詢算法是最簡單的一種負(fù)載均衡算法，無需考慮當(dāng)前所有連接的狀態(tài)，不考慮服務(wù)器的處理能力，當(dāng)請(qǐng)求服務(wù)時(shí)間間隔變化較大時(shí)，輪詢算法存在負(fù)載不平衡問題。由于每臺(tái)服務(wù)器的配置、應(yīng)用等不同，從而導(dǎo)致其性能存在差異?？紤]到輪詢算法的缺點(diǎn)，本文提出加權(quán)輪詢算法，根據(jù)服務(wù)器的不同性能，給每個(gè)服務(wù)器分配不同的權(quán)值，使其能夠接受相應(yīng)權(quán)值的服務(wù)請(qǐng)求。加權(quán)輪詢算法在某些情況下生成的序列是不均勻的，設(shè)計(jì)了一種叫做平滑的加權(quán)輪詢算法，它生產(chǎn)的序列更加均勻，使節(jié)點(diǎn)序列分散開來不再連續(xù)。

根據(jù)以上算法原理，MapReduce框架中，Map根據(jù)貪心算法分區(qū)將分區(qū)均衡后，利用Shuffle分配給Reduce，沒有考慮Reduce計(jì)算能力的差異性，默認(rèn)Reduce計(jì)算能力和其配置是相同的。考慮到數(shù)據(jù)本地性和節(jié)點(diǎn)配置兩方面，將兩個(gè)因素相加作為權(quán)重，利用加權(quán)輪詢算法將其放進(jìn)隊(duì)列，普通的加權(quán)輪詢算法在某些情況下生成的序列是不均勻的，所以改進(jìn)算法的平滑性采用平滑的加權(quán)輪詢算法動(dòng)態(tài)調(diào)整權(quán)重使其Reduce隊(duì)列均衡化。

每個(gè)Reduce都有兩個(gè)權(quán)重變量：[weight]（根據(jù)[Wj]大小配置，值固定不變）和[current_weight]（服務(wù)器目前的權(quán)重，一開始為0，之后會(huì)動(dòng)態(tài)調(diào)整）。每次當(dāng)請(qǐng)求選取Reduce節(jié)點(diǎn)時(shí)，會(huì)遍歷隊(duì)列中所有Reduce，對(duì)于每個(gè)Reduce，讓[current_weight]增加[weight]，同時(shí)累加所有服務(wù)器的[weight]，并保存為[total]，遍歷完所有Reduce之后，如果服務(wù)器的[current_weight]是最大的，就選擇這個(gè)Reduce接受請(qǐng)求，最后把該服務(wù)器的[current_weight]減去[total]。

假設(shè)Reduce個(gè)數(shù)為3，按照上述算法生成的Reduce隊(duì)列順序如表1所示。

通過上述過程，[R1]，[R2]，[R3]分別被選取了4，2，1次，符合它們的權(quán)重值，充分利用了Reduce節(jié)點(diǎn)的計(jì)算能力，減少任務(wù)落后，提高了Reduce執(zhí)行任務(wù)的效率。

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

2.1 ?實(shí)驗(yàn)配置及測(cè)試數(shù)據(jù)信息

實(shí)驗(yàn)設(shè)置了兩個(gè)Hadoop集群，一個(gè)是同構(gòu)的，另一個(gè)是異構(gòu)的。同構(gòu)Hadoop集群使用虛擬機(jī)軟件為VMware Workstation 8.0.4 build?744019，虛擬機(jī)操作系統(tǒng)是CentOS 6.5，設(shè)置為單核，8 GB內(nèi)存，Java開發(fā)工具版本使用JDK?1.8.0_102;Hadoop版本為2.8.1，采用zookeeper?3.4.6組件為實(shí)驗(yàn)平臺(tái)。本實(shí)驗(yàn)集群包括1個(gè)NameNode和5個(gè)DataNode，其中節(jié)點(diǎn)可以相互通信。HDFS塊大小設(shè)置為64 MB。異構(gòu)集群包含6臺(tái)物理機(jī)器，NameNode所在機(jī)器為4核4 GB內(nèi)存，其他機(jī)器為2核2 GB、4核2 GB、2核4 GB等配置，其他配置與同構(gòu)集群中的配置相同。分別在同構(gòu)Hadoop集群和異構(gòu)Hadoop集群中運(yùn)行不同類型的基準(zhǔn)測(cè)試來評(píng)估Reduce任務(wù)調(diào)度策略，本次實(shí)驗(yàn)采用兩組數(shù)據(jù)進(jìn)行測(cè)試，一組是利用不同參數(shù)控制的傾斜Zipf分布生成的合成數(shù)據(jù)，第二組WordCount是真實(shí)的網(wǎng)頁數(shù)據(jù)，利用爬蟲技術(shù)爬取紅帽官方網(wǎng)站的數(shù)據(jù)并將其轉(zhuǎn)化為鍵值對(duì)。

2.2 ?Reduce任務(wù)平均執(zhí)行時(shí)間

將表2中的數(shù)據(jù)使用原有調(diào)度算法（FIFO）、自適應(yīng)調(diào)度算法進(jìn)行實(shí)驗(yàn)，與本文平滑加權(quán)輪詢算法進(jìn)行結(jié)果對(duì)比，通過實(shí)驗(yàn)觀察對(duì)比結(jié)果如圖1所示。

2.3 ?Shuffle階段跨機(jī)器傳輸數(shù)據(jù)量

圖1中Reduce平均執(zhí)行時(shí)間是從Shuffle階段開始計(jì)算平均執(zhí)行時(shí)間。結(jié)果表明本文提出的動(dòng)態(tài)平滑加權(quán)算法在自適應(yīng)算法上進(jìn)行改進(jìn)，執(zhí)行時(shí)間比原來Hadoop系統(tǒng)效率提高了11.5%，比SARS算法效率提高了5%，但在處理偏斜數(shù)據(jù)時(shí)算法效率略有提高。

帶寬是一種稀缺資源，由于其龐大的網(wǎng)絡(luò)流量，Shuffle階段已成為MapReduce的瓶頸。Shuffle階段的跨節(jié)點(diǎn)傳輸可能會(huì)導(dǎo)致網(wǎng)絡(luò)堵塞，本文主要研究Reduce階段，Shuffle階段跨節(jié)點(diǎn)傳輸數(shù)據(jù)對(duì)比如圖2所示。由圖2可知，本文提出的加權(quán)平滑輪詢算法在Shuffle階段跨節(jié)點(diǎn)傳輸數(shù)據(jù)量有所減少，相比SARS算法在Zipf?0.5和Zipf?1.0減少了4%，當(dāng)數(shù)據(jù)偏斜時(shí)跨節(jié)點(diǎn)傳輸數(shù)據(jù)較大，效果不太明顯。WordCount任務(wù)數(shù)據(jù)減少了10%，證明了該算法減少了在Shuffle階段傳輸?shù)闹虚g數(shù)據(jù)。

2.4 ?在改進(jìn)的MapReduce上運(yùn)行圖像處理

MapReduce之所以成為大規(guī)模、高容量圖像處理應(yīng)用的合適平臺(tái)，主要有以下三個(gè)原因：

1） 圖像可以以多維結(jié)構(gòu)的形式表示;

2） 圖像處理中的大部分函數(shù)可以高度并行化;

3） HDFS是一種有效的圖像數(shù)據(jù)存儲(chǔ)方式。

本次實(shí)驗(yàn)中Map函數(shù)將大尺寸圖像分割成幾個(gè)部分。其中一塊由一個(gè)Map任務(wù)處理，它收集像素（灰度）值的計(jì)數(shù)。Reduce函數(shù)完成從Map函數(shù)收集的數(shù)字的聚合。在異構(gòu)集群中處理20張不同的大尺寸圖像時(shí)，得到了最短的執(zhí)行時(shí)間。與其他兩種方法相比，平均執(zhí)行時(shí)間分別減少了29%，16%，如圖3所示。

3 ?結(jié) ?語

針對(duì)Hadoop原有調(diào)度算法在分配Reduce任務(wù)時(shí)沒有考慮異構(gòu)環(huán)境下計(jì)算節(jié)點(diǎn)的差異性問題，本文提出了動(dòng)態(tài)平滑加權(quán)輪詢調(diào)度算法。該算法在選擇Reduce節(jié)點(diǎn)時(shí)不僅考慮數(shù)據(jù)本地性傳輸也考慮到節(jié)點(diǎn)計(jì)算能力，通過與FIFO和自適應(yīng)調(diào)度算法（SARS）實(shí)驗(yàn)對(duì)比，可得出本文提出的算法不僅在同構(gòu)集群上Reduce任務(wù)執(zhí)行時(shí)間有所增加，還在異構(gòu)環(huán)境下處理大數(shù)據(jù)Reduce任務(wù)時(shí)效率比FIFO、SARS算法分別提高了29%，16%。Shuffle階段跨節(jié)點(diǎn)數(shù)據(jù)傳輸比SARS算法減少了10%。綜上所述，動(dòng)態(tài)平滑加權(quán)輪詢調(diào)度算法在異構(gòu)環(huán)境下減少了Reduce任務(wù)執(zhí)行時(shí)間，在數(shù)據(jù)傳輸方面有一定的優(yōu)越性。

注：本文通訊作者為賈孟玉。

參考文獻(xiàn)

[1] LU Wei， CHEN Lei， WANG Liqiang， et al. NPIY： a novel partitioner for improving mapreduce performance [J]. Journal of visual languages & computing， 2018， 46（1）： 1?11.

[2] FUJISHIMA E， YAMAGUCHI S. Dynamic file placing control for improving the I/O performance in the reduce phase of Hadoop [C]// Proceedings of the 10th International Conference on Ubiquitous Information Management and Communication. New York： ACM Press， 2016： 1?7.

[3] 付彥卓，張樹東，李輝.異構(gòu)環(huán)境下自適應(yīng)Reduce任務(wù)調(diào)度算法的研究[J].計(jì)算機(jī)應(yīng)用研究，2018，35（7）：1989?1991.

[4] 朱潔，李雯睿，王江平，等.基于節(jié)點(diǎn)集計(jì)算能力差異的Hadoop自適應(yīng)任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用，2016，36（4）：918?922.

[5] TANG Zhuo， JIANG Lingang， ZHOU Junping， et al. A self?adaptive scheduling algorithm for reduce start time [J]. Future generation computer systems， 2015， 43/44： 51?60.

[6] 鄭建云，雷超陽，劉軍華，等.基于具閥值的加權(quán)輪詢算法的SDN負(fù)載平衡[J].長沙民政職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2018，25（4）：121?124.

[7] 韓朋花，葉青，姜曉明，等.改進(jìn)加權(quán)輪詢負(fù)載均衡算法研究[J].長春理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，41（3）：131?134.

[8] 隋然，杜江，邰銘，等.Hadoop中Reduce作業(yè)動(dòng)態(tài)調(diào)度算法[J].信息工程大學(xué)學(xué)報(bào)，2016，17（1）：83?87.

[9] 何沖.Hadoop集群調(diào)度優(yōu)化的研究[D].上海：上海師范大學(xué)，2015.

[10] 劉奎，劉向東，馬寶來，等.基于數(shù)據(jù)局部性的推測(cè)式Hadoop任務(wù)調(diào)度算法研究[J].計(jì)算機(jī)應(yīng)用研究，2014，31（1）：182?187.

[11] HASHEM I A T， ANUAR N B， MARJANI M， et al. Multi?objective scheduling of MapReduce jobs in big data processing [J]. Multimedia tools and applications， 2018， 77（8）： 9979?9994.