异构环境下平滑加权轮询Reduce任务调度算法研究

黄伟建 贾孟玉 黄亮

摘  要： 传统MapReduce在处理倾斜数据时会造成负载不均衡，降低MapReduce框架的执行效率。虽然利用贪心算法分区减轻了MapReduce应用中的数据倾斜，但是忽略了Reduce异构性，因为MapReduce的计算环境通常是异构的，即使中间数据没有倾斜，由于计算能力不同，任务在不同节点上的执行时间也是不同的。为了避免异构性导致Reduce性能下降的问题，提出一种在异构环境下动态平滑加权轮询调度算法。该算法根据节点的计算能力和数据本地性这两个因素选取Reduce计算节点来提高Reduce任务执行效率，还进一步将优化后的框架用于并行图像处理。实验结果表明，动态平滑加权轮询调度算法减少了Reduce跨节点传输的网络带宽，同时也减少了Reduce任务的执行时间。

关键词： Reduce任务调度; 负载均衡; 异构集群; 平滑加权轮询算法; 节点选取; 并行图像处理

中图分类号： 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  引  言

随着互联网的普及以及信息和数据的迅猛发展，每天都会产生大量的数据，Yahoo、Facebook、百度、中国移动研究院、淘宝还有社交网络领域，并行图像处理等都利用Hadoop集群进行各种信息的加工处理。处理大数据的现实需求促进了云计算的更多学术研究。

Hadoop是一种处理海量数据的软件框架，主要包含分布式文件系统（HDFS）和分布式计算框架（MapReduce）两部分。数据倾斜、集群异构、数据传输是影响作业的执行效率和资源利用率的三大重要问题。文献[1]采用两阶段分区降低了Map输出结果的不均衡性。文献[2]提出动态放置文件策略来提高Reduce阶段的I/O性能。文献[3]提出LoNARS算法来减少Reduce任务过程中的数据传输。但是在异构环境下，以上算法执行时间上没有太大的提高。由于忽略Reduce节点计算能力的差异性，从而导致任务的执行效率降低，节点之间的跨数据传输增大了网络通信开销，进一步降低了Reduce任务在异构环境下的执行效率。为了避免异构性导致的性能下降，本文采用动态平滑加权轮询算法，根据Reduce节点的计算能力和Reduce执行任务时数据的本地性这两个因素选取Reduce节点，提高异构环境中Reduce任务的执行效率。

1  平滑加权轮询调度算法

1.1  节点计算能力

节点的计算能力是指节点处理任务的效率。节点在处理任务时可以分为快节点和慢节点。任务如果都分配在快节点上执行，节点执行效率极高，应充分利用快节点计算能力超出部分，缩短任务执行时间，协助慢节点提高任务并行度。所以异构环境下节点的计算差异性会对整个任务的执行效率有很大的影响。

Hadoop集群通常是异构的。为了获得Reduce计算能力，即在每个DataNode上运行监听器。为了显著减少异构引起的转移开销，在选择Reduce任务的计算节点时，鉴于数据的本地性原则，应该考虑Reduce所在节点数据量大的机器，同一机器的数据传输率远高于跨机器的数据传输[3]。每个DataNode中的容量监控器在分区抽样开始运行时持续监视采样的输入数据，并在一段时间内获取Reduce监控数据量[dataj（1≤j≤n）]，这里[n]表示Reduce的个数。在此基础上，计算该监听器的计算能力[pi]，由式（1）可得，容量监听器任务通过心跳消息将所有Reduce的计算能力[pi]发送到节点选择器中。

本文利用zookeeper技术监听节点任务，以任务的平均处理速度代表其计算能力，节点的计算能力为：

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

式中：[pi]表示第[i]个节点的计算能力;[dataj（1≤j≤n）]表示第[i]节点上已经处理的第[j]个任务的数据;[costj]表示第[j]个任务的执行时间。

1.2  算法涉及的变量

节点理想状态下的选择是同时满足本地性和硬件配置最高，但在实际应用过程中，数据分布和节点性能是不能确定的，综合这两方面因素，本文提出一种新的选择计算节点策略。综合考虑任务所需数据的传输时间和任务执行时间，用这两个因素之和作为平滑加权轮询算法的权重值。算法涉及的变量如下。

[Rdatai]表示第[i]个节点上监听的数据量;在Reduce任务执行过程中用[dS]表示Reduce跨节点传输数据量的大小。则[dS]为：

1.3  算法原理

轮询算法是最简单的一种负载均衡算法，无需考虑当前所有连接的状态，不考虑服务器的处理能力，当请求服务时间间隔变化较大时，轮询算法存在负载不平衡问题。由于每台服务器的配置、应用等不同，从而导致其性能存在差异。考虑到轮询算法的缺点，本文提出加权轮询算法，根据服务器的不同性能，给每个服务器分配不同的权值，使其能够接受相应权值的服务请求。加权轮询算法在某些情况下生成的序列是不均匀的，设计了一种叫做平滑的加权轮询算法，它生产的序列更加均匀，使节点序列分散开来不再连续。

