李霞++柯琦

摘要：对Hadoop平台下现有的调度算法进行分析研究。在MapReduce计算模型下，针对Reduce阶段的任务调度问题提出在异构Hadoop环境下新的调度算法，算法在最大程度上提升 数据本地性的同时考虑各处理机节点的不同处理能力。对该算法进行实验和性能分析，表明该算法在减少调度时间方面有较好的表现，同时可以适用于更加符合实际的异构Hadoop机群系统中。

关键词：Hadoop；MapReduce模型；任务调度

中图分类号：TP311.13 文献标识码：A 文章编号：1007-9416（2017）02-0144-02

1 引言

随着计算机与网络技术的发展，通过网络进行传输、处理的数据流急剧增加，这也给传统的计算模式带来极大的挑战，在此情形下，云计算平台以强大的计算机能力和低廉的实现代价得到了广泛的应用。MapReduce是Google在2004年提出的用于处理海量数据的一个高效的并行计算模型，这种模型向程序员屏蔽了复杂的内部细节，并提供了简单的编程接口，这样大大缩短了分布式程序员的开发周期，因此得到广泛应用。而Hadoop作为MapReduce的开源实现，它提供了一个高可靠性、高容错性、良好的扩展性的分布式文件系统，因此被诸多企业应用于数据的存储与处理中。MapReduce的任务调度算法对Hadoop平台的性能有着非常重要的影响，但是，在实际环境中，MapReduce的任务调度依旧存在着不少的缺陷，因此许多学者与组织在此课题上做了不少的研究。

2 研究进展分析

在Hadoop平台中，机群节点数通常很多，因此，数据本地性是调度算法所要考虑的一个非常重要的指标，因为数据在网络中传输需要时间，且在不同机架之间传输需要的时间更多，从而会导致作业的执行周期变长，同时也会增加网络传输的开销。

MateiZaharia等人提出的延迟调度算法（Delay Scheduler）是目前研究的热点，该算法以牺牲公平性和响应时间来最大限度的保证作业在本机节点上被执行，并且设定一个时间阈值，在时间阈值内，让非本地任务进行等待。因此，当集群中大部分作业为小作业时，该算法可以大大提高数据本地性。针对该算法中时间阈值的设定，文献[1]和文献[2]通过节点负载量和节点释放速度进行分析，提出在运行中自适应调整时间阈值。以上研究都是提高Map阶段数据的本地性。

综上所述，许多研究学者为了提高Hadoop系统的各方面的性能，围绕MapReduce作业调度算法进行了大量的研究与改进，然而，其中大部分对Reduce任务的调度算法的研究较少。同时，他们更多考虑的是机群中节点具有相同处理能力的同构环境，从而限制了调度算法的应用范围。本文从提高数据本地性的角度出发，考虑更加符合实际应用的异构环境下的Reduce任务的调度算法。

3 MapReduce计算模型

在MapReduce计算模型下，把运行于大规模集群上的复杂的并行计算过程高度的抽象为两个函数：Map和Reduce。一个Map/Reduce作业（job）通常会把输入的数据集划分为若干独立的数据块，由Map任务以完全并行的方式处理它们。框架会对Map输出进行排序，然后把结果输入给Reduce任务。过程如图1所示。

通常，Map/Reduce框架由一个单独的Master JobTraker 和集群中节点上的Slave TaskTracker共同组成。Master节点负责调度构成一个作业的所有任务，这些任务分布在不同的Slave节点上。Master监控它们的执行，并重新执行已经失败的任务，而Slave节点负责执行由Master指派的任务。

4 新的调度算法

然而，在执行Reduce阶段任务时，由于数据和Reduce（ ）可能处在不同的节点上，因此在通常情况下需要通过数据或者Reduce任务的转移来实现数据的正常处理，为了避免在转移时花费巨大的网络开销和时间延迟，就要从根本上减少后期数据或Reduce任务的转移，提高数据的本地性。

4.1 Map阶段

由于本文考虑的是异构机群系统，因此每个处理机节点的处理能力可能都不一样，为了能够减少任务调度时间，根据处理能力的高低来分配数据，处理能力强的节点分配更多的数据块。这样，处理能力强的计算机节点上在该阶段结束后也会拥有更多的Map结果集，会减少Reduce阶段数据的转移。

4.2 Reduce阶段

在该阶段，由于Reduce任务所需要的数据块分布在不同的处理机节点上，为了减少数据的轉移带来的时间及网络消耗，本文也尽量的将Reduce任务调度到拥有最多所需数据集的节点上运行。

就Reduce任务何时开始执行的问题，Hadoop中提供了一种开关机制，也就是当Map任务执行到一定程度（默认是5%）的时候，同步执行Reduce任务，这样可以提高任务执行的并行性，但是会降低数据的本地性。同时，由于Reduce任务一旦被启动就会占用资源，如果该任务的数据集断断续续被提供直到所有Map任务结束，这样就会降低系统资源的利用率。如果这种开关机制关闭的话，则是当所有的Map任务执行结束后才开始执行Reduce任务，这样就可以清楚的知道每个Reduce任务所需的数据集所在的位置，通过向拥有最多所需数据集的节点转移Reduce任务，可以提高数据的本地性。本文考虑开关机制关闭的情形。

在Map阶段之后为每个Reduce任务建立列表，其中包含其所需的数据集所在的节点及数据量。然后依次对列表中的Reduce任务进行调度，如果当前Reduce任务所需最多的数据集所在的处理机节点的处理能力很低，还应该要考虑更换节点。

为了便于描述，假设机群系统中共有N个处理机节点，它们的计算速度分别为P1，P2，P3...PN。当前Reduce任务所需的数据集分布在P1，P2，...PM节点上（M<=N），这些节点上拥有该Reduce任务所需的数据量分别为L1，L2，...LM，数据在节点之间进行传输的速率为S。

令：L=L1+L2+...+LM，则选择P1节点进行Reduce任务处理所需的时间为： ，选择P2节点进行Reduce任务处理所需的时间为：；即，选择Pi（i=1，2...M）节点进行Reduce任务处理所需要的时间为：（i=1，2...M）。

因此，将当前的Reduce任务转移到具有MIN（）值的处理机节点j上，同时将所需的其他数据集传输到j节点上。如果j节点上已经有任务在处理，则要分两种情形：如果j节点上任务处理还需要的时间比j节点和下一个MIN（）值的处理机节点k（k<>j）之间时间差值大，则选择下一个节点，而对下一个节点的判断和刚刚判断的过程一致；否则选择j节点，等现有的Reduce任务处理完，再继续处理。

5 实验结果论证

本文通过在实际的异构Hadoop机群系统上分别以Hadoop自带的WordCount（单词统计程序）、Terasort（字符串排序算法）为测试程序实例，所有的实验在一台Intel四核机器、两台联想双核机器、一台联想单核机器通过100Mbps以太网互连组成的异构Hadoop机群系统上实现。各处理机节点运行的操作系统均为CentOS6.4；编程语言为Java，版本jdk1.7；Hadoop版本为2.2.0。

（1）实验一：实验向系统提交Hadoop自带的WordCount（单词统计程序）作业，作业输入的大小分别为2GB，4GB，8 GB。实验分别使用Hadoop自带的Fair Scheduler（公平调度算法）和本文提出的调度算法分别执行6次，统计了WordCount不同规模下整个任务执行的时间，然后取得平均值，实验结果对比如图2所示。

（2）实验二：实验向系统提交Hadoop自带的Terasort（字符串排序算法）作业，作业输入的大小分别为2GB，4GB，8 GB。实验分别使用Hadoop自带的Fair Scheduler（公平调度算法）和本文提出的调度算法分别执行6次，统计了Terasort不同规模下整个任务执行的时间，然后取得平均值，结果对比如图3所示。

通过两个不同的程序实例，从实际的实验结果可以看出，本文提出的调度算法在不同数据规模下均有较好的表现，因为在调度的过程中充分考虑了处理机节点处理能力的不同，同时在Reduce任务转移时考虑各处理机节点的数据集问题，从而最大程度减少数据的转移所花费的代价，進而减少了任务调度时间。

6 结语

本文就MapReduce计算模型下Reduce任务的调度问题，针对异构机群构成的Hadoop平台提出了新的调度算法，算法在考虑数据本地性的同时还考虑各个处理机节点的处理能力，最大程度减少调度长度，通过实验对调度算法进行验证，实验结果表明新的调度算法有着良好的调度效果。

参考文献

[1]金嘉晖，罗军舟，宋爱波，等.基于数据中心负载分析的自适应延迟调度算法[J].通信学报，2011（7）：47-56.

[2]宁文瑜，吴庆波，谭郁松.面向MapReduce 的自适应延迟调度算法[J].计算机工程与科学，2013（13）：53-57.