[
https://issues.apache.org/jira/browse/CASSANDRA-192?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12713213#action_12713213
]
Jonathan Ellis commented on CASSANDRA-192:
------------------------------------------
Citation search results
(http://scholar.google.com/scholar?hl=en&lr=&cites=9360931679730374378).
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: https://issues.apache.org/jira/browse/CASSANDRA-192
> 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:
> 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.")
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
