文档章节

【大数据技术干货】阿里云伏羲(fuxi)调度器FuxiMaster功能简介(二) 调度模型

_夜枫
 _夜枫
发布于 2017/03/28 21:27
字数 2036
阅读 23
收藏 0

各位好,这是介绍阿里云伏羲(fuxi)调度器系列文章的第二篇,今天主要介绍调度模型和FIFO\FAIR调度策略
 

一、FuxiMaster简介

FuxiMaster和Yarn非常相似,定位于分布式系统中资源管理与分配的角色:一个典型的资源分配流程图如下所示: 




作为调度器,目前FuxiMaster支持的功能主要有:

1、多租户管理

2、支持FIFO/FAIR调度策略(本文)

3、针对在线服务保持资源强稳定

4、支持NodeLabel动态划分集群

5、支持多机房调度

6、支持基于优先级的交互式抢占

7、支持AllOrNothing调度

8、支持基于硬件ID化的调度

9、单Master目前支持2w台机器的规模

10、......
 

二、基本调度单元与基于拓扑的调度语义.
 

1、基本调度单元:

在fuxi系统内,基本的调度单元称作ScheduleUnit,它的概念和Yarn的Container是不同的: 举个例子,假设一个MR的作业,规模是1000*1000, 那么在Yarn的调度器中,对应就有100,000个调度单元;而在fuxi系统里,只有2个调度单元(ScheduleUnit), 每一个SchedsuleUnit的SlotNumber是1000。在调度层面上,ScheduleUnit是同一类Slot的集合
 

2、基本调度语义:

在fuxi系统内,目前线上存在3种基于拓扑的调度语义:LT_MACHINE\LT_ENGINEROOM\LT_CLUSTER, 分别对应着指定机器、指定机房、全集群任选集群;且调度的优先级是LT_MACHINE > LT_ENGINEROOM > LT_CLUSTER; 一个典型的资源申请请求为: SchduleUnit{SlotNum:5, M1 *1, M2 * 1, M3 *1, M4 *1, M5 * 1, C * 5}, 这个ScheduleUnit理解为:总共需要5个slot,优先在M1\M2\M3\M4\M5上分配资源,如果这些机器资源不满足的话,也可以退而其次在其他机器上(LT_CLUSTER)上分配资源
 

三、主动调度策略:

作业第一次将SchduleUnit发送到调度器时,调度器会遍历ScheduleUnit的拓扑语义在对应机器上进行调度,对应LT_MACHINE的语义,会直接到指定机器上尝试分配资源;如果是LT_ENGINEOOM\LT_CLUSTER的语义,则在一组满足条件的机器列表内进行RoundRobin的分配(roundrobin);

除此之外,还有一些额外的分配限定:

1、ScheduleUnit如果是属于某个QuotaGroup的,那么会首先根据这个QuotaGroup的剩余可用Quota / ScheduleUnit体积 得出一个从Quota层面可以分配的slot数目,与ScheduleUnit的desireNum取一个min;

2、ScheduleUnit可以定义在同一台机器上分配的最大worker数目,主要防止相同类型的worker扎堆在同一台机器上;

3、如果机器处于ScheduleUnit的黑名单中,那么这台机器也不会被分配;黑名单的来源有2种,一种是集群中PE加入的全局黑名单,这个对所有SscheduleUnit都是不可用的;一种的ScheduleUnit自己的黑名单,通常是一台机器多次出现slot运行失败,则作业会通知调度器暂时不调度新的slot到这台机器上;

主动调度策略从全局来说是一种贪心的调度策略,尽量对ScheduleUnit进行调度,如果ScheduleUnit没有被完全满足,则ScheduleUnit携带剩余的DesireNum进入到排队队列,等待被动调度策略触发调度

四、被动调度策略:

被动调度策略顾名思义,是处于waitingQueue中的SchduleUnit被动的被调度器挑选中分配资源;触发被动调度策略的条件有2个:一个是跑完的作业归还资源;一个是机器的资源增加;即当有额外的可用资源时,就会触发被动调度策略,在内部有一个更形象的名字,称为”OnResourceFree“
 

1、如何挑选waitingQueue

WaitingQueue是基于QuotaGroup的,每一个QuotaGroup都有自己的waitingQueue,同组的ScheduleUnit只会插入到自己组的waitingQueue中;当有一台机器有剩余资源时,我们挑选哪一个QuotaGroup的waitingQueue进行分配呢? 在FuxiMaster中,QuotaGroup有“Hungry”的概念,Hungry的定义是:usdQuota/maxQuota(概念参见上一篇),此值越低,表明这个QuotaGroup越饥饿,越应该优先得到满足(这里我们也在讨论是否参考runtimeQuota更合理); 根据Hungry对所有QuotaGroup进行排序后,我们就可以得出一个waitingQueue的分配顺序
 

2、WaitingQueue的构成及遍历

WaitingQueue存放着没有被满足的ScheduleUnit,SchdeduleUnit排列的顺序是根据ScheduleUnit的优先级决定的: 每一个ScheduleUnit都被作业赋予了一个优先级,优先级越高,表明越应该优先分配资源,故在waitingQueue中的位置就越靠前。

在具体分配过程中,对于每一个ScheduleUnit的分配是贪心的,也收到在主动调度策略中的各种限制,一种典型的分配场景如下图所示:




