[
https://issues.apache.org/jira/browse/CASSANDRA-7032?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14394730#comment-14394730
]
Benedict edited comment on CASSANDRA-7032 at 4/3/15 6:22 PM:
-------------------------------------------------------------
One other thing to consider optimising for: hash bit distribution. A lot of
algorithmic optimisations can be made if we can assume each node has an
approximately uniform distribution of hash bits. We should introduce some
scoring based on this. e.g. try the best N candidates by our current
evaluation, and select the one that delivers the best resulting hash bit
distribution. I've filed CASSANDRA-9115 as a follow up ticket to investigate
this.
We can file a ticket for the anti-clumping if we decide this is too onerous to
introduce now (although I think it just requires a little bit of thought to
ensure the filtering is helpful and safe, since implementing the filtration
should be relatively easy)
was (Author: benedict):
One other thing to consider optimising for: hash bit distribution. A lot of
algorithmic optimisations can be made if we can assume each node has an
approximately uniform distribution of hash bits. We should introduce some
scoring based on this. e.g. try the best N candidates by our current
evaluation, and select the one that delivers the best resulting hash bit
distribution.
> Improve vnode allocation
> ------------------------
>
> Key: CASSANDRA-7032
> URL: https://issues.apache.org/jira/browse/CASSANDRA-7032
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Benedict
> Assignee: Branimir Lambov
> Labels: performance, vnodes
> Fix For: 3.0
>
> Attachments: TestVNodeAllocation.java, TestVNodeAllocation.java,
> TestVNodeAllocation.java, TestVNodeAllocation.java, TestVNodeAllocation.java,
> TestVNodeAllocation.java
>
>
> It's been known for a little while that random vnode allocation causes
> hotspots of ownership. It should be possible to improve dramatically on this
> with deterministic allocation. I have quickly thrown together a simple greedy
> algorithm that allocates vnodes efficiently, and will repair hotspots in a
> randomly allocated cluster gradually as more nodes are added, and also
> ensures that token ranges are fairly evenly spread between nodes (somewhat
> tunably so). The allocation still permits slight discrepancies in ownership,
> but it is bound by the inverse of the size of the cluster (as opposed to
> random allocation, which strangely gets worse as the cluster size increases).
> I'm sure there is a decent dynamic programming solution to this that would be
> even better.
> If on joining the ring a new node were to CAS a shared table where a
> canonical allocation of token ranges lives after running this (or a similar)
> algorithm, we could then get guaranteed bounds on the ownership distribution
> in a cluster. This will also help for CASSANDRA-6696.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
