cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jonathan Ellis (JIRA)" <>
Subject [jira] Commented: (CASSANDRA-192) Load balancing
Date Tue, 26 May 2009 19:54:45 GMT


Jonathan Ellis commented on CASSANDRA-192:

Citation search results (

Short version: Mercury section 4.4 and 5.5 are pertinent.  The rest is not.

"Mercury: Supporting scalable multi-attribute range queries:" Leave/join based load-balancing,
basically Case 2 of Ruhl's algorithm.  They conclude that alpha=2 represents perhaps the best
tradeoff of convergence (time to stop balancing) vs actual load ratio achieved, where "a node
is said to be lightly loaded if the ratio of its local load to average load is less than 1/alpha
and heavily loaded if the ratio is greater than alpha."  Most of the paper is spent describing
how by random sampling each node can build a histogram of load distribution in the cluster.

"Online balancing of range-partitioned data with applications to peer-to-peer systems:" weird
mix of single-point-of-failure and p2p system design.  LB algorithm is designed to be run
for each update/delete.

"One torus to rule them all: multi-dimensional queries in P2P systems:" classic overlay network
design for large volume of node churn.  Proposes SCRAP and MURK (better acronyms than most).
 SCRAP allows MD queries by mapping to a single dimension e.g. by z-ordering.  MURK uses kd-trees.
 Only concerned with routing LB (a non-issue for us).

"A case study in building layered DHT applications:" builds prefix hash trees on top of OpenDHT
for geographic range queries.  They started with the goal of using an unmodified DHT out of
the box, but had to add atomic operations to it.  The layering approach resulted in query
latency of up to 2s.  Not exactly a vindication of their approach.  Doesn't deal with LB.

"Load balancing and locality in range-queriable data structures:" pointer-based rather than
token-based routing.  Bucketized keys for range queries.  Per-update/delete balancing.

"Heterogeneity and load balance in distributed hash tables:" leave/join virtual node-based
LB in an overlay-linked DHT, with the twist that virtual node tokens are not random but picked
to mitigate the extra cost the virtual nodes add to the overlay links.  Assumes load is uniformly
distributed over key space.

> Load balancing
> --------------
>                 Key: CASSANDRA-192
>                 URL:
>             Project: Cassandra
>          Issue Type: New Feature
>            Reporter: Jonathan Ellis
>             Fix For: 0.4
> We need to be able to spread load evenly across a cluster to mitigate keys not being
uniformly distributed as well as heterogeneous nodes in a cluster.  The former is particularly
likely to be a problem when using the OrderPreservingPartitioner, since the keys are not randomized
by a hash function.
> Avinash suggested three papers on load balancing in this thread:
> Of these, the useful ones are
> (Simple Efficient Load Balancing
Algorithms for Peer-to-Peer Systems by David R. Karger and Matthias Ruhl)
> (Load Balancing in Structured
P2P Systems by Ananth Rao et al)
> The third, 
> (Simple Load Balancing
for Distributed Hash Tables by John Byers et al) is not applicable to Cassandra's design.
 ("First, we suggest the direct application of the 'power of two choices' paradigm, whereby
an item is stored at the less loaded of two (or more) random alternatives. We then consider
how associating a small constant number of hash values with a key can naturally be extended
to support other load balancing strategies.")

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

View raw message