在上图中,如果我们根据优先级依次对ScheduleUnit尝试分配时,发现处于前4个的ScheduleUnit的体积都比机器的可用资源大,那么总共产生80%的无用遍历,当队列中ScheduleUnit比较多时,这个遍历的代价是比较大的,时间复杂度是O(N), 为此,我们采用了如下的算法,期望能够直接找到从资源维度能够分配的ScheduleUnit,同时满足优先级的约定:


首先,我们根据ScheduleUnit的CPU体积构建子队列,每个子队列的ScheduleUnit CPU体积相同,且根据优先级进行排列;同时根据可用资源取出每个候选队列的对头的ScheduleUnit,构建成堆;



当对第一个元素进行分配并POP后,如果堆头ScheduleUnit的体积大于剩余资源,则直接POP;同时尝试将上一个POP出去的ScheduleUnit所属队列的下一个ScheduleUnitPush进堆;


继续:


直到绿线比最低的虚线还要低,表示无法在分配,算法结束



当然,同一条虚线上的ScheduleUnit虽然在CPU维度满足,但是在MEM维度还是可能不满足,所以还是可能会有很多无用遍历,还有优化的空间:


 

0、红黑树节点保存ScheduleUnit的指针,排序的key是priority

1、每个节点保存自己左、右子树的ScheduleUnit SlotDesc MEM的最小值;

2、先看左子树,如果左子树的ScheduleUnit SlotDesc MEM的最小值比可用资源MEM的值小,表示左子树中有可分的、高优先级的SU,向左子树递归;

3、如果左子树不满足,则看自己满足不满足

4、如果自己不满足,则看右子树的SU SlotDesc MEM的最小值是否比可用资源, MEM的值小,表示左右子树中有可分的、低优先级的SU,向右子树递归;

5、如果都不满足,则此树上所有节点都不再可能被分配资源,以后就不用在遍历此树了


这样做之后,我们就可以以O(logN)的代价找到优先级最高的、CPU、MEM也满足条件的ScheduleUnit,下面一组实验表明了算法的优越性:




在上述实验中,可分的ScheduleUnit只有一个,剩余的ScheduleUnit的体积全部比剩余资源大。可以看到,优化方案比普通遍历方案在性能上提升非常明显
 

3、FIFO\FAIR调度策略

FIFO\FAIR调度策略的却别体现在WaitingQueue的排序的Key: 如果ScheduleUnit的优先级不同,那么两者都会优先对高优先级的ScheduleUnit进行分配;当优先级相同时,FIFO是根据ScheduleUnit的提交时间进行排序的,提交时间越早,优先级越高; 而FAIR是根据已经分配到的SlotNum进行排序的,已经分配的slotNum越小,优先级越高。这样对FAIR组而言,基本保证了同优先级ScheduleUnits拿到的资源份数基本是相同的。

本文转载自:https://yq.aliyun.com/articles/64882

_夜枫
粉丝 10
博文 506
码字总数 0
作品 0
朝阳
后端工程师
私信 提问
阿里巴巴大数据计算平台MaxCompute(原名ODPS)全套攻略(持续更新20171127)

概况介绍 大数据计算服务(MaxCompute,原名ODPS,产品地址:https://www.aliyun.com/product/odps)是一种快速、完全托管的TB/PB级数据仓库解决方案。MaxCompute向用户提供了完善的数据导入方...

隐林
2017/05/05
0
0
将双11新增IT成本降低一半 阿里是咋做的?

  【IT168 技术】有人做过计算,当10万台服务器,利用率从28%提升到40%,就能节省出3万台机器。假设一台机器的成本为2万元,那么节约的成本就有6个亿。这是个惊人的数字,意味着在庞大的数...

it168网站
2017/11/13
0
0
阿里飞天云平台架构简介

原贴在这里:http://blog.csdn.net/yangcs2009/article/details/39292097。我做了部分修改。 飞天是由阿里云开发的一个大规模分布式计算系统,其中包括飞天内核和飞天开放服务。 飞天内核负责...

牧师-Panda
2016/10/16
796
0
阿里巴巴 Sigma 调度和集群管理系统架构详解

划重点 阿里巴巴 9 年双 11 经历下来,交易额增长了 280 倍、交易峰值增长 800 多倍、系统数呈现爆发式增长。系统在支撑双 11 过程中的复杂度和支撑难度以指数级形式上升。双 11 峰值的本质是...

阿里系统软件技术
2018/04/19
0
0
看完这些干货帖,大数据产品从入门到精通

摘要: 看完这些干货帖,了解大数据产品应用场景 欢迎来到“MVP教你玩转阿里云”系列教程,在这里,你将看到各行各业数字化转型的一线实践,学到资深开发者的经验结晶。 你将以云计算领域的技...

阿里云云栖社区
2018/11/29
14
0

没有更多内容

加载失败,请刷新页面

加载更多

哪些情况下适合使用云服务器?

我们一直在说云服务器价格适中,具备弹性扩展机制,适合部署中小规模的网站或应用。那么云服务器到底适用于哪些情况呢?如果您需要经常原始计算能力,那么使用独立服务器就能满足需求,因为他...

云漫网络Ruan
今天
5
0
Java 中的 String 有没有长度限制

转载: https://juejin.im/post/5d53653f5188257315539f9a String是Java中很重要的一个数据类型,除了基本数据类型以外,String是被使用的最广泛的了,但是,关于String,其实还是有很多东西...

低至一折起
今天
17
0
OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
11
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
9
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部