MapReduce在Hadoop平台下作业调度算法的改进和实现

解慧娟

摘要：该文在Hadoop实现的MapReduce架构基础上，分析了现有的三种作业调度算法，针对当前算法没有考虑服务器负载状况和数据本地性差的缺点，提出了基于可变长度队列的公平调度算法（FSVQ），该算法分析了空闲节点率，并通过采取等待的办法满足考虑数据本地性。实验证明该算法可增加服务器集群的工作效率，减少网络延迟，具有实际的应用意义。

关键词：云计算；MapReduce；Hadoop；调度算法；负载；数据本地性

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）14-3206-03

Abstract： Based on the MapReduce framework achieved by Hadoop，this article has a detailed analysis of the existing three job scheduling algorithm， For these three algorithms does not consider the load conditions of server cluster and poor data locality， this paper presents the FSVQ algorithm which analyze the number of the arrival of idle nodes in certain time，it is also meet the data locality by waiting approach.The results prove that the algorithm can increase the efficiency of server clusters and reduce network latency， with practical application significance by test.

Key words： cloud computing； MapReduce； Hadoop； scheduling algorithm； load； data locality

1 绪论

在Web2.0时代，MySpace、YouTube等网站的访问量巨大，同时凭借Google文件系统搭建起来Google服务器群，为Google提供强大的搜索速度与处理能力。正是由于一方对计算能力的需求，另一方可提供这样的计算能力，于是云计算就应运而生。维基百科中云计算的定义如下：云计算是一种基于互联网的计算方式，通过这种方式，共享的软硬件资源和信息可以按需提供给计算机和其他设备。

Google当数最大的云计算的使用者，Google已经允许第三方在Google的云计算中通过Google App Engine运行大型并行程序，同时它早已以发表学术论文的形式公开其云计算三大法宝：GFS、MapReduce和BigTable。

2 Hadoop平台及MapReduce概述

Hadoop是一个开发和运行处理大规模数据的软件平台，由分布式存储HDFS（Hadoop分布式文件系统）和分布式计算MapReduce两部分组成。

MapReduce是是一个编程模型，用以进行大数据量的计算。MapReduce的模型最早出现在Google，MapReduce框架模型通过简单的接口来实现自动的并行化和大规模的分布式计算，通过使用MapReduce模型接口实现在大量普通的PC机上高性能计算。MapReduce两个对外接口分别是Map函数和Reduce函数，用户指定一个Map（映射）函数，把一组键值对映射成一组新的键值对，指定并发的Reduce（化简）函数，用来保证所有映射的键值对中的每一个值共享相同的键组，从而将拆成小块的数据经过计算后再重组回来。

3 Hadoop平台作业调度算法的研究及改进

当前最常用的Hadoop作业调度算法有三种：默认的先进先出算法（FIFO）、Facebook提出的公平调度算法以及雅虎提出的计算能力调度算法。

先进先出算法是Hadoop默认的作业调度算法，该算法根据作业进去的先后顺序进行排队，先进来的作业被优先处理。该算法主要针对单用户单一类型作业设计，在分布式集群系统中表现出的性能往往不是很理想。

针对先进先出算法的缺点，Facebook和雅虎的工程师分别提出了新的作业调度算法：公平调度算法和计算能力调度算法。目前这两种算法已经被应用在新的Hadoop版本当中。公平调度算法可以保证每个用户都可以分到所需资源，这样就可以最大限度的利用集群的系统资源。公平调度算法采用一个分层次的设计，在最顶层，公平调度算法按照作业池（pool）把任务节点分配给用户，每个用户都会分配到一定量的任务节点，在第二层，每个作业池为不同的作业分配任务节点。

计算能力调度算法是由雅虎的工程师提出来的，在选择调度的队列的时候，计算能力调度算法会先选择资源利用率最低的队列，在该队列中选择作业去执行。计算能力调度算法把每个队列看做是独立的集群，该算法支持多作业并行执行提高了系统资源利用率。

4 一种改进的算法—基于可变长度队列的公平调度算法（FSVQ）

