The power-of-two-choices technique can also be used to improve load
balancing in peer-to-peer networks based on \emph{distributed hash tables}. A
distributed hash table is a system for storing and locating data in a
decentralized peer-to-peer network. The basis for many distributed
hash tables is the technique of \emph{consistent
hashing}~\cite{karger97:_consis_hashin_and_random_trees}, where both
data objects and servers are mapped to locations in a circular
identifier space using a common hash function. Then the server that is
the first successor of the key of some data object in the identifier
ring is the one responsible for storing it. Layered atop this is a
\emph{distributed lookup service} such as Chord~\cite{stoica03:_chord}, which
builds a routing topology for the network that makes it possible to
efficiently determine the successor of a given key even as nodes join
and leave the system, and a \emph{distributed hash table} such as
DHash~\cite{dabek04:_desig_dht_for_low} that stores the values
associated with keys.

These systems scale well in general, but direct application of
consistent hashing introduces a problem with load balancing. The
problem is that the servers are assigned essentially randomly to
locations in the ring (assuming a suitable hash function), so the
intervals that each server is responsible for can vary in length. For
$m$ servers, the expected size of the interval for each server is
$\frac{1}{m}$ of the ring, indicating that load is distributed
equally. However, this only holds in expectation; we can only
guarantee with high probability that each server receives $\frac{\log
  m}{m}$ of the total load. Indeed, with high probability there is at
least one server with $\bigTheta{\frac{\log m}{m}}$ load, and at least
one with $\bigTheta{\frac{1}{m^2}} $
load~\cite{byers04:_geomet_gener_of_power_of_two_choic}.

The standard solution to this problem is to have each node operate
$\bigTheta{\log m}$ ``virtual nodes,'' which guarantees with high
probability that no node will be responsible for more than a
$\bigO{\frac{1}{m}}$ fraction of the ring in total. However, when
applying this technique to a distributed hash table, this increases
the complexity of the routing layer. Without virtual nodes, each Chord
node maintains $\bigTheta{\log m}$ pointers to other nodes in the ring
in order to achieve its $\bigO{\log m}$-message lookup
operations~\cite{stoica03:_chord}. If each node is now operating
$\bigTheta{\log m}$ virtual nodes, however, it will need to maintain a
routing table for each one, thereby requiring a total of
$\bigTheta{\log^2 m}$ pointers to other nodes. This is an important
increase, since increasing the routing table size means increasing the
amount of maintenance traffic required to ensure that all pointers are
up to date even as nodes join and leave.

Byers et.\ al.\ propose using the power of two choices instead of
virtual nodes in order to achieve load balancing in distributed hash
tables based on consistent hashing
\cite{byers03:_simpl_load_balan_for_distr_hash_tables}. Their solution
is simple, straightforward, and achieves similar performance to the
virtual nodes approach, without the additional routing overhead. They
propose simply allowing each data object to map to $d$ keys rather
than 1, then choosing the least loaded of the $d$ to store the data
on. This does increase the cost to perform a query because now $d$
nodes must be contacted in order to find the data. The authors propose
addressing this problem by storing redirection pointers at each of the
$d-1$ nodes that an item hashes on which it is not stored; the
redirection pointers are small compared to the data, so there is not
much storage cost, though a maintenance cost is incurred in keeping
these up to date in the presence of churn.

\begin{theorem}
  The $d$-choices approach for load balancing in Chord ensures that,
  with high probability,
  the maximum load on any node is no more than $\log_d \log m +
  \bigO{1}$ times greater than the $\frac{1}{m}$ expected value.
\end{theorem}

\begin{proof}
  By application of the geometric generalization in
  Section~\ref{sec:variations:geometry}.
\end{proof}

Applying V\"{o}cking's \proc{Always-Go-Left} asymmetric tie-breaking
scheme, described in Section~\ref{sec:variations:asymmetry}, improves
this bound to $\frac{\log \log m}{d} + \bigO{1}$. In practice, the
authors suggest breaking ties by choosing the server responsible for
the shortest arc of the identifier space in the ring, since it is the
least likely to be selected by hashing when future items are added.
There exists no theoretical analysis of this tie-breaking strategy,
but simulation results have shown that it leads to the best
performance in practice. Indeed, using only two choices and this
tie-breaking rule provides better load-balancing performance in
simulation than the standard approach of using $\floor{\log_2 m}$
virtual nodes.
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "paper"
%%% End: