Understanding the Token Function in Cassandra

Question

Hello I was reading the Cassandra documentation on Token Function,

I am trying to achieve pagination for a Cassandra table, I am unable to understand the lines highlighted. The document speaks about the difference between k > 42 and TOKEN(k) > TOKEN(42), but I am not able to understand the "token based comparison"

Looking forward for a detailed explanation of what token function does when part of a WHERE clause.

Solution 1

In order to understand in which partition it should put your data, C* makes some calculations on the PARTITION KEYs of every row. Specifically, on each node, rows are sorted by the token generated by the partitioner, (and each partition have data sorted by the cluster key). Different partitioners perform different types of calculations.

While the Murmur3Partitioner calculates the MurmurHash of the partion key, the ByteOrderedPartitioner uses the raw data bytes of the partition key itself: when you use the Murmur3Partitioner, your rows are sorted by their hashes, while when you use the ByteOrderedPartitioner, your rows are sorted directly by their raw values.

As an example, assume you have a table like this:

CREATE TABLE test (
    username text,
    ...
    PRIMARY KEY (username)
);

And assume you're trying to locate where the rows corresponding to the usernames abcd and abce and abcf are stored. The hex representation of these strings are 0x61626364 and 0x61626365 and 0x61626366 respectively. Assuming we apply this MH3 implementation (x86, 32-bit for simplicity, no optional seed) on both strings we get ‭0x‭43ED676A‬‬ and 0x‭‭E297E8AA‬‬ and 0x‭‭87E62668‬‬ respectively. So, in the case of MH3, the tokens of the strings will be these 3 values, while in the case of the BOP the tokens will be the raw data values themselves: 0x61626364, 0x61626365 and 0x61626366.

Now you can see that storing data sorted by token produces different results when different partitioners are used. A SELECT * FROM test; query would return rows in different order. This can (but should not) be a problem if you have data already sorted by their raw values and you need to retrieve that in the same order because when you use MH3 the order is complelety unrelated to your data.

Back to the question, the TOKEN function allows you to filter directly by the tokens of your data instead of your data. The documentation says:

ordering with the TOKEN function does not always provide the expected results. Use the TOKEN function to express a conditional relation on a partition key column. In this case, the query returns rows based on the token of the partition key rather than on the value.

As an example, you could issue:

SELECT * FROM test WHERE TOKEN(username) <= TOKEN('abcf');

and you'd get figure what? abcd and acbf rows!!! This is because order sometimes matters... Like in the case of the pagination you're trying to do, which will be handled flawlessy for you by any available C* driver (eg the Java driver).

That said, the recommended partitioner for new clusters is Murmur3Partitioner, you can check the documentation for both pros and cons of each partitioner. Please note that the partitioner is a cluster-wide settings, and once set you cannot change it without pushing all of your data into another cluster.

Make your choice carefully.

Solution 2

Cassandra data is partitioned based on the Token of row's PartitionKey. The token is gerenated using a Hash Function. The function Token generates the value which would have been created by applying the hash function to it's arguments.

That said, almost all drivers now page automatically by default.

Comments

[Sohail Khan]

Definitely the answer I am looking for

[Sohail Khan]

what is the difference in sort order of a node and partition. I believe each partition of a table has a dedicated node

[Ihor M.]

How does token function work for a composite key if it only takes one argument?

[RussS]

It takes more than one argument cqlsh> SELECT TOKEN(k1,k2) FROM test.test2; system.token(k1, k2) ---------------------- 4881097376275569167

[Ihor M.]

[cqlsh 5.0.1 | Cassandra 2.1.20 | CQL spec 3.2.1 | Native protocol v3] CREATE TABLE test ( a bigint, b bigint, c text, PRIMARY KEY (a, b) ) WITH CLUSTERING ORDER BY (b ASC) When I place a query select token(a,b), a, b, c from test where token(a,b)>=-9223372036854775808 limit 50; I get: InvalidRequest: code=2200 [Invalid query] message="Invalid number of arguments in call to function token: 1 required but 2 provided" Any idea what's causing this error? I am pulling my hair here.

[RussS]

Your partition key has only 1 part "A". "B" is a clustering key If you wanted B to be part of the partition key it would look like PRIMARY KEY ((a, b)) The general format is PRIMARY KEY((Partition Key), Clustering Keys) Where when there are no parenthesis, the first column is assumed to be the partition key.

[Ihor M.]

Okay, thanks for the explanation, it makes sense now. I thought that token function takes all primary key columns into account in order to uniquely generate a token for a given row. I thought that token serves in a way as a substitute of a primary key and can be used to quickly paginate data as explained here: myhowto.org/bigdata/2013/11/04/… If only partition key columns are used in the token generation, it means that for the same token can have multiple rows associated. Is it not?

[RussS]

Yes, you are going to want a more recent manual for Cassandra. I suggest dsacademy. Tokens/partition key choose the node, the other primary key parts are called clustering keys because they define the order of rows following a token.

[Ihor M.]

I just have this legacy table that I have to migrate and it has the structure similar to what I have posted. It has billions of records in it and I wanted to use multiple workers reading from it and recording token offset after batch of records have been consumed. Now it turns into a nightmare b/c behind one token I can have multiple rows stashed.

[Ihor M.]

I worked in Cassandra in the past, I do know the basics, it's just that I haven't worked with it for 2 years and it is slowly coming back to me.

[Ihor M.]

It seems that the legacy table was not properly designed and therefore I'm having a trouble figuring out how to work with tokens properly.