Fair Resource Distribution Algorithm
This project provides an implementation of the
fairdist algorithm, a way to distribute a set
of resources fairly amongst a dynamic number of users. Its infrastructure manages a hierarchy
of users that currently hold shares of a resource. New users can be added at any time, and
charges can be requested and released dynamically. The system ensures that every new user
joining the system gets a guaranteed share of the total, regardless of how many users already
The API abstracts over resources through the
[counter::Counter] trait. This trait represents
a set of numeric resource counters. In most cases these will just be
However, that is not a requirement. The resource counter is only required to "look like an
[counter::Counter] and its dependencies on the
num crate). Furthermore, the
API abstracts over users. It does not track users who interact with the system, but relies on
the API user to provide a key or index that identifies the user of a given operation. This way
the resource allocators can tell whether separate operations are performed by the same
accounting user, or whether they are different. This is all information the system needs about
the different users.
At the root level, the API user has to create a
[Resource] object with the resource counters
initialized to reflect the total resources available for distribution. These resources can now
be requested through
[Charge] objects. Charges are RAII-type objects that record a resource
charge and make sure resources are released again when the
Charge is dropped. To request
resources, the API user must specify the accounting user to perform the charge as, as well as
the amount to charge. If the quotas of the accounting user were exceeded, the charge is
rejected. Otherwise, the charge will be granted. The allocators behind the resource objects
make sure resources are distributed fairly. Additionally to the root-level
objects, the API allows to create sub-hierarchies to redistribute resources further. That is,
[Resource] objects can be created given the accounting user to act as.
This new sub-resource will then behave similar to the top-level resource and allow charges to
be performed. It will ensure the same guarantees on its own sub-level, so the sub-distribution
is again fair. Furthermore, the top-level guarantees are unaffected by sub-hierarchies that
are formed. That is, individual accounting users cannot increase their resource shares by
There are multiple possible algorithm that can be used for the individual allocations. In most
cases the selected default is sufficient. However, the
[allocator::Allocator] trait allows
selecting from a range of predefined allocators, as well as creating individual allocators.
The default allocator guarantees quasilinear shares to every user of the system. In
particular, this means regardless how many users join the allocation system, each one is
guaranteed a share of 1 over
O(n * log(n)^2) of the total.
Abstract representation of a multi-dimensional resource counter.
A charge represents temporarily borrowed resources.
A resource that can be distributed amongst users.
A subscription to a resource.