MapReduce异构环境下调度优化综述

王力生　魏薇

摘要：MapReduce作为一个分布式并行计算框架，在大数据处理方面得到了广泛的应用。该计算框架在同构集群环境中能够高效地运行，但是在异构集群环境中原容错算法不能正确地检测慢速任务，导致了性能的大幅下降。该文针对这一现象，分析了问题的主要原因，并且介绍了现存的几个优化算法，即Longest Approximate Time to End（LATE）算法，Self-Adaptive MapReduce（SAMR）算法，Enhanced Self-Adaptive MapReduce（ESAMR）算法，比較了各个算法的优缺点，最后指出了未来的研究方向。

关键词：MapReduce；调度算法；优化；容错性；推测性执行

中图分类号：TP316.4 文献标识码：A 文章编号：1009-3044（2015）01-0051-03

Survey on MapReduce Scheduling Algorithms in Heterogeneous Environments

WANG Li-Sheng，WEI Wei

（Department of Electronic and Information Engineering， Tongji University， Shanghai 201804， China）

Abstract： As a parallel programming model， MapReduce is widely used to process large data sets on a cluster. The current MapReduce implementation works effectively in homogeneous environment， but has a poor performance due to the static method used to detect stragglers. This paper discusses how the heterogeneity affects the MapReduce performance and surveys some of the approaches that have been designed to improve the MapReduce performance in heterogeneous environments. Advantages and disadvantages of these algorithms are identified.

Key words： MapReduce； scheduling algorithms； optimization； fault tolerance； speculative execution

1 概述

近年来，随着互联网技术的迅猛发展，越来越多的网络应用需要进行大数据的处理和存储。为了满足计算需求，计算资源逐渐由单机多核发展为集群众核。MapReduce[1， 2]是由Google提出的一个用于海量数据处理的分布式并行计算框架，在大数据处理方面得到了业内的广泛认可。大多数互联网公司都使用MapReduce来处理大数据的查询响应以及数据挖掘工作。

MapReduce框架最初被设计在同构环境中运行，即各检点的计算性能、存储容量、存储速度和网络带宽是相近的。MapReduce在进行输入数据划分、集群任务调度和容错性处理时，也都是基于同构环境的性质做出决策。但是随着集群规模的扩展，保持所有节点都属于同一机型是相当困难的事，所以MapReduce框架也可能会被部署在异构环境中，即各节点的计算性能、存储速度等方面存在较大的差异。

由于最初设计时没有充分考虑异构环境的运行情况，MapReduce在异构环境中的性能并不理想。针对这一问题，国内外的一些学者分析了MapReduce性能下降的原因，并且提出了一些异构环境下的改进算法。该文通过对这些算法进行分析，总结出各个算法的优缺点，希望以此作为相关技术人员的参考。

2 MapReduce框架介绍

2.1 MapReduce工作原理

将海量数据分成较小的数据块，分发到各个节点并行处理。对用户而言，任务在分布式集群中的调度过程是透明的。用户只需要实现Map函数和Reduce函数即可，其中，Map函数处理输入的键值对（key/value），并生成一组临时的键值对，发送给Reduce函数进行处理；Reduce函数处理临时键值对，生成最终结果写到分布式文件系统。Map函数和Reduce函数的并行调度由MapReduce框架完成。

以MapReduce的开源实现Hadoop[3]为例，计算任务的执行过程如图1所示。

1） 主节点JobTracker将存储在Hadoop分布式文件系统[4]（HDFS）上的用户输入数据划分为若干份，每一份数据的大小约64M（可通过配置文件设置），并为每一个划分创建一个map任务，分配给从节点TaskTracker执行。

2） 执行Map任务的节点以数据块作为输入，调用用户定义的Map函数，把输出的中间结果写入内存缓冲区。当内存缓冲区快要写满时，再把数据写到本地磁盘。

3） 在写入磁盘之前，Map节点会对数据进行排序和归并，按照键值把数据映射到不同的分区，使每个分区的数据对应一个Reduce任务，再通过JobTracker节点通知Reduce节点数据的存储位置。

