Reconsider how seq works for sync under V2 packed changes #584

Problem

Each DB transaction is assigned a monotonically increasing version number (db_version). Each change made within a transaction is assigned a monotonically increasing seq number.

Nodes in a cluster determine whether they have received all changes for a given transaction by comparing the seqs they have locally with the seqs they still require. A node keeps track of the maximum seq for a transaction and considers the db_version complete once it has all seqs in the range 0..max_seq.

When a node discovers that it is missing seqs a..b, it requests those changes from other nodes (or waits for them to be broadcast).

This worked in cr-sqlite 0.17. In 0.18, we can send full rows worth of data in a single change, which significantly improves IO efficiency. However, this introduces a problem with the way chunks are currently represented.

Example

Consider this transaction:

BEGIN;

INSERT INTO foo(key, value, meta) VALUES('foo1', 'value1', 'meta1');
INSERT INTO foo(key, value, meta) VALUES('foo2', 'value2', 'meta2');
...
INSERT INTO foo(key, value, meta) VALUES('foo99', 'value99', 'meta99');

UPDATE foo SET meta='hello' WHERE key='foo1'; -- seq = 100

COMMIT;

When querying the changes, we can get a single packed change containing both seq = 0 and seq = 100, followed by 99 changes containing seq = 1, 2, ..., 99.

Currently, when changes within a single db_version are too large, we split them into chunks. Each chunk is labelled with:

• min_seq
• max_seq
• last_seq

This assumes that the seqs represented by a chunk are effectively contiguous.

With packed changes, that assumption is no longer true.

For example, a chunk containing only seqs {0, 100} has:

min_seq = 0
max_seq = 100

A peer could therefore incorrectly conclude that it has received seqs 0..100, even though seqs 1..99 are still missing.

Possible approaches

1. Only split chunks at safe boundaries

   This is what I will do temporarily for Replication metadata rework. Migrate from crsqlite 0.17 to 0.18 #572. It avoids the correctness issue, but doesn't solve the underlying representation problem.

2. Don't pack changes for a row when the seqs are non-consecutive

   This is probably the safest/simple solution, but it gives up a significant portion of the IO benefits of packed changes.

3. Represent seqs in a chunk as a list of ranges

   For example, a chunk could explicitly say that it contains:

   [0..0], [100..100]
   

   This is the most flexible solution and correctly represents arbitrary packed changes. This is the approach I think we should take.

4. Assign the same seq to all operations on the same row within a transaction

   This would likely give us the best bandwidth/performance characteristics, because multiple operations affecting the same row could be packed without introducing non-contiguous seqs.

   However, this would break unpacked/V1-style sync, so it would need to be opt-in initially and potentially become the default in 0.19. It may also require a cache in cr-sqlite to track whether a row has already been touched within the transaction.

Recommendation

I think we should implement (3) first, and then introduce (4) on top of it.

The reason for doing (3) first is that it also solves another problem we'll otherwise run into with (4).

Consider peer A having a version X with three packed changes:

{10, 13}
{11}
{12}

If peer B requests seq range [10, 11], peer A can satisfy the request with:

{10, 13}
{11}

However, if the protocol only represents contiguous ranges, peer A has no easy way to communicate that the first packed change contains seq = 10 but also seq = 13, nor is there an easy way to split an already-packed change without introducing fairly complicated/fragile unpacking logic.

Representing the seqs in a chunk as ranges would solve this cleanly and would make the protocol robust to arbitrary packed changes.