[CASSANDRA-16368] Lightweight transaction linearizability violations when using list append and prepend operations

• Type: Bug
• Status: Triage Needed
• Priority: Normal
• Resolution: Unresolved
• Component/s: Consistency/Coordination, Feature/Lightweight Transactions
• Platform: All
• Assignee: Unassigned
• Reporter: Konstantin
• Created: 23/Dec/20 12:01
• Updated: 23/Dec/20 12:16

Description

This is an equivalent of https://github.com/scylladb/scylla/issues/7611

Cassandra's "list" type is a CRDT which allows a write-only "append" operation, not requiring a read. This is implemented by using the current time on the coordinator node as the key of the new item, so that a second append operation will put the new item after the item from the first append operation.

However, in case of lightweight transactions, uncoordinated use of node-local timestamp may lead to duplicate and non-monotonic timestamp values.
This leads to loss of LWT linearizability.
The issue is reproducible with a Jepsen test for list append, prepend in presence of time and topology nemeses.

Relevant links: https://github.com/scylladb/scylla/issues/7116

Code generating an independent timestamp is in https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/cql3/Lists.java#L499

{{ ByteBuffer uuid = ByteBuffer.wrap(UUIDGen.getTimeUUIDBytes());}}
{{ params.addCell(column, CellPath.create(uuid), buffer);}}

 
A related problem is that this approach ignores user-supplied statement timestamps.