公平调度算法和计算能力调度算法需要分别设置作业池和作业队列的资源数，保证每个作业都能得到所需要的系统资源。当面对大量用户的时候，这种事先设置的方式往往忽略了作业在实际运行过程中的资源使用情况，导致预先的设置无法适应集群当前的负载情况，大大延长任务的执行时间。

MapReduce的架构设计和运算理念即移动计算比移动数据方便，因此MapReduce架构通过把任务复制到数据节点上，减少了数据在网络中的传送，提高了执行作业的效率，这一过程称为数据本地性。在现有的Hadoop作业调度算法里，先进先出算法只适合单用户的类型，当集群有空闲节点时，算法就会把队首作业的一个任务分配给该计算节点，而不管该节点是否含有该任务所需要的数据。其次是公平调度算法，公平调度算法把作业按照当前执行任务数量多少的增序进行排列。也就是说如果一个作业当前执行任务最少，它会被排到队首，当这样一个作业到达队首的时候，不管哪个节点空闲，算法都会把队首任务分配给该空闲节点。

因此现有的作业调度算法主要存在两个问题：没有实时的考虑系统的负载状况，不能获得良好的数据本地性。针对现有的算法不能实时的分析集群的负载状况，本算法提出了基于可变长度队列的公平调度算法（FSVQ）的设计，在设计算法的时候主要考虑两个原则：

1）自适应的负载调节。系统分析当前系统的负载状况，决定执行作业数的多少，而没有被执行的作业则放到等待队列中去。

2）在获得执行权限的作业，我们按照改进的公平调度算法去执行，通过采取等待的方式，使之获得良好的数据本地性。

FSVQ算法流程图如图1。

4.1满足负载均衡的设计

本算法设计两个队列，分别是作业执行队列和作业等待队列。Hadoop平台是通过主控节点接受心跳，感知空闲节点，从而给空闲节点分配任务。

定义1：单位时间内空闲节点的到达次数称为空闲节点率，记为λ。

定义2：该文把该阀值记为X，阀值的取值是管理员根据自己集群系统的状况，通过统计多次作业执行来确定。

过于频繁的改变作业执行队列的长度，不仅会浪费系统的资源，也会浪费作业执行的时间。该文在这里引入方差这个概念作为度量值。通过比较|λ-X|与方差的大小，决定是否改变作业执行队列的长度。

4.2满足数据本地性的设计及等待时间阀值T的数学模型求解

传统公平调度算法数据节点满足数据本地性很差，并不适合MapReduce的设计理念。在该算法中，设计了两个等待的时间w1和w2。在本文中只设计一个动态的等待时间的阀值以适应集群系统负载情况的变化，减少算法的执行时间，在本算法中，T由一个函数GetThreshhold（λ，K）实现。

该系统总共有M个计算节点，每个节点有L个作业槽，该系统中总共会有S=ML个作业槽。每个作业J会有N个任务。在分布式文件系统中，每个文件块的副本数为R。

任意时刻，假设作业J还有K个任务没有完成，那么对作业J来说，接下来如果有空闲节点到达，该空闲节点满足作业J的数据本地性的概率P为：P=1-（1-K/M）R。当前集群系统的空闲节点率为λ，则过了时间T后就会有λT个空闲节点到达。按照已经得出的满足作业J的概率P，可以得出，λT个空闲节点中能够满足J的数据本地性要求的节点有λT·[1-（1-K/M）R][≥][λ]T·（1-e-RK/M）。

要想T时间内等到满足数据本地性的节点，则在这段时间内，至少要有一个节点满足数据本地性，所以要满足公式：[λ]T·（1-e-RK/M） [≥]1。解这个不等式可以得出：

T[≥]1/ [λ]（1-e-RK/M）

5 实验及结果分析

搭建好实验平台之后，该文为了验证FSVQ算法的性能，主要分析数据本地性及算法的响应时间。该文把原始的公平调度算法称为FS算法，由facebook改进后的延迟调度算法称为DS算法。

