RFC: Cassandra Virtual Nodes

[Sam Overton <sa...@acunu.com>]

Hello cassandra-dev,

This is a long email. It concerns a significant change to Cassandra, so
deserves a thorough introduction.

*The summary is*: we believe virtual nodes are the way forward. We would
like to add virtual nodes to Cassandra and we are asking for comments,
criticism and collaboration!

Cassandra's current partitioning scheme is sub-optimal for bootstrap,
decommission, repair and re-balance operations, and places the burden on
users to properly calculate tokens (a common cause of mistakes), which is a
recurring pain-point.

Virtual nodes have a variety of benefits over the one-to-one mapping of
host to key range which Cassandra currently supports.

Among these benefits are:

* Even load balancing when growing and shrinking the cluster
A virtual node scheme ensures that all hosts in a cluster have an even
portion of the total data, and a new node bootstrapped into the cluster
will assume its share of the data. Doubling, or halving the cluster to
ensure even load distribution would no longer be necessary.

* Distributed rebuild
When sizing a cluster, one of the considerations is the amount of time
required to recover from a failed node. This is the exposure time, during
which a secondary failure could cause data loss. In order to guarantee an
upper bound on the exposure time, the amount of data which can be stored on
each host is limited by the amount of time taken to recover the required
replica count. At Acunu we have found that the exposure time is frequently
the limiting factor which dictates the maximum allowed node size in
customers' clusters.

Using a virtual node scheme, the data stored on one host is not replicated
on just RF-1 other physical hosts. Each virtual node is replicated to RF-1
other virtual nodes which may be on a different set of physical hosts to
replicas of other virtual nodes stored on the same host. This means data
for one host is replicated evenly across the entire cluster.

In the event of a failure then, restoring the replica count can be done in
a fully distributed way. Each host in the cluster participates in the
rebuild, drastically reducing the exposure time, allowing more data to be
stored on a single host while still maintaining an acceptable upper bound
on the likelihood of secondary failure. This reduces TCO concerns.

* Greater failure tolerance in streaming
Operations which require streaming of a large range of data, eg. bootstrap,
decommission, repair, etc. incur a heavy cost if an error (eg. dropped
network connection) is encountered during the streaming. Currently the
whole range must be re-streamed, and this could constitute a very large
amount of data. Virtual nodes reduce the impact of streaming failures,
since each virtual node is a much smaller range of the key-space, so
re-streaming a whole virtual node is a much cheaper process.

* Evenly distributed impact of streaming operations
Streaming operations such as bootstrap, repair, et al. would involve every
node in the cluster. This would distribute the load of these operations
across the whole cluster, and could be staggered so that only a small
subset of nodes were affected at once, similar to staggered repair[1].

* Possibility for active load balancing
Load balancing in Cassandra currently involves moving a token to
increase/reduce the amount of key-space for which a host is responsible.
This only allows load balancing between neighbouring nodes, so it could
involve moving more than one token just to redistribute a single overloaded
node. Virtual nodes could allow load balancing on a much finer granularity,
so heavily loaded portions of the key-space could be redistributed to
lighter-loaded hosts by reassigning one or more virtual nodes.


Implementing a virtual node scheme in Cassandra is not an insignificant
amount of work, and it will touch a large amount of the codebase related to
partitioning, placement, routing, gossip, and so on. We do believe that
this is possible to do incrementally, and in such a way that there is an
easy upgrade path for pre-virtual-node deployments.

It would not however touch the storage layer. The virtual node concept is
solely for partitioning and placement, not for segregating the data storage
of the host, so all keys for all virtual nodes on a host would be stored in
the same SSTables.

We are not proposing the adoption of the same scheme used by Voldemort[2]
and described in the Dynamo paper[3]. We feel this scheme is too different
from Cassandra's current distribution model to be a viable target for
incremental development. Their scheme also fixes the number of virtual
nodes for the lifetime of the cluster, which can prove to be a ceiling to
scaling the cluster if the virtual nodes grow too large.

The proposed design is:
* Assign each host T random tokens.
* A partition is assigned to a host for each of its tokens, where the
partition is defined by the interval between a token and the previous token
on the ring.
* When a host joins the ring it is assigned T random tokens which will
result in a portion of an existing partition being assigned to that host.
* When a host leaves the ring it relinquishes its tokens which will result
in its partitions becoming part of the neighbouring partitions.

This is just a basic extension of Cassandra's existing distribution model,
where instead of having 1 token per host, there are many tokens per host.
It is the same scheme used by libketama[4] for consistent hashing among
memcached instances, and is also the original scheme used by Dynamo as
described in [3] before they migrated to their current scheme with fixed
partitions.

The random assignment of tokens may seem unintuitive given that currently
in Cassandra a random token assigment leads to an unbalanced cluster. With
many virtual nodes, a random token assignment leads to load being evenly
balanced across the hosts in the cluster with high probability. As the
number of virtual nodes is increased, the variance in load across hosts
decreases, as demonstrated by simulation in [5].

This scheme has the following properties - (where N is the number of hosts
and B is the total data stored in the cluster):
* placement metadata size is O(N) which is the same as in Cassandra
currently
* partition size is O(B/N) so as data is inserted, if individual partitions
become too large then adding nodes to the cluster reduces this.
* the strategy shares the following properties in common with Cassandra
currently
** tokens are randomly assigned
** partitioning is determined by placement (and vice-versa)
** no two nodes may share the same token
** when a node leaves the ring, all of its tokens are removed - there is no
exchanging of partitions between nodes

One design concern is that replicas of a key range are not stored on the
same physical host, as failure of that host could cause the loss of more
than one replica of the data. This will be achieved by using a placement
strategy very similar the the existing NetworkTopologyStrategy, which
treats each individual host the same way as NTS treats a rack - that is
replicas are not assigned to two hosts on the same rack.

I will shortly create a ticket in JIRA to track discussion of this design.
We have also done some simulation of this scheme to observe the load
balancing properties, node size distribution, cluster resizing and so on. I
will attach some results of this simulation to the JIRA ticket in due
course.

We are keen to get the ball rolling on this and we look forward to your
input, ideas and recommendations.

Best Regards,

Sam Overton

[1] Staggering repair: https://issues.apache.org/jira/browse/CASSANDRA-3721
[2] Project Voldemort, Design: http://project-voldemort.com/design.php
[3] Dynamo:
http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
[4] Ketama: Consistent Hashing:
http://www.audioscrobbler.net/development/ketama/
[5] Consistent Hashing:
http://www.lexemetech.com/2007/11/consistent-hashing.html

-- 
Sam Overton
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Jonathan Ellis <jb...@gmail.com>]

A friend pointed out to me privately that I came across pretty harsh
in this thread.  While I stand by my technical concerns, I do want to
acknowledge that Sam's proposal here indicates a strong grasp of the
principles involved, and a deeper level of thought into the issues
than I think anyone else has brought to date.  Thanks for putting that
energy into it, Sam, and I look forward to seeing how you approach the
implementation.

On Fri, Mar 16, 2012 at 6:38 PM, Sam Overton <sa...@acunu.com> wrote:
> Hello cassandra-dev,
>
> This is a long email. It concerns a significant change to Cassandra, so
> deserves a thorough introduction.
>
> *The summary is*: we believe virtual nodes are the way forward. We would
> like to add virtual nodes to Cassandra and we are asking for comments,
> criticism and collaboration!
>
> Cassandra's current partitioning scheme is sub-optimal for bootstrap,
> decommission, repair and re-balance operations, and places the burden on
> users to properly calculate tokens (a common cause of mistakes), which is a
> recurring pain-point.
>
> Virtual nodes have a variety of benefits over the one-to-one mapping of
> host to key range which Cassandra currently supports.
>
> Among these benefits are:
>
> * Even load balancing when growing and shrinking the cluster
> A virtual node scheme ensures that all hosts in a cluster have an even
> portion of the total data, and a new node bootstrapped into the cluster
> will assume its share of the data. Doubling, or halving the cluster to
> ensure even load distribution would no longer be necessary.
>
> * Distributed rebuild
> When sizing a cluster, one of the considerations is the amount of time
> required to recover from a failed node. This is the exposure time, during
> which a secondary failure could cause data loss. In order to guarantee an
> upper bound on the exposure time, the amount of data which can be stored on
> each host is limited by the amount of time taken to recover the required
> replica count. At Acunu we have found that the exposure time is frequently
> the limiting factor which dictates the maximum allowed node size in
> customers' clusters.
>
> Using a virtual node scheme, the data stored on one host is not replicated
> on just RF-1 other physical hosts. Each virtual node is replicated to RF-1
> other virtual nodes which may be on a different set of physical hosts to
> replicas of other virtual nodes stored on the same host. This means data
> for one host is replicated evenly across the entire cluster.
>
> In the event of a failure then, restoring the replica count can be done in
> a fully distributed way. Each host in the cluster participates in the
> rebuild, drastically reducing the exposure time, allowing more data to be
> stored on a single host while still maintaining an acceptable upper bound
> on the likelihood of secondary failure. This reduces TCO concerns.
>
> * Greater failure tolerance in streaming
> Operations which require streaming of a large range of data, eg. bootstrap,
> decommission, repair, etc. incur a heavy cost if an error (eg. dropped
> network connection) is encountered during the streaming. Currently the
> whole range must be re-streamed, and this could constitute a very large
> amount of data. Virtual nodes reduce the impact of streaming failures,
> since each virtual node is a much smaller range of the key-space, so
> re-streaming a whole virtual node is a much cheaper process.
>
> * Evenly distributed impact of streaming operations
> Streaming operations such as bootstrap, repair, et al. would involve every
> node in the cluster. This would distribute the load of these operations
> across the whole cluster, and could be staggered so that only a small
> subset of nodes were affected at once, similar to staggered repair[1].
>
> * Possibility for active load balancing
> Load balancing in Cassandra currently involves moving a token to
> increase/reduce the amount of key-space for which a host is responsible.
> This only allows load balancing between neighbouring nodes, so it could
> involve moving more than one token just to redistribute a single overloaded
> node. Virtual nodes could allow load balancing on a much finer granularity,
> so heavily loaded portions of the key-space could be redistributed to
> lighter-loaded hosts by reassigning one or more virtual nodes.
>
>
> Implementing a virtual node scheme in Cassandra is not an insignificant
> amount of work, and it will touch a large amount of the codebase related to
> partitioning, placement, routing, gossip, and so on. We do believe that
> this is possible to do incrementally, and in such a way that there is an
> easy upgrade path for pre-virtual-node deployments.
>
> It would not however touch the storage layer. The virtual node concept is
> solely for partitioning and placement, not for segregating the data storage
> of the host, so all keys for all virtual nodes on a host would be stored in
> the same SSTables.
>
> We are not proposing the adoption of the same scheme used by Voldemort[2]
> and described in the Dynamo paper[3]. We feel this scheme is too different
> from Cassandra's current distribution model to be a viable target for
> incremental development. Their scheme also fixes the number of virtual
> nodes for the lifetime of the cluster, which can prove to be a ceiling to
> scaling the cluster if the virtual nodes grow too large.
>
> The proposed design is:
> * Assign each host T random tokens.
> * A partition is assigned to a host for each of its tokens, where the
> partition is defined by the interval between a token and the previous token
> on the ring.
> * When a host joins the ring it is assigned T random tokens which will
> result in a portion of an existing partition being assigned to that host.
> * When a host leaves the ring it relinquishes its tokens which will result
> in its partitions becoming part of the neighbouring partitions.
>
> This is just a basic extension of Cassandra's existing distribution model,
> where instead of having 1 token per host, there are many tokens per host.
> It is the same scheme used by libketama[4] for consistent hashing among
> memcached instances, and is also the original scheme used by Dynamo as
> described in [3] before they migrated to their current scheme with fixed
> partitions.
>
> The random assignment of tokens may seem unintuitive given that currently
> in Cassandra a random token assigment leads to an unbalanced cluster. With
> many virtual nodes, a random token assignment leads to load being evenly
> balanced across the hosts in the cluster with high probability. As the
> number of virtual nodes is increased, the variance in load across hosts
> decreases, as demonstrated by simulation in [5].
>
> This scheme has the following properties - (where N is the number of hosts
> and B is the total data stored in the cluster):
> * placement metadata size is O(N) which is the same as in Cassandra
> currently
> * partition size is O(B/N) so as data is inserted, if individual partitions
> become too large then adding nodes to the cluster reduces this.
> * the strategy shares the following properties in common with Cassandra
> currently
> ** tokens are randomly assigned
> ** partitioning is determined by placement (and vice-versa)
> ** no two nodes may share the same token
> ** when a node leaves the ring, all of its tokens are removed - there is no
> exchanging of partitions between nodes
>
> One design concern is that replicas of a key range are not stored on the
> same physical host, as failure of that host could cause the loss of more
> than one replica of the data. This will be achieved by using a placement
> strategy very similar the the existing NetworkTopologyStrategy, which
> treats each individual host the same way as NTS treats a rack - that is
> replicas are not assigned to two hosts on the same rack.
>
> I will shortly create a ticket in JIRA to track discussion of this design.
> We have also done some simulation of this scheme to observe the load
> balancing properties, node size distribution, cluster resizing and so on. I
> will attach some results of this simulation to the JIRA ticket in due
> course.
>
> We are keen to get the ball rolling on this and we look forward to your
> input, ideas and recommendations.
>
> Best Regards,
>
> Sam Overton
>
> [1] Staggering repair: https://issues.apache.org/jira/browse/CASSANDRA-3721
> [2] Project Voldemort, Design: http://project-voldemort.com/design.php
> [3] Dynamo:
> http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
> [4] Ketama: Consistent Hashing:
> http://www.audioscrobbler.net/development/ketama/
> [5] Consistent Hashing:
> http://www.lexemetech.com/2007/11/consistent-hashing.html
>
> --
> Sam Overton
> Acunu | http://www.acunu.com | @acunu



-- 
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com

Re: RFC: Cassandra Virtual Nodes

[Sam Overton <sa...@acunu.com>]

There is now a parent ticket for this issue in JIRA:
https://issues.apache.org/jira/browse/CASSANDRA-4119

Comments and contributions are still welcome!

Cheers,

Sam

