Hadoop 现在几乎已经成为业界在大数据上事实的标准，越来越多的企业开始采用hadoop进行数据的存储及处理。既然涉及数据处理，一个不可不提的术语就是“作业” or “job”，大量的作业必然要引入作业管理及调度，hadoop也不能例外。
传统企业中的调度工具，不管像是简单crontab，或者企业级的如control-M，很容易注意到，他们都主要考虑的是将作业分配到集群中的某一台，或者其中某几台上面运行。但是像hadoop 这种大规模分布式计算的集群，考虑都不足。通常Hadoop整个集群是作为一个整体对外服务，考虑的是集群整体资源利用的最大化，HDFS的多副本策略使得集群某一单独节点运行是否正常不再重要，hadoop的一个重要理念是移动计算而不是数据，所以hadoop会尽量在数据存储的节点进行运算，而传统调度工具需要支持这些特点就需要进行大量的改造，本文只讨论传统调度工具如何与hadoop内置调度器更好结合。作业监控部分则不在本文讨论范围内。
hadoop 的内置调度机制
在 2008 年以前，集成在 JobTracker 中的原有调度算法仅有 FIFO。在 FIFO 调度中，JobTracker 从工作队列中拉取作业，最老的作业最先。当hadoop最初出现的时候，主要是设计用来进行大型的批处理例如网页索引，日志挖掘，用户将任务提交至队列，而后集群按照提交的先后顺序执行即可，FIFO也足够用了。然后，当越来越多的数据放在hadoop集群后，另一个问题出现了，人们开始希望在多个用户间共享集群。而此时Hadoop 只支持与 JobTracker 逻辑混合在一起的单一调度器。
于是2008年5月18日有人提交了一个Improvement的issue 。HADOOP-3412 (Refactor the scheduler out of the JobTracker )，调度器从jobtracker的代码中分离出来，调度器变成可插入式的，在JobTracker中加载和调用，用户可以在配置文件mapred-site.xml中的mapred.jobtracker.taskScheduler属性中指定自己的调度器。
当前Hadoop自带的调度器随着hadoop版本的不同会略有区别，但是最常见的三种调度器，分别是FIFO（默认调度器），Capacity Scheduler （容量调度器）和FairScheduler（公平调度器）以下逐一介绍其算法及其适用场景：
1. FIFO
1.1 简介
FIFO(First In First Out)算法。所有用户的作业都被提交到一个队列中，然后由JobTracker按照作业提交时间的先后顺序选择将被执行的作业。 在hadoop的后期版本中,增加了优先级处理功能,可以通过设置mapred.job.priority属性 或者在JobClient 调用 setJobPriority() 方法来进行优先级设置(优先级可以设置为 VERY_HIGH, HIGH, NORMAL, LOW, VERY_LOW), Job scheduler在选择下一运行作业时,会选择一个最高优先级的作业，而后再根据提交时间排序,但是由于FIFO调度器不支持抢占，所以一个高优先级作业仍然可能被一个长期运行的低优先级作业所阻塞。FIFO不考虑各种作业资源需求的不同。
FIFO 是hadoop的默认调度器。
1.2 与传统调度工具的集成
FIFO方式适用于单系统，单用户的hadoop集群，作业提交给hadoop集群时一般需要传递的参数只有优先级
调度平台改造部分：
1）增加作业类型：map-reduce，hive，sqoop 。使得作业的命令行可以在调度平台中配置产生。
2）将作业的优先级转换成为hadoop标准（VERY_HIGH, HIGH, NORMAL, LOW, VERY_LOW), 并在想hadoop集群提交作业时同时设置作业优先级。
优先级设置的方法有以下两种
#1：作业源码中调用API JobConf.setJobPriority(JobPriority.NORMAL)
#2：在执行的时候在命令行中添加以下参数 -D mapred.job.priority=HIGH
实际调度中通常会由调度平台动态生成命令行的方式进行。
2.Capacity Scheduler
2.1 简介
CapacityScheduler 是Yahoo开发并捐献的，容量调度器是设计目标是让hadoop应用程序真正成为一个共享的，多租户的集群，并且使得集群的吞吐量和利用率最大化。说的有点绕口，咱们细说下容量调度器的来龙去脉。
传统上企业中每个系统都会有自己的私有服务器用来保证自己的系统在高峰情况，或者接近高峰情况下也能达到预设的SLA，而这样基本上都会导致很差的资源平均利用率，并且企业内众多的独立集群也带来更大的管理成本。
在企业内共享大规模的hadoop集群使得我们可以更加高效，低成本的使用计算资源，但是人们总是担心使用共享集群的话，如果其他系统占用了大量资源的话将会使得他们自己的应用在需要的时候无法获取足够的资源以致应用无法达到预定的SLA.
而容量调度器正是设计用来共享一个大规模的集群，并给予每个系统性能保证。中心思想是各系统按照自己计算的需要，共同投资一个hadoop集群，集群中的可用资源在各系统中分享。这样的集群有个附加的好处是单个系统可以利用别的系统的闲置计算资源进行计算，使得资源的利用更加弹性及高效。
而在各系统间共享集群就必须使系统对多租户( multi-tenancy)设计有很强的支持，因为必须给予每个系统性能保证。并且要确保集群在遇到一个异常的应用/用户/数据集等也不受影响。CapacityScheduler提供一系列严格的限制来确保一个应用/用户/队列不能消耗不恰当的集群资源，同时CapacityScheduler还限制了一个单一的用户/队列可以初始化/等待的应用程序数量来确保集群的公平使用和稳定性。
利用闲置资源有个问题，大部分的系统是一个大的项目群，里面有众多的子系统，他们希望闲置资源优先用于满足同一项目群内子系统的需求，如仍有剩余再共享给其他系统使用，[MAPREDUCE-824]提出了层次队列（hierarchical queues ）的概念，资源优先在子队列中共享，如还有剩余再共享给其他队列。此功能在0.21.0版本中实现。
2.2 特性
以下是Apache Hadoop 2.0.2-alpha官方文档中的特性说明，很官方，很权威。
层次队列-层次队列的支持可以确保资源在一个系统的子队列中共享，而后才允许其他队列使用空闲资源，使得资源分配更加可控及可预测。
性能保证-各个队列只分配了集群的一小部分性能，这样只有部分容量供队列进行处置。所有提交进同一个队列的应用程序都可以访问队列所分配的容量，管理员可以给每一个队列配置软性的限制或者硬性限制。
安全-每个队列都有严格的访问控制列表（ACLs） ，可以控制那个用户可以提交进入哪个队列，同时也有安全机制来保证用户不能查看 and/or 修改其他用户的程序，同样也支持按队列/按系统的管理角色。
弹性-空闲的资源可以分配给其他超过其处理容量的队列。如果将来某一个时刻先前空闲的队列再次需要这些资源，在这些资源所分配到的任务完成后，空闲资源会被重新分配给先前空闲的队列（不支持抢占）这样保证了资源以一种可预期，弹性的方式分配给队列。这个还能同时防止人为的资源孤岛，提高了集群的使用率。
多租户-提供了多种的限制来保证一个单应用/用户/队列独占队列或者集群，避免集群不堪重负。
易维护– 1）配置可动态加载，队列的定义及属性可以在运行时改变，可以将对晕乎的影响降到最低，同时也提供控制台接口可以让用户或者管理员查看当前系统中各个队列的资源分配情况，管理员可以在运行时增加队列，但是注意不能在运行时删除。2），清空队列，管理员可以在运行时停止一个队列，队列处于停止状态时已经在队列中的作业会继续完成，但是不能往里再新增作业
基于资源的调度 – 支持一些资源密集的作业，作业可以指定一个高于默认值的资源需求量，进而可以满足作业的不同的资源需求，当前，资源内存仅支持内存
上面的看起来有的复杂，还需要了解的几个很重要的特性是：
支持多用户多队列，支持多系统多用户共享集群
单个队列是FIFO调度方式，队列内可以开启优先级控制功能（优先级控制默认是关闭状态）。
支持资源共享，队列内资源有剩余时，可共享给其他缺资源的队列。
当某个tasktracker上出现空闲slot时，调度器的调度策略是，先选择资源利用率（numSlotsOccupied/capacity）低的队列，然后在队列中考虑FIFO和优先级进行作业选择，选择的时候会判断做业所在的用户资源未超限，以及有足够内存满足作业的内存需求。
计算能力调度器调度job时会考虑作业的内存限制，为了满足某些特殊job的特殊内存需求，可能会为该job分配多个slot；例如一个slot是1G内存，一个需要2G内存的程序就会被分配2个slot。fifo及公平调度器不具备此功能。
2.3 配置实例
2.4 与传统调度工具的集成
增加作业类型及优先级的需求同章节1.2，此外还需要进行队列配置
1）在调度平台上新增hadoop队列配置，配置好队列，及队列的资源限制后，可以使用调度工具指定作业在某一队列中运行。
map-reduce作业：可以在作业代码中设置代码属于的队列 conf.setQueueName(“queue1”);
或者在执行的时候在命令行中添加以下参数 -D mapred.job.queue.name=queue1
hive:在执行hive任务时，设置hive属于的队列,例如queue1:
set mapred.job.queue.name=queue1;
2）设置作业的内存资源量
通过设置一下两个属性，可以设置每个task所需要的内存量，如有必要，调度器会为每个task可以申请多个slot以获取根多内存，但最大值不超过mapred.cluster.max.map.memory.mb及mapred.cluster.max.map.memory.mb ，可以将值设置为-1以禁用此功能。
mapred.job.reduce.memory.mb
mapred.job.map.memory.mb
请注意：tasktracker需要先设置
mapred.tasktracker.vmem.reserved,
mapred.task.default.maxvmem，
mapred.task.default.maxvmem，以启用内存监控功能。
3.Fair Scheduler
3.1 简介
公平调度器是由facebook贡献的，适合于多用户共享集群的环境的调度器.
公平调度器在设计时有以下4个主要目标：
1）即使在与大作业共享集群的时候也能迅速的完成小作业。不像Hadoop默认的FIFO调度器，公平调度器可以在大作业运行时让小作业的执行也能取得执行进展，同时又不会使大作业处于资源“饥饿”状态。
2）在一个共享集群里，可以同时运行一些实验性的作业同时对集群中的生产作业提供可靠的SLA。
3）便于管理及配置，程序在遇到一些异常情况的时候也能做出合适的处理，用户也仅在他们需要一些高级功能的时候才需要进行配置。
4）支持在运行时进行重配置，而不需要重启集群。
公平调度器按资源池（pool）来组织作业，并把资源公平的分到这些资源池里。默认情况下，每一个用户拥有一个独立的资源池，以使每个用户都能获得一份等同的集群资源而不管他们提交了多少作业。按用户的 Unix 群组或作业配置（jobconf）属性来设置作业的资源池也是可以的。在每一个资源池内，会使用公平共享（fair sharing）的方法在运行作业之间共享容量（capacity）。用户也可以给予资源池相应的权重，以不按比例的方式共享集群。
除了提供公平共享方法外，公平调度器允许赋给资源池保证（guaranteed）最小共享资源，这个用在确保特定用户、群组或生产应用程序总能获取到足够的资源时是很有用的。当一个资源池包含作业时，它至少能获取到它的最小共享资源，但是当资源池不完全需要它所拥有的保证共享资源时，额外的部分会在其它资源池间进行切分。
3.2 特性
公平调度器的主要特性如下：
支持多用户多队列
资源公平共享（公平共享量由优先级决定）
保证最小共享量
支持时间片抢占
限制作业并发量，以防止中间数据塞满磁盘
3.2.1 Pools
公平调度器将作业分为‘pools’，而后在pool间公平的共享资源，每个pool内可以使用FIFO或者公平共享（fair sharing）的方式进行调度。作业在哪个pool由一个Jobconf 属性决定，“pool name property”默认取mapreduce.job.user.name，所以是每个用户一个pool，但是也可以取其他属性，例如group.name,这样就可以每个unix 组一个group。
一个通常使用的方法是把pool名称设为一个未使用的属性名，例如pool.name，而后将此值默认设为mapreduce.job.user.name，这样既可以让每个用户一个pool，也可以通过直接设置pool.name 将作业制定到一个特殊的pool。以下是一个mapred-site.xml中进行配置的简单示例：
<property>
<name>mapred.fairscheduler.poolnameproperty</name>
<value>pool.name</value>
</property>
<property>
<name>pool.name</name>
<value>${mapreduce.job.user.name}</value>
</property>
3.2.2 最小份额
通常情况下，活动的pool（内有作业的）会在集群中平分map和reduce的slots，但是也可以对指定的pool设置一个最小的map和reduce的slot的份额。这样pool在活动时就会给予指定的slot数量，即便公平份额是小于指定的份额。这样设置以后在非生产作业与生产作业共享hadoop集群的时候对保证生产作业的SLA非常有用。最小份额的设置有以下3个影响
1）pool的公平份额会大于等于其设置的最小份额，slot会冲其他pool的份额中取缺额以达到pool预设份额，有个例外是如果每个活动pool的最小份额加起来大于集群中全部slot的数量，如果遇到这种情况，每个pool中的份额都会成比例的缩小。
2）少于其最小份额的pool会在slot有空闲时最先获得slot。
3）可以给pool设置一个抢占超时（preemption timeout）属性，如果获得的slot不足最小份额，允许其杀死其他作业的task来获得slot，带抢占的最小份额实际使用起来有点像SLA。
请注意，如果一个pool不是活动的，其最小份额并不会被预留，slot会分配给其他pools。
3.2.3 抢占
就像上一小节说到的那样，调度器会将一个pool中作业的task杀死一边满足另一个pool的最小份额，我们把这样的动作成为抢占，准确的说这个称为最小份额抢占（min share preemption），因为还有一个类型的抢占称为公平份额抢占（fair share preemption），如果pool间slot份额未公平共享，也自动会将作业的task杀死以公平分配slot。公平份额的抢占远比最小份额抢占保守，因为未获得公平份额的作业通产是一些非生产的作业，可以容忍一定程度的不公平，公平份额抢占只有在一个pool只获得低于一半的公平份额，并且达到一个预设的抢占超时后才会发生，这个超时通常会设置的比较高（例如10分钟）
两种抢占调度器都会从过度调度的pools中杀死最近启动的一个task，以使抢占导致的资源浪费降到最低。
3.2.4 运行作业限制
公平调度器可以限制每个pool，每个用户可以并行运行的作业。这样就可以有效限制集群上产生的中间文件，作业根据提交时间和优先级运行，如果提交的作业超过限制则会等到正在运行的作业完成后再调起。
3.2.5 作业优先级
在pool内，无论pool内的调度模式是FIFO还是公平共享（fair sharing）都可以使用优先级来控制作业调度。
1）在FIFO的pools中，作业使用hadoop的默认调度器FIFO,首先根据优先级，而后根据提交时间排序决定下一调起作业。
2）在公平共享的pools中，作业优先级被用来设置作业的权重以控制作业所得到的slot份额，普通优先级的权重是1.0，每个优先级级别间权重为上一级别的两倍。例如一个高优先级的权重为2.0，这样他就得到普通优先级两倍的slot份额。
3.2.6 pool 权重
pool可以赋予权重以使集群中的资源不公平的共享。例如一个权重设为2.0的pool得到一个设为1.0的pool的两倍的份额。
3.2.7 延迟调度
公平调度器包含一个延迟调度的算法以提高数据的本地性。hadoop的一个重要理念是移动计算而非移动数据，计算尽量在存储数据的节点上运行，但是公平调度的算法是总是将slot分配给份额比较少的pool中的第一个作业，这就引起作业的数据本地性很差，需要通过网络将数据传输到本地。 1）如果队列头的作业是一个小作业，那么在集群的一个心跳期间接受到的数据就是作业所需的本地数据的几率会很低，从而如果我们总是将slot分配给队列头作业的话，小作业的本地性就会很差。
2）公平调度器有个很强的趋势是给作业分配刚刚完成task的slot，因为当一个task完成，作业就低于其公平份额，
延迟调度算法可以暂时的牺牲公平性来提高数据的本地性，如果队列头的任务无法在tasktracker中进行一个本地任务，他会发出心跳，并且跳过，这样其他的运行作业就会根据pool份额和pool内的调度规则来寻找一个可以运行本地task的作业，但是如果队列头的作业等待的了足够长的时间，他就会允许在数据同一机架的服务器上调去，如果再有足够长的时间，就会允许在不同机架上调起。这个延迟的时间被称为本地延迟（locality delays），通常只延迟几秒就已经足够答复提供数据的本地性。本地延迟在mapred-site.xml中设置，可以设置为0表示禁用。默认值设为1.5倍心跳时间。
3.2.8 管理
公平调度器包含一个web界面可以显示活动pools，作业和其公平公平份额，将作业在pool间移动或者改变作业的优先级。同时，作业的配置文件在被改变时会自动重新加载以便在运行状态下自动重配置。
3.2.9 调度算法
公平分享的一个简单的实现方式就是，无论何时一个slot空闲下来，就将其分配到运行task数最少的那个pool，这样就保证了各个pool间获得相等的slots，除非pool的需求少于其公平份额，那多余的slots就会在其他pool间平分。一下两个特性让公平调度器的算法更加复杂
1） Pool权重意味着某些pool会获得根多的slots，例如一个权重为2的pool获得的slots就会比一个权重为1多两倍，这个通过把调度算法改为将slot分配到runningTasks/Weight 最小的pool来实现。
2）最小份额意味着少于其最小份额的pool会最先得到slots，当我们把pools排序来选择下一个调度的pool时候，我们将少于其最小份额的pool放在大于其最小份额的pool前面，而那些小于其最小份额的pool通过其少于最小份额的比例进行排序。
公平调度器采用一个层次的调度来分配tasks，首选根据如上策略选择一个pool来分配task，而后pool内通过fifo或者fair sharing 来进行作业的内部调度。
3.2.10 fair share 计算
最后再说一下pool的公平共享量的计算方法。公平共享量是基于最小共享量和共享资源量计算得到的，它反映的是某个pool经过资源共享（某些pool的资源用不了，会自动共享给其他pool）之后，一共可以获取的资源总量，一般会大于等于最小共享量。
如果每个pool没有配置最小共享量，且提交了无限量的作业，则让每个pool的slotsAssigned / weight值相同即可。（其中slotsAssgined表示分配给该pool的slot数，weight表示pool的权重）。
而有了最小共享量minShare和pool中的需求量demand（该pool中所有作业尚需的slot总数）后，计算公平共享量fairShare需注意以下两种情况：
（1） 某些pool中的最小共享量可能用不完
（2） 给配给某些pool的资源量小于其最小共享量
考虑到以上两种情况，调度器设计了基于比率R的公平资源分配方法（设集群中资源总量为totalSlots）：
[1] 如果一个pool的demand<R*weight，则该pool的fairShare=demand
[2] 如果一个pool的minShare>weight，则该pool的fairShare=minShare
[3] 除此之外，所有pool的fairShare=R*weight
[4] 所有pool的的fairShare之和应为totalSlots
通过以上算法计算出的公平共享量即为“公平调度器”的“公平”含义之所在，应尽量保证每个pool获取的资源量为fairshare，如果一定时间期限内达不到，则抢占资源。
r的算法详见下图：
3.3 与传统调度工具的集成
集成上与2.4节类似，调度服务器通过使用不同的操作系统用户调起作业进入合适的pool。
参考资料
——————————————————————————————————
【1】 Hadoop 中的调度
【2】Refactor the scheduler out of the JobTracker
【3】如何编写Hadoop调度器
【4】Hadoop MapReduce Next Generation – Capacity Scheduler
【5】（MAPREDUCE-824）Support a hierarchy of queues in the capacity scheduler
【6】Hadoop-0.21.0公平调度器算法解析
