Cassandra: a stream reader can skip a record that is stored after a higher sequence number #660

What happens

On Cassandra, a write takes its stream sequence number before its stream
record is stored. Another write on the same shard can take a higher number
and store its record first. A GetRecords call that returns the higher record
moves the reader's position past the lower number. When the lower record is
stored later, no later GetRecords call returns it.

The record is not lost. It is in stream_records. But a reader that follows
the normal iterator never sees it. So a consumer misses a change to the table.

Where

All line numbers are at origin/main 877ef39.

• The sequence number comes from the server process's HLC (hybrid logical
  clock) when the write builds its record:
  crates/storage-cassandra/src/stream_util.rs:151-166. Callers include
  data/put_get_item.rs:550, data/update_item.rs:331 and
  data/delete_item.rs:353.
• The record is stored in a later batch round trip.
• The shard is crc32(partition key) % SHARDS_PER_STREAM:
  crates/storage-cassandra/src/stream_util.rs:117-122. So many items share
  one shard. The two writes do not need to touch the same item.
• GetRecords reads WHERE shard_id = ? AND sequence_number > ?:
  crates/storage-cassandra/src/stream_engine.rs:175-179. It returns every
  stored record above the reader's last position.

Steps

What makes the gap wider

1. The time between taking the number and storing the record. For a
   single-item write this is one batch round trip.
2. PR fix(cassandra): record stream records for transacted writes #576, as written, adds a second round trip for a transacted write
   whose stream record goes in its own batch (over 24,000 counted bytes).
3. Two server processes each have their own HLC. So their numbers can be out
   of order with respect to when each record is stored.

Scope

• This issue was found on the Cassandra backend.
• SQLite, PostgreSQL and MongoDB also page by sequence_number > cursor
  (storage-sqlite/src/stream.rs:143,
  storage-postgres/src/stream_records_sql.rs:45,
  storage-mongodb/src/bootstrapper.rs:172).
• Initial investigation, from reading the code only, indicates:
  • SQLite and MongoDB are not subject to this condition. On both, the
    write takes its number inside its own transaction, by updating a
    counter row or document. A second writer that wants the next number is
    blocked (SQLite) or gets a write conflict and retries (MongoDB) until
    the first writer commits. So records commit in number order. The
    MongoDB code says this on purpose, in next_sequence_number_in_session
    (crates/storage-mongodb/src/stream_engine.rs).
  • PostgreSQL may be subject to it. The write takes its number with
    SELECT nextval('stream_seq')
    (crates/storage-postgres/src/data/tx_helpers.rs, near line 341).
    nextval hands out numbers outside the transaction. It is never rolled
    back and holds no lock until commit. PostgreSQL does this by design.
    So write A can take 5, write B can take 6, and B can commit first. At
    READ COMMITTED, a reader can then see 6 and move past 5. Nothing found
    so far stops this. This has not been tested.

Expected

A consumer that reads a shard with GetRecords, from TRIM_HORIZON onward,
sees every record stored in that shard.

Found by

Review of PR #576. That PR widens the gap in one case but does not create it.