On 16 March 2012 23:38, Sam Overton <sa...@acunu.com> wrote:
> Hello cassandra-dev,
>
> This is a long email. It concerns a significant change to Cassandra, so
> deserves a thorough introduction.
>
> The summary is: we believe virtual nodes are the way forward. We would like
> to add virtual nodes to Cassandra and we are asking for comments, criticism
> and collaboration!
>
> Cassandra's current partitioning scheme is sub-optimal for bootstrap,
> decommission, repair and re-balance operations, and places the burden on
> users to properly calculate tokens (a common cause of mistakes), which is a
> recurring pain-point.
>
> Virtual nodes have a variety of benefits over the one-to-one mapping of host
> to key range which Cassandra currently supports.
>
> Among these benefits are:
>
> * Even load balancing when growing and shrinking the cluster
> A virtual node scheme ensures that all hosts in a cluster have an even
> portion of the total data, and a new node bootstrapped into the cluster will
> assume its share of the data. Doubling, or halving the cluster to ensure
> even load distribution would no longer be necessary.
>
> * Distributed rebuild
> When sizing a cluster, one of the considerations is the amount of time
> required to recover from a failed node. This is the exposure time, during
> which a secondary failure could cause data loss. In order to guarantee an
> upper bound on the exposure time, the amount of data which can be stored on
> each host is limited by the amount of time taken to recover the required
> replica count. At Acunu we have found that the exposure time is frequently
> the limiting factor which dictates the maximum allowed node size in
> customers' clusters.
>
> Using a virtual node scheme, the data stored on one host is not replicated
> on just RF-1 other physical hosts. Each virtual node is replicated to RF-1
> other virtual nodes which may be on a different set of physical hosts to
> replicas of other virtual nodes stored on the same host. This means data for
> one host is replicated evenly across the entire cluster.
>
> In the event of a failure then, restoring the replica count can be done in a
> fully distributed way. Each host in the cluster participates in the rebuild,
> drastically reducing the exposure time, allowing more data to be stored on a
> single host while still maintaining an acceptable upper bound on the
> likelihood of secondary failure. This reduces TCO concerns.
>
> * Greater failure tolerance in streaming
> Operations which require streaming of a large range of data, eg. bootstrap,
> decommission, repair, etc. incur a heavy cost if an error (eg. dropped
> network connection) is encountered during the streaming. Currently the whole
> range must be re-streamed, and this could constitute a very large amount of
> data. Virtual nodes reduce the impact of streaming failures, since each
> virtual node is a much smaller range of the key-space, so re-streaming a
> whole virtual node is a much cheaper process.
>
> * Evenly distributed impact of streaming operations
> Streaming operations such as bootstrap, repair, et al. would involve every
> node in the cluster. This would distribute the load of these operations
> across the whole cluster, and could be staggered so that only a small subset
> of nodes were affected at once, similar to staggered repair[1].
>
> * Possibility for active load balancing
> Load balancing in Cassandra currently involves moving a token to
> increase/reduce the amount of key-space for which a host is responsible.
> This only allows load balancing between neighbouring nodes, so it could
> involve moving more than one token just to redistribute a single overloaded
> node. Virtual nodes could allow load balancing on a much finer granularity,
> so heavily loaded portions of the key-space could be redistributed to
> lighter-loaded hosts by reassigning one or more virtual nodes.
>
>
> Implementing a virtual node scheme in Cassandra is not an insignificant
> amount of work, and it will touch a large amount of the codebase related to
> partitioning, placement, routing, gossip, and so on. We do believe that this
> is possible to do incrementally, and in such a way that there is an easy
> upgrade path for pre-virtual-node deployments.
>
> It would not however touch the storage layer. The virtual node concept is
> solely for partitioning and placement, not for segregating the data storage
> of the host, so all keys for all virtual nodes on a host would be stored in
> the same SSTables.
>
> We are not proposing the adoption of the same scheme used by Voldemort[2]
> and described in the Dynamo paper[3]. We feel this scheme is too different
> from Cassandra's current distribution model to be a viable target for
> incremental development. Their scheme also fixes the number of virtual nodes
> for the lifetime of the cluster, which can prove to be a ceiling to scaling
> the cluster if the virtual nodes grow too large.
>
> The proposed design is:
> * Assign each host T random tokens.
> * A partition is assigned to a host for each of its tokens, where the
> partition is defined by the interval between a token and the previous token
> on the ring.
> * When a host joins the ring it is assigned T random tokens which will
> result in a portion of an existing partition being assigned to that host.
> * When a host leaves the ring it relinquishes its tokens which will result
> in its partitions becoming part of the neighbouring partitions.
>
> This is just a basic extension of Cassandra's existing distribution model,
> where instead of having 1 token per host, there are many tokens per host. It
> is the same scheme used by libketama[4] for consistent hashing among
> memcached instances, and is also the original scheme used by Dynamo as
> described in [3] before they migrated to their current scheme with fixed
> partitions.
>
> The random assignment of tokens may seem unintuitive given that currently in
> Cassandra a random token assigment leads to an unbalanced cluster. With many
> virtual nodes, a random token assignment leads to load being evenly balanced
> across the hosts in the cluster with high probability. As the number of
> virtual nodes is increased, the variance in load across hosts decreases, as
> demonstrated by simulation in [5].
>
> This scheme has the following properties - (where N is the number of hosts
> and B is the total data stored in the cluster):
> * placement metadata size is O(N) which is the same as in Cassandra
> currently
> * partition size is O(B/N) so as data is inserted, if individual partitions
> become too large then adding nodes to the cluster reduces this.
> * the strategy shares the following properties in common with Cassandra
> currently
> ** tokens are randomly assigned
> ** partitioning is determined by placement (and vice-versa)
> ** no two nodes may share the same token
> ** when a node leaves the ring, all of its tokens are removed - there is no
> exchanging of partitions between nodes
>
> One design concern is that replicas of a key range are not stored on the
> same physical host, as failure of that host could cause the loss of more
> than one replica of the data. This will be achieved by using a placement
> strategy very similar the the existing NetworkTopologyStrategy, which treats
> each individual host the same way as NTS treats a rack - that is replicas
> are not assigned to two hosts on the same rack.
>
> I will shortly create a ticket in JIRA to track discussion of this design.
> We have also done some simulation of this scheme to observe the load
> balancing properties, node size distribution, cluster resizing and so on. I
> will attach some results of this simulation to the JIRA ticket in due
> course.
>
> We are keen to get the ball rolling on this and we look forward to your
> input, ideas and recommendations.
>
> Best Regards,
>
> Sam Overton
>
> [1] Staggering repair: https://issues.apache.org/jira/browse/CASSANDRA-3721
> [2] Project Voldemort, Design: http://project-voldemort.com/design.php
> [3] Dynamo:
> http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
> [4] Ketama: Consistent Hashing:
> http://www.audioscrobbler.net/development/ketama/
> [5] Consistent Hashing:
> http://www.lexemetech.com/2007/11/consistent-hashing.html
>
> --
> Sam Overton
> Acunu | http://www.acunu.com | @acunu



-- 
Sam Overton
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Sam Overton <sa...@acunu.com>]

On 19 March 2012 23:41, Peter Schuller <pe...@infidyne.com> wrote:
>>> Using this ring bucket in the CRUSH topology, (with the hash function
>>> being the identity function) would give the exact same distribution
>>> properties as the virtual node strategy that I suggested previously,
>>> but of course with much better topology awareness.
>>
>> I will have to re-read your orignal post. I seem to have missed something :)
>
> I did, and I may or may not understand what you mean.
>
> Are you comparing vnodes + hashing, with CRUSH + pre-partitioning by
> hash + identity hash as you traverse down the topology tree?

Yes. I was just trying to illustrate that it's not necessary to have
CRUSH doing the partitioning and placement of primary replicas. The
same functionality can be achieved by having logically separate
placement (a ring with virtual nodes) and a replication strategy which
implements the CRUSH algorithm for replica placement. I think you
agreed with this further down your previous reply anyway, perhaps I
was just being too verbose :)

The reason I'm trying to make that distinction is because it will be
less work than wholesale replacing the entire distribution logic in
Cassandra with CRUSH. I'm not sure if that's exactly what your design
is suggesting?

-- 
Sam Overton
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Peter Schuller <pe...@infidyne.com>]

>> Using this ring bucket in the CRUSH topology, (with the hash function
>> being the identity function) would give the exact same distribution
>> properties as the virtual node strategy that I suggested previously,
>> but of course with much better topology awareness.
>
> I will have to re-read your orignal post. I seem to have missed something :)

I did, and I may or may not understand what you mean.

Are you comparing vnodes + hashing, with CRUSH + pre-partitioning by
hash + identity hash as you traverse down the topology tree?

-- 
/ Peter Schuller (@scode, http://worldmodscode.wordpress.com)

Re: RFC: Cassandra Virtual Nodes

[Peter Schuller <pe...@infidyne.com>]

> a) a virtual node partitioning scheme (to support heterogeneity and
> management simplicity)
> b) topology aware replication
> c) topology aware routing

I would add (d) limiting the distribution factor to decrease the
probability of data loss/multiple failures within a replica set.

> First of all, I think that while (c) depends on (b) it does not affect
> partitioning or replication directly, so I'm going to set that aside
> for the moment and talk just about the former two.

Agreed (but I think (d) relates).

> 1. The hash-space is partitioned into a fixed number of partitions
> 2. The CRUSH algorithm is run - select(1, disk) - over the topology
> using each partition as a key, to get an assignment of partition ->
> physical host (primary)
> 2a. adding or removing a node requires re-running CRUSH to recalculate
> the partition assignment (and move data)

(or any other arbitrary change, yes)

> 3. The CRUSH algorithm is run - select(RF-1, disk) - over the topology
> using each primary host id, to get an assignment of primary host ->
> RF-1 replicas
> 3a. adding or removing a node requires re-running CRUSH to recalculate
> replica assignment (which might be a different set of hosts to
> before?)

Yes. Cassandra would have a minimum of two topologies; the "current"
and the "next" topology. Each would imply a mapping of partition ->
replica set, and that mapping will potentially be different between
the two.

Reads would always be served form the "current" topology. Writes would
go to the union of the current and the next topology, taking care to
"tie" replicas together correctly for consistency level purposes (this
is what CASSANDRA-3901 and CASSANDRA-3833 are talking about).

Any topology change is treated the same from the read/write path
perspective, regardless of whether you're adding a node, removing a
node, adding an entire rack, or even an entire data center. No added
complexity is introduced beyond the "base case".

> One of my concerns about using CRUSH exactly as described in the paper
> is that it seems to be sub-optimal in the amount of data that it moves
> after modifying the topology. The authors of the paper introduce
> several "bucket types" (uniform, list, tree, straw) which appear to be
> various sub-optimal alternatives to consistent hashing, with various
> trade-offs. Why not use consistent hashing? Given (2a) and (3a) I
> think we might end up moving way too much data when the set of
> replicas changes completely for a given host.

One of the benefits of pre-partitioning to a fixed set of partitions
is that we can pre-calculate the mapping. This removes the CPU
efficiency trade-off of the straw bucket, and the straw bucket would
be a good choice.

Consistent hashing: It's totally doable to use consistent hashing at
each node in the topology. It is not without its own trade-offs
though, because the granularity of weighting you want to support, and
the accurace of it, relates directly to the number of vnodes per child
you need to keep in your consistent hashing ring. Taking granularity,
accuracy target and number of children into account can easily lead to
very large amounts of vnodes.

(At least experimentally from when I've implemented and played with
the simple form of consistent hashing in the past. I don't currently
have good mathematical evidence.)

> Let's suppose we introduce our own bucket type called a "ring bucket".
> Each item in a ring bucket is assigned an equal, non-contiguous
> portion of the key hash-space, which determines which keys are
> assigned to it. When an item is added to the ring bucket, it takes an
> equal portion of the hash-space from every other item already in the
> bucket. And vice-versa for removals. It's easy to see that this ring
> bucket implements consistent hashing with some unspecified virtual
> node scheme. Additions and removals would be optimal (only \deltaw/W
> keys require moving when the topology changes).

This is my understanding of what you meant by consistent hashing, and
what I refer to above.

> Using this ring bucket in the CRUSH topology, (with the hash function
> being the identity function) would give the exact same distribution
> properties as the virtual node strategy that I suggested previously,
> but of course with much better topology awareness.

I will have to re-read your orignal post. I seem to have missed something :)

> This makes it evident that the partitioning scheme, and a CRUSH-like
> replication scheme are orthogonal concerns. In the same way as NTS
> currently uses the ring to provide distribution at DC and rack level
> by conceptually separating the ring into a distinct logical rings for
> each DC, a CrushReplicationStrategy could use the ring as its
> bucketing function to distribute partitions in the topology.

Yes, agreed. Also, the distribution factor limiting is also compatible
with non-crush by hash chaining from the primary replica instead of
the row key.

> This brings me on to (1) and the reasons for our choice of virtual
> node scheme - choose N random tokens - instead of the Dynamo-like
> scheme that you suggest where the partitions are fixed in advance.
> With the Dynamo scheme, the size of a virtual node partition will only
> ever grow as more data is inserted. Since the number of partitions is
> fixed when the cluster is created, the partition size is unbounded.

I'm not sure I see why my suggestion is dynamo like. In what way? It
is essentially random in the sense of converging toward uniformity,
but with the difference that the mapping is produced deterministically
(and in a stable fashion).

> There are certain advantages to having a limit on partition size.
> Streaming failures that cause retries do not have to resend so much
> data. Streaming operations can be staggered in smaller chunks to
> minimise the impact on the nodes involved. Load balancing can operate
> on a finer granularity.

In my scheme the limit would be implicit in the number of partitions
(combined with cluster size). And yes, this is a very good property
IMO. Relatedly, as mentioned, is that you can make sure to structure
the data in terms of these partitions. In terms of current Cassandra,
this means that "cleanup" is an instantaneous operation instead of an
expensive operation that has to truck through a lot of data (less so
with leveled compaction).

> The other concern you mentioned was
>> The probability of data loss increases linearly with cluster size.
>
> but you also acknowledge that
>
>> In making this determination, one must take into account that if a
>> larger `DF` makes reconstruction/replacement significantly faster,
>> that also decreases the time window in which multiple failures can
>> occurr. Increasing `DF` is thus not *necessarily* increasing the total
>> probability of data loss (for small values of `DF`).
>
> Our calculations lead us to believe that in fact the shorter rebuild
> window more than compensates for the increased probability of multiple
> failure, so with DF=N the probability of data loss is minimised.
>
> The CRUSH paper also states:
>
> "With 2-way mirroring these two factors cancel
> each other out, while overall data safety with more than two
> replicas increases with declustering [Xin et al. 2004]"
>
> ("declustering" meaning increasing DF towards N)

This is common argument against limiting RDF, but I am *strongly*
skeptical of this in real-life scenarios. This is one of those cases
where I think one needs to look beyond the pure math. For one thing, a
huge concern for me is that I don't want active re-balancing to have
such an extreme availability requirement that a downtime on actively
doing that implies a significantly increased risk of data loss. I
don't want a system to be constantly teetering on the edge of data
loss, and it not even being safe to *shut it down* because your lack
of data loss is dependent on the system as a whole being fully
available, working and actively moving data around. It also hinges on
reality matching theory perfectly well in terms of "independent"
failures truly being independent. I would feel much more comfortable
with a system that did not rely on super-fast re-replication to ensure
data safety. But like I said, a lot of people make this argument - I
just remain unconvinced thus far.

Further, even looking at just the math, the claim cannot possibly hold
as N grows sufficiently large. At some point you will bottleneck on
the network and no longer benefit form a higher RDF, but the
probability of data loss doesn't drop off until you reach DF=number of
partitions (because at that point an increased cluster size doesn't
increase the number of nodes with data sharing with another node).

-- 
/ Peter Schuller (@scode, http://worldmodscode.wordpress.com)

Re: RFC: Cassandra Virtual Nodes

[Sam Overton <sa...@acunu.com>]

On 20 March 2012 13:37, Eric Evans <ee...@acunu.com> wrote:
> On Tue, Mar 20, 2012 at 6:40 AM, Sam Overton <sa...@acunu.com> wrote:
>> On 20 March 2012 04:35, Vijay <vi...@gmail.com> wrote:
>>> May be, what i mean is little more simple than that... We can consider
>>> every node having a multiple conservative ranges and moving those ranges
>>> for bootstrap etc, instead of finding the mid point etc in the bootstrap
>>> code. Once we get that working all the way to the FS/Streaming then we can
>>> move those ranges and assign those ranges to nodes in random orders. Hope
>>> it makes sense.
>>
>> I agree that this should be approached in incremental steps. Rick
>> already raised concerns about stability issues which might arise from
>> changing large parts of code at once.
>>
>> I would anticipate the first step to be, exactly as you suggest, to
>> support multiple tokens per host instead of just one. Presumably in
>> your suggestion you imagine these tokens to define contiguous ranges
>> for a given host, so that the distribution model is the same as
>> before, but bootstrap can be done incrementally.
>>
>> This would be a great first step. The extension to a virtual node
>> scheme as described previously is then fairly trivial. The only
>> additional change needed is to assign the tokens in some other way
>> which does not restrict the ranges to being contiguous.
>
> Sounds good to me.
>
> What can an upgrading user expect in the way of disruption?  What
> would be required to move an existing cluster from one token per node
> to virtual nodes?  Could this be made transparent?
>

The disruption for an end-user would be no more than the same rolling
upgrade process that they have to go through currently to upgrade to a
new version.

This is how I envisage it working:
* When a node is upgraded and the new version starts up in an old
cluster, it would split its own token range into multiple sub-ranges
by assigning itself more tokens in its own range
* These tokens could then be gossiped to any other new versions in the
cluster. The old versions don't need to know about these intermediate
tokens because distribution is exactly the same - node ranges are
still contiguous
* Once every node has been upgraded, distribution is still the same as
before, but now ranges are split into sub-ranges
* The benefits of vnodes start to become apparent when adding new
nodes to the cluster - a new node bootstrapping would take an even
amount of data from each other node and would not require doubling the
cluster to maintain balance
* As more nodes are added to the cluster it gets closer to full vnode
distribution as more of the original hosts' ranges get reassigned to
new nodes

If the user wants to migrate to full vnode functionality straight away
then they can do a rolling migration (decommission/bootstrap). During
this migration there would be some imbalance in the cluster, but once
all of the old nodes have been migrated, the cluster would be
balanced.

-- 
Sam Overton
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Eric Evans <ee...@acunu.com>]

On Tue, Mar 20, 2012 at 6:40 AM, Sam Overton <sa...@acunu.com> wrote:
> On 20 March 2012 04:35, Vijay <vi...@gmail.com> wrote:
>> On Mon, Mar 19, 2012 at 8:24 PM, Eric Evans <ee...@acunu.com> wrote:
>>
>>> I'm guessing you're referring to Rick's proposal about ranges per node?
>>>
>>
>> May be, what i mean is little more simple than that... We can consider
>> every node having a multiple conservative ranges and moving those ranges
>> for bootstrap etc, instead of finding the mid point etc in the bootstrap
>> code. Once we get that working all the way to the FS/Streaming then we can
>> move those ranges and assign those ranges to nodes in random orders. Hope
>> it makes sense.
>
> I agree that this should be approached in incremental steps. Rick
> already raised concerns about stability issues which might arise from
> changing large parts of code at once.
>
> I would anticipate the first step to be, exactly as you suggest, to
> support multiple tokens per host instead of just one. Presumably in
> your suggestion you imagine these tokens to define contiguous ranges
> for a given host, so that the distribution model is the same as
> before, but bootstrap can be done incrementally.
>
> This would be a great first step. The extension to a virtual node
> scheme as described previously is then fairly trivial. The only
> additional change needed is to assign the tokens in some other way
> which does not restrict the ranges to being contiguous.