为了验证高负载集群对算法性能的影响，可以通过安装trickle软件实现控制网络带宽。本实验一共执行4个字数统计的作业，各个作业的信息如表1所示：

5.1响应时间分析

在10M网络环境下，网络传输开销大，空闲节点率降低，FSVQ算法认为集群负载高，从而减少了作业执行队列的长度，表2是各个算法下的每个作业的响应时间：

从表中可看出，在执行作业2和作业3的过程中，由于FSVQ算法减少了一个执行作业，所以作业2和作业3的执行时间都优于DS算法，而作业4之前被移除出作业执行队列，造成了作业相应时间的延长。但是在总的响应时间上FSVQ算法比DS算法少了44s。

5.2 数据本地性分析

下图是各个作业分别用上述算法执行时的数据本地性表示。

从图2中可以看出FS算法由于没有采用延迟机制，造成各个作业的数据本地性很差，这也是用FS算法执行的作业响应时间长的重要原因。DS算法由于采用了两个等待时间，所以在数据本地性上略优于FSVQ算法，但也正是由于采用了两个等待时间，造成了DS算法响应时间长于FSVQ算法。

由以上数据本地性和响应时间综合分析可以得知，FSVQ算法在保证数据本地性的前提下确保了响应时间，相比DS算法，FSVQ算法略微牺牲了数据本地性，但是响应时间是优于DS算法的。

6 总结

如今新版的Hadoop支持作业调度的热插拔，使得对已有作业算法的改进成为可能。该文重点对Hadoop的作业调度算法进行了研究，分析了已有的调度算法，针对目前算法不能够很好的解决数据本地性和负载均衡的问题，在以后的公平份额调度算法的基础上进行了改进，并通过实验验证了改进后算法的性能。

参考文献

[1] 陈全，邓倩妮.易购环境下自适应的MapReduce调度[J].计算机工程与科学，2009，31（z1）：5.

[2] 张密密.MapReduce模型在Hadoop实现中的性能分析及改进优化[D].电子科技大学，2010

[3] 张青.网格环境下任务调度算法的应用研究[D].大连海事大学，2009.

因此现有的作业调度算法主要存在两个问题：没有实时的考虑系统的负载状况，不能获得良好的数据本地性。针对现有的算法不能实时的分析集群的负载状况，本算法提出了基于可变长度队列的公平调度算法（FSVQ）的设计，在设计算法的时候主要考虑两个原则：

1）自适应的负载调节。系统分析当前系统的负载状况，决定执行作业数的多少，而没有被执行的作业则放到等待队列中去。

2）在获得执行权限的作业，我们按照改进的公平调度算法去执行，通过采取等待的方式，使之获得良好的数据本地性。

FSVQ算法流程图如图1。

4.1满足负载均衡的设计

本算法设计两个队列，分别是作业执行队列和作业等待队列。Hadoop平台是通过主控节点接受心跳，感知空闲节点，从而给空闲节点分配任务。

定义1：单位时间内空闲节点的到达次数称为空闲节点率，记为λ。

定义2：该文把该阀值记为X，阀值的取值是管理员根据自己集群系统的状况，通过统计多次作业执行来确定。

过于频繁的改变作业执行队列的长度，不仅会浪费系统的资源，也会浪费作业执行的时间。该文在这里引入方差这个概念作为度量值。通过比较|λ-X|与方差的大小，决定是否改变作业执行队列的长度。

4.2满足数据本地性的设计及等待时间阀值T的数学模型求解

传统公平调度算法数据节点满足数据本地性很差，并不适合MapReduce的设计理念。在该算法中，设计了两个等待的时间w1和w2。在本文中只设计一个动态的等待时间的阀值以适应集群系统负载情况的变化，减少算法的执行时间，在本算法中，T由一个函数GetThreshhold（λ，K）实现。

该系统总共有M个计算节点，每个节点有L个作业槽，该系统中总共会有S=ML个作业槽。每个作业J会有N个任务。在分布式文件系统中，每个文件块的副本数为R。

