Handle i64::MIN token when hashing.
Lorak-mmk opened this issue · 4 comments
I recently learned that i64::MIN is not a legal token in Scylla: https://github.com/scylladb/scylladb/blob/4be70bfc2bc7f133cab492b4aac7bab9c790a48c/dht/token.hh#L32
That's why Scylla is able to return left-open ranges when sending tablet info.
From what I see in our partitioner code, we don't handle this case.
This is a very minor issue, but an issue anyway, so we should fix it at some point.
I don't fully understand the motivation:
That's why Scylla is able to return left-open ranges when sending tablet info.
Could you explain in more detail to a person which is not up to speed with tablets? What are we fixing with this change?
The fix itself is not related to tablets, it's just an extremely rare edge case - I just happened to learn about it when implementing tablet support.
When you send a query to a wrong replica, and you use tablets, you get a response with custom payload.
This custom payloads contains information about a correct tablet for this query.
One part of this information is token pair for this tablet. If the payload contains tokens X and Y, then the tablet owns token range (X, Y] - notice than left end is exclusive.
So my immediate question was - what if the tablet owns i64::MIN token? That would require Scylla to send i64::MIN - 1 as left end of range.
Turns out a tablet can't own this token because it is not a correct token - see the link in the issue.
According to Scylla, if hashing algorithm outputs i64::MIN, it will be changed to i64::MAX.
Before the PR that fixes this issue we don't do that - so if we encounter a key that hashes to i64::MIN, we will send it to incorrect replica, both for Tablet and Token Ring tables.
I also like the PR because it introduces constructor for Token - I never liked that it is constructed the way it is now.
Ok, that's more clear now, thanks.
it's just an extremely rare edge case
Yeah... we'll be lucky if anybody ever triggers it. I don't think we assume anywhere that a token can't actually be i64::MIN (does the tablet code do that?). I can understand why Scylla/Cassandra normalize tokens, but in case of drivers it's always fine to send the request to a random node as a fallback.
However, if ensuring that token != i64::MIN simplifies reasoning about the whole code (not 100% sure it does or doesn't, can't tell) then I'm fine with it.
That would require Scylla to send i64::MIN - 1 as left end of range.
Theoretically, if we interpreted token ranges as wrapping ranges then sending i64::MAX as the left end of range would work, but that's not how token ranges work in Scylla/Cassandra, apparently.
Ok, that's more clear now, thanks.
it's just an extremely rare edge case
Yeah... we'll be lucky if anybody ever triggers it. I don't think we assume anywhere that a token can't actually be i64::MIN (does the tablet code do that?). I can understand why Scylla/Cassandra normalize tokens, but in case of drivers it's always fine to send the request to a random node as a fallback.
To add another complication, as I tried to explain in bc4d0fd5ad947eda1faa39345c029e10c309a5e6, Cassandra actually uses min_token for an empty partition key (by "empty" I mean an empty string, "" - not a null). Empty partition keys are not allowed in base tables, but they do appear in materialized views and secondary indexes. Because Scylla does consider the minimum token an "invalid token" (I can't find an example, but remember there is), in Scylla we deviated from Cassandra in this case - and we never use the minimum token - not even for empty partition keys.
I do agree that for a driver, sending a request to the wrong node in a one-in-a-billion case is fine.