  Designing algorithms for balanced allocation of clients to servers in dynamic
settings is a challenging problem for a variety of reasons. Both servers and
clients may be added and/or removed from the system periodically, and the main
objectives of allocation algorithms are: the uniformity of the allocation, and
the number of moves after adding or removing a server or a client. The most
popular solution for our dynamic settings is Consistent Hashing. However, the
load balancing of consistent hashing is no better than a random assignment of
clients to servers, so with $n$ of each, we expect many servers to be
overloaded with $\Theta(\log n/ \log\log n)$ clients. In this paper, with $n$
clients and $n$ servers, we get a guaranteed max-load of 2 while only moving an
expected constant number of clients for each update.
  We take an arbitrary user specified balancing parameter $c=1+\epsilon>1$.
With $m$ balls and $n$ bins in the system, we want no load above $\lceil
cm/n\rceil$. Meanwhile we want to bound the expected number of balls that have
to be moved when a ball or server is added or removed. Compared with general
lower bounds without capacity constraints, we show that in our algorithm when a
ball or bin is inserted or deleted, the expected number of balls that have to
be moved is increased only by a multiplicative factor $O({1\over \epsilon^2})$
for $\epsilon \le 1$ (Theorem 4) and by a factor $1+O(\frac{\log c}c)$ for
$\epsilon\ge 1$ (Theorem 3). Technically, the latter bound is the most
challenging to prove. It implies that we for superconstant $c$ only pay a
negligible cost in extra moves. We also get the same bounds for the simpler
problem where we instead of a user specified balancing parameter have a fixed
bin capacity $C$ for all bins.