Sounds good to me.

What can an upgrading user expect in the way of disruption?  What
would be required to move an existing cluster from one token per node
to virtual nodes?  Could this be made transparent?

-- 
Eric Evans
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Sam Overton <sa...@acunu.com>]

On 20 March 2012 04:35, Vijay <vi...@gmail.com> wrote:
> On Mon, Mar 19, 2012 at 8:24 PM, Eric Evans <ee...@acunu.com> wrote:
>
>> I'm guessing you're referring to Rick's proposal about ranges per node?
>>
>
> May be, what i mean is little more simple than that... We can consider
> every node having a multiple conservative ranges and moving those ranges
> for bootstrap etc, instead of finding the mid point etc in the bootstrap
> code. Once we get that working all the way to the FS/Streaming then we can
> move those ranges and assign those ranges to nodes in random orders. Hope
> it makes sense.

I agree that this should be approached in incremental steps. Rick
already raised concerns about stability issues which might arise from
changing large parts of code at once.

I would anticipate the first step to be, exactly as you suggest, to
support multiple tokens per host instead of just one. Presumably in
your suggestion you imagine these tokens to define contiguous ranges
for a given host, so that the distribution model is the same as
before, but bootstrap can be done incrementally.

This would be a great first step. The extension to a virtual node
scheme as described previously is then fairly trivial. The only
additional change needed is to assign the tokens in some other way
which does not restrict the ranges to being contiguous.

-- 
Sam Overton
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Vijay <vi...@gmail.com>]

On Mon, Mar 19, 2012 at 8:24 PM, Eric Evans <ee...@acunu.com> wrote:

> I'm guessing you're referring to Rick's proposal about ranges per node?
>

May be, what i mean is little more simple than that... We can consider
every node having a multiple conservative ranges and moving those ranges
for bootstrap etc, instead of finding the mid point etc in the bootstrap
code. Once we get that working all the way to the FS/Streaming then we can
move those ranges and assign those ranges to nodes in random orders. Hope
it makes sense.

Re: RFC: Cassandra Virtual Nodes

[Eric Evans <ee...@acunu.com>]

On Mon, Mar 19, 2012 at 9:37 PM, Vijay <vi...@gmail.com> wrote:
> I also did create a ticket
> https://issues.apache.org/jira/browse/CASSANDRA-3768 with some of the
> reason why I would like to see vnodes in cassandra.
> It can also potentially reduce the SSTable seeks which a node has to do to
> query data in SizeTireCompaction if extended to the filesystem.
>
> But 110% agree with Peter, we need to take incremental steps and start with
> the existing bootstrapping.

I'm guessing you're referring to Rick's proposal about ranges per node?

> May be we can start it by making a set of Ranges/Token to a node insted of
> one token. And then may be building things around the movement of those
> ranges.

> I have been thinking about this for a while but having trouble to get to a
> point where i am comfortable changing big chunks of code.

It might help to see some more detail in the proposals.  Both ideas
seem invasive, vnodes more so, but there are many more benefits as
well.

> On Mon, Mar 19, 2012 at 4:45 PM, Peter Schuller <peter.schuller@infidyne.com
>> wrote:
>
>> (I may comment on other things more later)
>>
>> > As a side note: vnodes fail to provide solutions to node-based
>> limitations
>> > that seem to me to cause a substantial portion of operational issues such
>> > as impact of node restarts / upgrades, GC and compaction induced
>> latency. I
>>
>> Actually, it does. At least assumign DF > RF (as in the original
>> proposal, and mine). The impact of a node suffering from a performance
>> degradation is mitigated because the effects are spread out over DF-1
>> (N-1 in the original post) nodes instead of just RF nodes.
>>
>> > think some progress could be made here by allowing a "pack" of
>> independent
>> > Cassandra nodes to be ran on a single host; somewhat (but nowhere near
>> > entirely) similar to a pre-fork model used by some UNIX-based servers.
>>
>> I have pretty significant knee-jerk negative reactions to that idea to
>> be honest, even if the pack is limited to a handful of instances. In
>> order for vnodes to be useful with random placement, we'd need much
>> more than a handful of vnodes per node (cassandra instances in a
>> "pack" in that model).


-- 
Eric Evans
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Vijay <vi...@gmail.com>]

I also did create a ticket
https://issues.apache.org/jira/browse/CASSANDRA-3768 with some of the
reason why I would like to see vnodes in cassandra.
It can also potentially reduce the SSTable seeks which a node has to do to
query data in SizeTireCompaction if extended to the filesystem.

But 110% agree with Peter, we need to take incremental steps and start with
the existing bootstrapping.
May be we can start it by making a set of Ranges/Token to a node insted of
one token. And then may be building things around the movement of those
ranges.

I have been thinking about this for a while but having trouble to get to a
point where i am comfortable changing big chunks of code.

Regards,
</VJ>



On Mon, Mar 19, 2012 at 4:45 PM, Peter Schuller <peter.schuller@infidyne.com
> wrote:

> (I may comment on other things more later)
>
> > As a side note: vnodes fail to provide solutions to node-based
> limitations
> > that seem to me to cause a substantial portion of operational issues such
> > as impact of node restarts / upgrades, GC and compaction induced
> latency. I
>
> Actually, it does. At least assumign DF > RF (as in the original
> proposal, and mine). The impact of a node suffering from a performance
> degradation is mitigated because the effects are spread out over DF-1
> (N-1 in the original post) nodes instead of just RF nodes.
>
> > think some progress could be made here by allowing a "pack" of
> independent
> > Cassandra nodes to be ran on a single host; somewhat (but nowhere near
> > entirely) similar to a pre-fork model used by some UNIX-based servers.
>
> I have pretty significant knee-jerk negative reactions to that idea to
> be honest, even if the pack is limited to a handful of instances. In
> order for vnodes to be useful with random placement, we'd need much
> more than a handful of vnodes per node (cassandra instances in a
> "pack" in that model).
>
> --
> / Peter Schuller (@scode, http://worldmodscode.wordpress.com)
>

Re: RFC: Cassandra Virtual Nodes

[Rick Branson <rb...@datastax.com>]

On Mon, Mar 19, 2012 at 4:45 PM, Peter Schuller
<pe...@infidyne.com> wrote:
> > As a side note: vnodes fail to provide solutions to node-based limitations
> > that seem to me to cause a substantial portion of operational issues such
> > as impact of node restarts / upgrades, GC and compaction induced latency. I
>
> Actually, it does. At least assumign DF > RF (as in the original
> proposal, and mine). The impact of a node suffering from a performance
> degradation is mitigated because the effects are spread out over DF-1
> (N-1 in the original post) nodes instead of just RF nodes.

You've got me on one of those after some re-thought. For any node
outage (an upgrade/restart) definitely has a big impact by distributed
the load more evenly, but (and correct me if I'm wrong) for things
like additional latency caused by GC/compaction, those requests will
just be slower rather than timing out or getting redirected via the
dynamic snitch.

> > think some progress could be made here by allowing a "pack" of independent
> > Cassandra nodes to be ran on a single host; somewhat (but nowhere near
> > entirely) similar to a pre-fork model used by some UNIX-based servers.
>
> I have pretty significant knee-jerk negative reactions to that idea to
> be honest, even if the pack is limited to a handful of instances. In
> order for vnodes to be useful with random placement, we'd need much
> more than a handful of vnodes per node (cassandra instances in a
> "pack" in that model).
>

Fair enough, I'm not super fond of the idea personally, but I don't
see a way around the limitations of the current JVM GC without
multiple processes.

After some rethinking my ideas a bit, I think actually what I've
settled a bit more on is to keep the existing node tokens, but add an
additional "active token" that would be used to determine the data
range that a node is ready to receive reads for. This should gain all
of the benefits highlighted in my earlier post, but with less
complexity in implementation. Node repair (AES) would still allow
ranges to be specified.

Re: RFC: Cassandra Virtual Nodes

[Peter Schuller <pe...@infidyne.com>]

(I may comment on other things more later)

> As a side note: vnodes fail to provide solutions to node-based limitations
> that seem to me to cause a substantial portion of operational issues such
> as impact of node restarts / upgrades, GC and compaction induced latency. I

Actually, it does. At least assumign DF > RF (as in the original
proposal, and mine). The impact of a node suffering from a performance
degradation is mitigated because the effects are spread out over DF-1
(N-1 in the original post) nodes instead of just RF nodes.

> think some progress could be made here by allowing a "pack" of independent
> Cassandra nodes to be ran on a single host; somewhat (but nowhere near
> entirely) similar to a pre-fork model used by some UNIX-based servers.

I have pretty significant knee-jerk negative reactions to that idea to
be honest, even if the pack is limited to a handful of instances. In
order for vnodes to be useful with random placement, we'd need much
more than a handful of vnodes per node (cassandra instances in a
"pack" in that model).

-- 
/ Peter Schuller (@scode, http://worldmodscode.wordpress.com)

Re: RFC: Cassandra Virtual Nodes

[Jonathan Ellis <jb...@gmail.com>]

On Wed, Mar 21, 2012 at 8:50 AM, Eric Evans <ee...@acunu.com> wrote:
> I must admit I find this a little disheartening.  The discussion has
> barely started.  No one has had a chance to discuss implementation
> specifics so that the rest of us could understand *how* disruptive it
> would be (a necessary requirement in weighing cost:benefit), or what
> an incremental approach would look like, and yet work has already
> begun on shutting this down.

This isn't the first time vnodes has been brought up, so I've thought
at least a little bit about what that would entail for TokenMetadata,
StorageProxy, streaming, CFS, and on down the stack.  And it scares
me.  So, I wanted to make my points about cost:benefit and about not
committing with intentions to work out the details "later," up front.

But if you're still in brainstorming mode, carry on.

> Unless I'm reading you wrong, your mandate (I say mandate because you
> hinted at a veto elsewhere), is No to anything complex or invasive
> (for some value of each).  The only alternative would seem to be a
> phased or incremental approach, but you seem to be saying No to that
> as well.
>
> There seems to be quite a bit of interest in having virtual nodes (and
> there has been for as long as I can remember), the only serious
> reservations relate to the difficulty/complexity.  Is there really no
> way to put our heads together and figure out how to properly manage
> that aspect?

At the risk of putting words in your mouth, I think your concern is
that you don't want to go off and put man-months into a vnode
implementation, only to have me come back and say, "Sorry, it's too
complicated, -1."

Which is totally reasonable, I get that.

I would suggest that the best way to mitigate that is, when you are
ready, to put together as detailed an implementation plan as possible
ahead of time before you start generating patchsets.  Then we can put
some meat on the discussion more meaningful than vague "that scares
me" statements from yours truly.

-- 
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com

Re: RFC: Cassandra Virtual Nodes

[Vijay <vi...@gmail.com>]

>>> I envision vnodes as Cassandra master being a shared cache,memtables,
and manager for what we today consider a Cassandra  instance.

It might be kind of problematic when you are moving the nodes you want the
data associated with the node to move too, otherwise it will be a pain to
cleanup after that (Something like nt clean). I think a vnode should be as
much isolated as possible to reduce the impact when it is moving (which
will become a normal cluster operation), Just my 2 cents.

Regards,
</VJ>



On Wed, Mar 21, 2012 at 5:41 PM, Edward Capriolo <ed...@gmail.com>wrote:

> I just see vnodes as a way to make the problem smaller and by making the
> problem smaller the overall system is more agile. Aka rather then 1 node
> streaming 100 gb the 4 nodes stream 25gb. Moves by hand are not so bad
> because the take 1/4th the time.
>
> The most simple vnode implementation is vmware.  Just make sure that 3 vm
> nodes consecutive nodes so not end up on the same host. This is wasteful
> because we have 4 jvms.
>
> I envision vnodes as Cassandra master being a shared cache,memtables, and
> manager for what we today consider a Cassandra  instance. Makes it simple
> to think about.
>
> On Wednesday, March 21, 2012, Peter Schuller <pe...@infidyne.com>
> wrote:
> >> Software wise it is the same deal. Each node streams off only disk 4
> >> to the new node.
> >
> > I think an implication on software is that if you want to make
> > specific selections of partitions to move, you are effectively
> > incompatible with deterministically generating the mapping of
> > partition to responsible node. I.e., it probably means the vnode
> > information must be kept as state. It is probably difficult to
> > reconcile with balancing solutions like consistent hashing/crush/etc.
> >
> > --
> > / Peter Schuller (@scode, http://worldmodscode.wordpress.com)
> >
>

Re: RFC: Cassandra Virtual Nodes

[Edward Capriolo <ed...@gmail.com>]

I just see vnodes as a way to make the problem smaller and by making the
problem smaller the overall system is more agile. Aka rather then 1 node
streaming 100 gb the 4 nodes stream 25gb. Moves by hand are not so bad
because the take 1/4th the time.

The most simple vnode implementation is vmware.  Just make sure that 3 vm
nodes consecutive nodes so not end up on the same host. This is wasteful
because we have 4 jvms.

I envision vnodes as Cassandra master being a shared cache,memtables, and
manager for what we today consider a Cassandra  instance. Makes it simple
to think about.

On Wednesday, March 21, 2012, Peter Schuller <pe...@infidyne.com>
wrote:
>> Software wise it is the same deal. Each node streams off only disk 4
>> to the new node.
>
> I think an implication on software is that if you want to make
> specific selections of partitions to move, you are effectively
> incompatible with deterministically generating the mapping of
> partition to responsible node. I.e., it probably means the vnode
> information must be kept as state. It is probably difficult to
> reconcile with balancing solutions like consistent hashing/crush/etc.
>
> --
> / Peter Schuller (@scode, http://worldmodscode.wordpress.com)
>

Re: RFC: Cassandra Virtual Nodes

[Peter Schuller <pe...@infidyne.com>]

> Software wise it is the same deal. Each node streams off only disk 4
> to the new node.

I think an implication on software is that if you want to make
specific selections of partitions to move, you are effectively
incompatible with deterministically generating the mapping of
partition to responsible node. I.e., it probably means the vnode
information must be kept as state. It is probably difficult to
reconcile with balancing solutions like consistent hashing/crush/etc.

-- 
/ Peter Schuller (@scode, http://worldmodscode.wordpress.com)

Re: RFC: Cassandra Virtual Nodes

[Edward Capriolo <ed...@gmail.com>]

On Wed, Mar 21, 2012 at 3:24 PM, Tom Wilkie <to...@acunu.com> wrote:
> Hi Edward
>
>> 1) No more raid 0. If a machine is responsible for 4 vnodes they
>> should correspond to for JBOD.
>
> So each vnode corresponds to a disk?  I suppose we could have a
> separate data directory per disk, but I think this should be a
> separate, subsequent change.
>
I think having more micro-ranges makes the process much easier.
Image a token ring 1-30

Node1 | major range 0-10  | disk 1    0-2 , disk2 3-4, disk 3 5-7, disk 4 8-10
Node2 | major range 11-20| disk 1 11-12 , disk2 13-14, disk 3 15-17,
disk 4 18-20
Node3 | major range 21-30| disk 1 21-22 , disk2 23-24, disk 3 25-27,
disk 4 28-30

Adding a 4th node is easy:
If you are at the data center, just take disk 4 out of each node and
place it in new server :)
Software wise it is the same deal. Each node streams off only disk 4
to the new node.

Now at this point disk 4 is idle and each machine should re balance
its own data across its 4 disks.

> However, do note that making the vnode ~size of a disk (and only have
> 4-8 per machine) would make any non-hotswap rebuilds slower.  To get
> the fast distributed rebuilds, you need to have at least as many
> vnodes per node as you do nodes in the cluster.  And you would still
> need the distributed rebuilds to deal with disk failure.
>
>> 2) Vnodes should be able to be hot pluged. My normal cassandra chassis
>> would be a 2U with 6 drive bays. Imagine I have 10 nodes. Now if my
>> chassis dies I should be able to take the disks out and physically
>> plug them into another chassis. Then in cassandra I should be able to
>> run a command like.
>> nodetool attach '/mnt/disk6'. disk6 should contain all data an it's
>> vnode information.
>>
>> Now this would be awesome for upgrades/migrations/etc.
>
> You know, your not the first person I've spoke to who has asked for
> this!  I do wonder whether it is optimising for the right thing though
> - in my experience, disks fail more often than machines.
>
> Thanks
>
> Tom

Re: RFC: Cassandra Virtual Nodes

[Tom Wilkie <to...@acunu.com>]

Hi Edward

> 1) No more raid 0. If a machine is responsible for 4 vnodes they
> should correspond to for JBOD.

So each vnode corresponds to a disk?  I suppose we could have a
separate data directory per disk, but I think this should be a
separate, subsequent change.

However, do note that making the vnode ~size of a disk (and only have
4-8 per machine) would make any non-hotswap rebuilds slower.  To get
the fast distributed rebuilds, you need to have at least as many
vnodes per node as you do nodes in the cluster.  And you would still
need the distributed rebuilds to deal with disk failure.

> 2) Vnodes should be able to be hot pluged. My normal cassandra chassis
> would be a 2U with 6 drive bays. Imagine I have 10 nodes. Now if my
> chassis dies I should be able to take the disks out and physically
> plug them into another chassis. Then in cassandra I should be able to
> run a command like.
> nodetool attach '/mnt/disk6'. disk6 should contain all data an it's
> vnode information.
>
> Now this would be awesome for upgrades/migrations/etc.

