文档章节

【大数据技术干货】阿里云伏羲(fuxi)调度器FuxiMaster功能简介(一) 多租户(QuotaGroup)管理

_夜枫
 _夜枫
发布于 2017/03/27 22:53
字数 1715
阅读 87
收藏 0

各位好,这是介绍阿里云伏羲(fuxi)调度器系列文章的第一篇,今天主要介绍多租户(QuotaGroup)管理的实现
 

一、FuxiMaster简介

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




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

1、多租户管理(本文)

2、调度模型及FIFO/FAIR调度策略

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

4、支持NodeLabel动态划分集群

5、支持多机房调度

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

7、支持AllOrNothing调度

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

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

10、......

二、多租户管理的用户场景

在典型场景下,可以简单理解为一个部门拥有一个QuotaGroup,这个QuotaGroup下可以有多位开发同学,他们使用的总资源是受到限制的。  

下面介绍有关的几个定义:

1、每个QuotaGroup拥有MaxQuota的语义,即可使用资源的上限;

2、每个QuotaGroup拥有MinQuota的语义,语义是当资源请求(Request,下同)小于MinQuota时,FuxiMaster必须分配Request这么多的资源;当Request大于MinQuota时,至少分配MinQuota这么多的资源;

3、由于系统总资源是固定的,所以每个QuotaGroup可用的资源一定是有限的、相互竞争的,每个QuotaGroup可以配置权重(Ratio),权重越大,分到的资源越多;

4、在某一时刻,有的QuotaGroup Request大,有的Request小;如果能够将Request小的QuotaGroup的Quota匀给Request大的QuotaGroup,那么系统的资源利用率会有明显提升;

5、最终QuotaGroup的Quota水位线我们称为RuntimeQuota;


用下图可以更好的描述上述概念:


假设系统中存在3个QuotaGroup组,为了简单,假设3个组的minQuota都为0; 左图中,蓝色部分是每个组的Request,红色部分是maxQuota,黄色虚线表示每个组按照ratio比列划分得出的可用quota水位线:
我们可以称之为RuntimeQuotaTmp,即:


然后我们发现,第一个组实际上request < RuntimeQuotaTmp,所以RuntimeQuotaTmp - request这部分可以匀给其他两个组使用;

在右图中,绿色虚线表示每个组最终的RuntimeQuota,可以看到对后面2个组,绿色虚线与黄色虚线的gap就是来自于第一个组的RuntimeQuotaTmp - request部分,分配的原则还是根据ratio比例:

由此可以总结出RuntimeQuota的计算公式:

三、一个典型的多租户管理的计算模型

根据上述描述,一个典型的计算模型为:

1、以各个QuotaGroup的ratio来分配集群总资源、得到RuntimeQuotaTmp;

2、当Request的总和小于集群总资源时,则每个用户的RuntimeQuota即是Request, 结束分配过程;

3、将用户分为两类,A类:Request小于RumtimeQuotaTmp;B类,Request大于RumtimeQuotaTmp;

4、对于A类用户,RumtimeQuotaTmp与Request的差可以分配给B类用户用;将这些差累计求和,记为系统中可以再分配的资源总量,记为∂

5、将∂按照ratio分配给B类用户,则B类用户新的RuntimeQuotaTmp =RuntimeQuotaTmp + 新得到的quota,记为Ω

6、如果B类用户的Ω大于Request,则Ω与Request的差还可以分配给B类用户中Ω仍小于Request的QuotaGroup,算法跳转回步骤3进行迭代,直到可再分配资源总量∂=0
 

这个算法有明显的缺点:时间复杂度是O(n2)

假设有n个用户,只有一个用户A的Request小于RuntimeQuotaTmp,更新可再分配资源总量∂,并分配给剩余n-1个用户后,假设只有一个用户B的新的资源配额Ω大于其Request,继续更新可再分配资源总量∂,并分配给剩余n-2个用户......如此反复,每次只有一个用户的RuntimeQuotaTmp大于其Request,那么则需要遍历n-1个用户才能完成分配过程,一次遍历时间复杂度是O(n),算法整体时间复杂度既是O(n2)。

四、FuxiMaster使用的多租户管理计算模型

FuxiMaster使用的模型算法复杂度是O(logN), 模型如下:

1、将每个用户视为一个盛水的桶,桶的底边是Ratio,面积是Request, 高既是用户的资源饱和度Req/Ratio。分配资源配额的过程就是将水(集群总资源)灌入到各个桶中的过程。将用户按照Req/Ratio进行排序:



2、将集群总资源按照ratio比例均匀的撒到每个组(往桶里面倒水), 故所有桶的水面高度(h)一齐上升。 



