A side project of mine tracks Magic: The Gathering matches. It is offline first, so the database lives on the phone and a small server exists for exactly one reason: the history should survive a lost phone and show up on the second one.
The bug report came from the only user in the system, which is me. Two phones, one account, and each had matches the other did not. No error anywhere. Both outboxes empty. Both screens saying everything was synced, both of them honestly believing it.
That combination is the interesting part. A sync bug that shows up as an error is a Tuesday. A sync bug where every component reports success is a design problem, and it took me a reproduction script to find out which one.
The protocol, in four moving parts
Nothing here is novel, and that is on purpose. Incremental sync converges on the same shape everywhere.
Every local write goes into an outbox: a row saying "this entity changed, it has not been uploaded yet", written in the same transaction as the change itself. That last part is the whole pattern. If the match is saved and the outbox row is not, the change exists and nobody will ever ship it; if they are written together, the queue cannot disagree with the data.
Each pending change carries an operation id, generated once and kept across retries, because on mobile networks the client never knows whether a request arrived before the timeout. It retries, and the server has to recognise what it has already seen.
The server assigns each accepted operation a sequence number, monotonic per user. The client stores the highest one it has processed as its cursor, and every sync says "give me what happened after this". That is the same since parameter CouchDB has used for years, and the same idea behind every change feed you have consumed.
One decision worth stating out loud: the sequence number is the server's clock, not the device's. Device clocks go backwards. They drift, they get corrected by NTP mid-session, and users set them by hand. A device timestamp is fine as a tiebreaker for content: when two phones edit the same match, last write wins, and ties break on device id so that every device reaches the same answer without racing. It is not fine as an ordering for delivery. Those are different jobs, and conflating them is how you get a feed that silently skips.
The cursor is a promise
Here is the sentence I wish I had written on a wall before starting.
When a client accepts a cursor, it is promising to never ask for anything before it again.
Not "probably won't". Cannot. The cursor only moves forward, so anything the server failed to deliver below that line is not late. It is gone, as far as that device is concerned. The row stays on the server forever, perfectly intact, and no device will ever request it.
This makes the cursor the single most dangerous value in the protocol. It is the one number where being off by one is unrecoverable.
The number that existed before the row
My server allocated sequence numbers like this:
UPDATE user_seq SET seq = seq + ? WHERE user_id = ? RETURNING seq;Then, in a second call, it wrote the documents with the numbers it had just reserved.
Two calls. Two round trips. And between them, a window where the counter has already moved and the rows do not exist yet.
Now put the second device in that window. It syncs, asks for everything after its cursor, and the server looks for rows, finds none because they are still in flight, and hands back a cursor taken from the counter. The device accepts it. Milliseconds later the rows land, carrying numbers that are now below a cursor that has already been promised away.
Both devices are consistent with themselves. Both outboxes are empty. Every request returned 200. And one match is never delivered to one phone, for as long as that account exists.
If you have written change-data-capture, you have met this animal before. It is the reason PostgreSQL's own documentation warns that sequences are not transactional and leave gaps: nextval does not roll back, and two transactions can commit in the opposite order from the numbers they took. Polling WHERE id > last_seen_id against a sequence is a well known way to lose rows, and Netflix's DBLog paper is essentially a long answer to the same question: how do you advance a watermark without stepping over something that has not become visible yet.
I did not think I was building CDC. I was building "sync". It turns out those are the same problem wearing different words.
Reproducing it on purpose
The bug needs two clients overlapping inside a window of a few hundred milliseconds. That happens all the time in real life: both phones on the table, both waking up when the app comes to the foreground. It is also impossible to hit by hand in a test.
So I stopped trying to hit it and built it instead. The database interface in the server is two methods, query and batch, which meant a test could wrap it and hold one call open:
batch: async (statements) => {
if (statements.some((s) => s.sql.includes('INTO documents'))) {
await blocked // device B is now frozen mid-write
}
return realBatch(statements)
}Device B starts uploading and freezes with its sequence number already reserved. Device A syncs into the hole. Device B unblocks. Device A syncs again, forever, and never sees the row.
Four assertions, a real SQLite file, no network and no mocking of the thing under test. Running it against the old code fails on exactly the line that describes the damage; against the fixed code it passes. That test is worth more than the fix, because the fix is obvious once you can see the failure, and the failure was invisible for months.
The fix is to stop having a window
The correction is not a smarter cursor. It is removing the gap the cursor was falling into.
The counter increment moved into the same batch as the document writes, and each insert computes its own number from the counter inside that transaction:
UPDATE user_seq SET seq = seq + ? WHERE user_id = ?;
INSERT INTO documents (user_id, entity, id, seq, ...)
VALUES (?, ?, ?, (SELECT seq FROM user_seq WHERE user_id = ?) - ?, ...);One transaction. The number and the row become visible together, or neither does. Since SQLite allows one writer at a time, commit order now matches allocation order, and there is no interleaving left to lose.
Which is the outbox pattern again, pointed at the server this time. On the device it says the change and the note that it must be uploaded are one write. On the server it says the row and the number that labels it are one write. I had applied the rule on the side where it is famous and broken it on the side where it is not, and the two halves of the system failed in the same way for the same reason.
I also changed the read side, because defence in depth is cheap here. The pull used to filter out the requesting device's own writes in SQL:
WHERE user_id = ? AND seq > ? AND device_id <> ?That filter is why the page could come back empty while the query had walked past rows, and why the cursor needed to be invented from somewhere else. Now the query selects the range and the filtering happens in code, after the rows are in hand. The cursor becomes the sequence number of the last row the query actually looked at, which cannot be ahead of anything, whatever the write side does.
Repairing what was already lost
Fixing the server fixes the future. The rows that fell behind a cursor stay behind it, because that is what a cursor means.
The only honest repair is to make the client forget. I already had the machinery for it: a stored marker of "which repairs this install has applied", and when it does not match the current one, the cursor is deleted and the whole archive is re-read once. Re-reading is cheap and safe, because every document the device already has is discarded on arrival by the same comparison that handles duplicate responses.
It is a blunt tool and I like that it is blunt. The subtle version of this, trying to work out exactly which rows a device missed, is more code running on less information, to solve a problem that a full re-read solves by definition.
What I would check in any sync protocol
Four questions, none of which I would have thought to ask before this:
Can your cursor ever point at something that is not visible yet? Anywhere a number is issued before the data it labels, that is the bug. Sequences, counters, timestamps taken at the start of a transaction.
Does delivery order depend on a clock you do not control? If a device timestamp decides what a client gets next, a phone with a wrong clock is a phone with a broken feed.
When a client's write loses a conflict, does the winner come back in the same response? If not, the loser keeps the losing content on screen until a later pull happens to cover a sequence number that may already be below its cursor. Which is to say: never.
Can you reproduce a two-client race deterministically? If the answer is "we would have to get lucky", you cannot fix these bugs, you can only wait for them.
Closing thoughts
What still bothers me is how well the system performed while being wrong. Queues drained. Requests returned 200. The UI said "synced" with complete sincerity. The only evidence was a human noticing that a match he remembered playing was not on the other phone.
That is the failure mode worth designing against in anything that syncs. Not the crash, not the conflict, not the merge. Those announce themselves. The one that matters is the write that was accepted, stored, and then quietly addressed to a place nobody will ever look again. Every safeguard I added here is really the same safeguard: never hand out a promise about data that has not landed yet.