算法：最大最小公平算法

当我们管理资源分配时，总是会遇到如下问题：每个用户具有相同的优先级，有的用户需求的资源少，有的用户需求的资源多，我们该如何分配才能尽量保证不会出现“饿死”的情况并保证公平的分配呢？对于这个问题，下面介绍大数据中资源管理利器YARN中的解决方案：最大最小公平算法。

最大最小公平算法的形式化定义：

资源按照需求递增的顺序进行分配

不存在用户得到的资源超过自己的需求

未得到满足的用户等价的分享资源

例：

假设：有4个用户，每个用户需求的资源量分别为A：1，B：2，C：5，D：6，总资源量为10。

第一轮：将10平均分成4份，每份是2.5，由于2.5大于了A的需求，故每个用户首先分得与A相同的资源，即为1，则剩余6。分配情况为：A：1，B：1，C：1，D：1；

第二轮：将剩余资源6平均分成3份，每份为2，累加第一轮分配的资源1，此时B的资源为3，超出了资源需求2。因此此轮每个用户分得1个资源，剩余资源量为3。分配情况为：A：1，B：2，C：2，D：2；

第三轮：将剩余资源3平均分成两份，每份为1.5，此时均小于C与D的资源需求，将1.5分配给剩余用户后，分配结束。此时，分配情况：A：1，B：2，C：3.5，D：3.5。

当用户具有不同权重时，又该如何分配呢？

此时我们可以根据之前的算法扩展到加权情况。

例：

假设：有4个用户，每个用户需求的资源量分别为A：1，B：9，C：6，D：4，权重为1，2，0.5，4，总资源量为15。

首先归一化权重，即将最小权重设为1，则此时权重分别为：2，4，1，8。此时，我们在拆分资源时，则不是平均分成4份，而是首先要根据权值，平均分成2+4+1+8=15份。

第一轮：将15份资源平均分成15份，每份为1，则A分得1x2=2，B分得1x4=4，C分得1x1=1，D分得1x8=8，由于A超出了需求，多出了1，D也超出了需求，多出了4，故剩余资源量为5，分配情况为，A：1，B：4，C：1，D：4；

第二轮：此时剩余B、C没有满足资源需求，其权值分别为4，1。将剩余资源5平均分成4+1=5份，每份为1，此时，B可再分得1x4=4，累加上一轮分得的资源总共为8，D可再分得1x1=1，累加上一轮分得的资源总共为2，C和D均没有满足需求，此时分配结束。总体分配情况为A：1，B：8，C：2，D：4。

最大最小公平被认为是一种很好权衡有效性和公平性的自由分配策略，在YARN中担当重要的资源分配策略。

0 条评论