Hadoop公平调度器算法解析
1. 目的
本文描述了Hadoop中的公平调度的实现算法，公平调度器是由facebook贡献的，适合于多用户共享集群的环境的调度器，其吞吐率高于FIFO，论文参见参考资料[1]。本文分析的Hadoop版本是0.20.2，在新版本（0.21.0）中，公平调度算法已经有了改进与增强。本文组织结构如下：1）目的 2）公平调度介绍 3）公平调度算法分析 4）新版hadoop中公平调度器的新特性 5）参考资料。
2. 公平调度介绍
公平调度器按资源池（pool）来组织作业，并把资源公平的分到这些资源池里。默认情况下，每一个用户拥有一个独立的资源池，以使每个用户都能获得一份等同的集群资源而不管他们提交了多少作业。按用户的 Unix 群组或作业配置（jobconf）属性来设置作业的资源池也是可以的。在每一个资源池内，会使用公平共享（fair sharing）的方法在运行作业之间共享容量（capacity）。用户也可以给予资源池相应的权重，以不按比例的方式共享集群。
除了提供公平共享方法外，公平调度器允许赋给资源池保证（guaranteed）最小共享资源，这个用在确保特定用户、群组或生产应用程序总能获取到足够的资源时是很有用的。当一个资源池包含作业时，它至少能获取到它的最小共享资源，但是当资源池不完全需要它所拥有的保证共享资源时，额外的部分会在其它资源池间进行切分。
主要特点如下：
Ø 支持多用户多队列
Ø 资源公平共享（公平共享量由优先级决定）
Ø 保证最小共享量
Ø 支持时间片抢占
Ø 限制作业并发量，以防止中间数据塞满磁盘
3. 公平调度算法分析
3.1 变量定义
Ø 描述job信息的变量(JobInfo)
jobWeight：作业的权重。实际计算时，map阶段和reduce阶段分开，分别记为mapWeight，reduceWeight
jobDeficit：作业的缺额，即作业在理想调度器上所应得的计算时间与实际所获得的计算时间的缺额，这个是测量作业的“不公平”待遇的度量标准。实际运算时将map阶段和reduce阶段分开，分别记为mapDeficit和reduceDeficit。
runningTasks：作业正在运行的task数。实际计算时，map task和reduce task需分开，分别记为：runningMaps和runningReduces
minSlots：作业在相应的pool中的最小slot保证量，实际计算时，map阶段和reduce阶段分开，分别记为：minMaps和minReduces
jobFairShare：上次更新给该job分配的公平共享量，实际计算时，map阶段和reduce阶段分开，分别记为mapFairShare和reduceFairShare
Ø 计算过程的中间变量
poolWeight：pool的权重，这个可由用户自己设定，默认为1。
tasksNum：某个作业正在运行任务与尚未运行的任务（包括Speculative 任务）数量和，有两种task类型：map task和reduce task，计算时需要分开
priorityFactor：与作业优先级相关的因子，用于计算作业的权重，具体如下：
| priority | priorityFactor |
| VERY_HIGH | 4.0 |
| HIGH | 2.0 |
| NORMAL | 1.0 |
| LOW | 0.5 |
| Default | 0.25 |
poolRunningJobsWeightSum：pool中已经开始运行的所有作业的权重之和
poolLowJobsWeightSum：在某个pool中，已经开始运行的，但尚需slot（tasksNum数量大于其最小共享量）的那些作业权重之和
systemJobsWeightSum：系统（可能有很多pool）中可以运行的所有作业的权重之和
timeDelta：两次信息更新的时间间隔
3.2 相关算法
当出现一个空闲slot时，公平调度器会将此slot分配给缺额最大的作业。系统每隔500毫秒（UPDATE_INTERVAL）更新一次信息（有一个专门的更新线程对job信息进行更新），包括：作业缺额（作业的其他属性，如权重、最小共享量、公平共享量等，均是为计算缺额服务的）、权重、最小共享量、公平共享量等。
1) 作业权重计算方法
（1）默认情况下，权重是基于作业优先权的，但也可以基于作业的大小和年龄。权重的计算方法如下：
（2）根据优先权计算权重：
（3）根据用户自定义的weightAdjuster类调整权重
2) 更新权重
每个已经运行的作业权重更新公式：
3) 初始缺额计算
每个作业的初始缺额mapDeficit，reduceDeficit设置为0。
4) 更新作业的最小共享量
在每个pool中，将其拥有的slot按作业的权重分配给各个作业（由步骤（1）完成），分完之后将剩余的slot按作业的权重和缺额分配给仍需slot的作业（由步骤（2）和（3）完成），如果还有slot剩余，则将这些slot共享给其他pool。
初始化：
当前所有作业的最小共享量置零；
pool的minMaps数或者minReduces数（由用户在配置文件中设定）
重复以下几步，直到slotsLeft=0：
（1）计算每个job的最小共享量：jobinfo.minMaps或jobinfo.minReduces
首先计算该作业可获得的共享值：
根据当前pool的剩余slot数，调整该共享值：
其中runnableNum表示作业尚需的slot数与正在运行的slot数之和，curMin表示作业的当前最小共享量（jobinfo.minMaps或jobinfo.minReduces），初始值为0。
将slotsToGive作为最小共享量赋予相应的job。
修改值为值减去slotsToGive。
如果此轮循环中，slotsLeft值未变，即没有slot分给任何作业，则将剩余的slot共享给pool中所有job，即，执行（2）（3）并结束算法：
（2）将pool中的job按weight和deficit排序
（3）按顺序依次计算每个job的最小共享量。
首先计算该作业可获得的共享值：
根据当前pool的剩余slot数，调整该共享值：
将slotsToGive作为最小共享量赋予相应的job。
修改slotsLeft值为slotsLeft值减去slotsToGive。
需要注意的是，当执行完（2）（3）后，slotsLeft可能仍大于0，这时候会将剩余的slotsLeft个slot共享给其他pool。
5) 更新公平共享量
主要思想：基于作业权重和最小共享量计算公平共享量。首先，根据权重分配可用slot数，如果作业的最小共享量大于公平共享量，先要满足最小共享量，更新可用slot数，重复以上步骤，直到所有作业的最小共享量小于或等于公平共享量，这样，每个作业的最小共享量都得到了满足，最后，所有作业平分剩下的slot数。
算法实现：
初始化：当前所有作业的公平共享量置零；slotsLeft={系统中map slot 或者reduce slot 总数}；jobsLeft={系统中正在运行的作业}
（1）遍历集合jobsLeft中的所有作业，计算每个作业的jobFairShare：
如果作业的最小共享量（minSlots）大于公平共享量（jobFairShare），则：将最小共享量作为公平共享量赋值给作业。
同时将此作业从集合jobsLeft中删除。
（2）将剩下的slot按权重比例给集合jobsLeft中剩余的作业：
将jobFairShare作为公平共享量赋值给作业。
6) 更新缺额
实际计算时，会分开：
7) 资源分配
当系统中产生一个空闲slot时，将此slot分配给缺额最大的作业。
4、新版hadoop中公平调度器的新特性
（1）增加抢占功能：若某个作业在一定时间间隔内获取的资源（sl0t）总小于minShare/2或者fairShare/2，则从多拿资源的作业那抢占（kill task）。
（2）系统中有多个pool时，每个pool可以配置自己的调度方式：FIFO或者fair schduler（以前强制所有pool的调度方式都一样，是要么是FIFO，要么是Fair scheduler）。
（3）支持delay scheduling（见参考文献[5]）。当空闲slot没有locality的task可匹配时，调度器会选择延迟一段时间直到选中一个locality的task或者超时，如果超时（该时间内仍没有locality的task），则分配给非locality的task。
5、参考资料
（1）Fair scheduler论文：M. Zaharia, D. Borthakur, J. S. Sarma, K. Elmeleegy, S. Shenker, and I. Stoica, “Job scheduling for multi-user mapreduce clusters,” EECS Department, University of California, Berkeley, Tech. Rep., Apr 2009. 【下载】
（2）Hadoop主页：http://hadoop.apache.org/
（3）Hadoop公平调度指南：http://hadoop.apache.org/common/docs/r0.20.2/fair_scheduler.html
（4）0.21.0版本中fair scheduler设计文档：【下载】
（5）Delay Scheduling: A Simple Technique for Achieving. Locality and Fairness in Cluster Scheduling. Matei Zaharia. University of California, Berkeley，【下载】