基于匹配规则的MapReduce任务调度模型

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于匹配规则的MapReduce任务调度模型范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：基于开源云计算平台Hadoop的MapReduce是当前流行的分布式计算框架之一，然而其先进先出（FIFO）调度算法存在资源利用效率低下的问题。提出了一种基于资源匹配规则的mapreduce任务调度模型并进行了算法实现。该调度模型通过获取任务的资源需求与计算节点的剩余资源，依据资源的匹配性进行任务分配，提高了系统的资源使用效率。首先对MapReduce的调度过程进行建模，提出了资源及匹配度的量化定义和相应的计算公式；然后给出了资源测量的具体方法及算法实现；最后利用TeraSort、GrepCount和WordCount任务与FIFO调度算法进行实验对比，实验结果显示，最好的情况下，提出的调度模型任务完成时间减少了22.19%，而最差情况下的吞吐量也提高了25.39%。

关键词：云计算；调度算法；Hadoop；MapReduce；先进先出

0 引言

目前一个普遍被接受的云计算的定义是由Vaquero等[1]提出的：云计算是一种大规模的易用的可访问的虚拟资源（如硬件、平台和/或服务）池。从云计算的定义可以看出，云是网络发展和信息技术（Information Technology，IT）计算发展的必然结果。如：Google公司为解决自身大规模数据集处理问题而提出的GFS（Google File System）[2]、MapReduce[3]计算框架以及为保证这两项技术顺利运行而提出的其他相关技术[4]。云计算代表了未来IT技术发展的方向。

2004年，Apache Nutch项目负责人Doug Cutting按照Google公司公布的文献实现了开源的MapReduce框架并命名为Hadoop，大大方便了云计算的学术研究。但是，在实际使用中，MapReduce调度算法存在效率低下的问题[5]。当前，Hadoop使用先进先出（FirstIn FirstOut，FIFO）算法进行调度。该算法调度中只考虑任务的到达的顺序，因此不能综合考虑任务的需求和节点剩余的资源。

本文提出了一种基于匹配规则的MapReduce任务调度（MA）模型，其基本思想是对任务的资源需求进行量化，同时考察计算节点剩余的资源，通过本文提出的匹配规则计算任务与资源节点匹配度，然后将任务调度到最匹配的计算节点，从而达到资源的最佳利用率，提高算法的调度效率。通过利用TeraSort、GrepCount和WordCount与Hadoop的FIFO调度算法相比较，结果显示本文提出的算法在任务完成时间上减少了22.19%，吞吐量上增加了25.39%。

1 MapReduce调度模型及相关工作

MapReduce是一种非常容易实现的分布式计算框架，图1显示了MapReduce任务调度的运行过程。在MapReduce运行过程中，用户程序需要被主节点调度到相应的从节点以满足分布式计算的需要。

当前，Hadoop平台中MapReduce的任务调度采用的是FIFO的调度算法，其基本思想是：将计算节点的计算能力划分，一份计算能力可以计算一个任务，这一份计算能力称为slot。当一个计算节点有空余的slot时，便向主节点请求一个计算任务。当主节点中有计算的任务时，则将相应的任务的按照到达的先后顺序进行调度和计算。这样的调度算法存在两个方面的问题：一方面无法优先照顾较短的计算任务，吞吐量较低；另一方面未考虑当前计算节点的实际运行情况，资源的利用效率不高。

针对Hadoop的FIFO算法无法及时响应交互式程序的问题，Yahoo公司提出了计算能力调度算法（Capacity Scheduler）[6]，该算法的基本思想是将任务分为多个队列，每个队列分配一定的资源，队列中的每个任务按照FIFO算法来调度，这样，就可以在一定程度上，让所有的用户的任务都能被执行。具有类似思想的还有Facebook公司提出的公平调度算法（Fair Scheduler）[7]，所不同的是公平调度算法默认情况下，会对每个用户分配一个资源池，这样公平地保证每个用户的任务都能被执行，而不考虑该用户提交任务的多少。

为了计算式（4），需要知道各个计算节点剩余的资源及任务的资源需求。对于计算节点资源的剩余情况，在具体实现上，本文在Slave与Master节点间通信的Heartbeat数据结构中增加了三个变量，同时在Slave端通过读取/proc下的文件来获取当前计算节点的资源剩余情况。对于任务的资源需求，如算法1所示，当请求任务的计算节点并没有任务在运行，且当前存在资源需求未知的任务时，则将该任务调度到该计算节点；当该任务在该计算节点运行时，则通过Linux自带的time指令来记录和获取该任务的资源需求。

3 实验及算法评估

本章对本文提出的算法进行验证，并与Hadoop自带的FIFO调度进行对比，并从任务的调度时间及吞吐量来评价其调度效果。

其中：hadoop为Hadoop平台自带的命令，用来执行任务的提交；hadoop1.0.4examples.jar为Hadoop提供的示例包。第一条命令将生成测验的数据，并将数据存放在HDFS中的input15GB目录；第二条命令执行TeraSort测试，MapReduce将从input5GB中读取数据，然后，将排序的结果输出到output15GB中。