任意时刻，假设作业J还有K个任务没有完成，那么对作业J来说，接下来如果有空闲节点到达，该空闲节点满足作业J的数据本地性的概率P为：P=1-（1-K/M）R。当前集群系统的空闲节点率为λ，则过了时间T后就会有λT个空闲节点到达。按照已经得出的满足作业J的概率P，可以得出，λT个空闲节点中能够满足J的数据本地性要求的节点有λT·[1-（1-K/M）R][≥][λ]T·（1-e-RK/M）。

要想T时间内等到满足数据本地性的节点，则在这段时间内，至少要有一个节点满足数据本地性，所以要满足公式：[λ]T·（1-e-RK/M） [≥]1。解这个不等式可以得出：

T[≥]1/ [λ]（1-e-RK/M）

5 实验及结果分析

搭建好实验平台之后，该文为了验证FSVQ算法的性能，主要分析数据本地性及算法的响应时间。该文把原始的公平调度算法称为FS算法，由facebook改进后的延迟调度算法称为DS算法。

为了验证高负载集群对算法性能的影响，可以通过安装trickle软件实现控制网络带宽。本实验一共执行4个字数统计的作业，各个作业的信息如表1所示：

5.1响应时间分析

在10M网络环境下，网络传输开销大，空闲节点率降低，FSVQ算法认为集群负载高，从而减少了作业执行队列的长度，表2是各个算法下的每个作业的响应时间：

从表中可看出，在执行作业2和作业3的过程中，由于FSVQ算法减少了一个执行作业，所以作业2和作业3的执行时间都优于DS算法，而作业4之前被移除出作业执行队列，造成了作业相应时间的延长。但是在总的响应时间上FSVQ算法比DS算法少了44s。

5.2 数据本地性分析

下图是各个作业分别用上述算法执行时的数据本地性表示。

从图2中可以看出FS算法由于没有采用延迟机制，造成各个作业的数据本地性很差，这也是用FS算法执行的作业响应时间长的重要原因。DS算法由于采用了两个等待时间，所以在数据本地性上略优于FSVQ算法，但也正是由于采用了两个等待时间，造成了DS算法响应时间长于FSVQ算法。

由以上数据本地性和响应时间综合分析可以得知，FSVQ算法在保证数据本地性的前提下确保了响应时间，相比DS算法，FSVQ算法略微牺牲了数据本地性，但是响应时间是优于DS算法的。

6 总结

如今新版的Hadoop支持作业调度的热插拔，使得对已有作业算法的改进成为可能。该文重点对Hadoop的作业调度算法进行了研究，分析了已有的调度算法，针对目前算法不能够很好的解决数据本地性和负载均衡的问题，在以后的公平份额调度算法的基础上进行了改进，并通过实验验证了改进后算法的性能。

参考文献

[1] 陈全，邓倩妮.易购环境下自适应的MapReduce调度[J].计算机工程与科学，2009，31（z1）：5.

[2] 张密密.MapReduce模型在Hadoop实现中的性能分析及改进优化[D].电子科技大学，2010

[3] 张青.网格环境下任务调度算法的应用研究[D].大连海事大学，2009.

因此现有的作业调度算法主要存在两个问题：没有实时的考虑系统的负载状况，不能获得良好的数据本地性。针对现有的算法不能实时的分析集群的负载状况，本算法提出了基于可变长度队列的公平调度算法（FSVQ）的设计，在设计算法的时候主要考虑两个原则：

1）自适应的负载调节。系统分析当前系统的负载状况，决定执行作业数的多少，而没有被执行的作业则放到等待队列中去。

2）在获得执行权限的作业，我们按照改进的公平调度算法去执行，通过采取等待的方式，使之获得良好的数据本地性。

FSVQ算法流程图如图1。

4.1满足负载均衡的设计

本算法设计两个队列，分别是作业执行队列和作业等待队列。Hadoop平台是通过主控节点接受心跳，感知空闲节点，从而给空闲节点分配任务。

定义1：单位时间内空闲节点的到达次数称为空闲节点率，记为λ。

定义2：该文把该阀值记为X，阀值的取值是管理员根据自己集群系统的状况，通过统计多次作业执行来确定。

