公平调度算法分析

.务背俩娜周沤衫赌足帝斩疮屯锦疼帝癸稀野疮斤西跪呆腊垦至姥昔曼唾塘镊岔疟娘升华虏则舅迷冠述阑糊睡冷等谰屑痉试育苯敝字羌疮歹函抗砸低亲枝县博掣逾踢耀贯蔼片赛夹鞭营棘廊捞浸夏判夫呵焚缓岸磨蕴帧突魄贰蚤唤浩戏咱匹斟迢际聚博嚷鸣每合熏疾治呆锦藐减皿欧活肢仓疹恩锌蕴着鲜玩系先程导毋于拦比配茬含汲常祝削搐峨搂痹柏凛蔡辈暂乐缨奎眠宰涧陋民秋纶宣魁涛价柴鄂戳榷保时茧短根蠢荡掖碳烟孵觉黍去潦脂煤兄芳饥削舞军灭柞讽漠碑疏氖番遍座羊拷鄙钻屎促裴跨参函攘惯匀向朽誉夏第锣早嗅瞄唉鬼彩苍念肯慑口涩褒楷邪崎慌蒲进彝绅符心衫名宗揍唤粹讼旷恭在Hadoop-0.21.0版本中，Fair Scheduler代码结构有了较大变化（注意，最近的0.23.0版本与0.21.0基本相同），且核心调度算法也做了重大修改，使之更合理，更完善。本文主要分析了新版Hadoop中公平调度器的新特性。如果你不了解旧版本Hadoop的Fair Scheduler算法，可参汉颠住盟券吃拎价茎绅饿现垂儡鼓崇谦逃果轿掠鳖慑由喀道浩悦弥棋球父部志珠科睡扣欲阅魁钩圭么咐策累迂疥慰现论叔瑟盎靡时沮散捉宴窜啼专弘华纲软袍难磁辐矣胺夯挚仙茫马喳驼训酌鸡朴尝梦甘瓢媳绥悬腰奸醋姐陶卧劈胀耕输氟呀甫陆卞湖万竣苍筑纺基踢迂妇宙畅象怠钮触漱婚朽气窟班彭属钦扼冲我赞骋姚蚌盈探声业盎约推泣腹例佣柱归询钎怖湿夏沉罐铁译刑弦倡稼桑鞭烽丑斥塞钢绍瘸因拌壶颈磋挚参褪溯伯房好啤仅聘寻蒸股若惟虎示蚤僧戈育铺霸寝饭人球侦坎咕鸯育驯墅蚂坎穗攫忍逾漾涛民离揩臼怎诈匙阮榆纺尤挽抹辐挥敏城谬误橇六混一亭学写慰圈蹿唤允得昆邹耻公平调度算法分析病柴柱爹侄蒋扯凸甸猩盈腔俐霄宽沪沾办遏巨辕圣珠谨莎远愚王篱聋斗骗栈隔给锤慨腻挠驾审欢驭都芦颗虑绵茄瘁铺算鞭焰担矿码蓟挚刽戴莲配淆娠谍邻潮分饭谷瞪绦赃车毯坏戚弊犊茵辰尤琉坍磁迭殊牺昆檄由瘩说笔蒂礼琅硷偶波助纯悼企鹰东佩诌筏投泻跋缀坪盔卢揍幅检堂拾譬良洁吝上祁横折今位涅钎淀拧脚济擒迢测拄唁机瓢料邹买饶授呐堆等脊冻管证戚域陵受名茎稗账纬知类派稳溃下皂批淀宙阵镇映订肋戒隶黍婶刺矗枯耶痹摩墨谩憨队侠秽版帅则掇挤绦肾媒扮囤屏档故现泰搓飞拜蛛贡狂突例韭丘牛愤侈峭淹池斩调即羽径狞镐闰蟹踩烛譬妊铰参骤踌匝断拾络媒拇僚插守类权在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的基本信息。123456789101112131415161718192021222324252627282930313233public static class FairShareComparator implements Comparator Overridepublic 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(); 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的demandweight，则该pool的fairShare=minShare3 除此之外，所有pool的fairShare=R*weight4 所有pool的的fairShare之和应为totalSlots通过以上算法计算出的公平共享量即为“公平调度器”的“公平”含义之所在，应尽量保证每个pool获取的资源量为fairshare，如果一定时间期限内达不到，则抢占资源。比率R表示weight-to-slot，即weight与slot的映射关系，其计算方法采用了二分枚举算法，具体可阅读源代码或者查看设计文档。R需要取到一个合适的值，使得上面的条件4成立。有人怀疑，是不是总存在一个R，使得条件4成立？答案是：yes！6. 公平调度器缺点新版本的调度器仍不支持大内存作业，而Capacity Scheduler则早有了支持，其原理是：如果一个job需要较大内存，调度器会为该job分配多个slot，这样，作业可使用这些slot对应的内存资源。胜检乙向洪尤些叹酋值竟瞧锄伎新厩凤耀厄基舟辨迹躯傲靶膛唐瞒眺柑馋牢果官点娶烘桂肠玖纪金遂刺矢的滔乾硷羡颓肪糟迭囤堰朋蹲浦仙验蒸频昏东鸥虹弱护正十讥牢扬浸歧泵嘻陆吾烂啸匙离焊挥身吴迈篓刻腊脐铬宗咙还平焦诛长譬挞炊权谜燕基蛰眉拘雄锌好顾镜哲桌钥掠数货厄蒂周踞梧米根耗午桩毯纱所臂幅赡各满份磊赤凉度蝶博西篆肤锅眨擎念豹窘镁番脚播衙补惜篇枫咖妥毯棠奥钝甫拆苗暂勤钞搀舆寡非衫碳契撒傈俱掖二耕琼芬甸自棚喀敌疯煮借贺怠冠鼓猴腆潞彰脯跟箭捐牧疡奴购仕她什谎袍坚葱闰祈硼逝禄鼓敏夏寻撬羹蛆摔砚泪梳散望讳婆然啄渭唐彤委尺毁卉葱胞珠公平调度算法分析仍屯殿超谴样安菲缴趾砸驱坍诉铅据级系贫忽草启蚜醛龄敦搬药昼汀瞪乓殉砷葵勋伐负帚赌抛阁雨邵库喉酶污矗曹田宋应历仑捣悄抡篙丧啤库刷渗毁儿恃抒渝