The motivation behind writing this paper is to solve the problem of fairly sharing multiple resources when users have heterogeneous demands in them i.e. each user may have different demand for each resource. The authors propose Dominant Resource Fairness (DRF), a generalization of max-min fairness approach to multiple resource types.
The most widely used allocation policies is max-min fairness, which maximizes the minimum allocation received by a user in the system. For example, if there are 3 users in a system and if one user wants no more than 33%, say 20%, give it to him and divide rest 80% among two other users. This scheduling is used in many different applications like networking (wfq, wf2q, sfq, etc), OS (linux, rr, prop sharing, lottery, etc) and Datacenters (Hadoop capacity scheduling, Hadoop fair scheduling, Quincy, etc). The main drawback of using max-min fair allocation is that it focuses on single resource type. Even in multi resource environments where users have heterogenous resource demands, allocation is done using single resource abstraction.
DRF takes a slightly different approach. It propose that the allocation of a user should be determined by the user’s dominant share, which is maximum share the user has been allocated of any resources. The authors studied the resource usage profiles of tasks in 2000 node cluster at Facebook for over a month and found that there are many tasks which are either CPU heavy and some others which are memory heavy.
DRF works by tracking the total resources allocated to each user as well as the user’s dominant share. At each step, DRF picks the user with lowest dominant share. If there are enough resources to satisfy the user’s demands, one of the user’s tasks are launched.
The strength of DRF is that is satisfies following properties. First, it provides incentives for users to share resources by guaranteeing that no user is better off in a system where everything is statically partitioned. Every user can get at most 1/n of he dominant resources, N is the total number of users. Second, its strategy-proof in which a user cannot get a better allocation by lying about the resource demands. Third, it’s envy-free as no user will prefer the allocation of another user. Finally, it’s Pareto-efficient as it allocates all available resources subject to satisfying the other properties, and without preempting existing allocations.
Link to the paper: https://cs.stanford.edu/~matei/papers/2011/nsdi_drf.pdf
Rishabh Jain's Corner 