cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Branimir Lambov (JIRA)" <>
Subject [jira] [Updated] (CASSANDRA-7032) Improve vnode allocation
Date Fri, 09 Jan 2015 16:39:34 GMT


Branimir Lambov updated CASSANDRA-7032:

A work-in-progress algorithm for selecting vnodes in the replicated case is attached. The
main idea of the algorithm is to select token positions for each new vnode in such a way as
to get best improvement in replicated load variance (i.e. standard deviation) across nodes
and vnodes *1. More specifically, it prepares a selection of token positions to try (by picking
the middle positions between existing vnodes *2), evaluates the expected improvement in variance
for each selection and chooses the best *3, continuing until all the vnodes of the new node
have assigned tokens. To improve average performance, the expected improvement for all choices
is calculated once; for the second and later vnode we only recalculate it for the best candidate
until we find one that does not deteriorate to worse than the next option in the list *4.

Tested with simple factor-3 replication, it maintains the following utilization ranges: 
- 1 vnode: 70% - 135%
- 4 vnodes: 80% - 115%
- 16 vnodes: 83 - 106%
- 64 vnodes: 86 - 103%
- 256 vnodes: 87 - 102%

Unlike random allocation, the overutilization does not grow with the number of nodes, and
a much smaller number of vnodes suffice (4 or 8 vnodes would probably be enough for most usecases).

The underutilization for this algorithm is affected less by the number of vnodes; this is
due to the effect of replication on newly added vnodes: they necessarily have to take the
share of one fewer vnode replica than the vnode they split (regardless of the algorithm we
use, if we add a new node to a large enough perfectly balanced cluster where all vnodes are
responsible for the same share of tokens, the new node will necessarily have at most 2/3 (for
RF=3) of the average load.). This could possibly be improved if we manage to keep enough individual
tokens with load closer to RF / (RF - 1), which I've yet to try.

The algorithm is implemented in the {{ReplicationAwareTokenDistributor}} in the attached file.
Running the file simulates the effect of adding nodes using this algorithm on a randomly-generated
cluster and prints out the minimum and maximum per-node and per-token replicated load after
each step, as well as the standard deviation of the load. Sample results:
Random generation of 500 nodes with 8 tokens each
Size 500   node max 1.88 min 0.51 stddev 0.22193
Adding 1 node(s) using ReplicationAwareTokenDistributor
Size 501   node max 1.90 min 0.51 stddev 0.21922    Simple 3 replicas
Adding 4 node(s) using ReplicationAwareTokenDistributor
Size 505   node max 1.63 min 0.51 stddev 0.20580   token max 3.72 min 0.01 stddev 0.58768
   Simple 3 replicas
Adding 15 node(s) using ReplicationAwareTokenDistributor
Size 520   node max 1.51 min 0.53 stddev 0.17369   token max 3.83 min 0.01 stddev 0.54526
   Simple 3 replicas
Adding 105 node(s) using ReplicationAwareTokenDistributor
Size 625   node max 1.15 min 0.63 stddev 0.08069   token max 2.73 min 0.00 stddev 0.40190
   Simple 3 replicas
Adding 375 node(s) using ReplicationAwareTokenDistributor
Size 1000   node max 1.08 min 0.84 stddev 0.03041   token max 1.99 min 0.00 stddev 0.22341
   Simple 3 replicas
Losing 1 nodes
Size 999   node max 1.09 min 0.84 stddev 0.03081   token max 1.98 min 0.00 stddev 0.22429
   Simple 3 replicas
Adding 1 node(s) using ReplicationAwareTokenDistributor
Size 1000   node max 1.08 min 0.84 stddev 0.03019   token max 1.99 min 0.00 stddev 0.22335
   Simple 3 replicas
Losing 5 nodes
Size 995   node max 1.17 min 0.83 stddev 0.03380   token max 2.01 min 0.00 stddev 0.22565
   Simple 3 replicas
Adding 5 node(s) using ReplicationAwareTokenDistributor
Size 1000   node max 1.08 min 0.84 stddev 0.03000   token max 1.99 min 0.00 stddev 0.22181
   Simple 3 replicas
Losing 20 nodes
Size 980   node max 1.19 min 0.88 stddev 0.04362   token max 2.44 min 0.00 stddev 0.23370
   Simple 3 replicas
Adding 20 node(s) using ReplicationAwareTokenDistributor
Size 1000   node max 1.08 min 0.89 stddev 0.02962   token max 1.99 min 0.00 stddev 0.21681
   Simple 3 replicas
Losing 125 nodes
Size 875   node max 1.31 min 0.79 stddev 0.08499   token max 2.81 min 0.00 stddev 0.28763
   Simple 3 replicas
Adding 125 node(s) using ReplicationAwareTokenDistributor
Size 1000   node max 1.08 min 0.90 stddev 0.02805   token max 1.85 min 0.00 stddev 0.19258
   Simple 3 replicas

This is far from finished as it is much slower than I'd like it to be.

Notes / other things I've tried:
 - *1 Only controlling individual vnode load: Because of the replication effect mentioned
above, the ratio between largest and smallest node has to necessarily be at best 3:2 (for
RF=3). If we don't control overall node size, about 30% over/underutilization is the best
we can achieve regardless of vnode count. Moreover, when this is applied to a randomly-generated
cluster, the first few added nodes tend to significantly increase the node overutilization
in the cluster.
 - *1 Only controlling the load of the whole node: This gets better results, but it can enter
pathological states where a large token is never split because that would create an even bigger
new node. The latter happens too often for this option to be useable.
 - *2 Picking a choice of e.g. 4 tokens splitting each existing vnode in 1/5 increments does
not appear to give any noticeable improvement over just picking the middle for RF>1.
 - *3 The evaluation of the expected improvement needs to include a component for the load
on the new node as well. To be able to assign vnodes independently (otherwise the complexity
of the procedure would go out of control) we use the following heuristic: assume the new node
starts at an optimal size, optimally split between the vnodes, and gradually replace this
ideal view with the actual assigned tokens as they come. An additional weight of filled_vnodes/vnode_count
is applied to the new node to allow for greater flexibility in choosing the first tokens,
which helps avoid the pathological cases.
 - *4 This heuristic does not necessarily yield the optimal choice, because assigning a token
changes the expected improvement for the load of the new node for the other candidates and
there is a chance that we will pick a candidate before reaching a better option that has improved
a lot. In practice the heuristic appears to give results that are very close to picking the
actual best candidate.

> Improve vnode allocation
> ------------------------
>                 Key: CASSANDRA-7032
>                 URL:
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Core
>            Reporter: Benedict
>            Assignee: Branimir Lambov
>              Labels: performance, vnodes
>             Fix For: 3.0
>         Attachments:,,,
> 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

View raw message