4） 执行Reduce任务的节点从远程获取到数据以后，对来自不同Map节点的数据进行排序和归并，然后调用用户定义的Reduce函数，得到最终结果后写入文件系统。

2.2 MapReduce在异构环境中存在的问题

MapReduce在分配计算任务时基于集群同构的前提进行决策，分配给每台机器的任务槽数量和计算数据是基本相同的。同时，出于容错方面的考虑，为了防止执行速度慢的任务影响整体的执行进度，MapReduce使用推测执行机制，会为慢速任务启动一个备份任务，让备份任务与原始任务同时处理同一份數据，将先运行完的任务的输出作为最终结果。其中，慢速任务通过任务进度值（ProgressScore）来评估，范围是0到1之间的小数。对于Map任务，任务进度值为输入数据的处理比例；对于Reduce任务，任务被分为复制数据、排序和执行用户定义的Reduce函数三个阶段，每个阶段各占1/3。假设M表示任务Ti已处理的键值对数，N表示任务Ti需要处理的总键值对数，K表示Reduce任务当前所处的阶段，则任务Ti的进度值PSi计算公式如下：

然而，在异构环境中，以上描述的机制不能很好的执行。因为，高性能的节点能够更加快速地运行任务，拉高了平均进度值，从而使较多性能低的节点被判为慢速任务，导致大量任务需要备份。节点之间数据的传输增大了网络通信开销，使异构环境中的框架性能降低。

3 MapReduce调度优化算法分析

3.1 LATE算法

文献[5]提出了一种名为LATE算法的任务调度策略。LATE算法的核心思想是对执行结束时间最长的任务进行备份，因为这样的任务最有可能拖慢整个计算任务的响应时间。假设Timei为Ti的已执行时间，PSi为Ti的任务进度值，对任务Ti的结束时间TRi的估计，LATE算法采用以下公式：

针对异构环境中可能会出现大量备份任务这一问题，LATE算法定义阈值SpeculativeCap（大约总任务槽数的10%），表示系统中同时可以运行的最大备份任务数，当备份任务数达到阈值时，不会启动新的备份任务。另外，LATE算法认为备份任务不应该被运行在慢节点上，因此定义阈值SlowNodeThreshold（大约25%），如果任务进度值低于该阈值，则认为当前节点也是一个慢节点，备份任务不能在该节点上运行。

LATE算法的调度策略可以总结为：当一个节点出现空闲资源，且系统中总的备份任务数小于SpeculativeCap时，（1） 如果该节点是慢节点（节点得分低于SlowNodeThreshold），则忽略这个请求。（2） 对当前正在运行的任务按估算的剩余完成时间排序。（3） 选择剩余完成时间最大且进度值低于SlowTaskThreshold的任务，为该任务启动备份任务。

对比Hadoop内置的调度算法，LATE算法在异构环境中仅备份最慢的任务，并且控制了系统中备份任务的总数，提升了异构环境中集群的总体性能。通过确保将执行时间最长的任务备份在快节点上，能够有效地缩短任务的响应时间。

但是，LATE算法也存在一些不足。任务结束时间的估计是建立在任务线性运行的假设上的，通常不能正确判断发生异常故障的节点。判断也只能在任务执行一分钟之后进行，不够及时。

3.2 SAMR算法

针对LATE算法不能适应异构环境动态变化的问题，文献[6]提出了名为SAMR的算法。该算法基于LATE算法的核心思想，改进了最慢执行任务的推测。相对于Hadoop内置的调度算法，SAMR算法将执行时间缩短了近24%；相对于LATE算法，执行时间缩短了近14%。

SAMR算法认为计算任务进度值时，Reduce任务三个阶段的执行时间比例不能绝对地设置为1/3（即R1=R2=R3=1/3） ，Map任务的排序阶段也不能直接忽视（即M1=1，M2=0），都应该根据节点的性能设置为不同的值。对慢节点的备份也应该分为Map慢节点和Reduce慢节点分别进行，因为有些情况下Reduce慢节点没有必要进行备份。该算法在每个节点上记录本地运行任务的时间信息，执行任务时读取本地的历史信息，动态地调整任务进度值中的参数值M1-2、R1-3。通过公式（4） 计算出任务Ti的ProgressRatei后，如果ProgressRatei满足以下公式，则被判断为慢节点：

