集群资源管理之 DRF

0. 引言

如果看过我的上一篇关于 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. 资源分配以需求递增的方式进行分配
  2. 每个用户获得的资源不超过其需求
  3. 未得到满足的用户等价平方剩下的资源

更形象的表达如下,有用户 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= ,其中 w_i,_j 表示用户 i 对资源 j 的需求权重,什么意思呢?举个例子,用户对 的权重向量为 <1, 2=""> ,那么则意味着如果用户分到了 1 单位 CPU,则一定能分到 2 单位的 RAM。

除此之外,u_i,_j 表示用户 i 对资源 j 的需求占比,则用户 i 的 dominant resource 计算方式为 s_i = max_j {u_i,_j / w_i,_j} ,也就是全局占比最大的资源,剩下的计算和 DRF 算法类似。

参考

  1. Dominant Resource Fairness: Fair Allocation of Multiple Resource Types
  2. max-min fair share