论文部分内容阅读
【摘 要】本文分析了先入先出调度算法（FIFO）、公平调度算法（Fair-Scheduler）以及计算能力调度算法（Capacity Scheduler）的优缺点，并针对 Hadoop 的调度算法问题，提出了一种基于预期效用的Hadoop作业调度算法，详细叙述了该算法的原理和实现过程。最后对该算法编程验证，实验结果表明，其在调度时间方面的性能有了明显的改进。
【关键词】云计算 Hadoop 任务调度
近年来云计算技术取得了长足发展，大量的云计算系统投入使用，实际中绝大多数的云计算系统采用Hadoop平台来作为基础平台。作业调度技术在Hadoop系统中作为核心技术之一，其技术直接关系到Hadoop系统的运行性能，改进现有调度算法的不足之处，对提高Hadoop系统具有重要的意义。
一、三种作业调度算法
Hadoop现有的作业调度算法包括默认的FIFO调度算法，Facebook公司开发的公平調度算法以及Yahoo公司开发的计算能力调度算法。在FIFO的实现中，使用了一个单独的队列，TaskTracker总是将新任务追加到就绪队列的末端。该FIFO算法是容易实现，且调度开销要小于整个群集。但该算法无视不同用户以及不同任务间的需求差异，系统会阻止低优先级的任务执行，由于优先级抢占的情况不被FIFO算法所支持，这就使得平台系统的整体性能和资源利用率不高，影响了执行这些任务。
公平调度算法（Fair Scheduler）的目标是能够并行执行的多种作业在MapReduced的计算框架中能够灵活应对[1]。其想法是尽可能的以确保所有的作业都是能够获得相同量的资源。由于其支持分类的任务调度，资源分配可以充分的在不同任务间进行分配，使得服务质量得到提高，系统资源充分利用[2]。它克服了简单的FIFO算法资源利用低和不支持任务抢占的缺点，但它不考虑每个节点当前的实际负载状态，导致负载不均衡的情况发生，从而影响到整个系统的响应时间。在实际应用中，系统的性能还极大的受到算法配置文件优劣的影响。
计算能力调度算法与公平调度算法虽在功能上很类似，但还是有很多特别之处。计算能力调度支持多个作业队列，用户提交的作业直接添加到队列中。为了提升其资源利用效率，每个队列会共享已分配但处于闲置状态的资源。在配置文件中配置相应的参数，为队列分配相应的资源数量，可以使得为各个队列完成Map/Reduce的各种操作。计算能力调度算法虽然克服了FIFO算法简单以及资源利用率低的特点，而且它支持多任务并行执行，但是计算能力调度算法中队列设置无法自动进行，需要了解系统信息才能对作业进行队列选组和队列设置，在很多大型商业系统中，这可能成为提高系统性能的瓶颈。
二、基于预期效用的作业调度算法
针对前面调度算法的一些不足，我们提出了基于预期效用的作业调度算法。此算法要求在作业进入系统执行以前且作业已经被提交到作业等待服务队列中去时，进行作业的预先判断。在作业队列中通过作业分类机制，对作业的当前特征和所需要占用的系统的资源情况等进行分析，以此判断作业是否能够被系统接受并处理。根据当前作业被接受或者拒绝的概率作为判断依据，在候选的作业中要选择被成功接受的概率大于不被成功接受的概率的作业去执行。通过作业的预期效用计算值来判断被接收或者拒绝，被选择成为将要执行的作业就是那个计算得出的预期效用值最大的作业。
在基于预期效用的作业调度算法设计过程中，所有提交到系统的相关作业将使用任务槽来完成存储或者计算任务，这些Map和Reduce任务槽是由云计算系统平台来指定的。每个作业都可以在执行过程中去预估计它的资源耗费的情况，例如内存的占用，CPU时间占用的长短以及预算量的大小等；对节点上的评估也是这样，也包括内存大小、带宽大小、磁盘数量、CPU速度及数量等节点特征，通过这些特征可以得知节点资源的占用情况；合理的调度与分配资源，可以平衡的让作业分享系统服务，避免大作业长时间占用资源，而小作业长时间得不到系统的服务[3]。
在进行作业选择调度的时候，根据预期效用的假设理论，我们一般按照式（1）来选择作业：
在上式（1）中是作业在系统指定的效用函数值，此值需要一定时间的积累和调整。是作业在分类器处理过后，作业被成功接受的概率，此值要受资源消耗状况的影响，主要包括了CPU、内存以及IO的占用情况等，F是综合描述作业特征。其算法的流程如图1所示。
预期效用函数计算出来的值将直接决定作业是否被系统所调度执行，在此效用计算过程中先计算与作业相关的概率值，它的含义是在集群环境下作业被成功调度的概率，是综合描述作业特的征。由此，有如下公式：
上式（2）是基于预期效用的Hadoop作业调度算法的理论基础，总体思路是在进行下一次作业的调度决策前，先要分析上次的作业调度运行的相关数值。为使调度尽量达到最优的状态，就要不断的追踪上次所做的决定，修正下次的决策，通过先验概率计算出可能产生的相关结果。其中也是可以计算的，因为是代表资源耗费情况的预计值，是在作业提交之前的设定值，也就可以当作常数。概率在作业调度算法决策过程中，先要进行分析比较这两个概率值，然后选择被成功接受概率值最大的值作为候选作业进行判断处理，而不符合要求的作业会被系统拒绝进行调度；通过这种设计的作业分类器将作业进行适当的分类—可能不被成功调度的作业和可能被成功调度的作业两类，在可能成功的作业队列中计算相应的作业预期效用值，从中选择预期效用值最大的作业进行调度执行。通过如下的公式计算作业的预期效用值，
在公式（3）中，为作业的预期效用值，为其作业效用函数。在选定作业进入调度序列执行后，如何去判断作业是否被成功调用呢，这就需要制定作业评判的标准。我们将作业任务节点执行的情况定为调度是否合适的评判指标。在节点反馈的信息中，通过一些集群信息参数来为节点上的资源消耗设定一个阀值。当作业执行过程中，如果反馈回来的节点信息这一阀值，就可以认为作业调度不合理，节点负载过重。集群参数列表如表格1所示。 在计算得出被成功调用的分类作业效用值后，就选择执行预期效用值最大的作业进行调度。如果来自作业的节点心跳信息的资源使用状况没有超过阀值，可认为调度决策是成功的，否则就是失败的；如果决策是失败的话，需要对预期效用值进行重新分析，对相关参数进行修改。
三、算法验证
该算法的具体实现是在已有的Hadoop提供的API接口基础之上进行的程序开发。实验环境为Ubuntu9.04、JDK1.6、Hadoop0.20；节点数量设置为4个，1个为NameNode，其他为计算节点。在实验中搭建好hadoop的计算环境集群，将用户作业分别提交到系统中进行处理。配置数据块的副本数量为5个，HDFS数据块的大小为64M，以及TaskTracker上心跳信息的反馈时间间隔为4秒等。实验中提交了三种作业，分别是在50G的数据文件中统计某个单词出现的频率；对100M数据中的键/值对进行一次平方运算；在本地服务器上对200M數据进行FTP上传下载100次。每次作业运行完成之后得到处理时间的数据，实验的结果如图2所示。
从图2中可以得出，基于预期效用的作业调度算法在处理作业的时间响应性方面大多数时候要优于FIFO算法以及公平调度算法，和计算能力调度算法的处理时间相当。刚开始时基于预期效用的调度算法所花费的时间较多，随着运算次数的增加，调度所花时间逐渐减少。
四、结论
在处理相同作业队列时，FIFO算法所消耗的时间最多，由于其未充分考虑了资源的使用情况，故调度算法实现起来比较简单。公平算法和计算能力调度算法在算法的设计上比FIFO复杂些，但是如果其参数设置不合理，也可能造成消耗时间比较多。随着时间的推移，基于预期效用的调度算法处理作业的时间会越来越少，直至达到稳定的状态。FIFO算法，公平算法以及计算能力算法在预先参数配置不恰当的情况之下其作业处理的响应时间将会受到影响，并且在以后的作业调度过程中不会被纠正，基于预期效用的调度算法则允许初始配置不合理，允许犯错，在后续的作业调度过程中，不断的去修改配置参数，使得系统的处理能力达到一个越来越优的状态。
参考文献：
[1] Fair Scheduler for Hadoop[EB/OL].Hadoop.apache.org/common/docs/current/Fair_scheduler.html， 2010-04-15
[2] 姜淼，Hadoop云平台下调度算法的研究[D]，吉林大学通信工程学院，2012-06
[3] Shvachko k，KUANG Hai-rong，Radia S，etal.The Hadoop Distributed File System[J].MSST，2010.1
作者简介：
方刚（1976—），男，四川，硕士研究生，主要研究领域为应用软件和云计算技术。
【关键词】云计算 Hadoop 任务调度
近年来云计算技术取得了长足发展，大量的云计算系统投入使用，实际中绝大多数的云计算系统采用Hadoop平台来作为基础平台。作业调度技术在Hadoop系统中作为核心技术之一，其技术直接关系到Hadoop系统的运行性能，改进现有调度算法的不足之处，对提高Hadoop系统具有重要的意义。
一、三种作业调度算法
Hadoop现有的作业调度算法包括默认的FIFO调度算法，Facebook公司开发的公平調度算法以及Yahoo公司开发的计算能力调度算法。在FIFO的实现中，使用了一个单独的队列，TaskTracker总是将新任务追加到就绪队列的末端。该FIFO算法是容易实现，且调度开销要小于整个群集。但该算法无视不同用户以及不同任务间的需求差异，系统会阻止低优先级的任务执行，由于优先级抢占的情况不被FIFO算法所支持，这就使得平台系统的整体性能和资源利用率不高，影响了执行这些任务。
公平调度算法（Fair Scheduler）的目标是能够并行执行的多种作业在MapReduced的计算框架中能够灵活应对[1]。其想法是尽可能的以确保所有的作业都是能够获得相同量的资源。由于其支持分类的任务调度，资源分配可以充分的在不同任务间进行分配，使得服务质量得到提高，系统资源充分利用[2]。它克服了简单的FIFO算法资源利用低和不支持任务抢占的缺点，但它不考虑每个节点当前的实际负载状态，导致负载不均衡的情况发生，从而影响到整个系统的响应时间。在实际应用中，系统的性能还极大的受到算法配置文件优劣的影响。
计算能力调度算法与公平调度算法虽在功能上很类似，但还是有很多特别之处。计算能力调度支持多个作业队列，用户提交的作业直接添加到队列中。为了提升其资源利用效率，每个队列会共享已分配但处于闲置状态的资源。在配置文件中配置相应的参数，为队列分配相应的资源数量，可以使得为各个队列完成Map/Reduce的各种操作。计算能力调度算法虽然克服了FIFO算法简单以及资源利用率低的特点，而且它支持多任务并行执行，但是计算能力调度算法中队列设置无法自动进行，需要了解系统信息才能对作业进行队列选组和队列设置，在很多大型商业系统中，这可能成为提高系统性能的瓶颈。
二、基于预期效用的作业调度算法
针对前面调度算法的一些不足，我们提出了基于预期效用的作业调度算法。此算法要求在作业进入系统执行以前且作业已经被提交到作业等待服务队列中去时，进行作业的预先判断。在作业队列中通过作业分类机制，对作业的当前特征和所需要占用的系统的资源情况等进行分析，以此判断作业是否能够被系统接受并处理。根据当前作业被接受或者拒绝的概率作为判断依据，在候选的作业中要选择被成功接受的概率大于不被成功接受的概率的作业去执行。通过作业的预期效用计算值来判断被接收或者拒绝，被选择成为将要执行的作业就是那个计算得出的预期效用值最大的作业。
在基于预期效用的作业调度算法设计过程中，所有提交到系统的相关作业将使用任务槽来完成存储或者计算任务，这些Map和Reduce任务槽是由云计算系统平台来指定的。每个作业都可以在执行过程中去预估计它的资源耗费的情况，例如内存的占用，CPU时间占用的长短以及预算量的大小等；对节点上的评估也是这样，也包括内存大小、带宽大小、磁盘数量、CPU速度及数量等节点特征，通过这些特征可以得知节点资源的占用情况；合理的调度与分配资源，可以平衡的让作业分享系统服务，避免大作业长时间占用资源，而小作业长时间得不到系统的服务[3]。
在进行作业选择调度的时候，根据预期效用的假设理论，我们一般按照式（1）来选择作业：
在上式（1）中是作业在系统指定的效用函数值，此值需要一定时间的积累和调整。是作业在分类器处理过后，作业被成功接受的概率，此值要受资源消耗状况的影响，主要包括了CPU、内存以及IO的占用情况等，F是综合描述作业特征。其算法的流程如图1所示。
预期效用函数计算出来的值将直接决定作业是否被系统所调度执行，在此效用计算过程中先计算与作业相关的概率值，它的含义是在集群环境下作业被成功调度的概率，是综合描述作业特的征。由此，有如下公式：
上式（2）是基于预期效用的Hadoop作业调度算法的理论基础，总体思路是在进行下一次作业的调度决策前，先要分析上次的作业调度运行的相关数值。为使调度尽量达到最优的状态，就要不断的追踪上次所做的决定，修正下次的决策，通过先验概率计算出可能产生的相关结果。其中也是可以计算的，因为是代表资源耗费情况的预计值，是在作业提交之前的设定值，也就可以当作常数。概率在作业调度算法决策过程中，先要进行分析比较这两个概率值，然后选择被成功接受概率值最大的值作为候选作业进行判断处理，而不符合要求的作业会被系统拒绝进行调度；通过这种设计的作业分类器将作业进行适当的分类—可能不被成功调度的作业和可能被成功调度的作业两类，在可能成功的作业队列中计算相应的作业预期效用值，从中选择预期效用值最大的作业进行调度执行。通过如下的公式计算作业的预期效用值，
在公式（3）中，为作业的预期效用值，为其作业效用函数。在选定作业进入调度序列执行后，如何去判断作业是否被成功调用呢，这就需要制定作业评判的标准。我们将作业任务节点执行的情况定为调度是否合适的评判指标。在节点反馈的信息中，通过一些集群信息参数来为节点上的资源消耗设定一个阀值。当作业执行过程中，如果反馈回来的节点信息这一阀值，就可以认为作业调度不合理，节点负载过重。集群参数列表如表格1所示。 在计算得出被成功调用的分类作业效用值后，就选择执行预期效用值最大的作业进行调度。如果来自作业的节点心跳信息的资源使用状况没有超过阀值，可认为调度决策是成功的，否则就是失败的；如果决策是失败的话，需要对预期效用值进行重新分析，对相关参数进行修改。
三、算法验证
该算法的具体实现是在已有的Hadoop提供的API接口基础之上进行的程序开发。实验环境为Ubuntu9.04、JDK1.6、Hadoop0.20；节点数量设置为4个，1个为NameNode，其他为计算节点。在实验中搭建好hadoop的计算环境集群，将用户作业分别提交到系统中进行处理。配置数据块的副本数量为5个，HDFS数据块的大小为64M，以及TaskTracker上心跳信息的反馈时间间隔为4秒等。实验中提交了三种作业，分别是在50G的数据文件中统计某个单词出现的频率；对100M数据中的键/值对进行一次平方运算；在本地服务器上对200M數据进行FTP上传下载100次。每次作业运行完成之后得到处理时间的数据，实验的结果如图2所示。
从图2中可以得出，基于预期效用的作业调度算法在处理作业的时间响应性方面大多数时候要优于FIFO算法以及公平调度算法，和计算能力调度算法的处理时间相当。刚开始时基于预期效用的调度算法所花费的时间较多，随着运算次数的增加，调度所花时间逐渐减少。
四、结论
在处理相同作业队列时，FIFO算法所消耗的时间最多，由于其未充分考虑了资源的使用情况，故调度算法实现起来比较简单。公平算法和计算能力调度算法在算法的设计上比FIFO复杂些，但是如果其参数设置不合理，也可能造成消耗时间比较多。随着时间的推移，基于预期效用的调度算法处理作业的时间会越来越少，直至达到稳定的状态。FIFO算法，公平算法以及计算能力算法在预先参数配置不恰当的情况之下其作业处理的响应时间将会受到影响，并且在以后的作业调度过程中不会被纠正，基于预期效用的调度算法则允许初始配置不合理，允许犯错，在后续的作业调度过程中，不断的去修改配置参数，使得系统的处理能力达到一个越来越优的状态。
参考文献：
[1] Fair Scheduler for Hadoop[EB/OL].Hadoop.apache.org/common/docs/current/Fair_scheduler.html， 2010-04-15
[2] 姜淼，Hadoop云平台下调度算法的研究[D]，吉林大学通信工程学院，2012-06
[3] Shvachko k，KUANG Hai-rong，Radia S，etal.The Hadoop Distributed File System[J].MSST，2010.1
作者简介：
方刚（1976—），男，四川，硕士研究生，主要研究领域为应用软件和云计算技术。