MapReduce架构下Reduce任务的调度优化

冒佳明　王鹏飞　赵然

摘 要：MapReduce作业执行过程包含Map和Reduce两个阶段，Reduce阶段需要复制Map阶段产生的中间数据到本地进行计算产生最终的输出数据。其中，Reduce阶段包括Sort，Shuffle和Reduce等3个子阶段，Shuffle子阶段通过网络链路传输数据，花费的时间占Reduce阶段的1/3以上，具有较大的优化空间。文章提出了一种基于Reduce阶段执行链路分析的优化节点选择算法，通过合理选择优化节点，并部署相对应的Reduce任务，降低节点间的数据传输开销，减少对网络带宽资源的占用，加速Reduce任务的执行，从而实现总体MapReduce作业的执行优化。

关键词：MapReduce；网络带宽；Shuffle；优化

Hadoop系统是MapReduce架构的开源实现，由于其对海量数据进行分布式处理的能力，得到了各行业应用领域的广泛使用[1]。MapReduce架构下的作业执行主要包括两个阶段：规约的Map阶段和映射的Reduce阶段。其中，Reduce阶段以Map阶段的输出作为自己的输入。因此，需要将Map阶段的结果传输到Reduce任务的执行节点，这一过程需要耗费一定的网络带宽资源。在数据中心环境下，网络资源属于较稀缺的资源，往往成为系统应用的瓶颈。在Hadoop系统中，通过使用数据压缩技术，将Map的输出结果进行压缩，再在Reduce节点进行解压缩。然而，解压过程也会引起一定的计算、时间开销。

鉴于Hadoop平台下作业调度算法在Reduce任务调度方面的不足，本文提出了一种新的任务调度算法，其基本思想在于选择系统中的最优节点，将特定的Reduce任务调度到最优节点上，从而减少任务的中间数据传输时间，省去对数据中心带宽资源的占用。其中最优节点是指集群中通过网络链路传输Map阶段中间数据时经过的跳数最少的节点。

Reduce任务调度算法不影响原有调度算法在作业调度层面的策略和优势[2-3]，但可以起到节约带宽的作用。因此，可以适用于网络资源较为紧缺的应用场景中，该算法也一定程度上可以降低整个作业的执行时间。

1 问题分析

MapReduce编程模型由Map和Reduce两个阶段构成，Map阶段读取输入数据并产生中间结果，Reduce阶段则对中间结果进行分析，从而得出最终作业分析结果。

MapReduce的基本执行流程如图1所示。其中，Map函数读取一个初始数据，然后计算产生中间数据的键/值对的集合，由MapReduce系统将具有相同Key的中间Values合并在一起，并且将这些中间数据定期存储在本地磁盘上，然后将这些数据传送给Reduce函数。Reduce函数读取Map输出的中间数据，在本地节点计算产生最终的结果，并将结果写入全局的Hadoop分布式文件系统（Hadoop Distributed File System ，HDFS）中。

图1 MapReduce基本工作原理

對于Reduce阶段，其过程包括3个子阶段，分别是：Shuffle子阶段、Sort子阶段、Reduce子阶段，具体执行过程如图2所示。其中，Shuffle子阶段从每一个运行Map任务的节点上将属于自己处理的数据分片并通过网络传输到运行Reduce任务的节点内存中，当内存缓冲满时再溢写到本地磁盘中去；Sort子阶段在Shuffle复制完所有Map输出期间，循环对Map的输出数据进行归并排序，以保证数据整体的有序性。Reduce子阶段对已排序输出的数据中的每个键迭代地调用Reduce函数，执行用户编写的Reduce函数代码，产生最后的输出数据，并写入最终的HDFS中。

通过进一步地分析，在Reduce的执行过程中，Shuffle子阶段一般占用长的时间，这主要是因为这一阶段需要通过网络传输数据，而且网络链路的情况不稳定，且网络带宽已经成为网络中的瓶颈资源，对数据的传输时间有很大的影响；Reduce子阶段需要的时间次之，因为这一阶段需要将最终结果写入HDFS中，且每个数据块需要存储一定数量的副本，需要花费较长的时间；Sort子阶段需要的时间最短，因此，这3个子阶段所占Reduce阶段的时间比例并不是Hadoop平台默认情况下的各占1/3。因此，基于各子阶段的实际时间占比，可以进一步优化Reduce执行过程的时间开销。

图2 Reduce执行过程

2 优化节点选择算法思想

由于磁盘和非易失存储器（Non-Volatile Memory，NVM）的存储介质不同，数据存储在不同介质上的性能差异较大，所以针对此问题我们设计了相应的数据部署方案。假设所有的数据原本均存储在磁盘中，设定初始数据块的标签表示Label=N，并且以读写、冷热和生存周期标签为迁移标准。

优化节点选择算法对每一个有空闲Reduce Slot的节点计算相应的链路长度和Shuffle阶段执行时间，获得所有Map中间数据经过的传输链路的长度和，通过比较在不同节点调度Reduce任务时的链路情况，选择具有最小值执行时间的节点（即最优节点），调度Reduce任务到该选中节点上执行，减少了Shuffle子阶段获得中间数据时对带宽资源的消耗和传输的时间开销，进而减少了单个作业的执行时间。这主要是因为数据传输时经过的链路的数目和数据经过的路由器的数目通常情况下是线性的关系：在各段链路网络传输速率相同的情况下，经过的链路长度越短，数据在物理链路上传播时消耗的时间也会减少，在这一阶段花费的时间就越短；并且经过的链路段数少时，经过的路由器数目就少，消耗的带宽也会减少；从而单个作业的执行时间也会减少。

优化节点选择算法属于调度模型的第3个层次，可将其嵌入已有的FIFO，Capacity Scheduler和Fair Scheduler等任务调度算法中。若将其嵌入FIFO中，FIFO只有一个作业队列，不需要第一级选择队列的调度，第二级选择作业的调度利用FIFO原有的先来先服务的调度策略，这样可以保持FIFO简单易实现等的优势，并且在第三级调度时，Map任务的调度策略也沿用原来的，在调度Reduce任务时应用本文中的调度算法选择最优的节点将作业的Reduce任务分配给该节点。若将其嵌入Capacity Scheduler中，类似的，其第一、第二级调度策略依旧沿用计算能力调度算法原来的机制，这样可以保留计算能力调度算法在作业并发执行方面的优势，然后在第三级调度时Map任务调度机制不变，Reduce任务调度算法使用本文中的调度算法，以求尽量减少Shuffle阶段需要的时间。若将其嵌入Fair Scheduler中时，第一级和第二级的调度策略沿用公平调度算法，可以保留公平调度算法在公平性方面的优势，同时在第三级调度时Map任务的调度策略也不做改变，即尽力满足数据本地性，而在调度选中的作业池中的特定的作业的Reduce任务时，将本文的算法嵌入进去，可以最大程度减少Shuffle阶段的链路传输时间。

3 结语

文章提出了一种针对MapReduce架构的Reduce任务优化调度方法。其核心在于分析Reduce各子阶段的真实时间占比，并采用优化节点选择算法来优化Reduce子阶段的执行，降低对集群带宽的使用，减少数据传输量，缩短Reduce任务的执行时间。

[参考文献]

[1]王少亚.Haboop在企业中的应用现状分析[J].商场现代化，2013（18）：84.

[2]赖海明.MapReduce作业调度算法分析与优化研究[D].杭州：杭州电子科技大学，2012.

[3]曹丙瑞.Hadoop平台作业调度算法研究与改进[D].石家庄：河北经贸大学，2015.