Dominant resource fairness (DRF) is a rule for
fair division
Fair division is the problem in game theory of dividing a set of resources among several people who have an Entitlement (fair division), entitlement to them so that each person receives their due share. The central tenet of fair division is that ...
. It is particularly useful for dividing computing resources in among users in
cloud computing
Cloud computing is "a paradigm for enabling network access to a scalable and elastic pool of shareable physical or virtual resources with self-service provisioning and administration on-demand," according to International Organization for ...
environments, where each user may require a different combination of resources. DRF was presented by
Ali Ghodsi,
Matei Zaharia, Benjamin Hindman, Andy Konwinski,
Scott Shenker
Scott J. Shenker (born January 24, 1956) is an American computer scientist, and professor of computer science at the University of California, Berkeley. He is also the leader of the Extensible Internet Group at the International Computer Science ...
and
Ion Stoica
Ion Stoica (born ) is a Romanian–American computer scientist specializing in distributed systems, cloud computing and computer networking. He is a professor of computer science at the University of California, Berkeley and co-director of AMPL ...
in 2011.
Motivation
In an environment with a single resource, a widely used criterion is
max-min fairness
In communication networks, multiplexing and the division of scarce resources, max-min fairness is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any participant necessari ...
, which aims to maximize the minimum amount of resource given to a user. But in cloud computing, it is required to share different types of resource, such as: memory, CPU, bandwidth and disk-space. Previous fair schedulers, such as in
Apache Hadoop
Apache Hadoop () is a collection of open-source software utilities for reliable, scalable, distributed computing. It provides a software framework for distributed storage and processing of big data using the MapReduce programming model. Hadoop wa ...
, reduced the multi-resource setting to a single-resource setting by defining ''nodes'' with a fixed amount of each resource (e.g. 4 CPU, 32 MB memory, etc.), and dividing ''slots'' which are fractions of nodes. But this method is inefficient, since not all users need the same ratio of resources. For example, some users need more CPU whereas other users need more memory. As a result, most tasks either under-utilize or over-utilize their resources.
DRF solves the problem by maximizing the minimum amount of the ''dominant resource'' given to a user (then the second-minimum etc., in a
leximin order
In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division.
Definition
A vec ...
). The dominant resource may be different for different users. For example, if user A runs CPU-heavy tasks and user B runs memory-heavy tasks, DRF will try to equalize the CPU share given to user A and the memory share given to user B.
Definition
There are ''m'' resources. The total capacities of the resources are ''r''
1,...,''r
m''.
There are ''n'' users. Each users runs individual ''tasks''. Each task has a ''demand-vector'' (''d''
1,..,''d
m''), representing the amount it needs of each resource. It is implicitly assumed that the utility of a user equals the number of tasks he can perform. For example, if user A runs tasks with demand-vector
CPU, 4 GB RAM and receives 3 CPU and 8 GB RAM, then his utility is 2, since he can perform only 2 tasks. More generally, the utility of a user receiving ''x''
1,...,''x
m'' resources is min''
j''(''x
j''/''d
j''), that is, the users have
Leontief utilities In economics, especially in consumer theory, a Leontief utility function is a function of the form:
u(x_1,\ldots,x_m)=\min\left\ .
where:
* m is the number of different goods in the economy.
* x_i (for i\in 1,\dots,m) is the amount of good i in the ...
.
The demand-vectors are normalized to fractions of the capacities. For example, if the system has 9 CPUs and 18 GB RAM, then the above demand-vector is normalized to
/9 CPU, 2/9 GB For each user, the resource with the highest demand-fraction is called the ''dominant resource''. In the above example, the dominant resource is memory, as 2/9 is the largest fraction. If user B runs a task with demand-vector
CPU, 1 GB which is normalized to
/3 CPU, 1/18 GB then his dominant resource is CPU.
DRF aims to find the maximum x such that all agents can receive at least x of their dominant resource. In the above example, this maximum x is 2/3:
* User A gets 3 tasks, which require 3/9 CPU and 2/3 GB.
* User B gets 2 tasks, which require 2/3 CPU and 1/9 GB.
The maximum x can be found by solving a linear program; see
Lexicographic max-min optimization
Lexicographic max-min optimization (also called lexmaxmin or leximin or leximax or lexicographic max-ordering optimization) is a kind of multi-objective optimization. In general, multi-objective optimization deals with optimization problems with tw ...
. Alternatively, the DRF can be computed sequentially.
The algorithm tracks the amount of dominant resource used by each user. At each round, it finds a user with the smallest allocated dominant resource so far, and allocates the next task of this user. Note that this procedure allows the same user to run tasks with different demand vectors.
Properties
DRF has several advantages over other policies for resource allocation.
#
Proportionality: each user receives at least as much resources as they could get in a system in which all resources are partitioned equally among users (the authors call this condition "sharing incentive").
#
Strategyproofness
In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly- dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have privat ...
: a user cannot get a larger allocation by lying about his needs. Strategyproofness is important, as evidence from cloud operators show that users try to manipulate the servers in order to get better allocations.
#
Envy-freeness
Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by ...
: no user would prefer the allocation of another user.
#
Pareto efficiency
In welfare economics, a Pareto improvement formalizes the idea of an outcome being "better in every possible way". A change is called a Pareto improvement if it leaves at least one person in society better off without leaving anyone else worse ...
: no other allocation is better for some users and not worse for anyone.
#
Population monotonicity: when a user leaves the system, the allocations of remaining users do not decrease.
When there is a single resource that is a
bottleneck resource (highly demanded by all users), DRF reduces to
max-min fairness
In communication networks, multiplexing and the division of scarce resources, max-min fairness is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any participant necessari ...
.
However, DRF violates
resource monotonicity
Resource monotonicity (RM; aka aggregate monotonicity) is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM pri ...
: when resources are added to the system, some allocations might decrease.
Extensions
''Weighted DRF'' is an extension of DRF to settings in which different users have different weights (representing their different
entitlements
An entitlement is a government program guaranteeing access to some benefit by members of a specific group and based on established rights or by legislation. A "right" is itself an entitlement associated with a moral or social principle, while an ...
).
Parkes,
Procaccia and Shah formally extend weighted DRF to a setting in which some users do not need all resources (that is, they may have demand 0 to some resource). They prove that the extended version still satisfies proportionality, Pareto-efficiency, envy-freeness, strategyproofness, and even
Group strategyproof
In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly-dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private ...
ness. On the other hand, they show that DRF may yield poor utilitarian social welfare, that is, the sum of utilities may be only 1/''m'' of the optimum. However, they prove that ''any'' mechanism satisfying one of proportionality, envy-freeness or strategyproofness may suffers from the same low utilitarian welfare. They also extend DRF to the setting in which the users' demands are indivisible (as in
fair item allocation
Fair item allocation is a kind of the fair division problem in which the items to divide are ''discrete'' rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be gi ...
). For the indivisible setting, they relax envy-freeness to EF1. They show that strategyproofness is incompatible with PO+EF1 or with PO+proportionality. However, a mechanism called SequentialMinMax satisfies efficiency, proportionality and EF1.
Wang, Li and Liang
present DRFH - an extension of DRF to a system with several heterogeneous servers.
Implementation
DRF was first implemented in
Apache Mesos
Apache Mesos is an Open-source software, open-source project to manage computer clusters. It was developed at the University of California, Berkeley.
History
Mesos began as a research project in the UC Berkeley RAD Lab by then PhD students Benja ...
- a cluster resource manager, and it led to better throughput and fairness than previously used fair-sharing schemes.
See also
*
Round-robin scheduling
Round-robin (RR) is one of the algorithms employed by process and network schedulers in computing. Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, , 2016.
As the term ...
*
Weighted fair queueing
*
Max-min fairness
In communication networks, multiplexing and the division of scarce resources, max-min fairness is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any participant necessari ...
References
{{Reflist
Fair division protocols
Cloud computing
Network scheduling algorithms