異構環(huán)境下平滑加權輪詢Reduce任務調度算法研究

黃偉建 賈孟玉 黃亮

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

關鍵詞： Reduce任務調度; 負載均衡; 異構集群; 平滑加權輪詢算法; 節(jié)點選取; 并行圖像處理

中圖分類號： TN911.1?34; TP311 ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? 文章編號： 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 ?引 ?言

隨著互聯網的普及以及信息和數據的迅猛發(fā)展，每天都會產生大量的數據，Yahoo、Facebook、百度、中國移動研究院、淘寶還有社交網絡領域，并行圖像處理等都利用Hadoop集群進行各種信息的加工處理。處理大數據的現實需求促進了云計算的更多學術研究。

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

1 ?平滑加權輪詢調度算法

1.1 ?節(jié)點計算能力

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

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

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

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

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

1.2 ?算法涉及的變量

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

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

1.3 ?算法原理

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

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

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

假設Reduce個數為3，按照上述算法生成的Reduce隊列順序如表1所示。

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

2 ?實驗過程及結果分析

2.1 ?實驗配置及測試數據信息

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

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

將表2中的數據使用原有調度算法（FIFO）、自適應調度算法進行實驗，與本文平滑加權輪詢算法進行結果對比，通過實驗觀察對比結果如圖1所示。

2.3 ?Shuffle階段跨機器傳輸數據量

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

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

2.4 ?在改進的MapReduce上運行圖像處理

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

1） 圖像可以以多維結構的形式表示;

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

3） HDFS是一種有效的圖像數據存儲方式。

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

3 ?結 ?語

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

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

參考文獻

[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] 付彥卓，張樹東，李輝.異構環(huán)境下自適應Reduce任務調度算法的研究[J].計算機應用研究，2018，35（7）：1989?1991.

[4] 朱潔，李雯睿，王江平，等.基于節(jié)點集計算能力差異的Hadoop自適應任務調度算法[J].計算機應用，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] 鄭建云，雷超陽，劉軍華，等.基于具閥值的加權輪詢算法的SDN負載平衡[J].長沙民政職業(yè)技術學院學報，2018，25（4）：121?124.

[7] 韓朋花，葉青，姜曉明，等.改進加權輪詢負載均衡算法研究[J].長春理工大學學報（自然科學版），2018，41（3）：131?134.

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

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

[10] 劉奎，劉向東，馬寶來，等.基于數據局部性的推測式Hadoop任務調度算法研究[J].計算機應用研究，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.