不同于其他分布式算法的复杂实现，对于基于MapReduce的分布式计算来说，算法的实现者只需要按照MapReduce框架的接口，实现自己的代码即可，而无需关心任务分配等一系列的分布式算法的细节。这正是MapReduce平台最为重要的优势之一。

3.4 实验结果

3.4.1 资源利用率

实验中，首先验证本文算法提出的基础，即任务的差异性，首先测试三种任务的资源需求。将各种任务连续提交25次，表2给出了三种任务在前述硬件环境及设置的云计算平台上经本文提出的算法获取的平均资源需求。

从表2中可以看出，三种任务的资源需求是不同的。TeraSort是著名排序基准测试任务，该任务对内存、I/O需求非常大，对CPU的需求较大，这是因为该任务需要将排序的数据从硬盘或者网络读出，在排序好后，又需要将全部的数据写回到硬盘，因此需要较多的I/O资源。

GrepCount是基于Linux平台上的Grep命令来完成的，GrepCount的输入参数为查询的字符串和查找的文本集。使用Linux平台上的Grep命令查询时，其查询结果会返回匹配的行，而GrepCount则不同，其返回的是文本的名字及其匹配字符串所在的行。因此，其I/O的需求较TeraSort小。GrepCount的CPU资源需求与输入的正则字符串有较为密切的关系，本文将其查询的字符串设置为[.]*，此时，GrepCount需要消耗大量的CPU资源来进行字符串的检索。

WordCount任务主要通过将文本按照一定的规则，通常是按行进行分割，然后将分割后的小块输入到Map任务中，在Map中只是简单地将各个字符以关键字和出现次数的形式输出，然后由Shuffle和Reduce模块来共同完成字符的统计。因此，该任务的CPU资源需求非常小，实验的结果也验证了这一点。

通过表3可以知道，不同种类的任务具有不同的资源需求，因此，如果计算节点总是运行相同的资源，则会造成某种资源的短缺，成为计算的瓶颈。如：将两个TeraSort安排到同一个计算节点，则会造成内存与I/O的短缺，同时，CPU却还要一定的剩余空间；如果将TeraSort和GrepCount安排到同一个计算节点，则资源的利用效率会有较大的提高。因此，依据任务的资源需求和当前计算节点所剩余的资源合理地安排计算任务，可以提高云计算平台的资源利用效率。通过上述实验验证了资源匹配的优势及本文算法的可行性。

3.4.2 与Hadoop调度算法的对比

3.4.1节验证了Hadoop原始的调度算法FIFO在资源利用效率方面的缺陷，本节将通过实验来对比两种算法的差异性。实验中，将三种任务通过三个客户端来同时提交给Master，一个客户端提交一种任务；同时，当该客户端的任务运行完毕时，该客户端继续提交相同的任务，每个任务提交5次后，完成计算。这和现实中的任务调度是一致的，很多的云计算平台每天都重复运行着相同的任务。

本文通过任务完成的总时间和吞吐量来评价两种算法的调度效果，实验重复了25次。图2和3分别表示了任务完成的时间和吞吐量。从图2可以看出基于资源匹配的调度算法无论是最好情况、平均情况还是最差情况都要优于Hadoop的原始调度算法。最好的情况下，Hadoop调度任务完成时间是7750s，而匹配调度的算法则达到了6030s，其任务的完成时间减少了22.19%；而最差的情况下，则减少了27.26%。从吞吐量来看，即使最差的情况下，也提高了25.39%。

4 结语

本文讨论了Hadoop平台上MapReduce计算框架的调度算法，提出了一种基于匹配规则的MapReduce调度模型。不同于原始的Hadoop中MapReduce的FIFO调度算法，本文的调度算法在Map任务进行调度时不再采用FIFO的策略进行任务分配，而是通过计算任务与计算节点的资源匹配度来达到任务分配的目的。在Hadoop平台上，采用TeraSort、GrepCount和WordCount三个MapReduce任务验证了本文算法的可行性并对比了Hadoop的原始调度算法。实验结果表明，考虑任务的资源需求是很有必要的，同时从任务完成时间和吞吐量两个方面看，基于资源匹配的MapReduce任务调度模型比Hadoop的原始调度算法的性能有较大提高。

参考文献：

[1]ARMBRUST M， FOX A， GRIFFITH R， et al. A view of cloud computing [J]. Communications of the ACM， 2010， 53（4）：50-58.

[1]VAQUERO L， RODEROMERINO L， CACERES J， et al. A break in the clouds： towards a cloud definition [J]. ACM SIGCOMM Computer Communication Review， 2008， 39（1）：50-55.

[2]GHEMAWAT S， GOBIOFF H， LEUNG ST. The Google file system [C]// SOSP 03： Proceedings of the 19th ACM Symposium on Operating Systems Principles. New York： ACM， 2003： 29-43.

[3]DEAN J， GHEMAWAT S. MapReduce： Simplified data processing on large clusters [J]. Communications of the ACM， 2008， 51（1）：107-113.