Dominant resource fairness: fair allocation of multiple resource types

TLDR

Fair resource allocation in systems with multiple resource types and heterogeneous user demands is a challenging problem. To address this problem, we propose Dominant Resource Fairness (DRF), a generalization of max‑min fairness to multiple resource types. DRF generalizes max‑min fairness by ensuring that no user is better off with equal partitioning, is strategy‑proof, envy‑free, Pareto efficient, and has been implemented in Mesos to improve throughput and fairness. DRF satisfies desirable properties such as incentive compatibility, strategy‑proofness, envy‑freedom, Pareto efficiency, and empirically yields higher throughput and fairness than slot‑based fair sharing schemes in current cluster schedulers.

Abstract

We consider the problem of fair resource allocation in a system containing different resource types, where each user may have different demands for each resource. To address this problem, we propose Dominant Resource Fairness (DRF), a generalization of max-min fairness to multiple resource types. We show that DRF, unlike other possible policies, satisfies several highly desirable properties. First, DRF incentivizes users to share resources, by ensuring that no user is better off if resources are equally partitioned among them. Second, DRF is strategy-proof, as a user cannot increase her allocation by lying about her requirements. Third, DRF is envy-free, as no user would want to trade her allocation with that of another user. Finally, DRF allocations are Pareto efficient, as it is not possible to improve the allocation of a user without decreasing the allocation of another user. We have implemented DRF in the Mesos cluster resource manager, and show that it leads to better throughput and fairness than the slot-based fair sharing schemes in current cluster schedulers.