You know, your not the first person I've spoke to who has asked for
this!  I do wonder whether it is optimising for the right thing though
- in my experience, disks fail more often than machines.

Thanks

Tom

Re: RFC: Cassandra Virtual Nodes

[Edward Capriolo <ed...@gmail.com>]

On Wed, Mar 21, 2012 at 9:50 AM, Eric Evans <ee...@acunu.com> wrote:
> On Tue, Mar 20, 2012 at 9:53 PM, Jonathan Ellis <jb...@gmail.com> wrote:
>> It's reasonable that we can attach different levels of importance to
>> these things.  Taking a step back, I have two main points:
>>
>> 1) vnodes add enormous complexity to *many* parts of Cassandra.  I'm
>> skeptical of the cost:benefit ratio here.
>>
>> 1a) The benefit is lower in my mind because many of the problems
>> solved by vnodes can be solved "well enough" for "most people," for
>> some value of those two phrases, without vnodes.
>>
>> 2) I'm not okay with a "commit something half-baked and sort it out
>> later" approach.
>
> I must admit I find this a little disheartening.  The discussion has
> barely started.  No one has had a chance to discuss implementation
> specifics so that the rest of us could understand *how* disruptive it
> would be (a necessary requirement in weighing cost:benefit), or what
> an incremental approach would look like, and yet work has already
> begun on shutting this down.
>
> Unless I'm reading you wrong, your mandate (I say mandate because you
> hinted at a veto elsewhere), is No to anything complex or invasive
> (for some value of each).  The only alternative would seem to be a
> phased or incremental approach, but you seem to be saying No to that
> as well.
>
> There seems to be quite a bit of interest in having virtual nodes (and
> there has been for as long as I can remember), the only serious
> reservations relate to the difficulty/complexity.  Is there really no
> way to put our heads together and figure out how to properly manage
> that aspect?
>
>> On Tue, Mar 20, 2012 at 11:10 AM, Richard Low <rl...@acunu.com> wrote:
>>> On 20 March 2012 14:55, Jonathan Ellis <jb...@gmail.com> wrote:
>>>> Here's how I see Sam's list:
>>>>
>>>> * Even load balancing when growing and shrinking the cluster
>>>>
>>>> Nice to have, but post-bootstrap load balancing works well in practice
>>>> (and is improved by TRP).
>>>
>>> Post-bootstrap load balancing without vnodes necessarily streams more
>>> data than is necessary.  Vnodes streams the minimal amount.
>>>
>>> In fact, post-bootstrap load balancing currently streams a constant
>>> fraction of your data - the network traffic involved in a rebalance
>>> increases linearly with the size of your cluster.  With vnodes it
>>> decreases linearly.
>>>
>>> Including removing the ops overhead of running the load balance and
>>> calculating new tokens, this makes removing post-bootstrap load
>>> balancing a pretty big deal.
>>>
>>>> * Greater failure tolerance in streaming
>>>>
>>>> Directly addressed by TRP.
>>>
>>> Agreed.
>>>
>>>> * Evenly distributed impact of streaming operations
>>>>
>>>> Not a problem in practice with stream throttling.
>>>
>>> Throttling slows them down, increasing rebuild times so increasing downtime.
>>>
>>>> * Possibility for active load balancing
>>>>
>>>> Not really a feature of vnodes per se, but as with the other load
>>>> balancing point, this is also improved by TRP.
>>>
>>> Again with the caveat that more data is streamed with TRP.  Vnodes
>>> removes the need for any load balancing with RP.
>>>
>>>> * Distributed rebuild
>>>>
>>>> This is the 20% that TRP does not address.  Nice to have?  Yes.  Can I
>>>> live without it?  I have so far.  Is this alone worth the complexity
>>>> of vnodes?  No, it is not.  Especially since there are probably other
>>>> approaches that we can take to mitigate this, one of which Rick has
>>>> suggested in a separate sub-thread.
>>>
>>> Distributed rebuild means you can store more data per node with the
>>> same failure probabilities.  This is frequently a limiting factor on
>>> how much data you can store per node, increasing cluster sizes
>>> unnecessarily.  I'd argue that this alone is worth the complexity of
>>> vnodes.
>>>
>>> Richard.
>>
>>
>>
>> --
>> Jonathan Ellis
>> Project Chair, Apache Cassandra
>> co-founder of DataStax, the source for professional Cassandra support
>> http://www.datastax.com
>
>
>
> --
> Eric Evans
> Acunu | http://www.acunu.com | @acunu

I have also thought of how I would like Vnodes to work from an
operational prospective rather then a software one. I would like these
features.
1) No more raid 0. If a machine is responsible for 4 vnodes they
should correspond to for JBOD.

2) Vnodes should be able to be hot pluged. My normal cassandra chassis
would be a 2U with 6 drive bays. Imagine I have 10 nodes. Now if my
chassis dies I should be able to take the disks out and physically
plug them into another chassis. Then in cassandra I should be able to
run a command like.
nodetool attach '/mnt/disk6'. disk6 should contain all data an it's
vnode information.

Now this would be awesome for upgrades/migrations/etc.

Re: RFC: Cassandra Virtual Nodes

[Chris Goffinet <cg...@chrisgoffinet.com>]

I'm going to agree with Eric on this one. Twitter has wanted some sort of vnode support for quite sometime. We even were willing to do all the work. I have reservations about that now  We have been silent due to the community and how this is more like an exclusive Datastax project than an Apache one. I share Eric's frustration and do not like this veto/control attitude I see on this thread. 

Sent from my iPhone 

On Mar 21, 2012, at 6:50 AM, Eric Evans <ee...@acunu.com> wrote:

> On Tue, Mar 20, 2012 at 9:53 PM, Jonathan Ellis <jb...@gmail.com> wrote:
>> It's reasonable that we can attach different levels of importance to
>> these things.  Taking a step back, I have two main points:
>> 
>> 1) vnodes add enormous complexity to *many* parts of Cassandra.  I'm
>> skeptical of the cost:benefit ratio here.
>> 
>> 1a) The benefit is lower in my mind because many of the problems
>> solved by vnodes can be solved "well enough" for "most people," for
>> some value of those two phrases, without vnodes.
>> 
>> 2) I'm not okay with a "commit something half-baked and sort it out
>> later" approach.
> 
> I must admit I find this a little disheartening.  The discussion has
> barely started.  No one has had a chance to discuss implementation
> specifics so that the rest of us could understand *how* disruptive it
> would be (a necessary requirement in weighing cost:benefit), or what
> an incremental approach would look like, and yet work has already
> begun on shutting this down.
> 
> Unless I'm reading you wrong, your mandate (I say mandate because you
> hinted at a veto elsewhere), is No to anything complex or invasive
> (for some value of each).  The only alternative would seem to be a
> phased or incremental approach, but you seem to be saying No to that
> as well.
> 
> There seems to be quite a bit of interest in having virtual nodes (and
> there has been for as long as I can remember), the only serious
> reservations relate to the difficulty/complexity.  Is there really no
> way to put our heads together and figure out how to properly manage
> that aspect?
> 
>> On Tue, Mar 20, 2012 at 11:10 AM, Richard Low <rl...@acunu.com> wrote:
>>> On 20 March 2012 14:55, Jonathan Ellis <jb...@gmail.com> wrote:
>>>> Here's how I see Sam's list:
>>>> 
>>>> * Even load balancing when growing and shrinking the cluster
>>>> 
>>>> Nice to have, but post-bootstrap load balancing works well in practice
>>>> (and is improved by TRP).
>>> 
>>> Post-bootstrap load balancing without vnodes necessarily streams more
>>> data than is necessary.  Vnodes streams the minimal amount.
>>> 
>>> In fact, post-bootstrap load balancing currently streams a constant
>>> fraction of your data - the network traffic involved in a rebalance
>>> increases linearly with the size of your cluster.  With vnodes it
>>> decreases linearly.
>>> 
>>> Including removing the ops overhead of running the load balance and
>>> calculating new tokens, this makes removing post-bootstrap load
>>> balancing a pretty big deal.
>>> 
>>>> * Greater failure tolerance in streaming
>>>> 
>>>> Directly addressed by TRP.
>>> 
>>> Agreed.
>>> 
>>>> * Evenly distributed impact of streaming operations
>>>> 
>>>> Not a problem in practice with stream throttling.
>>> 
>>> Throttling slows them down, increasing rebuild times so increasing downtime.
>>> 
>>>> * Possibility for active load balancing
>>>> 
>>>> Not really a feature of vnodes per se, but as with the other load
>>>> balancing point, this is also improved by TRP.
>>> 
>>> Again with the caveat that more data is streamed with TRP.  Vnodes
>>> removes the need for any load balancing with RP.
>>> 
>>>> * Distributed rebuild
>>>> 
>>>> This is the 20% that TRP does not address.  Nice to have?  Yes.  Can I
>>>> live without it?  I have so far.  Is this alone worth the complexity
>>>> of vnodes?  No, it is not.  Especially since there are probably other
>>>> approaches that we can take to mitigate this, one of which Rick has
>>>> suggested in a separate sub-thread.
>>> 
>>> Distributed rebuild means you can store more data per node with the
>>> same failure probabilities.  This is frequently a limiting factor on
>>> how much data you can store per node, increasing cluster sizes
>>> unnecessarily.  I'd argue that this alone is worth the complexity of
>>> vnodes.
>>> 
>>> Richard.
>> 
>> 
>> 
>> --
>> Jonathan Ellis
>> Project Chair, Apache Cassandra
>> co-founder of DataStax, the source for professional Cassandra support
>> http://www.datastax.com
> 
> 
> 
> -- 
> Eric Evans
> Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Eric Evans <ee...@acunu.com>]

On Tue, Mar 20, 2012 at 9:53 PM, Jonathan Ellis <jb...@gmail.com> wrote:
> It's reasonable that we can attach different levels of importance to
> these things.  Taking a step back, I have two main points:
>
> 1) vnodes add enormous complexity to *many* parts of Cassandra.  I'm
> skeptical of the cost:benefit ratio here.
>
> 1a) The benefit is lower in my mind because many of the problems
> solved by vnodes can be solved "well enough" for "most people," for
> some value of those two phrases, without vnodes.
>
> 2) I'm not okay with a "commit something half-baked and sort it out
> later" approach.

I must admit I find this a little disheartening.  The discussion has
barely started.  No one has had a chance to discuss implementation
specifics so that the rest of us could understand *how* disruptive it
would be (a necessary requirement in weighing cost:benefit), or what
an incremental approach would look like, and yet work has already
begun on shutting this down.

Unless I'm reading you wrong, your mandate (I say mandate because you
hinted at a veto elsewhere), is No to anything complex or invasive
(for some value of each).  The only alternative would seem to be a
phased or incremental approach, but you seem to be saying No to that
as well.

There seems to be quite a bit of interest in having virtual nodes (and
there has been for as long as I can remember), the only serious
reservations relate to the difficulty/complexity.  Is there really no
way to put our heads together and figure out how to properly manage
that aspect?

> On Tue, Mar 20, 2012 at 11:10 AM, Richard Low <rl...@acunu.com> wrote:
>> On 20 March 2012 14:55, Jonathan Ellis <jb...@gmail.com> wrote:
>>> Here's how I see Sam's list:
>>>
>>> * Even load balancing when growing and shrinking the cluster
>>>
>>> Nice to have, but post-bootstrap load balancing works well in practice
>>> (and is improved by TRP).
>>
>> Post-bootstrap load balancing without vnodes necessarily streams more
>> data than is necessary.  Vnodes streams the minimal amount.
>>
>> In fact, post-bootstrap load balancing currently streams a constant
>> fraction of your data - the network traffic involved in a rebalance
>> increases linearly with the size of your cluster.  With vnodes it
>> decreases linearly.
>>
>> Including removing the ops overhead of running the load balance and
>> calculating new tokens, this makes removing post-bootstrap load
>> balancing a pretty big deal.
>>
>>> * Greater failure tolerance in streaming
>>>
>>> Directly addressed by TRP.
>>
>> Agreed.
>>
>>> * Evenly distributed impact of streaming operations
>>>
>>> Not a problem in practice with stream throttling.
>>
>> Throttling slows them down, increasing rebuild times so increasing downtime.
>>
>>> * Possibility for active load balancing
>>>
>>> Not really a feature of vnodes per se, but as with the other load
>>> balancing point, this is also improved by TRP.
>>
>> Again with the caveat that more data is streamed with TRP.  Vnodes
>> removes the need for any load balancing with RP.
>>
>>> * Distributed rebuild
>>>
>>> This is the 20% that TRP does not address.  Nice to have?  Yes.  Can I
>>> live without it?  I have so far.  Is this alone worth the complexity
>>> of vnodes?  No, it is not.  Especially since there are probably other
>>> approaches that we can take to mitigate this, one of which Rick has
>>> suggested in a separate sub-thread.
>>
>> Distributed rebuild means you can store more data per node with the
>> same failure probabilities.  This is frequently a limiting factor on
>> how much data you can store per node, increasing cluster sizes
>> unnecessarily.  I'd argue that this alone is worth the complexity of
>> vnodes.
>>
>> Richard.
>
>
>
> --
> Jonathan Ellis
> Project Chair, Apache Cassandra
> co-founder of DataStax, the source for professional Cassandra support
> http://www.datastax.com



-- 
Eric Evans
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Jonathan Ellis <jb...@gmail.com>]

It's reasonable that we can attach different levels of importance to
these things.  Taking a step back, I have two main points:

1) vnodes add enormous complexity to *many* parts of Cassandra.  I'm
skeptical of the cost:benefit ratio here.

1a) The benefit is lower in my mind because many of the problems
solved by vnodes can be solved "well enough" for "most people," for
some value of those two phrases, without vnodes.

2) I'm not okay with a "commit something half-baked and sort it out
later" approach.

On Tue, Mar 20, 2012 at 11:10 AM, Richard Low <rl...@acunu.com> wrote:
> On 20 March 2012 14:55, Jonathan Ellis <jb...@gmail.com> wrote:
>> Here's how I see Sam's list:
>>
>> * Even load balancing when growing and shrinking the cluster
>>
>> Nice to have, but post-bootstrap load balancing works well in practice
>> (and is improved by TRP).
>
> Post-bootstrap load balancing without vnodes necessarily streams more
> data than is necessary.  Vnodes streams the minimal amount.
>
> In fact, post-bootstrap load balancing currently streams a constant
> fraction of your data - the network traffic involved in a rebalance
> increases linearly with the size of your cluster.  With vnodes it
> decreases linearly.
>
> Including removing the ops overhead of running the load balance and
> calculating new tokens, this makes removing post-bootstrap load
> balancing a pretty big deal.
>
>> * Greater failure tolerance in streaming
>>
>> Directly addressed by TRP.
>
> Agreed.
>
>> * Evenly distributed impact of streaming operations
>>
>> Not a problem in practice with stream throttling.
>
> Throttling slows them down, increasing rebuild times so increasing downtime.
>
>> * Possibility for active load balancing
>>
>> Not really a feature of vnodes per se, but as with the other load
>> balancing point, this is also improved by TRP.
>
> Again with the caveat that more data is streamed with TRP.  Vnodes
> removes the need for any load balancing with RP.
>
>> * Distributed rebuild
>>
>> This is the 20% that TRP does not address.  Nice to have?  Yes.  Can I
>> live without it?  I have so far.  Is this alone worth the complexity
>> of vnodes?  No, it is not.  Especially since there are probably other
>> approaches that we can take to mitigate this, one of which Rick has
>> suggested in a separate sub-thread.
>
> Distributed rebuild means you can store more data per node with the
> same failure probabilities.  This is frequently a limiting factor on
> how much data you can store per node, increasing cluster sizes
> unnecessarily.  I'd argue that this alone is worth the complexity of
> vnodes.
>
> Richard.



-- 
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com

Re: RFC: Cassandra Virtual Nodes

[Richard Low <rl...@acunu.com>]

On 20 March 2012 14:55, Jonathan Ellis <jb...@gmail.com> wrote:
> Here's how I see Sam's list:
>
> * Even load balancing when growing and shrinking the cluster
>
> Nice to have, but post-bootstrap load balancing works well in practice
> (and is improved by TRP).

Post-bootstrap load balancing without vnodes necessarily streams more
data than is necessary.  Vnodes streams the minimal amount.

In fact, post-bootstrap load balancing currently streams a constant
fraction of your data - the network traffic involved in a rebalance
increases linearly with the size of your cluster.  With vnodes it
decreases linearly.