过于频繁的改变作业执行队列的长度，不仅会浪费系统的资源，也会浪费作业执行的时间。该文在这里引入方差这个概念作为度量值。通过比较|λ-X|与方差的大小，决定是否改变作业执行队列的长度。

4.2满足数据本地性的设计及等待时间阀值T的数学模型求解

传统公平调度算法数据节点满足数据本地性很差，并不适合MapReduce的设计理念。在该算法中，设计了两个等待的时间w1和w2。在本文中只设计一个动态的等待时间的阀值以适应集群系统负载情况的变化，减少算法的执行时间，在本算法中，T由一个函数GetThreshhold（λ，K）实现。

该系统总共有M个计算节点，每个节点有L个作业槽，该系统中总共会有S=ML个作业槽。每个作业J会有N个任务。在分布式文件系统中，每个文件块的副本数为R。

任意时刻，假设作业J还有K个任务没有完成，那么对作业J来说，接下来如果有空闲节点到达，该空闲节点满足作业J的数据本地性的概率P为：P=1-（1-K/M）R。当前集群系统的空闲节点率为λ，则过了时间T后就会有λT个空闲节点到达。按照已经得出的满足作业J的概率P，可以得出，λT个空闲节点中能够满足J的数据本地性要求的节点有λT·[1-（1-K/M）R][≥][λ]T·（1-e-RK/M）。

要想T时间内等到满足数据本地性的节点，则在这段时间内，至少要有一个节点满足数据本地性，所以要满足公式：[λ]T·（1-e-RK/M） [≥]1。解这个不等式可以得出：

T[≥]1/ [λ]（1-e-RK/M）

5 实验及结果分析

搭建好实验平台之后，该文为了验证FSVQ算法的性能，主要分析数据本地性及算法的响应时间。该文把原始的公平调度算法称为FS算法，由facebook改进后的延迟调度算法称为DS算法。

为了验证高负载集群对算法性能的影响，可以通过安装trickle软件实现控制网络带宽。本实验一共执行4个字数统计的作业，各个作业的信息如表1所示：

5.1响应时间分析

在10M网络环境下，网络传输开销大，空闲节点率降低，FSVQ算法认为集群负载高，从而减少了作业执行队列的长度，表2是各个算法下的每个作业的响应时间：

从表中可看出，在执行作业2和作业3的过程中，由于FSVQ算法减少了一个执行作业，所以作业2和作业3的执行时间都优于DS算法，而作业4之前被移除出作业执行队列，造成了作业相应时间的延长。但是在总的响应时间上FSVQ算法比DS算法少了44s。

5.2 数据本地性分析

下图是各个作业分别用上述算法执行时的数据本地性表示。

从图2中可以看出FS算法由于没有采用延迟机制，造成各个作业的数据本地性很差，这也是用FS算法执行的作业响应时间长的重要原因。DS算法由于采用了两个等待时间，所以在数据本地性上略优于FSVQ算法，但也正是由于采用了两个等待时间，造成了DS算法响应时间长于FSVQ算法。

由以上数据本地性和响应时间综合分析可以得知，FSVQ算法在保证数据本地性的前提下确保了响应时间，相比DS算法，FSVQ算法略微牺牲了数据本地性，但是响应时间是优于DS算法的。

6 总结

如今新版的Hadoop支持作业调度的热插拔，使得对已有作业算法的改进成为可能。该文重点对Hadoop的作业调度算法进行了研究，分析了已有的调度算法，针对目前算法不能够很好的解决数据本地性和负载均衡的问题，在以后的公平份额调度算法的基础上进行了改进，并通过实验验证了改进后算法的性能。

参考文献

[1] 陈全，邓倩妮.易购环境下自适应的MapReduce调度[J].计算机工程与科学，2009，31（z1）：5.

[2] 张密密.MapReduce模型在Hadoop实现中的性能分析及改进优化[D].电子科技大学，2010

[3] 张青.网格环境下任务调度算法的应用研究[D].大连海事大学，2009.