MyException - 我的异常网
当前位置:我的异常网» 行业应用 » 【大数据技术干货】阿里云伏羲(fuxi)调度器FuxiMast

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

www.MyException.Cn  网友分享于:2013-04-21  浏览:0次
【大数据技术干货】阿里云伏羲(fuxi)调度器FuxiMaster功能简介(一) 多租户(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方法在更大规模下面的表现:

阅读全文:http://click.aliyun.com/m/13950/

文章评论

相关解决方案
  • 暂无相关解决方案
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
10个调试和排错的小建议
10个调试和排错的小建议
我是如何打败拖延症的
我是如何打败拖延症的
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
如何成为一名黑客
如何成为一名黑客
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
为什么程序员都是夜猫子
为什么程序员都是夜猫子
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员和编码员之间的区别
程序员和编码员之间的区别
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
总结2014中国互联网十大段子
总结2014中国互联网十大段子
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
代码女神横空出世
代码女神横空出世
老程序员的下场
老程序员的下场
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员都该阅读的书
程序员都该阅读的书
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员必看的十大电影
程序员必看的十大电影
旅行,写作,编程
旅行,写作,编程
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
我的丈夫是个程序员
我的丈夫是个程序员
鲜为人知的编程真相
鲜为人知的编程真相
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序员应该关注的一些事儿
程序员应该关注的一些事儿
那些争议最大的编程观点
那些争议最大的编程观点
Java程序员必看电影
Java程序员必看电影
一个程序员的时间管理
一个程序员的时间管理
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
 程序员的样子
程序员的样子
漫画:程序员的工作
漫画:程序员的工作
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有