Including removing the ops overhead of running the load balance and
calculating new tokens, this makes removing post-bootstrap load
balancing a pretty big deal.

> * Greater failure tolerance in streaming
>
> Directly addressed by TRP.

Agreed.

> * Evenly distributed impact of streaming operations
>
> Not a problem in practice with stream throttling.

Throttling slows them down, increasing rebuild times so increasing downtime.

> * Possibility for active load balancing
>
> Not really a feature of vnodes per se, but as with the other load
> balancing point, this is also improved by TRP.

Again with the caveat that more data is streamed with TRP.  Vnodes
removes the need for any load balancing with RP.

> * Distributed rebuild
>
> This is the 20% that TRP does not address.  Nice to have?  Yes.  Can I
> live without it?  I have so far.  Is this alone worth the complexity
> of vnodes?  No, it is not.  Especially since there are probably other
> approaches that we can take to mitigate this, one of which Rick has
> suggested in a separate sub-thread.

Distributed rebuild means you can store more data per node with the
same failure probabilities.  This is frequently a limiting factor on
how much data you can store per node, increasing cluster sizes
unnecessarily.  I'd argue that this alone is worth the complexity of
vnodes.

Richard.

Re: RFC: Cassandra Virtual Nodes

[Jonathan Ellis <jb...@gmail.com>]

On Tue, Mar 20, 2012 at 9:08 AM, Eric Evans <ee...@acunu.com> wrote:
> On Tue, Mar 20, 2012 at 8:39 AM, Jonathan Ellis <jb...@gmail.com> wrote:
>> I like this idea.  It feels like a good 80/20 solution -- 80% of the
>> benefits, 20% of the effort.  More like 5% of the effort.  I can't
>> even enumerate all the places full vnode support would change, but an
>> "active token range" concept would be relatively limited in scope.
>
> It only addresses 1 of Sam's original 5 points, so I wouldn't call it
> an "80% solution".

I guess a more accurate way to put this is, "only 20% of Sam's list is
an actual pain point that doesn't get addressed by The Rick Proposal
[TRP]."

Here's how I see Sam's list:

* Even load balancing when growing and shrinking the cluster

Nice to have, but post-bootstrap load balancing works well in practice
(and is improved by TRP).

* Greater failure tolerance in streaming

Directly addressed by TRP.

* Evenly distributed impact of streaming operations

Not a problem in practice with stream throttling.

* Possibility for active load balancing

Not really a feature of vnodes per se, but as with the other load
balancing point, this is also improved by TRP.

* Distributed rebuild

This is the 20% that TRP does not address.  Nice to have?  Yes.  Can I
live without it?  I have so far.  Is this alone worth the complexity
of vnodes?  No, it is not.  Especially since there are probably other
approaches that we can take to mitigate this, one of which Rick has
suggested in a separate sub-thread.

>> Full vnodes feels a lot more like the counters quagmire, where
>> Digg/Twitter worked on it for... 8? months, and then DataStax worked
>> on it about for about 6 months post-commit, and we're still finding
>> the occasional bug-since-0.7 there.  With the benefit of hindsight, as
>> bad as maintaining that patchset was out of tree, committing it as
>> early as we did was a mistake.  We won't do that again.  (On the
>> bright side, git makes maintaining such a patchset easier now.)
>
> And yet counters have become a very important feature for Cassandra;
> We're better off with them, than without.

False dichotomy (we could have waited for a better counter design),
but that's mostly irrelevant to my point that jamming incomplete code
in-tree to sort out later is a bad idea.

> I think there were a number of problems with how counters went down
> that could be avoided here.  For one, we can take a phased,
> incremental approach, rather than waiting 8 months to drop a large
> patchset.

If there are incremental improvements to be made that justify
themselves independently, then I agree.  Small, self-contained steps
are a good thing.  A good example is
https://issues.apache.org/jira/browse/CASSANDRA-2319, a product of The
Grand Storage Engine Redesign of 674 fame.

But, when things don't naturally break down into such mini-features,
then I'm -1 on committing code that has no purpose other than to be a
foundation for later commits.  I've seen people get bored or assigned
to other projects too often to just trust that those later commits
will indeed be forthcoming.  Or even if Sam [for instance] is still
working hard on it, it's very easy for unforseen difficulties to come
up that invalidate the original approach.  Since we were talking about
counters, the original vector clock approach -- that we ended up
ripping out, painfully -- is a good example.  Once bitten, twice shy.

-- 
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com

Re: RFC: Cassandra Virtual Nodes

[Richard Low <rl...@acunu.com>]

On 20 March 2012 14:50, Rick Branson <rb...@datastax.com> wrote:

> To support a form of DF, I think some tweaking of the replica placement could achieve this effect quite well. We could introduce a variable into replica placement, which I'm going to incorrectly call DF for the purposes of illustration. The key range for a node would be sub-divided by DF (1 by default) and this would be used to further distribution replica selection based on this "sub-partition".
>
> Currently, the offset formula works out to be something like this:
>
> offset = replica
>
> For RandomPartitioner, DF placement might look something like:
>
> offset = replica + (token % DF)
>
> Now, I realize replica selection is actually much more complicated than this, but these formulas are for illustration purposes.
>
> Modifying replica placement & the partitioners to support this seems straightforward, but I'm unsure of what's required to get it working for ring management operations. On the surface, it does seem like this could be added without any kind of difficult migration support.
>
> Thoughts?

This solution increases the DF, which has the advantage of providing
some balancing when a node is down temporarily.  The reads and writes
it would have served are now distributed around ~DF nodes.

However, it doesn't have any distributed rebuild.  In fact, any
distribution mechanism with one token per node cannot have distributed
rebuild.  Should a node fail, the next node in the ring has twice the
token range so must have twice the data.  This node will limit the
rebuild time - 'nodetool removetoken' will have to replicate the data
of the failed node onto this node.

Increasing the distribution factor without speeding up rebuild
increases the failure probability - both for data loss or being unable
to reach required consistency levels.  The failure probability is a
trade-off between rebuild time and distribution factor.  Lower rebuild
time helps, and lower distribution factor helps.

Cassandra as it is now has the longest rebuild time and lowest
possible distribution factor.  The original vnodes scheme is the other
extreme - shortest rebuild time and largest possible distribution
factor.
 It turns out that the rebuild time is more important, so this
decreases failure probability (with some assumptions you can show it
decreases by a factor RF! - I'll spare you the math but can send it if
you're interested).

This scheme has the longest rebuild time and a (tuneable) distribution
factor, but larger than the lowest.  That necessarily increases the
failure probability over both Cassandra now and vnode schemes, so I'd
be very careful about choosing it.

Richard.

Re: RFC: Cassandra Virtual Nodes

[Rick Branson <rb...@datastax.com>]

> > I like this idea. It feels like a good 80/20 solution -- 80% of the
> > benefits, 20% of the effort. More like 5% of the effort. I can't
> > even enumerate all the places full vnode support would change, but an
> > "active token range" concept would be relatively limited in scope.
> 
> 
> It only addresses 1 of Sam's original 5 points, so I wouldn't call it
> an "80% solution".
> 
To support a form of DF, I think some tweaking of the replica placement could achieve this effect quite well. We could introduce a variable into replica placement, which I'm going to incorrectly call DF for the purposes of illustration. The key range for a node would be sub-divided by DF (1 by default) and this would be used to further distribution replica selection based on this "sub-partition". 

Currently, the offset formula works out to be something like this:

offset = replica

For RandomPartitioner, DF placement might look something like:

offset = replica + (token % DF)

Now, I realize replica selection is actually much more complicated than this, but these formulas are for illustration purposes.

Modifying replica placement & the partitioners to support this seems straightforward, but I'm unsure of what's required to get it working for ring management operations. On the surface, it does seem like this could be added without any kind of difficult migration support. 

Thoughts?

Re: RFC: Cassandra Virtual Nodes

[Eric Evans <ee...@acunu.com>]

On Tue, Mar 20, 2012 at 8:39 AM, Jonathan Ellis <jb...@gmail.com> wrote:
> I like this idea.  It feels like a good 80/20 solution -- 80% of the
> benefits, 20% of the effort.  More like 5% of the effort.  I can't
> even enumerate all the places full vnode support would change, but an
> "active token range" concept would be relatively limited in scope.

It only addresses 1 of Sam's original 5 points, so I wouldn't call it
an "80% solution".

> Full vnodes feels a lot more like the counters quagmire, where
> Digg/Twitter worked on it for... 8? months, and then DataStax worked
> on it about for about 6 months post-commit, and we're still finding
> the occasional bug-since-0.7 there.  With the benefit of hindsight, as
> bad as maintaining that patchset was out of tree, committing it as
> early as we did was a mistake.  We won't do that again.  (On the
> bright side, git makes maintaining such a patchset easier now.)

And yet counters have become a very important feature for Cassandra;
We're better off with them, than without.

I think there were a number of problems with how counters went down
that could be avoided here.  For one, we can take a phased,
incremental approach, rather than waiting 8 months to drop a large
patchset.

> On Mon, Mar 19, 2012 at 5:16 PM, Rick Branson <rb...@datastax.com> wrote:
>> I think if we could go back and rebuild Cassandra from scratch, vnodes
>> would likely be implemented from the beginning. However, I'm concerned that
>> implementing them now could be a big distraction from more productive uses
>> of all of our time and introduce major potential stability issues into what
>> is becoming a business critical piece of infrastructure for many people.
>> However, instead of just complaining and pedantry, I'd like to offer a
>> feasible alternative:
>>
>> Has there been consideration given to the idea of a supporting a single
>> token range for a node?
>>
>> While not theoretically as capable as vnodes, it seems to me to be more
>> practical as it would have a significantly lower impact on the codebase and
>> provides a much clearer migration path. It also seems to solve a majority
>> of complaints regarding operational issues with Cassandra clusters.
>>
>> Each node would have a lower and an upper token, which would form a range
>> that would be actively distributed via gossip. Read and replication
>> requests would only be routed to a replica when the key of these operations
>> matched the replica's token range in the gossip tables. Each node would
>> locally store it's own current active token range as well as a target token
>> range it's "moving" towards.
>>
>> As a new node undergoes bootstrap, the bounds would be gradually expanded
>> to allow it to handle requests for a wider range of the keyspace as it
>> moves towards it's target token range. This idea boils down to a move from
>> hard cutovers to smoother operations by gradually adjusting active token
>> ranges over a period of time. It would apply to token change operations
>> (nodetool 'move' and 'removetoken') as well.
>>
>> Failure during streaming could be recovered at the bounds instead of
>> restarting the whole process as the active bounds would effectively track
>> the progress for bootstrap & target token changes. Implicitly these
>> operations would be throttled to some degree. Node repair (AES) could also
>> be modified using the same overall ideas provide a more gradual impact on
>> the cluster overall similar as the ideas given in CASSANDRA-3721.
>>
>> While this doesn't spread the load over the cluster for these operations
>> evenly like vnodes does, this is likely an issue that could be worked
>> around by performing concurrent (throttled) bootstrap & node repair (AES)
>> operations. It does allow some kind of "active" load balancing, but clearly
>> this is not as flexible or as useful as vnodes, but you should be using
>> RandomPartitioner or sort-of-randomized keys with OPP right? ;)
>>
>> As a side note: vnodes fail to provide solutions to node-based limitations
>> that seem to me to cause a substantial portion of operational issues such
>> as impact of node restarts / upgrades, GC and compaction induced latency. I
>> think some progress could be made here by allowing a "pack" of independent
>> Cassandra nodes to be ran on a single host; somewhat (but nowhere near
>> entirely) similar to a pre-fork model used by some UNIX-based servers.
>>
>> Input?
>>
>> --
>> Rick Branson
>> DataStax
>
>
>
> --
> Jonathan Ellis
> Project Chair, Apache Cassandra
> co-founder of DataStax, the source for professional Cassandra support
> http://www.datastax.com



-- 
Eric Evans
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Jonathan Ellis <jb...@gmail.com>]

I like this idea.  It feels like a good 80/20 solution -- 80% of the
benefits, 20% of the effort.  More like 5% of the effort.  I can't
even enumerate all the places full vnode support would change, but an
"active token range" concept would be relatively limited in scope.

Full vnodes feels a lot more like the counters quagmire, where
Digg/Twitter worked on it for... 8? months, and then DataStax worked
on it about for about 6 months post-commit, and we're still finding
the occasional bug-since-0.7 there.  With the benefit of hindsight, as
bad as maintaining that patchset was out of tree, committing it as
early as we did was a mistake.  We won't do that again.  (On the
bright side, git makes maintaining such a patchset easier now.)

On Mon, Mar 19, 2012 at 5:16 PM, Rick Branson <rb...@datastax.com> wrote:
> I think if we could go back and rebuild Cassandra from scratch, vnodes
> would likely be implemented from the beginning. However, I'm concerned that
> implementing them now could be a big distraction from more productive uses
> of all of our time and introduce major potential stability issues into what
> is becoming a business critical piece of infrastructure for many people.
> However, instead of just complaining and pedantry, I'd like to offer a
> feasible alternative:
>
> Has there been consideration given to the idea of a supporting a single
> token range for a node?
>
> While not theoretically as capable as vnodes, it seems to me to be more
> practical as it would have a significantly lower impact on the codebase and
> provides a much clearer migration path. It also seems to solve a majority
> of complaints regarding operational issues with Cassandra clusters.
>
> Each node would have a lower and an upper token, which would form a range
> that would be actively distributed via gossip. Read and replication
> requests would only be routed to a replica when the key of these operations
> matched the replica's token range in the gossip tables. Each node would
> locally store it's own current active token range as well as a target token
> range it's "moving" towards.
>
> As a new node undergoes bootstrap, the bounds would be gradually expanded
> to allow it to handle requests for a wider range of the keyspace as it
> moves towards it's target token range. This idea boils down to a move from
> hard cutovers to smoother operations by gradually adjusting active token
> ranges over a period of time. It would apply to token change operations
> (nodetool 'move' and 'removetoken') as well.
>
> Failure during streaming could be recovered at the bounds instead of
> restarting the whole process as the active bounds would effectively track
> the progress for bootstrap & target token changes. Implicitly these
> operations would be throttled to some degree. Node repair (AES) could also
> be modified using the same overall ideas provide a more gradual impact on
> the cluster overall similar as the ideas given in CASSANDRA-3721.
>
> While this doesn't spread the load over the cluster for these operations
> evenly like vnodes does, this is likely an issue that could be worked
> around by performing concurrent (throttled) bootstrap & node repair (AES)
> operations. It does allow some kind of "active" load balancing, but clearly
> this is not as flexible or as useful as vnodes, but you should be using
> RandomPartitioner or sort-of-randomized keys with OPP right? ;)
>
> As a side note: vnodes fail to provide solutions to node-based limitations
> that seem to me to cause a substantial portion of operational issues such
> as impact of node restarts / upgrades, GC and compaction induced latency. I
> think some progress could be made here by allowing a "pack" of independent
> Cassandra nodes to be ran on a single host; somewhat (but nowhere near
> entirely) similar to a pre-fork model used by some UNIX-based servers.
>
> Input?
>
> --
> Rick Branson
> DataStax



-- 
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com

Re: Cassandra and Round Robin

[Adam Haney <ad...@retickr.com>]

We use HaProxy on Ubuntu your mileage might vary on OS X.



On Apr 10, 2012, at 16:37, "Benny Rönnhager"
<be...@thrutherockies.com> wrote:

> I think Cassandra is a very interesting database but there a re a couple of things I don't understand.
>
> My plan is to have several Mac minis with one Cassandra node on each Mac mini. If one of my Mac minis will fail I want others to take over. Several nodes will also help me to load balance. I think that is exactly what Cassandra is built to do but…
>
> What do you guys suggest in front of Cassandra? Round-Robin or something else? I know that DynDNS have Round Robin in their Dynect platform but it's very expensive. I need a cheaper way.
>
>
>
>

Cassandra and Round Robin

[Benny Rönnhager <be...@thrutherockies.com>]

I think Cassandra is a very interesting database but there a re a couple of things I don't understand. 

My plan is to have several Mac minis with one Cassandra node on each Mac mini. If one of my Mac minis will fail I want others to take over. Several nodes will also help me to load balance. I think that is exactly what Cassandra is built to do but…

What do you guys suggest in front of Cassandra? Round-Robin or something else? I know that DynDNS have Round Robin in their Dynect platform but it's very expensive. I need a cheaper way.

Re: RFC: Cassandra Virtual Nodes

[Zhu Han <sc...@gmail.com>]

On Sat, Mar 24, 2012 at 7:55 AM, Peter Schuller <peter.schuller@infidyne.com
> wrote:

> > No I don't think you did, in fact, depending on the size of your SSTable
> a
> > contiguous range (or the entire SSTable) may or may not be affected by a
> > cleanup/move or any type of topology change. There is lots of room for
> > optimization here. After loading the indexes we actually know start/end
> > range for an SSTable so we can include/exclude it in any such operation
>
>
> Just note that unless there is some correlation between range and
> these sstables being created to begin with (like with leveled), you're
> highly unlikely to be able to optimize here. For uniformly distributed
> tokens (hashed keys), all sstables are likely to have almost the
> entire possible token range in them.
>

As Peter pointed out, for random partitioner, the rows of  a specific range
might scatter around all sstables.

Unless whole sstable can be ignored, disk seek is the performance killer
here.




> --
> / Peter Schuller (@scode, http://worldmodscode.wordpress.com)
>

Re: RFC: Cassandra Virtual Nodes

[Peter Schuller <pe...@infidyne.com>]

> No I don't think you did, in fact, depending on the size of your SSTable a
> contiguous range (or the entire SSTable) may or may not be affected by a
> cleanup/move or any type of topology change. There is lots of room for
> optimization here. After loading the indexes we actually know start/end
> range for an SSTable so we can include/exclude it in any such operation.

Just note that unless there is some correlation between range and
these sstables being created to begin with (like with leveled), you're
highly unlikely to be able to optimize here. For uniformly distributed
tokens (hashed keys), all sstables are likely to have almost the
entire possible token range in them.

-- 
/ Peter Schuller (@scode, http://worldmodscode.wordpress.com)

Re: RFC: Cassandra Virtual Nodes

[Ben Coverston <be...@datastax.com>]

> The SSTable indices should still be scanned for size tiered compaction.
> Do I miss anything here?
>
>
No I don't think you did, in fact, depending on the size of your SSTable a
contiguous range (or the entire SSTable) may or may not be affected by a
cleanup/move or any type of topology change. There is lots of room for
optimization here. After loading the indexes we actually know start/end
range for an SSTable so we can include/exclude it in any such operation.

-- 
Ben Coverston
DataStax -- The Apache Cassandra Company

Re: RFC: Cassandra Virtual Nodes

[Zhu Han <sc...@gmail.com>]

On Fri, Mar 23, 2012 at 6:54 AM, Peter Schuller <peter.schuller@infidyne.com
> wrote:

> > You would have to iterate through all sstables on the system to repair
> one
> > vnode, yes: but building the tree for just one range of the data means
> that
> > huge portions of the sstables files can be skipped. It should scale down
> > linearly as the number of vnodes increases (ie, with 100 vnodes, it will
> > take 1/100th the time to repair one vnode).
>

The SSTable indices should still be scanned for size tiered compaction.
Do I miss anything here?


> The story is less good for "nodetool cleanup" however, which still has
> to truck over the entire dataset.
>
> (The partitions/buckets in my crush-inspired scheme addresses this by
> allowing that each ring segment, in vnode terminology, be stored
> separately in the file system.)
>

But the number of files can be a big problem if there are hundreds of
vnodes and millions of sstables
on the same physical node.

We need a way to pin sstable inode to memory.  Otherwise,
it's possible the average number of disk IO to access a row in a sstable
could
be five or more.


>
> --
> / Peter Schuller (@scode, http://worldmodscode.wordpress.com)
>

Re: RFC: Cassandra Virtual Nodes

[Peter Schuller <pe...@infidyne.com>]

> You would have to iterate through all sstables on the system to repair one
> vnode, yes: but building the tree for just one range of the data means that
> huge portions of the sstables files can be skipped. It should scale down
> linearly as the number of vnodes increases (ie, with 100 vnodes, it will
> take 1/100th the time to repair one vnode).

The story is less good for "nodetool cleanup" however, which still has
to truck over the entire dataset.

(The partitions/buckets in my crush-inspired scheme addresses this by
allowing that each ring segment, in vnode terminology, be stored
separately in the file system.)

-- 
/ Peter Schuller (@scode, http://worldmodscode.wordpress.com)

Re: RFC: Cassandra Virtual Nodes

[Stu Hood <st...@gmail.com>]

>
> Does the new scheme  still require the node to re-iterate all sstables to
> build the merkle tree or streaming data for partition level
> repair and move?

You would have to iterate through all sstables on the system to repair one
vnode, yes: but building the tree for just one range of the data means that
huge portions of the sstables files can be skipped. It should scale down
linearly as the number of vnodes increases (ie, with 100 vnodes, it will
take 1/100th the time to repair one vnode).

On Thu, Mar 22, 2012 at 5:46 AM, Zhu Han <sc...@gmail.com> wrote:

> On Thu, Mar 22, 2012 at 6:20 PM, Richard Low <rl...@acunu.com> wrote:
>
> > On 22 March 2012 05:48, Zhu Han <sc...@gmail.com> wrote:
> >
> > > I second it.
> > >
> > > Is there some goals we missed which can not be achieved by assigning
> > > multiple tokens to a single node?
> >
> > This is exactly the proposed solution.  The discussion is about how to
> > implement this, and the methods of choosing tokens and replication
> > strategy.
> >
>
> Does the new scheme  still require the node to re-iterate all sstables to
> build the merkle tree or streaming data for partition level
> repair and move?
>
> The disk IO triggered by above steps could be very time-consuming if the
> dataset on single node is very large.  It could be much more costly than
> the network IO, especially when concurrent repair tasks hit the same
> node.
>
> Is there any good ideas on it?
>
>
> > Richard.
> >
>

Re: RFC: Cassandra Virtual Nodes

[Zhu Han <sc...@gmail.com>]

On Thu, Mar 22, 2012 at 6:20 PM, Richard Low <rl...@acunu.com> wrote:

> On 22 March 2012 05:48, Zhu Han <sc...@gmail.com> wrote:
>
> > I second it.
> >
> > Is there some goals we missed which can not be achieved by assigning
> > multiple tokens to a single node?
>
> This is exactly the proposed solution.  The discussion is about how to
> implement this, and the methods of choosing tokens and replication
> strategy.
>

Does the new scheme  still require the node to re-iterate all sstables to
build the merkle tree or streaming data for partition level
repair and move?

The disk IO triggered by above steps could be very time-consuming if the
dataset on single node is very large.  It could be much more costly than
the network IO, especially when concurrent repair tasks hit the same
node.

Is there any good ideas on it?


> Richard.
>

Re: RFC: Cassandra Virtual Nodes

[Richard Low <rl...@acunu.com>]

On 22 March 2012 05:48, Zhu Han <sc...@gmail.com> wrote:

> I second it.
>
> Is there some goals we missed which can not be achieved by assigning
> multiple tokens to a single node?

This is exactly the proposed solution.  The discussion is about how to
implement this, and the methods of choosing tokens and replication
strategy.

Richard.

Re: RFC: Cassandra Virtual Nodes

[Zhu Han <sc...@gmail.com>]

On Tue, Mar 20, 2012 at 11:24 PM, Jeremiah Jordan <
JEREMIAH.JORDAN@morningstar.com> wrote:

> So taking a step back, if we want "vnodes" why can't we just give every
> node 100 tokens instead of only one?  Seems to me this would have less
> impact on the rest of the code.  It would just look like you had a 500 node
> cluster, instead of a 5 node cluster.  Your replication strategy would have
> to know about the physical machines so that data gets replicated right, but
> there is already some concept of this with the data center aware and rack
> aware stuff.
>
> From what I see I think you could get most of the benefits of vnodes by
> implementing a new Placement Strategy that did something like this, and you
> wouldn't have to touch (and maybe break) code in other places.
>
> Am I crazy? Naive?
>
> Once you had this setup, you can start to implement the vnode like stuff
> on top of it.  Like bootstrapping nodes in one token at a time, and taking
> them on from the whole cluster, not just your neighbor. etc. etc.
>

I second it.

Is there some goals we missed which can not be achieved by assigning
multiple tokens to a single node?


>
> -Jeremiah Jordan
>
> ________________________________________
> From: Rick Branson [rbranson@datastax.com]
> Sent: Monday, March 19, 2012 5:16 PM
> To: dev@cassandra.apache.org
> Subject: Re: RFC: Cassandra Virtual Nodes
>
> I think if we could go back and rebuild Cassandra from scratch, vnodes
> would likely be implemented from the beginning. However, I'm concerned that
> implementing them now could be a big distraction from more productive uses
> of all of our time and introduce major potential stability issues into what
> is becoming a business critical piece of infrastructure for many people.
> However, instead of just complaining and pedantry, I'd like to offer a
> feasible alternative:
>
> Has there been consideration given to the idea of a supporting a single
> token range for a node?
>
> While not theoretically as capable as vnodes, it seems to me to be more
> practical as it would have a significantly lower impact on the codebase and
> provides a much clearer migration path. It also seems to solve a majority
> of complaints regarding operational issues with Cassandra clusters.
>
> Each node would have a lower and an upper token, which would form a range
> that would be actively distributed via gossip. Read and replication
> requests would only be routed to a replica when the key of these operations
> matched the replica's token range in the gossip tables. Each node would
> locally store it's own current active token range as well as a target token
> range it's "moving" towards.
>
> As a new node undergoes bootstrap, the bounds would be gradually expanded
> to allow it to handle requests for a wider range of the keyspace as it
> moves towards it's target token range. This idea boils down to a move from
> hard cutovers to smoother operations by gradually adjusting active token
> ranges over a period of time. It would apply to token change operations
> (nodetool 'move' and 'removetoken') as well.
>
> Failure during streaming could be recovered at the bounds instead of
> restarting the whole process as the active bounds would effectively track
> the progress for bootstrap & target token changes. Implicitly these
> operations would be throttled to some degree. Node repair (AES) could also
> be modified using the same overall ideas provide a more gradual impact on
> the cluster overall similar as the ideas given in CASSANDRA-3721.
>
> While this doesn't spread the load over the cluster for these operations
> evenly like vnodes does, this is likely an issue that could be worked
> around by performing concurrent (throttled) bootstrap & node repair (AES)
> operations. It does allow some kind of "active" load balancing, but clearly
> this is not as flexible or as useful as vnodes, but you should be using
> RandomPartitioner or sort-of-randomized keys with OPP right? ;)
>
> As a side note: vnodes fail to provide solutions to node-based limitations
> that seem to me to cause a substantial portion of operational issues such
> as impact of node restarts / upgrades, GC and compaction induced latency. I
> think some progress could be made here by allowing a "pack" of independent
> Cassandra nodes to be ran on a single host; somewhat (but nowhere near
> entirely) similar to a pre-fork model used by some UNIX-based servers.
>
> Input?
>
> --
> Rick Branson
> DataStax
>

RE: RFC: Cassandra Virtual Nodes

[Jeremiah Jordan <JE...@morningstar.com>]

So taking a step back, if we want "vnodes" why can't we just give every node 100 tokens instead of only one?  Seems to me this would have less impact on the rest of the code.  It would just look like you had a 500 node cluster, instead of a 5 node cluster.  Your replication strategy would have to know about the physical machines so that data gets replicated right, but there is already some concept of this with the data center aware and rack aware stuff.

>From what I see I think you could get most of the benefits of vnodes by implementing a new Placement Strategy that did something like this, and you wouldn't have to touch (and maybe break) code in other places.

Am I crazy? Naive?

Once you had this setup, you can start to implement the vnode like stuff on top of it.  Like bootstrapping nodes in one token at a time, and taking them on from the whole cluster, not just your neighbor. etc. etc.

-Jeremiah Jordan

________________________________________
From: Rick Branson [rbranson@datastax.com]
Sent: Monday, March 19, 2012 5:16 PM
To: dev@cassandra.apache.org
Subject: Re: RFC: Cassandra Virtual Nodes

I think if we could go back and rebuild Cassandra from scratch, vnodes
would likely be implemented from the beginning. However, I'm concerned that
implementing them now could be a big distraction from more productive uses
of all of our time and introduce major potential stability issues into what
is becoming a business critical piece of infrastructure for many people.
However, instead of just complaining and pedantry, I'd like to offer a
feasible alternative:

Has there been consideration given to the idea of a supporting a single
token range for a node?

While not theoretically as capable as vnodes, it seems to me to be more
practical as it would have a significantly lower impact on the codebase and
provides a much clearer migration path. It also seems to solve a majority
of complaints regarding operational issues with Cassandra clusters.

Each node would have a lower and an upper token, which would form a range
that would be actively distributed via gossip. Read and replication
requests would only be routed to a replica when the key of these operations
matched the replica's token range in the gossip tables. Each node would
locally store it's own current active token range as well as a target token
range it's "moving" towards.

As a new node undergoes bootstrap, the bounds would be gradually expanded
to allow it to handle requests for a wider range of the keyspace as it
moves towards it's target token range. This idea boils down to a move from
hard cutovers to smoother operations by gradually adjusting active token
ranges over a period of time. It would apply to token change operations
(nodetool 'move' and 'removetoken') as well.

Failure during streaming could be recovered at the bounds instead of
restarting the whole process as the active bounds would effectively track
the progress for bootstrap & target token changes. Implicitly these
operations would be throttled to some degree. Node repair (AES) could also
be modified using the same overall ideas provide a more gradual impact on
the cluster overall similar as the ideas given in CASSANDRA-3721.

While this doesn't spread the load over the cluster for these operations
evenly like vnodes does, this is likely an issue that could be worked
around by performing concurrent (throttled) bootstrap & node repair (AES)
operations. It does allow some kind of "active" load balancing, but clearly
this is not as flexible or as useful as vnodes, but you should be using
RandomPartitioner or sort-of-randomized keys with OPP right? ;)

As a side note: vnodes fail to provide solutions to node-based limitations
that seem to me to cause a substantial portion of operational issues such
as impact of node restarts / upgrades, GC and compaction induced latency. I
think some progress could be made here by allowing a "pack" of independent
Cassandra nodes to be ran on a single host; somewhat (but nowhere near
entirely) similar to a pre-fork model used by some UNIX-based servers.

Input?

--
Rick Branson
DataStax

Re: RFC: Cassandra Virtual Nodes

[Peter Schuller <pe...@infidyne.com>]

> Each node would have a lower and an upper token, which would form a range
> that would be actively distributed via gossip. Read and replication
> requests would only be routed to a replica when the key of these operations
> matched the replica's token range in the gossip tables. Each node would
> locally store it's own current active token range as well as a target token
> range it's "moving" towards.

How is this significantly different than just using "nodetool move"
(in post-1.x) more rapidly and on smaller segments at a time?

There is the ring delay stuff which makes it un-workable to do at high
granularity, but that should apply to the active range solution too.

-- 
/ Peter Schuller (@scode, http://worldmodscode.wordpress.com)

Re: RFC: Cassandra Virtual Nodes

[Rick Branson <rb...@datastax.com>]

I think if we could go back and rebuild Cassandra from scratch, vnodes
would likely be implemented from the beginning. However, I'm concerned that
implementing them now could be a big distraction from more productive uses
of all of our time and introduce major potential stability issues into what
is becoming a business critical piece of infrastructure for many people.
However, instead of just complaining and pedantry, I'd like to offer a
feasible alternative:

Has there been consideration given to the idea of a supporting a single
token range for a node?

While not theoretically as capable as vnodes, it seems to me to be more
practical as it would have a significantly lower impact on the codebase and
provides a much clearer migration path. It also seems to solve a majority
of complaints regarding operational issues with Cassandra clusters.

Each node would have a lower and an upper token, which would form a range
that would be actively distributed via gossip. Read and replication
requests would only be routed to a replica when the key of these operations
matched the replica's token range in the gossip tables. Each node would
locally store it's own current active token range as well as a target token
range it's "moving" towards.

As a new node undergoes bootstrap, the bounds would be gradually expanded
to allow it to handle requests for a wider range of the keyspace as it
moves towards it's target token range. This idea boils down to a move from
hard cutovers to smoother operations by gradually adjusting active token
ranges over a period of time. It would apply to token change operations
(nodetool 'move' and 'removetoken') as well.

Failure during streaming could be recovered at the bounds instead of
restarting the whole process as the active bounds would effectively track
the progress for bootstrap & target token changes. Implicitly these
operations would be throttled to some degree. Node repair (AES) could also
be modified using the same overall ideas provide a more gradual impact on
the cluster overall similar as the ideas given in CASSANDRA-3721.

While this doesn't spread the load over the cluster for these operations
evenly like vnodes does, this is likely an issue that could be worked
around by performing concurrent (throttled) bootstrap & node repair (AES)
operations. It does allow some kind of "active" load balancing, but clearly
this is not as flexible or as useful as vnodes, but you should be using
RandomPartitioner or sort-of-randomized keys with OPP right? ;)

As a side note: vnodes fail to provide solutions to node-based limitations
that seem to me to cause a substantial portion of operational issues such
as impact of node restarts / upgrades, GC and compaction induced latency. I
think some progress could be made here by allowing a "pack" of independent
Cassandra nodes to be ran on a single host; somewhat (but nowhere near
entirely) similar to a pre-fork model used by some UNIX-based servers.

Input?

--
Rick Branson
DataStax

Re: RFC: Cassandra Virtual Nodes

[Sam Overton <sa...@acunu.com>]

Hi Peter,

It's great to hear that others have come to some of the same conclusions!

I think a CRUSH-like strategy for topologically aware
replication/routing/locality is a great idea. I think I can see three
mostly orthogonal sets of functionality that we're concerned with:

a) a virtual node partitioning scheme (to support heterogeneity and
management simplicity)
b) topology aware replication
c) topology aware routing

