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?
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.
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.
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!
5 People are following this question.
