DataStax Academy FAQ

DataStax Academy migrated to a new learning management system (LMS) in July 2020. We are also moving to a new Cassandra Certification process so there are changes to exam bookings, voucher system and issuing of certificates.

Check out the Academy FAQ pages for answers to your questions:


question

bhupalreddy1992_162660 avatar image
bhupalreddy1992_162660 asked ·

How do tokens get generated for virtual nodes?

In Cassandra Vnodes , if I give num_tokens 16 ,

Each node will generate 16 tokens.

My question is what is the algorithm used to generate 16 (num_token ) tokens?

Is there any probability different nodes generating same token?

Is there any possibility of skew in token ranges assigned to nodes?

virtual nodes
10 |1000 characters needed characters left characters exceeded

Up to 8 attachments (including images) can be used with a maximum of 1.0 MiB each and 10.0 MiB total.

1 Answer

Erick Ramirez avatar image
Erick Ramirez answered ·

In most cases, tokens are generated at random from the range of minimum and maximum token values which are valid for the configured partitioner. The default is the Murmur3Partitioner which has a range of possible token values from -263 to 263-1.

Being randomly generated, there is a possibility that a generated token value is already in use by another node but the algorithm is smart enough to detect this by comparing with the stored token metadata (gathered from gossiping with another nodes) and filtering out "duplicates".

There is a slight skew in the load (amount of data) between nodes as a result of the random token generation. The skew is more pronounced when the number of tokens (vnodes) is small like 8 or 16 compared to 256 vnodes. To deal with this skew, new token allocation algorithms have been introduced in more recent versions of Cassandra.

Cassandra 3.x

In Cassandra 3.0, a new allocation algorithm was introduced which tries to pick tokens which provides an even distribution of ownership (data load) across the cluster based on the replication strategy of a keyspace (CASSANDRA-7032).

To trigger this algorithm, specify a keyspace in cassandra.yaml with:

allocate_tokens_for_keyspace: keyspace_name

If not set, tokens will be picked at random as normal.

If you are interested in the details, see the ReplicationAwareTokenAllocator.java class. Note that this algorithm is only supported with the Murmur3Partitioner.

Cassandra 4.0

Another new allocation algorithm in 4.0 built on top of the above algorithm to achieve the same even distribution of data load but based on the chosen replication factor of the most used keyspace (CASSANDRA-15260).

To trigger this algorithm, specify a replication factor in cassandra.yaml with:

allocate_tokens_for_local_replication_factor: 3

If not set, tokens will be picked at random as normal.

If you are interested in the details, see the TokenAllocation.java class. Note that this algorithm is only supported with the Murmur3Partitioner. Cheers!

Share
10 |1000 characters needed characters left characters exceeded

Up to 8 attachments (including images) can be used with a maximum of 1.0 MiB each and 10.0 MiB total.