1 最大最小公平算法(Max-Min Fairness)

首先考虑一个简单的情况(不带权重)，假设资源总量为S，有n个用户，他们的资源需求分别是r1, r2, …, rn，并且r1<r2<…<rn。

一个简单粗暴的想法是先给资源需求量最小的用户，然后再给次小的，依次类推，但是这样可能会导致需求量大的用户很难获得资源。
或者，按照相反的方向，先给大的，后给小的，但是这样可能会导致很多需求小的用户很难获得资源。

以上两种方法都是有失公平的。

这时就引入了**Max-Min Fairness(最大最小公平算法)**：

将资源平分成n份,每份都是S/n,把每份分给相应的用户
如果超过了用户的需求，就回收超过的部分
然后把总体回收的资源，平均分给上一轮分配中尚未得到满足的用户，依次类推，直到没有回收的资源为止

或者，还有另外一种说法

将资源S/n分配给需求最小的用户1，然后将超出需求的部分a回收，如果没有超出需求，那么a=0
当前剩余的资源总量为S’=S-(S/n)+a，然后把S’/(n-1)分配给需求最小的用户2，将超出需求的部分a’回收，如果没有超出需求，那么a’=0
当前剩余的资源问题为S’’=S’-(S’/(n-1))+a’，然后依次类推，直接分配给最后一个用户为止。

以上两种说法，最终达到的效果是一样的。

2 加权最大最小公平算法(Weighted Max-Min Fairness)

接下来考虑一个稍微复杂一点的情况，带权重的情况。假设资源总量为S，有n个用户，他们的资源需求分别是r1, r2, …, rn，且有r1<r2<…<rn，并且他们的优先级权重不同，分别是w1，w2, … , wn。

加权是一种更加常见的场景，比如同样都是作业，但是有些作业的优先级更高一些，有些作业的优先级更低一些，权重就是优先组的量化的表达。

原生的最大最小公平算法其实是加权的一种特例，在这种场景下，所有用户的权重是相同的。这里只需要对最大最小公平算法略作修改，即可支持加权：

令W=w1 + w2+ … + wn, 将资源按照权重分成n份，每份分别是：S*w1/W, S*w2/W,…, S*wn/W。把每份分给相应的用户。
如果超过了用户的需求，就回收超过的部分，假设有m个用户尚未得到满足
然后把总体回收的资源，按照目前尚未满足的用户的权重分成m份，给对应的用户。依次类推，直到没有回收的资源为卡。

3 主资源公平调度算法(Dominant Resource Fairness)

接下来，考虑另一个稍微复杂一点的情况，不带权重，但是资源是多维度的。假设资源总量为(S1,S2,…,Sm)，其中每个数字代表不同维度的资源总量。有n个用户，他们的资源需求的单位分别是(r11,r12,…,r1m),(r21,r22,…,r2m),…,(rn1,rn2,…,rnm)
。

主资源：用户申请的各个维度的资源无法直接比较大小，但是有一点可以比较，就是用户申请的各个维度的资源占其维度上的资源总量的百分比，主资源公平调度算法(Dominant Resource Fairness, DRF)中认为用户申请的一个资源单位中的各个维度中占维度资源总量百分比最大的是用户的主资源
share值：用户分得的主资源累积值占其维度资源总量的百分比

资源分配过程：每次进行资源分配时，先比较一下各个用户当前占据的share，找到share值最小的，分配一个资源单位，然后依次类推。

4 加权主资源公平调度算法(Weighted Dominant Resource Fairness)

接下来，考虑一个最为复杂也是最通用的情况，带权重，资源也是多维度的。假设资源总量为(S1,S2,…,Sm)，其中每个数字代表不同维度的资源总量。有n个用户，他们的资源需求的单位分别是(r11,r12,…,r1m),(r21,r22,…,r2m),…,(rn1,rn2,…,rnm)
，并且他们的优先级权重不同，分别是w1，w2, … , wn。

原生的主资源公平调度算法其实是加权的一种特例，在这种场景下，所有用户的权重都是相同的。这里只需要略作修改，即可以支持加权：

主资源：与主资源公平调度算法中的主资源逻辑保持不变。
share值：用户分得的主资源累积值占其维度资源总量的百分比，再除以用户的权重占整体权重的百分比。

资源分配过程：与主资源公平调度算法中的资源分配过程相同。

后记：

从网上查了好久，没有一篇好的博客能把最大最小公平算法和DRF和权重的关系讲清楚，于是自己写了一篇。
后面争取尽快把yarn中的FairScheduler的整体分析写出来。