New token allocation algorithm in Cassandra 3.0
The central idea of the algorithm is to generate candidate tokens, and figure out what would be the effect of adding each of them to the ring as part of the new node. The new token will become primary for part of the range of the next one in the ring, but it will also affect the replication of preceding ones. The algorithm is able to quickly assess the effects thanks to some observations which lead to a simplified but equivalent version of the replication topology2: Replication is defined per datacentre and replicas for data for this datacentre are only picked from local nodes. That is, no matter how we change nodes in other datacentres, this cannot affect what replicates where in the local one. Therefore in analysing the effects of adding a new token to the ring, we can work with a local version of the ring that only contains the tokens belonging to local nodes. If there are no defined racks (or the datacentre is a single rack), data must be replicated in distinct nodes. If racks