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, …, 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 CPUs, 1 GB RAM>，则用户 B 的 Dominant Resource 为 CPU。最后 DRF 最求的结果就是平等权利的用户的 Dominant Resource 占的份额是一样的：分配给 A <3 CPUs, 12 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,_1 ,…, w_i,_m> ，其中 w_i,_j 表示用户 i 对资源 j 的需求权重，什么意思呢？举个例子，用户对 <CPU, RAM> 的权重向量为 <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 算法类似。
参考
- Dominant Resource Fairness: Fair Allocation of Multiple Resource Types
- max-min fair share