公平调度算法分析

《公平调度算法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、在Hadoop-0.21.0版本中，FairScheduler代码结构有了较大变化（注意，最近的0.23.0版本与0.21.0基本相同），且核心调度算法也做了重大修改，使之更合理，更完善。本文主要分析了新版Hadoop中公平调度器的新特性。如果你不了解旧版本Hadoop的FairScheduler算法，可参考这篇文章：Hadoop-0.20.2公平调度器算法解析。1.Hadoop-0.21.0版本公平调度器新特性(1)将之前（0.21.0之前版本）的基于缺额的调度算法改为层次调度算法(2)支持资源抢占(3)添加delayscheduling机制

2、，使调度策略更优。(4)每个队列的调度策略可以配置，支持两种调度策略，分别为FIFO和FAIR，不管采用哪种调度策略，以上三个功能全部支持。2.层次调度算法2.1改进动机之前的FairScheduler采用了基于缺额调度算法，主要思想是：将作业的优先级转化成权重，优先级越高权重越大，而权重越大，获得的资源越多，通过权重计算出的资源就是“公平共享量”，这是理想状态下，每个作业应得到资源量，而在实际情况下，可能获取不到这些资源，因而可以得到一个“理想和现实之间的差距”，为了是这个差距更能体现实际意义，又将时间融合进去，即：“理想和现实之差乘以时间”

3、，这就是缺额（缺额是累加的，如果一个作业为获得资源，其缺额会随着时间不段增大，直到能够排到队列前头）。每次出现空闲资源时，优先选择缺额大的作业，以便达到公平调度的目的。这个调度器在Yahoo和Cloudera内部均被采用，但在使用过程中，会出现以下现象：（1）用户提交两个作业，其中一个提交时间早一些，因而占下了集群中所有的资源，而第二个作业以一半集群资源的速度积累缺额，直到一段时间之后，它的缺额才足以使得达到可以获取资源的资格；（2）当用户继续提交大量作业时，由于第二个作业的缺额非常大，则后面的作业完全获取不到资源。要消除这种现象，则需要对调度

4、算法进行改进一种改进方法是每隔一段时间重置缺额，而新版公平调度器则采用了以下算法。2.2新调度算法首先介绍几个概念：Pool：资源池，或者作业池。每个pool里有一定量的资源（管理员配置），每个用户属于某个pool，其作业可使用这个pool中的资源，可限定每个pool中最大并发作业数和每个用户最多提交作业数。默认情况下，一个linux用户对应一个pool，而管理员也可以配以一个linuxgroup对应一个pool。pool实际上也可以称为group或者队列。最小共享量：管理员可给每个pool配置一个最小共享量，调度器在分配资源时，需要保证每个p

5、ool中的作业至少获取该数目的资源。一个常见的应用场景是，对产品pool设置最小共享量，而测试pool不设置，这样，当可用资源有限时时，优先保证产品pool有资源可用。公平共享量：当集群中存在多个pool时，某些pool中的资源可能用不了，这时候调度器会自动将这些pool中剩余的资源共享给其他需要的pool，其他这些pool获取的共享资源多少主要由其poolweight决定，poolweight越大，获取的资源越多。一个pool的最小共享量加上其获取的共享资源数目，就是公平共享量。下面正式介绍公平调度器的层次调度算法，大的思想与Capacity

6、Scheduler类似，首先选择一个pool，然后从该pool中选择一个job，最后从该job中选择一个locality的task。其中，选择pool和job的策略相同，均采用了FairShareComparator比较器对pool或者job进行排序，然后从头到尾扫描队列，选出合适的pool或者job。在FairShareComparator中，Schedulable封装了是一个pool或者job的基本信息。1234567891011121314151617181920212223242526publicstaticclassFairShare

7、ComparatorimplementsComparator{@Overridepublicintcompare(Schedulables1,Schedulables2){doubleminShareRatio1,minShareRatio2;doubletasksToWeightRatio1,tasksToWeightRatio2;intminShare1=Math.min(s1.getMinShare(),s1.getDemand());intminShare2=Math.min(s2.getMinShare(),

8、s2.getDemand());booleans1Needy=s1.getRunningTasks()