First of all, I think that while (c) depends on (b) it does not affect
partitioning or replication directly, so I'm going to set that aside
for the moment and talk just about the former two.

I'll summarise your design here, mainly to make sure that I understand
it, but also to refer back to it:

1. The hash-space is partitioned into a fixed number of partitions
2. The CRUSH algorithm is run - select(1, disk) - over the topology
using each partition as a key, to get an assignment of partition ->
physical host (primary)
2a. adding or removing a node requires re-running CRUSH to recalculate
the partition assignment (and move data)
3. The CRUSH algorithm is run - select(RF-1, disk) - over the topology
using each primary host id, to get an assignment of primary host ->
RF-1 replicas
3a. adding or removing a node requires re-running CRUSH to recalculate
replica assignment (which might be a different set of hosts to
before?)

Here are some thoughts:
(clarification: when I'm talking about buckets, I'm referring to the
same concept as in the CRUSH paper!)

One of my concerns about using CRUSH exactly as described in the paper
is that it seems to be sub-optimal in the amount of data that it moves
after modifying the topology. The authors of the paper introduce
several "bucket types" (uniform, list, tree, straw) which appear to be
various sub-optimal alternatives to consistent hashing, with various
trade-offs. Why not use consistent hashing? Given (2a) and (3a) I
think we might end up moving way too much data when the set of
replicas changes completely for a given host.

Let's suppose we introduce our own bucket type called a "ring bucket".
Each item in a ring bucket is assigned an equal, non-contiguous
portion of the key hash-space, which determines which keys are
assigned to it. When an item is added to the ring bucket, it takes an
equal portion of the hash-space from every other item already in the
bucket. And vice-versa for removals. It's easy to see that this ring
bucket implements consistent hashing with some unspecified virtual
node scheme. Additions and removals would be optimal (only \deltaw/W
keys require moving when the topology changes).

Using this ring bucket in the CRUSH topology, (with the hash function
being the identity function) would give the exact same distribution
properties as the virtual node strategy that I suggested previously,
but of course with much better topology awareness.

This makes it evident that the partitioning scheme, and a CRUSH-like
replication scheme are orthogonal concerns. In the same way as NTS
currently uses the ring to provide distribution at DC and rack level
by conceptually separating the ring into a distinct logical rings for
each DC, a CrushReplicationStrategy could use the ring as its
bucketing function to distribute partitions in the topology.

This brings me on to (1) and the reasons for our choice of virtual
node scheme - choose N random tokens - instead of the Dynamo-like
scheme that you suggest where the partitions are fixed in advance.
With the Dynamo scheme, the size of a virtual node partition will only
ever grow as more data is inserted. Since the number of partitions is
fixed when the cluster is created, the partition size is unbounded.

There are certain advantages to having a limit on partition size.
Streaming failures that cause retries do not have to resend so much
data. Streaming operations can be staggered in smaller chunks to
minimise the impact on the nodes involved. Load balancing can operate
on a finer granularity.

In the N tokens per node scheme, adding nodes to the cluster decreases
the partition size and so gives some control about how much data is
stored in each partition. The average size can be reduced by adding
more machines to the cluster.

The other concern you mentioned was
> The probability of data loss increases linearly with cluster size.

but you also acknowledge that

> In making this determination, one must take into account that if a
> larger `DF` makes reconstruction/replacement significantly faster,
> that also decreases the time window in which multiple failures can
> occurr. Increasing `DF` is thus not *necessarily* increasing the total
> probability of data loss (for small values of `DF`).

Our calculations lead us to believe that in fact the shorter rebuild
window more than compensates for the increased probability of multiple
failure, so with DF=N the probability of data loss is minimised.

The CRUSH paper also states:

"With 2-way mirroring these two factors cancel
each other out, while overall data safety with more than two
replicas increases with declustering [Xin et al. 2004]"

("declustering" meaning increasing DF towards N)


Regards,


--
Sam Overton
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Peter Schuller <pe...@infidyne.com>]

Point of clarification: My use of the term "bucket" is completely
unrelated to the term "bucket" used in the CRUSH paper.

-- 
/ Peter Schuller (@scode, http://worldmodscode.wordpress.com)

Re: RFC: Cassandra Virtual Nodes

[Peter Schuller <pe...@infidyne.com>]

> *The summary is*: we believe virtual nodes are the way forward. We would
> like to add virtual nodes to Cassandra and we are asking for comments,
> criticism and collaboration!

I am very happy to see some momentum on this, and I would like to go
even further than what you propose. The main reasons why I do not
think simply adding vnodes and making random assignments is the best
end goal are:

(1) The probability of data loss increases linearly with cluster size.
(2) It does not take network topology into account.

What follows is mostly a half-finished long text that I have been
sitting on for a few months but not finished/posted. Unfortunately I
do not have the possibility (due to time constraints) to go through
everything in detail and update with current information and to
specifically address what you already said, so there will be overlap
with your original post. However given your E-Mail and the momentum in
this thread, I really wanted to post something rather than not. It
would be awesome if interested parties had a chance to read the
referenced CRUSH paper, and the deltas proposed below.

The goals are to address everything you already wanted in your post,
while also addressing:

(1) Probability of data loss
(2) Network topology awareness

The following text will first try to paint a picture of the goals that
I have in mind, and then go on to the actual proposed solution. The
proposition is very very short and undetailed now and there is plenty
of discussion and details to fill in. I apologize, but again, I really
want to post something now that this is being brought up.

BEGIN un-polished text ("we" = "I"):=

= CRUSHing Cassandra

Author: Peter Schuller <pe...@infidyne.com>

This is a proposal for a significant re-design of some fundamentals of
Cassandra, aimed at addressing a number of current issues as well as
anticipating future issues. It is particularly aimed at large
clusters, but as a side-effect should improve the small cluster
experience as well.

== New terminology: Distribution factor

A Cassandra cluster is today said to have `N` nodes, and data is
replicated at a particular replication factor (`RF`). The placement of
replicas is such that all rows that has a certain node `N1` as its
primary replica, are located on a specific set of `RF-1` other
nodes. In addition, it holds secondary replicas of data for `RF-1`
other nodes. In total, it shares data with `2RF - 2` other nodes.

The number of nodes with whom a node shares data is the distribution
factor. In the case of Cassandra, `DF = 2RF - 2`.

== Goals

The goals this suggestion attempts to help solve include the following.

=== Goal: DF should not be tied to RF, nor N

`DF` is important for these reasons:

* The `DF` determines how many nodes are involved in re-constructing a
  lost node after failure; the higher the `DF`, the less of a
  performance impact a reconstruction has on remaining nodes.
* The `DF` determines the significance on other nodes, with respect to
  read/write load, on a node being down.
* The `DF` affects the probability of multiple failures causing data
  loss, since one looses data if any `RF` nodes within a group of `DF`
  nodes all go down.

Having `DF` tied to `RF` like Cassandra does now has its problems. A
single node failure has a significant effect on the performance
characteristics of neighboring nodes (in terms relative to the normal
level of load on the neighbors).

On large data sets, a failed node needing reconstruction is a
significant event, as it

* Increases the load on neighbors just from going down.
* Further increases the load on neighbors as they have to stream data
(adding I/O
  and cache thrashing).

This typically leads to the desire to throttle / rate limit
reconstruction, which adds to the reconstruction window in addition to
the fact that it was already naturally bottlenecking on neighbors.

The other extreme is to tie `DF` to `N`, such that the data contained
on one node, has it's secondary replicas spread out over the entire
ring. This is an unacceptable choice because the probabiliy of multiple
failures increases linearly with the cluster size.

In other words, we want `DF` to be tied to neither `RF` nor
`N`. Rather, `DF` should be chosen as a trade-off between the effects
of `DF`:

* The higher the `DF`, the higher the probability of data loss in case
  of multiple failures.
* The higher the `DF`, the faster to reconstruct/replace a lost node.
* The higher the `DF`, the less impact is seen on node failures on the
  performance requirements on other nodes.

In making this determination, one must take into account that if a
larger `DF` makes reconstruction/replacement significantly faster,
that also decreases the time window in which multiple failures can
occurr. Increasing `DF` is thus not *necessarily* increasing the total
probability of data loss (for small values of `DF`).

=== Goal: Topologically aware redundancy

We maintain the goal of being topology aware for the purpose of
ensuring that we place replicas on "independent" nodes (for a
definition of "independent" that is up to the operator). This is
currently implemented in a limited fashion by the DC and rack
awareness offered by the `NetworkTopologyStrategy`.

We want to go further than that, and allow close to arbitrary
topologies to be modeled. For example, we may require, in a single
data center, that a piece of data is replicated to 3 distinct racks,
at least two of which must be within different cages in the data
center.

=== Goal: Topologically aware locality

Somewhat in conflict with the previous goal, there is also a desire to
keep replicas "close". In a sufficiently large cluster, it becomes
cost-prohibitive to pipe all inter-replica traffic through a fast
backbone network.

Ideally, one want to balance the two. For example, one could arrange
for replicas to be distributed across different racks in a cage in a
data center, limiting cross-replica network bandwidth requirements to
the local switch in said cage, while maintaining independent power
supply/networking to racks for redundancy.

With gigabit+ speeds from a node, it is very easy to saturate
networking infrastructure once you start having hundreds of nodes or
more.

=== Goal: Topologically aware routing

Once a cluster grows sufficiently large, even with topologically aware
locality, you eventually want to avoid the
everybody-talks-to-everybody situtation of current Cassandra, for
network efficiency reasons. This includes the clients.

Topologically aware routing would enable selection of a co-ordinator
node more intelligently (consider "edge" router nodes that are
Cassandra aware, to which application clients connect to - e.g. you
might have one such per data center, or part of a DC), and provided
sufficient site-specific integration, allow the routing of traffic to
that co-ordinator to be routed efficiently at the networking level.

A request could go all the way from a client, to a
co-ordinator/router, to responsible replicas, and back - never
crossing a backbone switch/router.

=== Goal: Agility

We want adding, removing or re-balancing nodes to be a trivial
operation for the operator's perspective, and to have a minimal impact
on the performance of the cluster. We want to enable adding individual
hosts, groups of hosts, or entire racks of hosts easily and without
significant risk of mistakes. There should be no need to carefully
plan and co-ordinate upgrades due to performance reasons.

The operator should have the flexibility of quickly adding capacity as
demands change (which they will, even with careful planning to
minimize it). There must not be artificial limitations like requiring
a doubling of the cluster in order to avoid very painful and
performance degrading operations. The operator should never be in a
position to have to consider the trae-off between adding 30% capacity
now at great cost in operator effort and risk, vs. waiting another two
weeks for that promised delivery of servers, for example.

Consider a large deployment with multiple clusters. It is desirable to
capacity project each cluster individually, and have a constantly
re-populated pool of servers that are used for expansion and/or
replacement of nodes. Adding capacity to existing cluters could be
done even on a daily basis, in an effort to keap average utilization
as smooth as possible (having a varying average utilization
contributes is one more factor that contributes to the need to
over-provision; in a 1000 node cluster expected to double in size in a
year for example, it is efficient to incrementally add capacity rather
than, say, add 500 on day one and 500 at the half-way point; if
nothing else, doing the latter would imply a 250 node average
over-provisioning during a year *just* due to lack of agility in
expansion, on top of other factors).

=== Goal: Heterogenous nodes

We want it to be realistic and minimally impactful to have nodes of
different performance characteristics in the cluster.

=== Goal: Operator simplicity

The current situation is unacceptably complex. Maintaing a multi-DC
cluster with rack awareness requires significant planning, care and
often automation on the part of the operator to maintain an
appropriately layed out ring, without causing rack hotspots or other
issues. Auditing correct ring layout is essentially impossible for a
human with the out-of-the-box tools, and currently require
site-specific scripting (e.g., `nodetool ring` is close to useless
without significant mental or automated post-processing).

We want to significantly increase operator simplicity (minimizing the
risk for operator error and minimize the effort required by an
operator).

== Proposed solution

The proposal draws inspiration from the CRUSH paper:

   http://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf

Currently, because this is an unfinished document, that paper is
pre-requisite reading.

Here are the deltas proposed:

=== Buckets and pre-calculation

The key on which we would apply the crush algorithm would not be the
Cassandra row key. Instead the Cassandra keyspace is partitioned (by
hashing) into N buckets. N must be large enough to accomodate future
cluster expansions, and to accomodate probabilistic effects when
applying a CRUSH-like algorithm so that we achieve balancing.

The main reasons to use buckets are:

* It allows pre-calculation of the results of the CRUSH-like algorithm, which
  removes the CPU/balancing trade-offs from the equation that the CRUSH paper
  focuses on. We can go with the optimally balanced solution.
* A "bucket" is tantamount to a ring segment. Similarly to how
Cassandra already does it,
  we want to efficiently be able to transfer a single bucket without
having to traverse
  the entire data set or a node-global index of all data. Thus,
buckets directly relate
  to structuring data on disk in a way which is non-orthogonal to the
unit of data being
  moved around on topology changes.
* It helps the balancing/accurace trade-off, see below.

=== Replica selection

In order to cater to Distrihution Factor, we need to use the primary
replica, as opposed to the bucket id, in the key when applying the
CRUSH-like algorithm on finding secondary replicas.

=== Balancing accuracy vs. RDF vs. unnecessary movement trade-off

When limiting replicas to be among RDF other nodes, you introduce an
artificial constraint on replica placement that causes greater
imbalance due to the low number of nodes you are distributing over
(each node has replicas for data otherwise primary on DF-1 nodes, and
assuming DF is not huge, DF-1 is a smallish number, and thus balancing
will be limited).

An algorithm to get around this is to calculate the placement in a
deterministic fashion (such as in order) with resperct to bucket
id. If, when assigning a secondary replica, the proposed replica is
already above quota, you reject the selection and keep going. This
achieves balance, but at the cost of additional data movement because
every time you perform a rejection, you are causing the placement of a
virtual bucket to be affected by something *other* than the nodes on
which it is placed.

-- 
/ Peter Schuller (@scode, http://worldmodscode.wordpress.com)

Re: RFC: Cassandra Virtual Nodes

[Eric Evans <ee...@acunu.com>]

On Sat, Mar 17, 2012 at 3:22 PM, Zhu Han <sc...@gmail.com> wrote:
> On Sat, Mar 17, 2012 at 7:38 AM, Sam Overton <sa...@acunu.com> wrote:
>> This is a long email. It concerns a significant change to Cassandra, so
>> deserves a thorough introduction.
>>
>> *The summary is*: we believe virtual nodes are the way forward. We would
>> like to add virtual nodes to Cassandra and we are asking for comments,
>> criticism and collaboration!
>>
>> Cassandra's current partitioning scheme is sub-optimal for bootstrap,
>> decommission, repair and re-balance operations, and places the burden on
>> users to properly calculate tokens (a common cause of mistakes), which is a
>> recurring pain-point.
>>
>> Virtual nodes have a variety of benefits over the one-to-one mapping of
>> host to key range which Cassandra currently supports.
>>
>> Among these benefits are:
>>
>> * Even load balancing when growing and shrinking the cluster
>> A virtual node scheme ensures that all hosts in a cluster have an even
>> portion of the total data, and a new node bootstrapped into the cluster
>> will assume its share of the data. Doubling, or halving the cluster to
>> ensure even load distribution would no longer be necessary.
>>
>> * Distributed rebuild
>> When sizing a cluster, one of the considerations is the amount of time
>> required to recover from a failed node. This is the exposure time, during
>> which a secondary failure could cause data loss. In order to guarantee an
>> upper bound on the exposure time, the amount of data which can be stored on
>> each host is limited by the amount of time taken to recover the required
>> replica count. At Acunu we have found that the exposure time is frequently
>> the limiting factor which dictates the maximum allowed node size in
>> customers' clusters.
>>
>> Using a virtual node scheme, the data stored on one host is not replicated
>> on just RF-1 other physical hosts. Each virtual node is replicated to RF-1
>> other virtual nodes which may be on a different set of physical hosts to
>> replicas of other virtual nodes stored on the same host. This means data
>> for one host is replicated evenly across the entire cluster.
>>
>> In the event of a failure then, restoring the replica count can be done in
>> a fully distributed way. Each host in the cluster participates in the
>> rebuild, drastically reducing the exposure time, allowing more data to be
>> stored on a single host while still maintaining an acceptable upper bound
>> on the likelihood of secondary failure. This reduces TCO concerns.
>>
>> * Greater failure tolerance in streaming
>> Operations which require streaming of a large range of data, eg. bootstrap,
>> decommission, repair, etc. incur a heavy cost if an error (eg. dropped
>> network connection) is encountered during the streaming. Currently the
>> whole range must be re-streamed, and this could constitute a very large
>> amount of data. Virtual nodes reduce the impact of streaming failures,
>> since each virtual node is a much smaller range of the key-space, so
>> re-streaming a whole virtual node is a much cheaper process.
>>
>> * Evenly distributed impact of streaming operations
>> Streaming operations such as bootstrap, repair, et al. would involve every
>> node in the cluster. This would distribute the load of these operations
>> across the whole cluster, and could be staggered so that only a small
>> subset of nodes were affected at once, similar to staggered repair[1].
>>
>> * Possibility for active load balancing
>> Load balancing in Cassandra currently involves moving a token to
>> increase/reduce the amount of key-space for which a host is responsible.
>> This only allows load balancing between neighbouring nodes, so it could
>> involve moving more than one token just to redistribute a single overloaded
>> node. Virtual nodes could allow load balancing on a much finer granularity,
>> so heavily loaded portions of the key-space could be redistributed to
>> lighter-loaded hosts by reassigning one or more virtual nodes.
>>
>>
>> Implementing a virtual node scheme in Cassandra is not an insignificant
>> amount of work, and it will touch a large amount of the codebase related to
>> partitioning, placement, routing, gossip, and so on. We do believe that
>> this is possible to do incrementally, and in such a way that there is an
>> easy upgrade path for pre-virtual-node deployments.
>>
>> It would not however touch the storage layer. The virtual node concept is
>> solely for partitioning and placement, not for segregating the data storage
>> of the host, so all keys for all virtual nodes on a host would be stored in
>> the same SSTables.
>>
>> We are not proposing the adoption of the same scheme used by Voldemort[2]
>> and described in the Dynamo paper[3]. We feel this scheme is too different
>> from Cassandra's current distribution model to be a viable target for
>> incremental development. Their scheme also fixes the number of virtual
>> nodes for the lifetime of the cluster, which can prove to be a ceiling to
>> scaling the cluster if the virtual nodes grow too large.
>>
>> The proposed design is:
>> * Assign each host T random tokens.
>>
>
> Will it work well for OrderedPartitioner?

It doesn't preclude the use of an ordered partitioner, but depending
on the size of the range, and the number of tokens (T * nodes), it
could mean contacting more nodes.  You could look at that as a
negative or positive I suppose.

Either way, I'm sure that most people would agree at this point that
it doesn't make sense to optimize for ordered partitioning;
Conventional wisdom is to use the RandomPartitioner

> For load balance purpose, is it possible to detect the access pattern of
> range and move
> the range dynamically instead of introducing virtual node?

Anything is possible, but automating doesn't solve any of the real
problems.  Ultimately you want to avoid having to rebalance in the
first place, and if it can't be avoided, to parallelize it over many
nodes.

-- 
Eric Evans
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Zhu Han <sc...@gmail.com>]

On Sat, Mar 17, 2012 at 7:38 AM, Sam Overton <sa...@acunu.com> wrote:

> Hello cassandra-dev,
>
> This is a long email. It concerns a significant change to Cassandra, so
> deserves a thorough introduction.
>
> *The summary is*: we believe virtual nodes are the way forward. We would
> like to add virtual nodes to Cassandra and we are asking for comments,
> criticism and collaboration!
>
> Cassandra's current partitioning scheme is sub-optimal for bootstrap,
> decommission, repair and re-balance operations, and places the burden on
> users to properly calculate tokens (a common cause of mistakes), which is a
> recurring pain-point.
>
> Virtual nodes have a variety of benefits over the one-to-one mapping of
> host to key range which Cassandra currently supports.
>
> Among these benefits are:
>
> * Even load balancing when growing and shrinking the cluster
> A virtual node scheme ensures that all hosts in a cluster have an even
> portion of the total data, and a new node bootstrapped into the cluster
> will assume its share of the data. Doubling, or halving the cluster to
> ensure even load distribution would no longer be necessary.
>
> * Distributed rebuild
> When sizing a cluster, one of the considerations is the amount of time
> required to recover from a failed node. This is the exposure time, during
> which a secondary failure could cause data loss. In order to guarantee an
> upper bound on the exposure time, the amount of data which can be stored on
> each host is limited by the amount of time taken to recover the required
> replica count. At Acunu we have found that the exposure time is frequently
> the limiting factor which dictates the maximum allowed node size in
> customers' clusters.
>
> Using a virtual node scheme, the data stored on one host is not replicated
> on just RF-1 other physical hosts. Each virtual node is replicated to RF-1
> other virtual nodes which may be on a different set of physical hosts to
> replicas of other virtual nodes stored on the same host. This means data
> for one host is replicated evenly across the entire cluster.
>
> In the event of a failure then, restoring the replica count can be done in
> a fully distributed way. Each host in the cluster participates in the
> rebuild, drastically reducing the exposure time, allowing more data to be
> stored on a single host while still maintaining an acceptable upper bound
> on the likelihood of secondary failure. This reduces TCO concerns.
>
> * Greater failure tolerance in streaming
> Operations which require streaming of a large range of data, eg. bootstrap,
> decommission, repair, etc. incur a heavy cost if an error (eg. dropped
> network connection) is encountered during the streaming. Currently the
> whole range must be re-streamed, and this could constitute a very large
> amount of data. Virtual nodes reduce the impact of streaming failures,
> since each virtual node is a much smaller range of the key-space, so
> re-streaming a whole virtual node is a much cheaper process.
>
> * Evenly distributed impact of streaming operations
> Streaming operations such as bootstrap, repair, et al. would involve every
> node in the cluster. This would distribute the load of these operations
> across the whole cluster, and could be staggered so that only a small
> subset of nodes were affected at once, similar to staggered repair[1].
>
> * Possibility for active load balancing
> Load balancing in Cassandra currently involves moving a token to
> increase/reduce the amount of key-space for which a host is responsible.
> This only allows load balancing between neighbouring nodes, so it could
> involve moving more than one token just to redistribute a single overloaded
> node. Virtual nodes could allow load balancing on a much finer granularity,
> so heavily loaded portions of the key-space could be redistributed to
> lighter-loaded hosts by reassigning one or more virtual nodes.
>
>
> Implementing a virtual node scheme in Cassandra is not an insignificant
> amount of work, and it will touch a large amount of the codebase related to
> partitioning, placement, routing, gossip, and so on. We do believe that
> this is possible to do incrementally, and in such a way that there is an
> easy upgrade path for pre-virtual-node deployments.
>
> It would not however touch the storage layer. The virtual node concept is
> solely for partitioning and placement, not for segregating the data storage
> of the host, so all keys for all virtual nodes on a host would be stored in
> the same SSTables.
>
> We are not proposing the adoption of the same scheme used by Voldemort[2]
> and described in the Dynamo paper[3]. We feel this scheme is too different
> from Cassandra's current distribution model to be a viable target for
> incremental development. Their scheme also fixes the number of virtual
> nodes for the lifetime of the cluster, which can prove to be a ceiling to
> scaling the cluster if the virtual nodes grow too large.
>
> The proposed design is:
> * Assign each host T random tokens.
>

Will it work well for OrderedPartitioner?

For load balance purpose, is it possible to detect the access pattern of
range and move
the range dynamically instead of introducing virtual node?



> * A partition is assigned to a host for each of its tokens, where the
> partition is defined by the interval between a token and the previous token
> on the ring.
> * When a host joins the ring it is assigned T random tokens which will
> result in a portion of an existing partition being assigned to that host.
> * When a host leaves the ring it relinquishes its tokens which will result
> in its partitions becoming part of the neighbouring partitions.
>
> This is just a basic extension of Cassandra's existing distribution model,
> where instead of having 1 token per host, there are many tokens per host.
> It is the same scheme used by libketama[4] for consistent hashing among
> memcached instances, and is also the original scheme used by Dynamo as
> described in [3] before they migrated to their current scheme with fixed
> partitions.
>
> The random assignment of tokens may seem unintuitive given that currently
> in Cassandra a random token assigment leads to an unbalanced cluster. With
> many virtual nodes, a random token assignment leads to load being evenly
> balanced across the hosts in the cluster with high probability. As the
> number of virtual nodes is increased, the variance in load across hosts
> decreases, as demonstrated by simulation in [5].
>
> This scheme has the following properties - (where N is the number of hosts
> and B is the total data stored in the cluster):
> * placement metadata size is O(N) which is the same as in Cassandra
> currently
> * partition size is O(B/N) so as data is inserted, if individual partitions
> become too large then adding nodes to the cluster reduces this.
> * the strategy shares the following properties in common with Cassandra
> currently
> ** tokens are randomly assigned
> ** partitioning is determined by placement (and vice-versa)
> ** no two nodes may share the same token
> ** when a node leaves the ring, all of its tokens are removed - there is no
> exchanging of partitions between nodes
>
> One design concern is that replicas of a key range are not stored on the
> same physical host, as failure of that host could cause the loss of more
> than one replica of the data. This will be achieved by using a placement
> strategy very similar the the existing NetworkTopologyStrategy, which
> treats each individual host the same way as NTS treats a rack - that is
> replicas are not assigned to two hosts on the same rack.
>
> I will shortly create a ticket in JIRA to track discussion of this design.
> We have also done some simulation of this scheme to observe the load
> balancing properties, node size distribution, cluster resizing and so on. I
> will attach some results of this simulation to the JIRA ticket in due
> course.
>
> We are keen to get the ball rolling on this and we look forward to your
> input, ideas and recommendations.
>
> Best Regards,
>
> Sam Overton
>
> [1] Staggering repair:
> https://issues.apache.org/jira/browse/CASSANDRA-3721
> [2] Project Voldemort, Design: http://project-voldemort.com/design.php
> [3] Dynamo:
> http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
> [4] Ketama: Consistent Hashing:
> http://www.audioscrobbler.net/development/ketama/
> [5] Consistent Hashing:
> http://www.lexemetech.com/2007/11/consistent-hashing.html
>
> --
> Sam Overton
> Acunu | http://www.acunu.com | @acunu
>

Re: RFC: Cassandra Virtual Nodes

[Edward Capriolo <ed...@gmail.com>]

 I agree having smaller regions would help the rebalencing situation both
with rp and bop. However i an not sure if  dividing tables across disk s
will give any better performance. you will have more seeking spindles and
can possibly sub divide token ranges into separate files. But fs cache will
get shared across all disks so that is a wash.

On Saturday, March 17, 2012, Eric Evans <ee...@acunu.com> wrote:
> On Sat, Mar 17, 2012 at 11:15 AM, Radim Kolar <hs...@filez.com> wrote:
>> I don't like that every node will have same portion of data.
>>
>> 1. We are using nodes with different HW sizes (number of disks)
>> 2.  especially with ordered partitioner there tends to be hotspots and
you
>> must assign smaller portion of data to nodes holding hotspots
>
> Yes, these are exactly the sorts of problems that virtual nodes are
> meant to make easier.
>
> --
> Eric Evans
> Acunu | http://www.acunu.com | @acunu
>

Re: RFC: Cassandra Virtual Nodes

[Eric Evans <ee...@acunu.com>]

On Sat, Mar 17, 2012 at 11:15 AM, Radim Kolar <hs...@filez.com> wrote:
> I don't like that every node will have same portion of data.
>
> 1. We are using nodes with different HW sizes (number of disks)
> 2.  especially with ordered partitioner there tends to be hotspots and you
> must assign smaller portion of data to nodes holding hotspots

Yes, these are exactly the sorts of problems that virtual nodes are
meant to make easier.

-- 
Eric Evans
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Edward Capriolo <ed...@gmail.com>]

