How Data is Distributed: Hashing and Tokens
In your very first query, the employees came back in a strange order: 5, 10, 11, 1 and so on. This lesson explains that order.
From partition key to token
When you write a row, Cassandra puts its partition key through a hash function. This function is called the partitioner, and by default it is Murmur3. The result is a big number called the token. For Murmur3, a token is always between -9223372036854775808 and 9223372036854775807.
You can see the tokens yourself with the token() function:
SELECT id, name, token(id) FROM employees;
Output:
id | name | system.token(id)
----+-------+----------------------
5 | Emma | -7509452495886106294
10 | Jack | -6715243485458697746
11 | Sarah | -4156302194539278891
1 | Alice | -4069959284402364209
8 | Henry | -3799847372828181882
2 | Bob | -3248873570005575792
4 | David | -2729420104000364805
7 | Grace | 1634052884888577606
6 | Frank | 2705480034054113608
9 | Mike | 3728482343045213994
12 | Lucy | 8582886034424406875
3 | John | 9010454139840013625
(12 rows)
The rows are sorted by the token, from the smallest to the largest. Emma (id 5) has the smallest token, so she comes first. This is the same order as in your first query.
From token to node
The nodes of the ring share the full range of tokens. Each node owns a part of it. A row is stored on the node that owns its token, and its copies go to other nodes in the ring:
all tokens, smallest to largest
-9223372036854775808 ......... 9223372036854775807
+-----------+-----------+-----------+-----------+
| Node A | Node B | Node C | Node D |
+-----------+-----------+-----------+-----------+
^ ^
id 5 (Emma) id 3 (John)
A SELECT with no WHERE walks through the ring in token order. That is why the rows come back in token order. It looks random, but it is not. The same key always gets the same token, so you get the same order every time.
Why use a hash at all?
A hash spreads the data evenly over the nodes. Real values are often uneven. Imagine putting all names that start with "A" on one node and all names that start with "Z" on another: the "A" node would get far more rows. Hashes don't have this problem, so every node gets about the same amount of data.
There is a cost. Values that are close together, like ids 3 and 4, get tokens that are far apart: John (id 3) has the largest token, and David (id 4) is in the middle of the list. So a range on the partition key would have to visit every node, and Cassandra refuses it:
SELECT * FROM employees WHERE id > 10;
Output:
InvalidRequest: Error from server: code=2200 [Invalid query] message="Cannot execute this query as it might involve data filtering and thus may have unpredictable performance. If you want to execute this query despite the performance unpredictability, use ALLOW FILTERING"
Cassandra chose an even spread of data over range queries across partitions. Inside one partition, ranges on clustering columns still work, as you saw earlier in this section.
Answer a short question about row order below.