本文描述了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 priorityFactorVERY_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) 更新作业的最小共享量