................. ................. 在Hadoop-0.21.0版本中，Fair Scheduler代码结构有了较大变化（注意，最近的0.23.0版本与0.21.0基本相同），且核心调度算法也做了重大修改，使之更合理，更完善。本文主要分析了新版Hadoop中公平调度器的新特性。 如果你不了解旧版本Hadoop的Fair Scheduler算法，可参考这篇文章：Hadoop-0.20.2公平调度器算法解析 。 1. Hadoop-0.21.0版本公平调度器新特性 (1) 将之前（0.21.0之前版本）的基于缺额的调度算法改为层次调度算法 (2) 支持资源抢占 (3) 添加delay scheduling机制，使调度策略更优。 (4) 每个队列的调度策略可以配置，支持两种调度策略，分别为FIFO和FAIR，不管采用哪种调度策略，以上三个功能全部支持。 2. 层次调度算法 2.1 改进动机 之前的Fair Scheduler采用了基于缺额调度算法，主要思想是：将作业的优先级转化成权重，优先级越高权重越大，而权重越大，获得的资源越多，通过权重计算出的资源就是“公平共享量”，这是理想状态下，每个作业应得到资源量，而在实际情况下，可能获取不到这些资源，因而可以得到一个“理想和现实之间的差距”，为了是这个差距更能体现实际意义，又将时间融合进去，即：“理想和现实之差乘以时间”，这就是缺额（缺额是累加的，如果一个作业为获得资源，其缺额会随着时间不段增大，直到能够排到队列前头）。每次出现空闲资源时，优先选择缺额大的作业，以便达到公平调度的目的。 这个调度器在Yahoo和Cloudera内部均被采用，但在使用过程中，会出现以下现象： （1） 用户提交两个作业，其中一个提交时间早一些，因而占下了集群中所有的资源，而第二个作业以一半集群资源的速度积累缺额，直到一段时间之后，它的缺额才足以使得达到可以获取资源的资格； （2） 当用户继续提交大量作业时，由于第二个作业的缺额非常大，则后面的作业完全获取不到资源。 要消除这种现象，则需要对调度算法进行改进 一种改进方法是每隔一段时间重置缺额，而新版公平调度器则采用了以下算法。 2.2 新调度算法 首先介绍几个概念： Pool：资源池，或者作业池。 每个pool里有一定量的资源（管理员配置），每个用户属于某个pool，其作业可使用这个pool中的资源，可限定每个pool中最大并发作业数和每个用户最多提交作业数。默认情况下，一个linux用户对应一个pool，而管理员也可以配以一个linux group对应一个pool。pool实际上也可以称为group或者队列。 最小共享量：管理员可给每个pool配置一个最小共享量，调度器在分配资源时，需要保证每个pool中的作业至少获取该数目的资源。一个常见的应用场景是，对产品pool设置最小共享量，而测试pool不设置，这样，当可用资源有限时时，优先保证产品pool有资源可用。 公平共享量：当集群中存在多个pool时，某些pool中的资源可能用不了，这时候调度器会自动将这些pool中剩余的资源共享给其他需要的pool，其他这些pool获取的共享资源多少主要由其pool weight决定，pool weight越大，获取的资源越多。 一个pool的最小共享量加上其获取的共享资源数目，就是公平共享量。 下面正式介绍公平调度器的层次调度算法，大的思想与Capacity Scheduler类似，首先选择一个pool，然后从该pool中选择一个job，最后从该job中选择一个locality的task。 ................. ................. 其中，选择pool和job的策略相同，均采用了FairShareComparator比较器对pool或者job进行排序，然后从头到尾扫描队列，选出合适的pool或者job。在FairShareComparator中，Schedulable封装了是一个pool或者job的基本信息。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static class FairShareComparator implements Comparator { @Override public int compare(Schedulable s1, Schedulable s2) { double minShareRatio1, minShareRatio2; double tasksToWeightRatio1, tasksToWeightRatio2; int minShare1 = Math.min(s1.getMinShare(), s1.getDemand()); int minShare2 = Math.min(s2.getMinShare(), s2.getDemand()); boolean s1Needy = s1.getRunningTasks() < minShare1; boolean s2Needy = s2.getRunningTasks() < minShare2; minShareRatio1 = s1.getRunningTasks() / Math.max(minShare1, 1.0); minShareRatio2 = s2.getRunningTasks() / Math.max(minShare2, 1.0); tasksToWeightRatio1 = s1.getRunningTasks() / s1.getWeight(); tasksToWeightRatio2 = s2.getRunningTasks() / s2.getWeight(); int res = 0; if (s1Needy && !s2Needy) res = -1; else if (s2Needy && !s1Needy) res = 1; else if (s1Needy && s2Needy) res = (int) Math.signum(minShareRatio1 - minShareRatio2); else // Neither schedulable is needy res = (int) Math.signum(tasksToWeightRatio1 - tasksToWeightRatio2); if (res == 0) { // Jobs are tied in fairness ratio. Break the tie by submit time and job // name to get a deterministic ordering, which is useful for unit tests. res = (int) Math.signum(s1.getStartTime() - s2.getStartTime()); ................. ................. 27 28 29 30 31 32 33 if (res == 0) res = s1.getName().compareTo(s2.getName()); } return res; } }
3. 资源抢占 当一定时间（管理员可配置）内，某个pool中获取的资源量少于最小共享量，或者公平共享量的一半，则调度器会找出哪个pool抢占了该pool的资源，并杀死相应数量的task以抢占资源。 之所以要进行抢占，还是为了“公平”，即：保证每个pool能获取到它应得到的资源。
4. delay scheduling机制 当出现空闲slot时，如果排在队列前面的job对应的所有task均没有locality特性，则该作业会延迟调度，直到一段时间后，该job出现locality的task或者发生超时，才不得不调度该job的task。 有些人可能不了解locality，在此解释如下：当出现空闲slot时，该slot来自某个节点，而该节点上存有部分数据，如果某个task所需要的数据正好位于该节点上，则将该slot分配给该task是非常好的，因为它避免了通过网络读取数据。 5. 公平共享量计算方法
最后再说一下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[2] 如果一个pool的minShare>weight，则该pool的fairShare=minShare [3] 除此之外，所有pool的fairShare=R*weight
[4] 所有pool的的fairShare之和应为totalSlots 通过以上算法计算出的公平共享量即为“公平调度器”的“公平”含义之所在，应尽量保证每个pool获取的资源量为fairshare，如果一定时间期限内达不到，则抢占资源。
比率R表示weight-to-slot，即weight与slot的映射关系，其计算方法采用了二分枚举算法，具体可阅读源代码或者查看设计文档。R需要取到一个合适的值，使得上面的条件[4]成立。有人怀疑，是不是总存在一个R，使得条件[4]成立？答案是：yes！ 6. 公平调度器缺点 新版本的调度器仍不支持大内存作业，而Capacity Scheduler则早有了支持，其原理是：如果一个job需要较大内存，调度器会为该job分配多个slot，这样，作业可使用这些slot对应的内存资源。