内容简介:如果看过我的上一篇关于 mesos 的文章,应该还记得 mesos 的资源调度策略写的泛化的 max-min fairness 算法,其实这个就是 DRF 算法。DRF,全称 dominant resource fairness,由伯克利大学提出,论文链接在文末列出。论文中介绍 DRF 为 generaliztion of max-min fairness to multiple resource types,所以下面先介绍一下 max-min fairness 算法。我们经常会遇到将稀缺资源分配给多个用户
如果看过我的上一篇关于 mesos 的文章,应该还记得 mesos 的资源调度策略写的泛化的 max-min fairness 算法,其实这个就是 DRF 算法。
DRF,全称 dominant resource fairness,由伯克利大学提出,论文链接在文末列出。论文中介绍 DRF 为 generaliztion of max-min fairness to multiple resource types,所以下面先介绍一下 max-min fairness 算法。
1. Max-min fairness
我们经常会遇到将稀缺资源分配给多个用户的情况,每个用户获得资源的权利都相同,但是需求数却可能不同,这个时候应该怎么办?一种常用的方法叫 max-min fairness share,中文可以叫最大最小化公平分配算法,也就是尽量满足用户中的最小的需求,然后将剩余的资源公平分配给剩下的用户。形式化定义如下:
- 资源分配以需求递增的方式进行分配
- 每个用户获得的资源不超过其需求
- 未得到满足的用户等价平方剩下的资源
更形象的表达如下,有用户 1, …, n,资源需求分别为 x1 , x2 , …, xn .不失一般性,假设 x1 <= x2 <= … <= xn 。假设资源总数为 C。然后先给需求最小 x1 的用户分配资源数 C/n 。如果 x1 < C/n,则用户 1 剩余资源 C/n - x1,则剩下的用户每人获取资源数为 C/n + (C/n - x1)/(n-1),然后依次处理剩下的用户,直到资源数小于等于需求数或者所有用户分配完。举个例子如下:
用户 1, 2, 3, 4 的需求分别为 2, 2.6, 4, 5,总资源数为 10。首先我们将资源数平分 4 等份,10/4 = 2.5。用户 1 需求是 2,则剩余 2.5 - 2 = 0.5,0.5 再平分给用户 2,3,4,0.5/3 = 0.1666…。然后用户 2 需求 2.6,剩余 2.5 + 0.1666 - 2.6 = 0.066…,再平分,0.066/2 = 0.033…,则用户 3 获得 2.5 + 0.66… + 0.033… = 2.7 ,此时不满足资源需求,结束。最终 4 个用户获得的资源数依次为 2, 2.6, 2.7, 2.7。
2. Weighted max-min fairness
上面我们假设每个用户获得资源的权重一样,对于权重不一样的处理方式也就是 weighted max-min fairness share。用户 1,2,…,n 的权重分别为 w1, w2 , …, wn ,这也就意味我们第一次总资源切分以及之后多余资源切分不是等分,而是按权重来切分。举例如下。
用户 1, 2, 3, 4 需要的资源数分别为 4, 2, 10, 4,权重分别为 2.5, 4, 0.5, 1,资源总数为 16。首先对权重做处理为 5, 8, 1, 2,然后将资源 16 按权重切分每个用户获得资源数:5, 8, 1, 2。我们先遍历可以满足需求的用户:用户 1 需要资源 4,得到 5, 剩余 1。用户需要资源 2,得到 8,剩余 6。用户 3 和 4 资源无法满足。总剩余资源数为 7,按权重分给用户 3 和 4,用户 4 得到资源 7 2/3 + 2 = 6.666 多于需求 4,剩下 2.666,分给用户 3。最后用户 3 获得资源数为 1 + 7 1/3 + 2.666 = 6。
3. DRF
max-min fairness 算法的最大问题是认为资源是单一的,但是现实情况中资源却不是单一的,CPU,RAM,I/O 等都是计算机资源。这个时候 DRF 应运而生。简单来说 DRF 就是 max-min fairness 算法的泛化版本,可以支持多种类型资源的 fairness。所谓多种资源的 fairness 是每个用户在主资源,也就是 DRF 中的 DR (Domain Resource),上是满足 max-min fairness 的。
那么何谓 Dominant Resource 呢?简而言之,用户被分配的资源中占比总资源比重最大的资源就是 Dominant Resource。举个例子,系统拥有资源 9 CPUs, 18 GB RAM,用户 A 的 task 需要资源为<1 cpu,4="" gb="" ram="">,则用户 A 的资源占比分别为 CPU 1/9,RAM 2/9,则用户 A 的 Dominant Resource 就是 RAM。用户 B 的 task 需要资源<3 1="" cpus,="" gb="" ram="">,则用户 B 的 Dominant Resource 为 CPU。最后 DRF 最求的结果就是平等权利的用户的 Dominant Resource 占的份额是一样的:分配给 A<3 12="" cpus,="" gb="" ram="">运行 3 个 task;分配给 B<6 cpus,="" 2gb=""> 资源可以运行两个 task。这样 A 的 DR 占的份额为 12/18 = 2/3,B 的 DR 占比 6/9 = 2/3。
我们看一下具体的计算的过程,继续使用上述的例子。设 x 和 y 为用户 A,B 所得资源可以运行的 task 个数,则可以得到下面的优化函数
max(x,y)
s.t
x+3y\leq9 (CPU total)
4x+y \leq 18 (RAM total)
\cfrac{2x}{9} = \cfrac{y}{3}
解得:x = 3, y = 2。
需要注意的是,并不是说 Dominant Resource 占比一定要相同,和 max-min fairness 算法一样,当其中一个用户的需求已经得到满足,剩下的资源即可全部分配给其他用户。DRF 算法的形式化定义如下:
4. Weighted DRF
带权重的 DRF 算法可以认为是 DRF 算法和 weighted max-min fairness 算法的结合。每个用户都分配一个权重向量 W_i=
除此之外,u_i,_j 表示用户 i 对资源 j 的需求占比,则用户 i 的 dominant resource 计算方式为 s_i = max_j {u_i,_j / w_i,_j} ,也就是全局占比最大的资源,剩下的计算和 DRF 算法类似。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Hadoop 系列(二)—— 集群资源管理器 YARN
- 京东万台规模Hadoop集群 | 分布式资源管理与作业调度
- Memcache/Redis 集群管理探索与实现:美图开源 PaaS 平台资源网关
- Kubernetes 资源管理概述
- 初略讲解Flutter的资源管理
- 虚拟化云计算中的资源管理策略
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
遗传算法与工程优化
程润伟 / 清华大学出版社 / 2004-1 / 39.00元
《遗传算法与工程优化》总结了遗传算法在工业工程相关领域应用的前沿进展。全书共分9章:遗传算法基础、组合优化问题、多目标优化问题、模糊优化问题、可靠性设计问题、调度问题、高级运输问题、网络设计与路径问题和制造元设计问题。内容既涵盖了遗传算法在传统优化问题中的新进展,又涉及了目前在供应链和物流研究中相当热门的话题。一起来看看 《遗传算法与工程优化》 这本书的介绍吧!