本站原创
摘要： 随着信息和数据爆炸式增长，Hadoop等海量数据处理平台日益重要，作业调度算法是Hadoop集群的核心，本文对Hadoop集群默认的三种作业调度算法以及异构集群环境下的作业调度算法进行了系统的研究和对比，并提出了今后相关科研工作的重点。
Abstract： With the explosive growth of information and data，mass data processing platform such as Hadoop is more and more important. Job-scheduling algorithm is the core of Hadoop cluster.Three acquiescent job-scheduling algorithms of Hadoop cluster and the job-scheduling algorithm of heterogeneous cluster he been researched and compared.The key point of future research is proposed.
关键词： Hadoop集群；海量数据；作业调度
Key words： Hadoop cluster；mass data；job-scheduling
1006-4311（2013）07-0187-02
0 引言
Hadoop是一个能够对海量数据进行分布式处理的具有可靠性和可扩展性的存储与计算平台，其中作业调度算法是Hadoop集群的核心，一个好的调度算法可以提高整个集群的利用率和吞吐率。Hadoop中常用的作业调度算法包括FIFO算法、公平份额调度算法、计算能力调度算法，近来国内外广大科研工作积极投入相关的科研工作，从各个方面对整个集群整体性能的提高做出了积极的贡献。随着现代信息及数据的爆炸式增长，对Hadoop性能的要求也越来越高，所以如何设计一种高效的作业调度算法将是今后Hadoop研究工作的重点。
1.2 公平份额调度算法 公平份额调度算法（Fair Scheduler）是Facebook工程师们针对FIFO作业调度算法存在的问题提出的作业调度的新算法，旨在使MapReduce计算框架适应多用户共享同一平台，更好并行处理多种类型作业的需求。当系统中只有一个作业在执行时，它可以独占整个系统的资源，但是当有其它作业加入时，或者有多个作业时，那么JobTracker将重新进行调度，系统释放相应比例的TaskTracker，并把这些TaskTracker分配给新提交的作业，以保证所有作业都能平均分配到系统的资源。这样，如FIFO算法中的例子，Job2和Job3两个交互型短作业很快就能得到处理，同时Job1大型作业也能够得到执行，不至于长期处于饥饿状态。
在公平份额调度算法实际应用过程中，不管是作业池还是作业都被赋予了一定的权值，系统并以此为依据给予分配相应比例的资源。根据这种机制，虽然各作业池和作业在共享资源时不再是严格的平均分配，但是系统更合理地根据用户或者作业的重要程度及实际计算需求给予分配资源，提高系统的整体效率。
虽然上述算法能够保证各用户尽可能地公平共享系统资源，但是某些情况下为了能够确保特定的用户或者群组获得足够的共享资源，而又不会因此导致其它用户无法获得满足而无法执行，公平份额调度算法允许为作业池设定最小保障共享资源，这样既能确保特定的用户或者群组的需求，又能保证其它作业能够得到执行。另外，如果某些小作业执行所需资源小于最小保障共享资源，那么系统会将额外的部分公平分给其它作业池，进一步提高资源的利用率。
除了上述缺省方法，为了更合理地选择合适作业去执行，公平份额调度算法还定义了作业赤字作为选择依据。所谓作业赤字指一个作业在理想情况下应该获得的计算资源与实际获得的计算资源的差距，当有空闲的TaskTracker出现时，在确保各作业池获得最小保障资源的前提下，优先分配给赤字最高的作业使用。
综上所述，在实际应用过程中，公平份额调度算法首先根据作业赤字等因素确定各作业池及作业的权值，系统根据权值为各作业池设定最小保障共享资源，最后在限定各作业池最大运行作业数的前提下，根据最小保障共享资源及作业赤字等因素为各作业池分配资源并在执行过程中进行公平调度。它克服了FIFO算法资源利用率低的缺点，但是它只从用户及作业的角度来考虑问题，没有考虑当前系统各节点的负载水平及实际负载状态，导致节点实际负载不均，从而影响整个系统的性能。1.3 计算能力调度算法（Capacity Scheduling） 计算能力调度算法是Yahoo！工程师为克服FIFO算法的缺点而提出的作业调度算法，它提供了类似公平份额调度算法的功能，但在设计和实现上计算能力调度算法侧重作业队列的计算能力，而公平调度算法侧重的是作业能公平地共享资源。在公平调度算法中，系统为确保各用户能公平共享系统资源，为不同用户分配一个独立的作业池，而在计算能力调度算法的设计中，它直接针对作业，它定义了多个作业队列，每个队列分配一定量的TaskTracker，把每个作业队列模拟成一个具有特定计算能力的Hadoop集群资源。
计算能力调度算法作业运行时，多个作业队列独立进行，每个队列内部使用带优先权的FIFO调度算法，而每个队列之间虽然是独立进行，但又不完全独立，当已经被分配的资源尚处于空闲状态时，该资源将会被其它队列分享，当该队列中增加了作业压力时，则之前分享它空闲资源的队列在完成当前任务后把会把借来的资源配回给原队列。当系统出现空闲的TaskTracker时，算法会根据一定的标准选择合适的队列，这样，计算能力调度算法使得每个队列既独立又相互合作地进行共享系统资源，而不像公平调度算法一味强调各作业公平共享系统资源，进一步提高了资源的利用率。
在计算能力调度算法的具体实现中，最关键的仍然是如何选择合适的作业去执行。什么样的作业是最合适的作业呢？作业的执行除了需要TaskTracker还需要足够的空闲系统资源，两者缺一不可。因此，计算能力调度算法通过计算队列中正在运行的作业数与其分得的计算资源之间的比值是否最低来判断该队列是否是最适合的队列，即当有空闲的TaskTracker时，算法会选择一个具有最多空闲空间的队列。选择一个合适的队列之后，算法在队列内部采用带优先权的FIFO算法，空闲的TaskTracker就选择当前队列中具有最高优先权的作业去执行。
计算能力调度算法与公平调度算法一样克服了FIFO算法资源利用率低的缺点，它通过动态调整资源分配，支持多作业并行执行提高了资源的利用率及作业的执行率，但是计算能力调度算法中队列设置和队列选组无法自动进行，用户需要了解系统信息进而对作业进行队列设置及队列选组，在大型系统中，这将限制了系统整体性能的提高。
以上三种调度算法获得了Hadoop社区的广泛认可，是目前Hadoop平台默认的调度算法，但是这些方法主要针对同构集群计算资源，随着硬件的升级换代及云计算资源虚拟化，集群节点的异构性不可避免，即使在目前的同构环境下，也可能因为资源竞争或者资源分配不公平导致某些作业执行落后，这些情况下系统的整体性能将大大受到影响，因此开发一种适应异构集群环境的作业调度机制是非常必要的。
针对异构集群环境下重调度算法存在的问题，加州大学伯克利分校的研究小组设计了一种新的调度算法LATE（Longest Approximate Time to End）。由于在异构环境下执行进度不能准确反映作业是否真的落后，因此LATE算法对于执行进度落后于慢作业阈值（SlowTaskThreshold）的作业，还需要估算该作业还需要多久才能执行完成，即只有剩余时间最长的作业才是真正需要重新调度的落后作业。与此同时，算法在快节点上为其启动备份任务执行，以减少作业在异构环境下的总执行时间。
LATE算法采用最长剩余完成时间作为落后作业的判断标准较好地解决了上述异构集群环境下的性能问题，但仍然存在一些问题：①它检测设所有job的map任务和reduce任务内部各阶段比例不变，这种检测设是不合理的，对于不同的作业来说，Map函数的执行时间可能存在差别，固定的比例势必影响性能的提高；②LATE算法没有考虑重调度代价，当把慢作业调到快节点上执行时，会丢弃已执行的部分而重头开始执行，这种作法并一定能够真正缩短作业的执行时间。
针对LATE算法的问题，西安交通大学计算机系新型计算机研究所的相关研究课题组提出了基于历史信息的重调度优化算法H-LATE算法[4]。该算法根据执行进度不断修正Map任务和Reduce任务内部各子阶段所占的比例，并保证重新调度后，作业在快节点上的执行速度要比原节点快，且不会成为新的落后作业，一定程度上优化了LATE算法。
3 小结
目前的Hadoop集群都只使用了唯一的JobTracker进行作业调度，设计合理高效
参考文献：
Isard M，Budiu M，Yu Y，et al. Distributed Data-Parallel Programs from Sequential Building Blocks[A].Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007[C]，ACM，2007：59-72.
王峰.Hadoop集群作业的调度算法[J].程序员，2009，12.
[3]Edmund B， Nightingale E.B， Chen P，M，et al.Speculative execution in a distribute file system[A]. Proceedings of the twentieth ACM symposium on Operating systems principles[C].2005：191-205.
[4]曹海军.异构集群环境下Hadoop作业调度优化[J].计算机工程，2012（07）.
Abstract： With the explosive growth of information and data，mass data processing platform such as Hadoop is more and more important. Job-scheduling algorithm is the core of Hadoop cluster.Three acquiescent job-scheduling algorithms of Hadoop cluster and the job-scheduling algorithm of heterogeneous cluster he been researched and compared.The key point of future research is proposed.
关键词： Hadoop集群；海量数据；作业调度
Key words： Hadoop cluster；mass data；job-scheduling
1006-4311（2013）07-0187-02
0 引言
Hadoop是一个能够对海量数据进行分布式处理的具有可靠性和可扩展性的存储与计算平台，其中作业调度算法是Hadoop集群的核心，一个好的调度算法可以提高整个集群的利用率和吞吐率。Hadoop中常用的作业调度算法包括FIFO算法、公平份额调度算法、计算能力调度算法，近来国内外广大科研工作积极投入相关的科研工作，从各个方面对整个集群整体性能的提高做出了积极的贡献。随着现代信息及数据的爆炸式增长，对Hadoop性能的要求也越来越高，所以如何设计一种高效的作业调度算法将是今后Hadoop研究工作的重点。
1 当前Hadoop平台默认的三种作业调度算法
1.1 FIFO算法 FIFO（First In First Out）算法，即先进先出算法，这是Hadoop调度器默认的作业调度算法，用户的所有作业被提交到一个队列中，JobTracker结节根据作业提交时间的先后顺序来选择将被执行的作业，排在前面的作业执行完之后，后来的作业才能执行，该算法具有调度算法简单明了，容易实现，JobTra源于：免费论文www.udooo.com
cker调度开销小的优点，但是FIFO具有自身的局限性。在Hadoop平台的最早的MapReduce计算架构中，面对的基本都是单用户提交的大型批处理，所以FIFO主要是针对单用户单一类型作业而设计的。在面对多用户共享同一平台运行多类型作业时，FIFO算法无法识别不同用户不同作业间的需求差异，所以，随着用户数量及作业类型的增多，应用FIFO调度算法的平台往往会出现整体性能和系统资源利用率比较低的情况，严重影响到作业的执行效率。如果Job1是一个海量数据处理的大型作业，预计执行时间1小时，而Job2和Job3只是一个简单的交互型作业，预计执行时间均为1s，那么根据FIFO算法，Job2和Job3只能等3600s和3601s才能执行，这将大大降低了系统的整体效率及严重影响了用户的体验。因此，随着Hadoop平台的使用率越来越高及多用户共享同一平台运行多种类型作业的需求的不断增加，FIFO算法已经不能满足用户的需求，需要能适应新要求的作业调度算法。1.2 公平份额调度算法 公平份额调度算法（Fair Scheduler）是Facebook工程师们针对FIFO作业调度算法存在的问题提出的作业调度的新算法，旨在使MapReduce计算框架适应多用户共享同一平台，更好并行处理多种类型作业的需求。当系统中只有一个作业在执行时，它可以独占整个系统的资源，但是当有其它作业加入时，或者有多个作业时，那么JobTracker将重新进行调度，系统释放相应比例的TaskTracker，并把这些TaskTracker分配给新提交的作业，以保证所有作业都能平均分配到系统的资源。这样，如FIFO算法中的例子，Job2和Job3两个交互型短作业很快就能得到处理，同时Job1大型作业也能够得到执行，不至于长期处于饥饿状态。
在公平份额调度算法实际应用过程中，不管是作业池还是作业都被赋予了一定的权值，系统并以此为依据给予分配相应比例的资源。根据这种机制，虽然各作业池和作业在共享资源时不再是严格的平均分配，但是系统更合理地根据用户或者作业的重要程度及实际计算需求给予分配资源，提高系统的整体效率。
虽然上述算法能够保证各用户尽可能地公平共享系统资源，但是某些情况下为了能够确保特定的用户或者群组获得足够的共享资源，而又不会因此导致其它用户无法获得满足而无法执行，公平份额调度算法允许为作业池设定最小保障共享资源，这样既能确保特定的用户或者群组的需求，又能保证其它作业能够得到执行。另外，如果某些小作业执行所需资源小于最小保障共享资源，那么系统会将额外的部分公平分给其它作业池，进一步提高资源的利用率。
除了上述缺省方法，为了更合理地选择合适作业去执行，公平份额调度算法还定义了作业赤字作为选择依据。所谓作业赤字指一个作业在理想情况下应该获得的计算资源与实际获得的计算资源的差距，当有空闲的TaskTracker出现时，在确保各作业池获得最小保障资源的前提下，优先分配给赤字最高的作业使用。
综上所述，在实际应用过程中，公平份额调度算法首先根据作业赤字等因素确定各作业池及作业的权值，系统根据权值为各作业池设定最小保障共享资源，最后在限定各作业池最大运行作业数的前提下，根据最小保障共享资源及作业赤字等因素为各作业池分配资源并在执行过程中进行公平调度。它克服了FIFO算法资源利用率低的缺点，但是它只从用户及作业的角度来考虑问题，没有考虑当前系统各节点的负载水平及实际负载状态，导致节点实际负载不均，从而影响整个系统的性能。1.3 计算能力调度算法（Capacity Scheduling） 计算能力调度算法是Yahoo！工程师为克服FIFO算法的缺点而提出的作业调度算法，它提供了类似公平份额调度算法的功能，但在设计和实现上计算能力调度算法侧重作业队列的计算能力，而公平调度算法侧重的是作业能公平地共享资源。在公平调度算法中，系统为确保各用户能公平共享系统资源，为不同用户分配一个独立的作业池，而在计算能力调度算法的设计中，它直接针对作业，它定义了多个作业队列，每个队列分配一定量的TaskTracker，把每个作业队列模拟成一个具有特定计算能力的Hadoop集群资源。
计算能力调度算法作业运行时，多个作业队列独立进行，每个队列内部使用带优先权的FIFO调度算法，而每个队列之间虽然是独立进行，但又不完全独立，当已经被分配的资源尚处于空闲状态时，该资源将会被其它队列分享，当该队列中增加了作业压力时，则之前分享它空闲资源的队列在完成当前任务后把会把借来的资源配回给原队列。当系统出现空闲的TaskTracker时，算法会根据一定的标准选择合适的队列，这样，计算能力调度算法使得每个队列既独立又相互合作地进行共享系统资源，而不像公平调度算法一味强调各作业公平共享系统资源，进一步提高了资源的利用率。
在计算能力调度算法的具体实现中，最关键的仍然是如何选择合适的作业去执行。什么样的作业是最合适的作业呢？作业的执行除了需要TaskTracker还需要足够的空闲系统资源，两者缺一不可。因此，计算能力调度算法通过计算队列中正在运行的作业数与其分得的计算资源之间的比值是否最低来判断该队列是否是最适合的队列，即当有空闲的TaskTracker时，算法会选择一个具有最多空闲空间的队列。选择一个合适的队列之后，算法在队列内部采用带优先权的FIFO算法，空闲的TaskTracker就选择当前队列中具有最高优先权的作业去执行。
计算能力调度算法与公平调度算法一样克服了FIFO算法资源利用率低的缺点，它通过动态调整资源分配，支持多作业并行执行提高了资源的利用率及作业的执行率，但是计算能力调度算法中队列设置和队列选组无法自动进行，用户需要了解系统信息进而对作业进行队列设置及队列选组，在大型系统中，这将限制了系统整体性能的提高。
以上三种调度算法获得了Hadoop社区的广泛认可，是目前Hadoop平台默认的调度算法，但是这些方法主要针对同构集群计算资源，随着硬件的升级换代及云计算资源虚拟化，集群节点的异构性不可避免，即使在目前的同构环境下，也可能因为资源竞争或者资源分配不公平导致某些作业执行落后，这些情况下系统的整体性能将大大受到影响，因此开发一种适应异构集群环境的作业调度机制是非常必要的。
2 异构集群环境下的作业调度算法
在缺省情况下，Hadoop采用了一种投机执行策略（Speculative Execution）[3]的重调度机制，在执行过程中，通过计算每个作业的执行进度，及时发现执行落后的作业，对它进行重调度。这种方法可以适当缓解由于某些作业落后而造成的性能下降问题，但是该重调度算法在异构集群环境下效率低下，仍然不能较好解决上述问题。针对异构集群环境下重调度算法存在的问题，加州大学伯克利分校的研究小组设计了一种新的调度算法LATE（Longest Approximate Time to End）。由于在异构环境下执行进度不能准确反映作业是否真的落后，因此LATE算法对于执行进度落后于慢作业阈值（SlowTaskThreshold）的作业，还需要估算该作业还需要多久才能执行完成，即只有剩余时间最长的作业才是真正需要重新调度的落后作业。与此同时，算法在快节点上为其启动备份任务执行，以减少作业在异构环境下的总执行时间。
LATE算法采用最长剩余完成时间作为落后作业的判断标准较好地解决了上述异构集群环境下的性能问题，但仍然存在一些问题：①它检测设所有job的map任务和reduce任务内部各阶段比例不变，这种检测设是不合理的，对于不同的作业来说，Map函数的执行时间可能存在差别，固定的比例势必影响性能的提高；②LATE算法没有考虑重调度代价，当把慢作业调到快节点上执行时，会丢弃已执行的部分而重头开始执行，这种作法并一定能够真正缩短作业的执行时间。
针对LATE算法的问题，西安交通大学计算机系新型计算机研究所的相关研究课题组提出了基于历史信息的重调度优化算法H-LATE算法[4]。该算法根据执行进度不断修正Map任务和Reduce任务内部各子阶段所占的比例，并保证重新调度后，作业在快节点上的执行速度要比原节点快，且不会成为新的落后作业，一定程度上优化了LATE算法。
3 小结
目前的Hadoop集群都只使用了唯一的JobTracker进行作业调度，设计合理高效
源于：论文网www.udooo.com
的作业调度算法虽然能很大程度上提高系统的整体性能，但是大量用户提交的大量作业及大规模TaskTracker分布必将给JobTracker带来繁重的工作压力，而且作业调度算法的实现无疑也给系统带来了很大的系统开销，这也是为什么FIFO算法始终没有被遗弃的原因。这样，随着作业量的不断增大，JobTracker的效率反而成为制约系统性能提高的因素，而且一旦JobTracker节点失效或者宕机，那么整个集群也将完全瘫痪，因此怎样解决这个问题，进一步提高系统的性能，将是广大科研工作者今后开展工作的重点。参考文献：
Isard M，Budiu M，Yu Y，et al. Distributed Data-Parallel Programs from Sequential Building Blocks[A].Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007[C]，ACM，2007：59-72.
王峰.Hadoop集群作业的调度算法[J].程序员，2009，12.
[3]Edmund B， Nightingale E.B， Chen P，M，et al.Speculative execution in a distribute file system[A]. Proceedings of the twentieth ACM symposium on Operating systems principles[C].2005：191-205.
[4]曹海军.异构集群环境下Hadoop作业调度优化[J].计算机工程，2012（07）.