3、若有的桶水面高度到顶且集群剩余可分配资源仍有剩余,则此桶的水面高度不再上升,继续向其他水面高度未到顶的桶中灌水,直到集群剩余可分配资源为0或者所有桶的水面均已到顶。

当集群剩余可分配资源为0后,我们需要找到Request得到满足和Request没有完全的满足的桶边界,在边界左边的桶的RuntimeQuota就是Request;而在边界右边的桶deRuntimeQuota是H * Ratio,其中H如下图所示。可知,如果能够计算出边界和H,那么每个用户的RuntimeQuota就是可知的。



判断边界的条件是:

Requst(A~D) + RequestE + (RequestE / RatioE) * (ratioF + ratioG) < TotalRes &&  Requst(A~D) + RequestE +(RequestF / RatioF)  * (ratioF + ratioG) >TotalRes


由于每个桶是按照Request/Ratio排序的,所以可以通过构建一颗自定义的旋转的红黑树,就可以以O(logN)的时间复杂度来找出边界点,找出边界点后,通过公式:



即可以求出H,进而得到每个Quota组的RuntimeQuota

4、如果考虑minQuota,则根据minQuota的定义将相应部分事先减去即可,如下图所示:




这个方法和典型方法从数学上可以推导对于runtimeQuota结果是保持一致的,由于比较复杂这里就不列出了,有兴趣的同学可以私下讨论

五、性能表现


我们同时实现了2种方法进行性能对比,其中组数是指QuotaGroup的个数;资源数是指资源维度的数目(资源分配是多维的),结果如下:





可以看到,FuxiMaster目前采用的方法与组数是对数关系,与资源数成线性关系,符合预期;相对于典型方法,性能提升巨大

下面进一步给出FuxiMaster方法在更大规模下面的表现:

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

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

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

隐林
2017/05/05
0
0
2018年 云效 干货文章大盘点!

2018年已过,我们迎来了新的一年,在机遇与挑战同在的环境下,我们更应勤于学习。为了方便大家学习,小编为大家盘点了2018年云效云栖号最火的干货文章分享给大家,让我们在新的一年里共同学习...

技术小能手
03/04
0
0
飞天,进化!

转:阿里云的“飞天“是什么? 一、飞天是什么? 飞天(Apsara)是由阿里云自主研发、服务全球的超大规模通用计算操作系统。它可以将遍布全球的百万级服务器连成一台超级计算机,以在线公共服...

啊莱
2016/10/29
0
0
MaxCompute,基于Serverless的高可用大数据服务

摘要:2019年1月18日,由阿里巴巴MaxCompute开发者社区和阿里云栖社区联合主办的“阿里云栖开发者沙龙大数据技术专场”走近北京联合大学,本次技术沙龙上,阿里巴巴高级技术专家吴永明为大家...

zhaowei121
02/20
6
0
阿里飞天云平台架构简介

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

牧师-Panda
2016/10/16
802
0

没有更多内容

加载失败,请刷新页面

加载更多

JS基础-该如何理解原型、原型链?

JS的原型、原型链一直是比较难理解的内容,不少初学者甚至有一定经验的老鸟都不一定能完全说清楚,更多的"很可能"是一知半解,而这部分内容又是JS的核心内容,想要技术进阶的话肯定不能对这个...

OBKoro1
今天
7
0
高防CDN的出现是为了解决网站的哪些问题?

高防CDN是为了更好的服务网络而出现的,是通过高防DNS来实现的。高防CDN是通过智能化的系统判断来路,再反馈给用户,可以减轻用户使用过程的复杂程度。通过智能DNS解析,能让网站访问者连接到...

云漫网络Ruan
今天
14
0
OSChina 周一乱弹 —— 熟悉的味道,难道这就是恋爱的感觉

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @xiaoshiyue :好久没分享歌了分享张碧晨的单曲《今后我与自己流浪》 《今后我与自己流浪》- 张碧晨 手机党少年们想听歌,请使劲儿戳(这里)...

小小编辑
今天
3K
24
SpringBoot中 集成 redisTemplate 对 Redis 的操作(二)

SpringBoot中 集成 redisTemplate 对 Redis 的操作(二) List 类型的操作 1、 向列表左侧添加数据 Long leftPush = redisTemplate.opsForList().leftPush("name", name); 2、 向列表右......

TcWong
今天
46
0
排序––快速排序(二)

根据排序––快速排序(一)的描述,现准备写一个快速排序的主体框架: 1、首先需要设置一个枢轴元素即setPivot(int i); 2、然后需要与枢轴元素进行比较即int comparePivot(int j); 3、最后...

FAT_mt
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部