论文部分内容阅读
摘要：Hadoop作为MapReduce的开源实现被越来越多的企业使用。但是当Hadoop集群中出现较多的小作业时，使用其内置的调度算法就会降低整个系统的吞吐率[1]。该文针对这个不足，提出了基于公平调度的延时调度算法。通过设定一定的延时来保证数据的本地性，实验结果表明改进的调度算法可以提高整个系统的吞吐率。
关键词：公平调度；延时分配；MapReduce；Hadoop
中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)01-0166-03
Hadoop Cluster of Fair Scheduling Lgorithms to Improve and Achieve
LI Xin, ZHANG Peng
( Xi’an University of Architecture and Technology, Xi’an 710055, China)
Abstract: Hadoop is increasingly using for enterprises as an open source implantation of MapReduce. But when Hadoop clusters occur more small job, using its built-in scheduling will reduce the overall system throughput. In this paper, put forward a delay scheduling algorithm base on fair scheduling aiming at its defect. By setting a delay to ensure the local nature of the data. Experimental results show that the new scheduling algorithm can improve overall system throughput.
Key words: fair scheduling; delay scheduling; MapReduce; Hadoop
作业调度算法是一个集群的核心[2]，一个好的调度算法可以提高整个集群的利用率和吞吐率。Hadoop其自身就带有一种简单的作业调度算法，为了满足各种不同类型的复杂作业的调度，又有一些新的调度算法被以插件的形式集成到Hadoop中去[3,4]，使用比较多的有公平调度算法(Fair Scheduling)和计算能力调度算法(Capacity Schedule)。但是针对系统从在较多小左的情况，目前上面提出的这两种新的调度算法并不能保证系统较高的吞吐率。针对由小作业引起的吞吐率下降，采用一种作业延时分配的策略可以有效的解决这个问题[1,5]。
1 Hadoop现有的作业调度算法分析
1.1 MapReduce简介
MapReduce是由Google发明的一种处理大规模数据的分布式编程框架，最初是由Google的工程师设计并实现。Hadoop是Ma? pReduee计算模型的一种开源实现，用于大规模数据集的并行化分析处理。Hadoop由Hadoop MapReduce和HDFS(Hadoop Distribut? ed File System)组成。HDFS提供了一个集群范围内的全局文件访问机制。Hadoop中的作业调度是Job Tracker指派任务(Tasks)到相应Task Tracker上执行的过程。下面对Hadoop中的调度算法进行介绍和分析。
1.2 Hadoop默认调度策略
最早的Hadoop Map/Reduce计算架构中，Job Tracker在进行作业调度时使用的是FIFO(First In First Out)算法。所有用户的作业都被提交到一个队列中，然后由Job Tracker先按照作业的优先级高低，再按照作业提交时间的先后顺序选择将被执行的作业。FIFO算法的优点是简单明了，Job Tracker工作负担轻。但是缺点也很突出，该算法主要是忽略了不同作业的需求差异。基于FIFO的缺点，新的调度算法被提出，分别是计算能力调度算法(Fail Scheduling)和公平调度算法(Capacity Schedule)。当前，新的调度器已经作为插件的形式集成在Hadoop框架当中。
1.3计算能力调度算法
计算能力调度算法是由Yahoo提出的一种调度算法。其核心思想就是为每一个作业队列定义一个指标，该指标是队列中正在运行的作业数与其应该分得的计算资源(配置文件中为此队列分配了相应数量的资源，而实际中该队列可能没有分配到)之间的比值。当系统中出现空闲的Task Tracker，算法会首先选择一个该比值最低的队列。
队列被选中后，将按照作业优先级(如果支持的话)和提交时间顺序选择执行的作业。在选择作业的时候，还需要考虑作业所属的用户是否已经超出了他所能使用的资源限制。此外，还会考虑Task Tracker内存资源是否满足作业的要求。
1.4公平调度算法
公平调度算法是由Facebook提出的一种调度算法。公平调度是一种赋予作业(Job)资源的方法，它的目的是让所有的作业随着时间的推移，都能平均的获取等同的共享资源。当单独一个作业在运行时，它将使用整个集群。当有其它作业被提交上来时，系统会将任务(Task)空闲时间片(Slot)赋给这些新的作业，以使得每一个作业都大概获取到等量的CPU时间。
公平调度器按资源池(Pool)来组织作业，并把资源公平的分到这些资源池里。默认情况下，每一个用户拥有一个独立的资源池，以使每个用户都能获得一份等同的集群资源而不管他们提交了多少作业。
公平调度器还可以限制每用户和每资源池的并发运行作业数量。当一个用户必须一次性提交数百个作业时，或当大量作业并发执行时，用来确保中间数据不会塞满集群上的磁盘空间，这是很有用的。设置作业限制会使超出限制的作业被列入调度器的队列中进行等待，直到一些用户/资源池的早期作业运行完毕。系统会根据作业优先权和提交时间的排列来运行每个用户/资源池中的作业。
2延时调度(Delay Scheduling)
2.1公平调度算法吞吐率分析
公平调度算法可以让有多用户提交的作业在一定的时间内都能平均的获取等同的共享资源。本文通过实验发现，当出现较多小作业时，整个集群的吞吐率就会出现明显的下降，分析原因发现，是由于作业数据的本地性所造成的。集群对于数据的计算采用移动计算比移动数据更划算，换句话说就是要把计算放在离数据比较近的节点。由于集合中网络的传输速度是不同的，数据传输速度最快的是在本节点之内，紧接是在本机架内，最慢是在不同的机架之间。所以为了提高整个集群的吞吐率，就要提高数据的本地性，尽量让数据在本节点或本机架内运算。下面分析一下为什么较多的小作业会导致数据的本地性变差。
由于小作业占用资源池的资源比较小，集群当中很容易出现空闲的资源池满足小作业的需求，所以当一个小作业按照最小共享额度的公平调度算法被调度到队列的头部时，就会很快出现满足条件的资源，而这个满座条件的资源不是本节点的概率会很高，而且跟集群的大小有直接关系，当集群较小时，这个概率会较小，当集群很大时，这个概率也会很大。由于这个原因从而导致当小作业较多时，整个集群的吞吐率就会出现明显的下降。为了解决小作业的调度问题，本文提出了基于公平调度算法的延时调度算法(DSFS, Delay Scheduling Base on Fail Scheduling)。
2.2基于公平调度的延时调度
当一个小作业按照公平调度算法被调度到队列的头部时，此时会等待满足条件的资源，在有节点释放空闲资源池时，调度队列头部用户池的作业就会判断此空闲资源是否满足节点本地性，如果满足本地性，就立即分配资源，否则就继续等待满足条件的本节点所释放的资源，等待时间为T1，如果超过时间T1，就会继续等待满足条件的本机架所释放的空闲资源，等待时间为T2。如果超过时间T2还没有分配到资源，就会在第一时间获取到其他节点所释放的空闲资源(这里的其他节点可能是本节点的，也可能是本机架的，也有可能是其他节点的)。其中等待时间，T2>T1，这两个时间可以自由的由用户自己在配置文件当中定义。具体的算法如下：
初始化作业队列JobList
if节点n发送心跳信号到master then
if节点n释放了空闲池then
for作业J=JobList.get(i), 0 =< i < JobList.size(), i
if作业J有一个在节点n上的节点本地性任务then
立即执行此任务
else if作业J.wait < T1then
继续等待
else if作业T1< J.wait < T2then
if作业J有一个在节点n所在机架的任务then立即执行此任务
else继续等待
end if
else if作业J.wait > T2
立即执行此任务
end if
end for
end if
end if
2.3延时调度算法吞吐率分析
在有很多作业运行且各节点之间负载均衡时，当一个作业无法提交本地作业时，调度队列后面也可能会有符合数据本地性的作业，故延时调度对系统的吞吐率的提高是有利的。
Hadoop分布式文件系统(HDFS)在进行数据的存储时是考虑了数据在整个集群分布的均衡性的。但不排除在一些情况下会出 现多个调度队列中的作业都等待在同一个节点上执行作业。如果这多个待执行作业在性能特性上相似(如都为计算型作业)，那么延时调度对吞吐率几乎没有影响。
为了进一步提高系统的吞吐率，可以根据作业的性能特性采用不同的调度策略，针对计算型作业可以调度它到本机架内的节点上执行，I/O型作业可以调度到具有节点本地性的节点上执行。同样数据大小的输入数据，I/O型作业需要花费更多的时间去读取数据，需要较高的数据带宽，而计算型作业的主要时间花费在计算上从而可以边计算边进行数据的读取，对数据带宽要求相对较低。
3实验
3.1实验环境
整个集群共由9台普通PC机组成，其中1台作为主控制节点，另外8台是工作节点。我们将工作节点分为2组，每组4台PC机构成一个机柜，在同一个机柜内的工作节点通过全双工1Gbps以太网卡与CiscoSD208 1Gbps交换机相连接，连接两个机柜的是一个千兆路由器。在集群中的每台计算机都是Dell OptiPlex 780的PC机，配置2G内存，CPU配置为Intel酷睿2双核E7500，硬盘为7200转的SCSI硬盘。每台机器上都装有相同的RHEL5作为操作系统。
3.2 I/O型数据节点本地性实验
本实验采用文本搜索进行I/O型实验，因为文本搜索主要是扫描整个文本，搜索到匹配值输出，输出结果是非常小的，且集群绝大部分时间是在进行数据读取和扫描操作，主要受限于硬盘的I/O速度。对不同的作业规模试验结果如图1所示。
通过上面的数据分析可以看出，当系统有较多小作业时，DSFS算法可以有效地减少作业的完成时间，从而提高系统的吞吐率。
4结束语
MapReduce计算模型已经被越来越多的企业的支持和应用。由于MapReduce集群的昂贵硬件成本和其上的许多应用都使得多用户共享集群变得更加必要。集群的共享，就要求集群调度器能够实现公平性和效率的均衡。公平调度算法可以很好的保证公平性，但小作业调度数据本地性差的问题，明显的降低了整个集群的吞吐率。本文通过延时调度可以极大改善数据本地性的问题，甚至可以达到几乎100%的节点本地性，实验证明延时调度对整个集群的平均吞吐率有明显的提高。
参考文献:
[1]张密密.MapReduce模型在Hadoop实现中的性能分析及改进优化[D].电子科技大学,2010.
[2]张青.网格环境下任务调度算法的应用研究[D].大连海事大学,2009.
[3]陈全,邓倩妮.异构环境下自适应的Map-Reduce调度[J].计算机工程与科学,2009,31(z1):5.
[4]王凯,吴泉源,杨树强.一种多用户MapReduce集群的作业调度算法的设计与实现[J].计算机与现代化,2010(10).
[5]开华东,田琪.基于MapReduce集群的加权公平队列调度算法研究[J].电脑知识与技术,2011,7(9).
[6]王峰.Hadoop集群作业的调度算法[J].程序员,2009(12).
[7]周锋,李旭伟.一种改进的MapReduce并行编程模型[J].科协论坛(下半月),2009(02).
[8]孙广中,肖锋,熊曦.MapReduce模型的调度及容错机制研究[J].微电子学与计算机,2007(09).
[9] Dean Jeffrey. MapReduce:simplified data processing on large clusters[C].Communications of the ACM, 2008 :107-113 .
[10] Ranger C,Raghuraman R,Penmetsa A,et al. Evaluating Map Reduce for Multi-core and Multiprocessor Systems[C].Pro-ceedings of the 13th Symposium on High-Performance Computer Architecture (HPCA). 2007:13-24 .
[11] Apache. Apache hadoop .http://hadoop.apache.org/core/.
关键词：公平调度；延时分配；MapReduce；Hadoop
中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)01-0166-03
Hadoop Cluster of Fair Scheduling Lgorithms to Improve and Achieve
LI Xin, ZHANG Peng
( Xi’an University of Architecture and Technology, Xi’an 710055, China)
Abstract: Hadoop is increasingly using for enterprises as an open source implantation of MapReduce. But when Hadoop clusters occur more small job, using its built-in scheduling will reduce the overall system throughput. In this paper, put forward a delay scheduling algorithm base on fair scheduling aiming at its defect. By setting a delay to ensure the local nature of the data. Experimental results show that the new scheduling algorithm can improve overall system throughput.
Key words: fair scheduling; delay scheduling; MapReduce; Hadoop
作业调度算法是一个集群的核心[2]，一个好的调度算法可以提高整个集群的利用率和吞吐率。Hadoop其自身就带有一种简单的作业调度算法，为了满足各种不同类型的复杂作业的调度，又有一些新的调度算法被以插件的形式集成到Hadoop中去[3,4]，使用比较多的有公平调度算法(Fair Scheduling)和计算能力调度算法(Capacity Schedule)。但是针对系统从在较多小左的情况，目前上面提出的这两种新的调度算法并不能保证系统较高的吞吐率。针对由小作业引起的吞吐率下降，采用一种作业延时分配的策略可以有效的解决这个问题[1,5]。
1 Hadoop现有的作业调度算法分析
1.1 MapReduce简介
MapReduce是由Google发明的一种处理大规模数据的分布式编程框架，最初是由Google的工程师设计并实现。Hadoop是Ma? pReduee计算模型的一种开源实现，用于大规模数据集的并行化分析处理。Hadoop由Hadoop MapReduce和HDFS(Hadoop Distribut? ed File System)组成。HDFS提供了一个集群范围内的全局文件访问机制。Hadoop中的作业调度是Job Tracker指派任务(Tasks)到相应Task Tracker上执行的过程。下面对Hadoop中的调度算法进行介绍和分析。
1.2 Hadoop默认调度策略
最早的Hadoop Map/Reduce计算架构中，Job Tracker在进行作业调度时使用的是FIFO(First In First Out)算法。所有用户的作业都被提交到一个队列中，然后由Job Tracker先按照作业的优先级高低，再按照作业提交时间的先后顺序选择将被执行的作业。FIFO算法的优点是简单明了，Job Tracker工作负担轻。但是缺点也很突出，该算法主要是忽略了不同作业的需求差异。基于FIFO的缺点，新的调度算法被提出，分别是计算能力调度算法(Fail Scheduling)和公平调度算法(Capacity Schedule)。当前，新的调度器已经作为插件的形式集成在Hadoop框架当中。
1.3计算能力调度算法
计算能力调度算法是由Yahoo提出的一种调度算法。其核心思想就是为每一个作业队列定义一个指标，该指标是队列中正在运行的作业数与其应该分得的计算资源(配置文件中为此队列分配了相应数量的资源，而实际中该队列可能没有分配到)之间的比值。当系统中出现空闲的Task Tracker，算法会首先选择一个该比值最低的队列。
队列被选中后，将按照作业优先级(如果支持的话)和提交时间顺序选择执行的作业。在选择作业的时候，还需要考虑作业所属的用户是否已经超出了他所能使用的资源限制。此外，还会考虑Task Tracker内存资源是否满足作业的要求。
1.4公平调度算法
公平调度算法是由Facebook提出的一种调度算法。公平调度是一种赋予作业(Job)资源的方法，它的目的是让所有的作业随着时间的推移，都能平均的获取等同的共享资源。当单独一个作业在运行时，它将使用整个集群。当有其它作业被提交上来时，系统会将任务(Task)空闲时间片(Slot)赋给这些新的作业，以使得每一个作业都大概获取到等量的CPU时间。
公平调度器按资源池(Pool)来组织作业，并把资源公平的分到这些资源池里。默认情况下，每一个用户拥有一个独立的资源池，以使每个用户都能获得一份等同的集群资源而不管他们提交了多少作业。
公平调度器还可以限制每用户和每资源池的并发运行作业数量。当一个用户必须一次性提交数百个作业时，或当大量作业并发执行时，用来确保中间数据不会塞满集群上的磁盘空间，这是很有用的。设置作业限制会使超出限制的作业被列入调度器的队列中进行等待，直到一些用户/资源池的早期作业运行完毕。系统会根据作业优先权和提交时间的排列来运行每个用户/资源池中的作业。
2延时调度(Delay Scheduling)
2.1公平调度算法吞吐率分析
公平调度算法可以让有多用户提交的作业在一定的时间内都能平均的获取等同的共享资源。本文通过实验发现，当出现较多小作业时，整个集群的吞吐率就会出现明显的下降，分析原因发现，是由于作业数据的本地性所造成的。集群对于数据的计算采用移动计算比移动数据更划算，换句话说就是要把计算放在离数据比较近的节点。由于集合中网络的传输速度是不同的，数据传输速度最快的是在本节点之内，紧接是在本机架内，最慢是在不同的机架之间。所以为了提高整个集群的吞吐率，就要提高数据的本地性，尽量让数据在本节点或本机架内运算。下面分析一下为什么较多的小作业会导致数据的本地性变差。
由于小作业占用资源池的资源比较小，集群当中很容易出现空闲的资源池满足小作业的需求，所以当一个小作业按照最小共享额度的公平调度算法被调度到队列的头部时，就会很快出现满足条件的资源，而这个满座条件的资源不是本节点的概率会很高，而且跟集群的大小有直接关系，当集群较小时，这个概率会较小，当集群很大时，这个概率也会很大。由于这个原因从而导致当小作业较多时，整个集群的吞吐率就会出现明显的下降。为了解决小作业的调度问题，本文提出了基于公平调度算法的延时调度算法(DSFS, Delay Scheduling Base on Fail Scheduling)。
2.2基于公平调度的延时调度
当一个小作业按照公平调度算法被调度到队列的头部时，此时会等待满足条件的资源，在有节点释放空闲资源池时，调度队列头部用户池的作业就会判断此空闲资源是否满足节点本地性，如果满足本地性，就立即分配资源，否则就继续等待满足条件的本节点所释放的资源，等待时间为T1，如果超过时间T1，就会继续等待满足条件的本机架所释放的空闲资源，等待时间为T2。如果超过时间T2还没有分配到资源，就会在第一时间获取到其他节点所释放的空闲资源(这里的其他节点可能是本节点的，也可能是本机架的，也有可能是其他节点的)。其中等待时间，T2>T1，这两个时间可以自由的由用户自己在配置文件当中定义。具体的算法如下：
初始化作业队列JobList
if节点n发送心跳信号到master then
if节点n释放了空闲池then
for作业J=JobList.get(i), 0 =< i < JobList.size(), i
if作业J有一个在节点n上的节点本地性任务then
立即执行此任务
else if作业J.wait < T1then
继续等待
else if作业T1< J.wait < T2then
if作业J有一个在节点n所在机架的任务then立即执行此任务
else继续等待
end if
else if作业J.wait > T2
立即执行此任务
end if
end for
end if
end if
2.3延时调度算法吞吐率分析
在有很多作业运行且各节点之间负载均衡时，当一个作业无法提交本地作业时，调度队列后面也可能会有符合数据本地性的作业，故延时调度对系统的吞吐率的提高是有利的。
Hadoop分布式文件系统(HDFS)在进行数据的存储时是考虑了数据在整个集群分布的均衡性的。但不排除在一些情况下会出 现多个调度队列中的作业都等待在同一个节点上执行作业。如果这多个待执行作业在性能特性上相似(如都为计算型作业)，那么延时调度对吞吐率几乎没有影响。
为了进一步提高系统的吞吐率，可以根据作业的性能特性采用不同的调度策略，针对计算型作业可以调度它到本机架内的节点上执行，I/O型作业可以调度到具有节点本地性的节点上执行。同样数据大小的输入数据，I/O型作业需要花费更多的时间去读取数据，需要较高的数据带宽，而计算型作业的主要时间花费在计算上从而可以边计算边进行数据的读取，对数据带宽要求相对较低。
3实验
3.1实验环境
整个集群共由9台普通PC机组成，其中1台作为主控制节点，另外8台是工作节点。我们将工作节点分为2组，每组4台PC机构成一个机柜，在同一个机柜内的工作节点通过全双工1Gbps以太网卡与CiscoSD208 1Gbps交换机相连接，连接两个机柜的是一个千兆路由器。在集群中的每台计算机都是Dell OptiPlex 780的PC机，配置2G内存，CPU配置为Intel酷睿2双核E7500，硬盘为7200转的SCSI硬盘。每台机器上都装有相同的RHEL5作为操作系统。
3.2 I/O型数据节点本地性实验
本实验采用文本搜索进行I/O型实验，因为文本搜索主要是扫描整个文本，搜索到匹配值输出，输出结果是非常小的，且集群绝大部分时间是在进行数据读取和扫描操作，主要受限于硬盘的I/O速度。对不同的作业规模试验结果如图1所示。
通过上面的数据分析可以看出，当系统有较多小作业时，DSFS算法可以有效地减少作业的完成时间，从而提高系统的吞吐率。
4结束语
MapReduce计算模型已经被越来越多的企业的支持和应用。由于MapReduce集群的昂贵硬件成本和其上的许多应用都使得多用户共享集群变得更加必要。集群的共享，就要求集群调度器能够实现公平性和效率的均衡。公平调度算法可以很好的保证公平性，但小作业调度数据本地性差的问题，明显的降低了整个集群的吞吐率。本文通过延时调度可以极大改善数据本地性的问题，甚至可以达到几乎100%的节点本地性，实验证明延时调度对整个集群的平均吞吐率有明显的提高。
参考文献:
[1]张密密.MapReduce模型在Hadoop实现中的性能分析及改进优化[D].电子科技大学,2010.
[2]张青.网格环境下任务调度算法的应用研究[D].大连海事大学,2009.
[3]陈全,邓倩妮.异构环境下自适应的Map-Reduce调度[J].计算机工程与科学,2009,31(z1):5.
[4]王凯,吴泉源,杨树强.一种多用户MapReduce集群的作业调度算法的设计与实现[J].计算机与现代化,2010(10).
[5]开华东,田琪.基于MapReduce集群的加权公平队列调度算法研究[J].电脑知识与技术,2011,7(9).
[6]王峰.Hadoop集群作业的调度算法[J].程序员,2009(12).
[7]周锋,李旭伟.一种改进的MapReduce并行编程模型[J].科协论坛(下半月),2009(02).
[8]孙广中,肖锋,熊曦.MapReduce模型的调度及容错机制研究[J].微电子学与计算机,2007(09).
[9] Dean Jeffrey. MapReduce:simplified data processing on large clusters[C].Communications of the ACM, 2008 :107-113 .
[10] Ranger C,Raghuraman R,Penmetsa A,et al. Evaluating Map Reduce for Multi-core and Multiprocessor Systems[C].Pro-ceedings of the 13th Symposium on High-Performance Computer Architecture (HPCA). 2007:13-24 .
[11] Apache. Apache hadoop .http://hadoop.apache.org/core/.