mesos DRF

dominant resource fairness算法是Mesos的灵魂,不同于hadoop基于slot-based实现的fair scheduler和capacity scheduler,这是一种针对不同资源类型的max-min fairness。首先DRF激励用户去共享资源,如果资源是在用户之间被平均地切分,会保证没有用户会拿到更多资源。其次,DRF 是strategy-proof,用户不能通过欺骗来获取更多地资源分配。然后,RDF是envy-free(非嫉妒),没有一个用户会与其他用户交换资源分配。最后,RDF分配是Pareto efficient,不可能出现既能增加一个用户的资源分配而又不会减少其他用户的资源的情况。

max min fairness算法

最大最小公平分配算法的形式化定义如下:

资源按照需求递增的顺序进行分配
不存在用户得到的资源超过自己的需求
未得到满足的用户等价的分享资源
与之对应的可执行定义:

考虑用户集合1, …, n分别有资源需求x1, x2, …, xn.不失一般性,令资源需求满足x1 <= x2 <= … <= xn.令服务器具有能力C.那么,我们初始把C/n资源给需求最小的用户.这可能会超过用户1的需求,继续处理.该过程结束时,每个用户得到的没有比自己要求更多,而且,如果其需求得不到满足,得到的资源也不会比其他用户得到的最多的资源还少.我们之所以称之为最大最小公平分配是因为我们最大化了资源得不到满足的用户最小分配的资源.

示例1

有一四个用户的集合,资源需求分别是2,2.6,4,5,其资源总能力为10,为其计算最大最小公平分配

解决方法:我们通过几轮的计算来计算最大最小公平分配.第一轮,我们暂时将资源划分成4个大小为2.5的.由于这超过了用户1的需求,这使得剩了0.5个均匀的分配给剩下的3个人资源,给予他们每个2.66.这又超过了用户2的需求,所以我们拥有额外的0.066…来分配给剩下的两个用户,给予每个用户2.5+0.66…+0.033…=2.7.因此公平分配是:用户1得到2,用户2得到2.6,用户3和用户4每个都得到2.7.

Dominant Resource Fairness(DRF)

DRF是一种支持多资源的max-min fair 资源分配机制,其中max表示max{CPU,mem},而min表示min{user1,user2,…}=min{max{CPU1,mem1}, max{CPU2,mem2}, …},其中user代表mesos中的framework,算法伪代码如下图所示:

Image Title

举例说明,假设系统中共有9 CPUs 和18 GB RAM,有两个user(framework)分别运行了两种任务,分别需要的资源量为<1 CPU, 4 GB> 和 <3 CPUs, 1 GB>。对于用户A,每个task要消耗总CPU的1/9和总内存的2/9,因而A的支配性资源为内存;对于用户B,每个task要消耗总CPU的1/3和总内存的1/18,因而B的支配性资源为CPU。DRF将均衡所有用户的支配性资源,即:A获取的资源量为:<3 CPUs,12 GB>,可运行3个task;而B获取的资源量为<6 CPUs, 2GB>,可运行2个task,这样分配,每个用户获取了相同比例的支配性资源,即:A获取了2/3的RAMs,B获取了2/3的CPUs。
DRF算法的一个可能的调度序列如下图所示:

Image Title

DRF算法每次都选择资源请求中具有最小dominant resource的user,然后把资源分配给改用户,更新分配表重复以上过程。

references

http://my.oschina.net/zhengyang841117/blog/184046
http://dongxicheng.org/apache-mesos/mesos-scheduler/