On Mon, Mar 19, 2012 at 4:24 PM, Sam Overton <sa...@acunu.com> wrote:
>> For OPP the problem of load balancing is more profound. Now you need
>> vnodes per keyspace because you can not expect each keyspace to have
>> the same distribution. With three keyspaces you are not unsure as to
>> which was is causing the hotness. I think OPP should just go away.
>
> That's a good point, but isn't that the same problem with trying to
> balance tokens with OPP currently?

Yes. I was bringing this up because the external management process
you suggested performing active load balancing will have to be smart
enough to understand this. Right now since this is done manually it is
the users problem.

Re: RFC: Cassandra Virtual Nodes

[Sam Overton <sa...@acunu.com>]

> For OPP the problem of load balancing is more profound. Now you need
> vnodes per keyspace because you can not expect each keyspace to have
> the same distribution. With three keyspaces you are not unsure as to
> which was is causing the hotness. I think OPP should just go away.

That's a good point, but isn't that the same problem with trying to
balance tokens with OPP currently?

Re: RFC: Cassandra Virtual Nodes

[Edward Capriolo <ed...@gmail.com>]

On Mon, Mar 19, 2012 at 4:15 PM, Sam Overton <sa...@acunu.com> wrote:
> On 19 March 2012 09:23, Radim Kolar <hs...@filez.com> wrote:
>>
>>>
>>> Hi Radim,
>>>
>>> The number of virtual nodes for each host would be configurable by the
>>> user, in much the same way that initial_token is configurable now. A host
>>> taking a larger number of virtual nodes (tokens) would have
>>> proportionately
>>> more of the data. This is how we anticipate support for heterogeneity in
>>> cluster hardware.
>>
>> Yes, but this is good only for random partitioner. For ordered you need to
>> be able split token space on highly loaded servers. With virtual tokens it
>> will move load to random node.
>> What if random node will be also hotspot node? Administration will be more
>> difficult because you don't know where workload lands after you reduce
>> number of tokens held by node.
>
> For OPP we envisage an external management process performing active
> load balancing. The initial token assignment would be random within
> some user-specified range corresponding to the range of their keys.
> The load would then be monitored and hot-spots would be moved by
> reassigning virtual nodes to lightly loaded machines, or introducing
> new tokens into hot ranges. It makes sense that this would not be a
> manual process, but there would certainly be more control than just
> increasing or decreasing the number of tokens assigned to a node.
>
> --
> Sam Overton
> Acunu | http://www.acunu.com | @acunu

For OPP the problem of load balancing is more profound. Now you need
vnodes per keyspace because you can not expect each keyspace to have
the same distribution. With three keyspaces you are not unsure as to
which was is causing the hotness. I think OPP should just go away.

Re: RFC: Cassandra Virtual Nodes

[Sam Overton <sa...@acunu.com>]

On 19 March 2012 09:23, Radim Kolar <hs...@filez.com> wrote:
>
>>
>> Hi Radim,
>>
>> The number of virtual nodes for each host would be configurable by the
>> user, in much the same way that initial_token is configurable now. A host
>> taking a larger number of virtual nodes (tokens) would have
>> proportionately
>> more of the data. This is how we anticipate support for heterogeneity in
>> cluster hardware.
>
> Yes, but this is good only for random partitioner. For ordered you need to
> be able split token space on highly loaded servers. With virtual tokens it
> will move load to random node.
> What if random node will be also hotspot node? Administration will be more
> difficult because you don't know where workload lands after you reduce
> number of tokens held by node.

For OPP we envisage an external management process performing active
load balancing. The initial token assignment would be random within
some user-specified range corresponding to the range of their keys.
The load would then be monitored and hot-spots would be moved by
reassigning virtual nodes to lightly loaded machines, or introducing
new tokens into hot ranges. It makes sense that this would not be a
manual process, but there would certainly be more control than just
increasing or decreasing the number of tokens assigned to a node.

-- 
Sam Overton
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Radim Kolar <hs...@filez.com>]

>
> Hi Radim,
>
> The number of virtual nodes for each host would be configurable by the
> user, in much the same way that initial_token is configurable now. A host
> taking a larger number of virtual nodes (tokens) would have proportionately
> more of the data. This is how we anticipate support for heterogeneity in
> cluster hardware.
Yes, but this is good only for random partitioner. For ordered you need 
to be able split token space on highly loaded servers. With virtual 
tokens it will move load to random node.
What if random node will be also hotspot node? Administration will be 
more difficult because you don't know where workload lands after you 
reduce number of tokens held by node.

Re: RFC: Cassandra Virtual Nodes

[Sam Overton <sa...@acunu.com>]

On 17 March 2012 11:15, Radim Kolar <hs...@filez.com> wrote:

> I don't like that every node will have same portion of data.
>
> 1. We are using nodes with different HW sizes (number of disks)
> 2.  especially with ordered partitioner there tends to be hotspots and you
> must assign smaller portion of data to nodes holding hotspots
>

Hi Radim,

The number of virtual nodes for each host would be configurable by the
user, in much the same way that initial_token is configurable now. A host
taking a larger number of virtual nodes (tokens) would have proportionately
more of the data. This is how we anticipate support for heterogeneity in
cluster hardware.

Sam

-- 
Sam Overton
Acunu | http://www.acunu.com | @acunu

Re: RFC: Cassandra Virtual Nodes

[Radim Kolar <hs...@filez.com>]

I don't like that every node will have same portion of data.

1. We are using nodes with different HW sizes (number of disks)
2.  especially with ordered partitioner there tends to be hotspots and 
you must assign smaller portion of data to nodes holding hotspots