根据以上算法原理，MapReduce框架中，Map根据贪心算法分区将分区均衡后，利用Shuffle分配给Reduce，没有考虑Reduce计算能力的差异性，默认Reduce计算能力和其配置是相同的。考虑到数据本地性和节点配置两方面，将两个因素相加作为权重，利用加权轮询算法将其放进队列，普通的加权轮询算法在某些情况下生成的序列是不均匀的，所以改进算法的平滑性采用平滑的加权轮询算法动态调整权重使其Reduce队列均衡化。

每个Reduce都有两个权重变量：[weight]（根据[Wj]大小配置，值固定不变）和[current_weight]（服务器目前的权重，一开始为0，之后会动态调整）。每次当请求选取Reduce节点时，会遍历队列中所有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节点的计算能力，减少任务落后，提高了Reduce执行任务的效率。

2  实验过程及结果分析

2.1  实验配置及测试数据信息

实验设置了两个Hadoop集群，一个是同构的，另一个是异构的。同构Hadoop集群使用虚拟机软件为VMware Workstation 8.0.4 build?744019，虚拟机操作系统是CentOS 6.5，设置为单核，8 GB内存，Java开发工具版本使用JDK?1.8.0_102;Hadoop版本为2.8.1，采用zookeeper?3.4.6组件为实验平台。本实验集群包括1个NameNode和5个DataNode，其中节点可以相互通信。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任务平均执行时间

将表2中的数据使用原有调度算法（FIFO）、自适应调度算法进行实验，与本文平滑加权轮询算法进行结果对比，通过实验观察对比结果如图1所示。

2.3  Shuffle阶段跨机器传输数据量

图1中Reduce平均执行时间是从Shuffle阶段开始计算平均执行时间。结果表明本文提出的动态平滑加权算法在自适应算法上进行改进，执行时间比原来Hadoop系统效率提高了11.5%，比SARS算法效率提高了5%，但在處理偏斜数据时算法效率略有提高。

带宽是一种稀缺资源，由于其庞大的网络流量，Shuffle阶段已成为MapReduce的瓶颈。Shuffle阶段的跨节点传输可能会导致网络堵塞，本文主要研究Reduce阶段，Shuffle阶段跨节点传输数据对比如图2所示。由图2可知，本文提出的加权平滑轮询算法在Shuffle阶段跨节点传输数据量有所减少，相比SARS算法在Zipf?0.5和Zipf?1.0减少了4%，当数据偏斜时跨节点传输数据较大，效果不太明显。WordCount任务数据减少了10%，证明了该算法减少了在Shuffle阶段传输的中间数据。

2.4  在改进的MapReduce上运行图像处理

MapReduce之所以成为大规模、高容量图像处理应用的合适平台，主要有以下三个原因：

1） 图像可以以多维结构的形式表示;

2） 图像处理中的大部分函数可以高度并行化;

3） HDFS是一种有效的图像数据存储方式。

本次实验中Map函数将大尺寸图像分割成几个部分。其中一块由一个Map任务处理，它收集像素（灰度）值的计数。Reduce函数完成从Map函数收集的数字的聚合。在异构集群中处理20张不同的大尺寸图像时，得到了最短的执行时间。与其他两种方法相比，平均执行时间分别减少了29%，16%，如图3所示。

3  结  语

针对Hadoop原有调度算法在分配Reduce任务时没有考虑异构环境下计算节点的差异性问题，本文提出了动态平滑加权轮询调度算法。该算法在选择Reduce节点时不仅考虑数据本地性传输也考虑到节点计算能力，通过与FIFO和自适应调度算法（SARS）实验对比，可得出本文提出的算法不仅在同构集群上Reduce任务执行时间有所增加，还在异构环境下处理大数据Reduce任务时效率比FIFO、SARS算法分别提高了29%，16%。Shuffle阶段跨节点数据传输比SARS算法减少了10%。综上所述，动态平滑加权轮询调度算法在异构环境下减少了Reduce任务执行时间，在数据传输方面有一定的优越性。

注：本文通讯作者为贾孟玉。

参考文献

[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] 付彦卓，张树东，李辉.异构环境下自适应Reduce任务调度算法的研究[J].计算机应用研究，2018，35（7）：1989?1991.

[4] 朱洁，李雯睿，王江平，等.基于节点集计算能力差异的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].长沙民政职业技术学院学报，2018，25（4）：121?124.

[7] 韩朋花，叶青，姜晓明，等.改进加权轮询负载均衡算法研究[J].长春理工大学学报（自然科学版），2018，41（3）：131?134.

[8] 隋然，杜江，邰铭，等.Hadoop中Reduce作业动态调度算法[J].信息工程大学学报，2016，17（1）：83?87.

[9] 何冲.Hadoop集群调度优化的研究[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.