简介：fair shechedule （公平调度算法），是由facebook提出来的作业调度算法，它的目标是为了所有的作业随着时间的推移，都能够平均得获得相同的功效资源。Fair让hadoop能够更好的处理不同类型的作业并行执行。
1产生背景
Facebook每天都要产生大量的数据，数据的存储管理给facebook带来了很大的困扰，facebook使用hadoop就是看中了hdfs文件系统所具有的优秀存储管理能力，随着hadoop的使用，越来越多的人队其中存储的数据产生了兴趣，于是他们提交了很多生产型作业用于对数据进行统计分析，于此同时，一些用户开始研究与使用HIVE（一种构建在hadoop平台上的分布式数据仓库，由facebook提出）来对这些数据进行自定义的查询，还有一些用户提交了大型的批处理作业用于在这个大数据集上面进行各种实验，这些不同用户提交的作业在计算时间、存储空间、数据流量、相应时间、计算量上都有着不同的需求甚至存在冲突。所以为了提高小作业共享集群相应时间以及提高集群的利用率，公平调度算法应运而生。
2公平调度器介绍
公平调度器按资源池（pool）来组织作业，并把资源公平的分到这些资源池里。默认情况下，每一个用户拥有一个独立的资源池，以使每个用户都能获得一份等同的集群资源而不管他们提交了多少作业。按用户的 Unix 群组或作业配置（jobconf）属性来设置作业的资源池也是可以的。在每一个资源池内，会使用公平共享（fairsharing）的方法在运行作业之间共享容量（capacity）。用户也可以给予资源池相应的权重，以不按比例的方式共享集群。
除了提供公平共享方法外，公平调度器允许赋给资源池保证（guaranteed）最小共享资源，这个用在确保特定用户、群组或生产应用程序总能获取到足够的资源时是很有用的。当一个资源池包含作业时，它至少能获取到它的最小共享资源，但是当资源池不完全需要它所拥有的保证共享资源时，额外的部分会在其它资源池间进行切分。
图2-1是一个作业池分配资源的实例。
在这个实例中，整个hadoop集群有100个计算插槽和三个作业池，作业池1和3分别设置了最小保证资源60和10，这样分配资源的时候会优先保证作业池分别获得最小保证资源。然后将剩下的分配个池2，此图作业池3未有作业，其获得的作业将被分给其它作业池（2）。在实际中为了有利于用户/作业的重要程度以及实际计算需要合理分配资源，可以对作业和作业池赋予一定的权值以此为依据获得相应比例的资源额度。
在这种计算资源槽分配过程中存在两个问题，一个是分配池中的作业所需要的计算资源有差额这种差额或则是分配到池中最小配额的差额，也是作业除了最小配额的资源还需要更多的资源，这种差距用一个词赤字来表示。赤字越高表明受到不公平待遇越多，赤字当然随着时间的推移值就越大，当有空闲的tasktracker时优先分配具有最高赤字的作业使用，当然如果在系统中存在尚未获得最低资源的作业池，属于这个池的作业将会被优先调用。
3任务槽的分配算法
算法中di表示池i的需求，mi表示池i的最小配额，S表示激活池的集合，F表示系统中槽的总数，要分配资源槽需满足：，池i的共享额为fi。
SA= S;//未分配的池
SB=0；//已分配的池
M=F//未分配的槽
//分配槽给池，并且需求小于等于最小配额
For(each pool iSA ) do
If di<mi then
Fi=di;M-=di;
SA=SA\{i} ;SB=SB{i};
End if
End for
//分配最小配额给剩余的池
For(each pool iSA ) do
Fi=mi;M-=mi;
End for
//分配余下的槽
While((SA 0))^(M>0))do
dmin=smallest demand amongpools in SA;
fmin=smallest share amongpools in SA;
smin=set of all pools whoseshare is fmin
fnext-min=next smallest shareamong pools in SA;
;
For(each pool i Smin )do
Fi+= ;M-= ;
SA=SA\{i}; SB=SB{i};
End for
End while
4配置使用
公平调度算法在hadoop配置文件中，有两处配置文件。算法参数在mapred-site.xml中设置，还有一个fair 独有的配额文件（allocation file）的xml文件，可以用来配置资源池、最小共享资源、运行作业限制和抢占超时时间。配额文件在运行时会定期的被重新加载，这样不用重启hadoop集群就可以更新资源池的配置。
Mapreduce-site.xml
<property>
<name>mapred.jobtracker.taskScheduler</name>
<value>org.apache.Hadoop.mapred.FairScheduler</vaule>
</property>
<property>
<name>mapred.fairScheduler.allocation.file</name>
<value>path/to/pools.xml</vaule>
</property>
B配额文件
配额文件为每一个资源池配置最小共享资源、运行作业限制、权重和抢占超时时间。
<allocations>
<pool name=”sample_pool>
<minMaps>5</minMaps>
<minReduces>5</minReduces>
<weight>2.0</weight>
<username=”sample_user”>
<maxRunningJobs>6</maxRunningJobs>
<user>
<userMaxJobsDefault>3</userMaxJobsDefault>
</allocations>
6、参考资料
（1）Fairscheduler论文：M. Zaharia, D. Borthakur, J. S. Sarma, K. Elmeleegy, S. Shenker, andI. 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 ) http://hadoop.apache.org/common/docs/r0.20.2/fair_scheduler.html
（4）0.21.0版本中fair scheduler设计文档
（5）Delay Scheduling: A Simple Technique forAchieving. Locality and Fairness in Cluster Scheduling. Matei Zaharia.University of California, Berkeley，