其中，SlowTaskCap是0到1直接的值，越接近0，就有越多的任务被判断为慢任务。在执行完计算任务后，SAMR算法更新本地的历史数据，将本次参数信息写入文件。

SAMR算法与LATE算法相比，能够根据不同节点的性能，更准确地计算任务进度值，推测出需要备份的慢节点。但是，SAMR算法忽略了数据集的大小和不同计算任务类型对任务进度值计算参数的影响，仅依靠历史信息调整计算参数仍然存在偏差。

3.3 ESAMR算法

ESAMR算法[7]是SAMR算法的一个优化版本，基于记录历史执行信息的方案，采用k-means算法动态调整计算任务进度值公式的参数M1-2、R1-3，提高了推测慢速任务的准确率。

ESAMR算法根据参数M1-2、R1-3的数值，通过机器学习的技术将每个节点上的记录的历史信息划分为k个聚簇。对于Map阶段，该算法根据计算任务在节点上已完成的Map任务得出一个M1的临时值，通过临时值找到最邻近的聚簇，使用该聚簇的任务进度值计算节点的任务结束时间；对于Reduce阶段，采用类似的方法，通过R1和R2的临时值找到最邻近的聚簇，使用该聚簇的任务进度值来推测慢速任务。在计算任务结束后，ESAMR算法记录各节点的执行信息，然后对聚簇进行重新划分。

对比于LATE算法和SAMR算法，ESAMR算法能够跟准确地推测慢速任务，从而提高了集群的运行效率。不足之处在于，使用k-means算法本身也存在一些额外的开销，增加了系统的负载。

4 总结

本文以Hadoop内置调度算法为例，介绍了MapReduce框架在异构集群环境中性能下降的主要原因，并且对LATE算法、SAMR算法和ESAMR算法在异构集群中的表现进行了分析和比较。MapReduce框架在设计时仅考虑了同构集群的环境，其容错算法在异构集群中会导致大量任务备份，影响框架的整体性能。LATE算法提出备份运行结束时间最长的任务的核心思想，提高了框架的响应时间。SAMR算法基于LATE算法的思想，利用节点的历史信息更加准确地计算任务的结束时间。ESAMR算法在SAMR算法的基础上，通过数据挖掘的技术动态调整计算参数，提高了结束时间计算的准确性。

綜上所述，对于MapReduce在异构集群环境下的调度算法仍然有待优化，是一个充满前途的挑战的领域。

参考文献：

[1] Dean J，Ghemawat S.Mapreduce： simplied data processing on large clusters[C]//OSDI 2004： Proceedings of 6th Symposium on Operating System Design and Implemention，（New York）， ACM Press，2004：137-150.

[2] Dean J，Ghemawat S.MapReduce： a flexible data processing tool[C]//Communications of the ACM，2010，53（1）：72-77.

[3] Apache Hadoop[EB/OL].http：//hadoop.apache.org.

[4] Hadoop Distributed File System[EB/OL].http：//hadoop.apache.org/hdfs.

[5] Zaharia M，Konwinski A，Joseph A D，et al.Improving mapreduce performance in heterogeneous environments[C]//8th Usenix Symposium on Operating Systems Design and Implementation， （New York）， ACM Press，2008：29-42.

[6] Quan Chen， Daqiang Zhang， Minyi Guo， et al.SAMR： A Self-adaptive MapReduce Scheduling Algorithm in Heterogeneous Environment[C].Computer and Information Technology （CIT）， 2010 IEEE 10th International Conference on， 2010：2736-2743.

[7] Xiaoyu Sun， Chen He，Ying Lu.ESAMR： An Enhanced Self-Adaptive MapReduce Scheduling Algorithm[C]//IEEE 18th International Conference on Parallel and Distributed Systems，2012.