[CASSANDRA-192] Load balancing

• Type: New Feature
• Status: Resolved
• Priority: Normal
• Resolution: Fixed
• Fix Version/s: 0.5
• Assignee: Jonathan Ellis
• Reporter: Jonathan Ellis

Authors

Jonathan Ellis

• Created: 21/May/09 19:45
• Updated: 16/Apr/19 09:33
• Resolved: 15/Nov/09 00:21

Description

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: http://groups.google.com/group/cassandra-dev/msg/b3d67acf35801c41

Of these, the useful ones are
http://www.iptps.org/papers-2004/karger-load-balance.pdf (Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems by David R. Karger and Matthias Ruhl)
http://iptps03.cs.berkeley.edu/final-papers/load_balancing.ps (Load Balancing in Structured P2P Systems by Ananth Rao et al)

The third,
http://iptps03.cs.berkeley.edu/final-papers/simple_load_balancing.ps (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.")

Issue Links

• is blocked by: CASSANDRA-242 Implement method to "evenly" split a Range
• is blocked by: CASSANDRA-435 unbootstrap