Two devices, one todo list, and a tiebreak that wasn't

The setup

I built a personal tool that runs on two devices, a desktop app and a phone. It holds real financial records of mine, so I won't describe what it tracks, only how it's built. The interesting part is generic enough to be worth writing down on its own.

State isn't stored directly. Every change is appended to an event log, and the current state is derived by replaying that log from the start. That's useful, because two devices appending to the same log can't conflict with each other. Appending is the one operation that never needs to know what else is happening. So sync becomes "make sure both devices have the same list of events," which is a much smaller problem than "make sure both devices agree on the current state."

The phone app was written in a different language from the desktop app, for reasons that had nothing to do with the architecture. That meant the replay logic (the function that takes an event log and produces the current state) existed twice, once per platform. At the time I treated that as a nuisance, and it turned out to be what saved me.

The bug

Replaying an event log needs a total order. Events are timestamped, but timestamps aren't unique, and two events can land in the same millisecond, especially when a batch of changes is created programmatically. When two events tie on timestamp you need a deterministic tiebreak, or the two implementations can order them differently and derive different state from an identical log.

The tiebreak I used was the row id the local database assigned when the event was inserted.

That id is local. It's an auto-incrementing integer scoped to whichever device created the row. It isn't part of the event's identity, it doesn't travel with the event, and it means nothing on a second device. I'd used it because it was convenient and always distinct, and I hadn't asked myself whether "always distinct on this device" was the same guarantee as "always distinct and consistent across devices." It isn't.

So two devices holding a byte-identical event log (same events, same order, nothing dropped, nothing duplicated) could derive different final state. One showed a task as open, and the other showed the same task as done. Nothing was corrupted. Both devices were faithfully replaying exactly the same input and getting different answers, because the value they used to break a tie wasn't the same on both sides.

I think that's worse than a crash. A crash at least tells you something's wrong, whereas here both devices thought they were right.

Why I didn't just fix the tiebreak

The obvious fix is to switch the tiebreak to something that travels with the event, like a UUID assigned at creation time. I did that. But a better tiebreak doesn't answer the question the bug actually raised, which is how I know the replay logic in two different languages agrees on every case that matters.

Fixing the bug I'd found tells me nothing about the ones I hadn't found yet. And with two independent implementations of the same logic, there was no reason to assume the desktop version was the reference and the phone version had the bug. They could each be wrong in different, unrelated ways, and comparing them to each other would only catch where they disagree. It would miss any mistake they share.

Writing the behaviour down as data

What I built instead is a corpus, a committed set of event logs, each paired with the hash of the projection it has to produce. It looks something like this.

fixtures/
  concurrent-completion.json      # the input event log
  concurrent-completion.hash      # the expected projection hash
  same-millisecond-tiebreak.json
  same-millisecond-tiebreak.hash
  out-of-order-delivery.json
  out-of-order-delivery.hash

Both implementations read the same fixture files, replay them, hash the resulting state and compare that hash to the committed one. Neither is allowed to regenerate the expected hash at test time. The hash is fixed, checked-in data, the same as the input.

I wrote the corpus for the tiebreak scenario before I'd written the second implementation, and that order matters more than it looks. If you write the fixture after both implementations exist, there's a real risk you just encode whatever the two of them already happen to agree on, bugs and all. Writing it first gives the second implementation something external to satisfy, so it isn't just copying another program.

If the "expected" value is computed by calling the same function you're testing, every run passes by construction. The fixtures have to be independent of the code that reads them, which in practice means committing the expected output as data and never regenerating it from a passing run.

I also added tests that are meant to fail. These are fixtures that introduce a divergent tiebreak or a truly ambiguous ordering on purpose, where the two implementations are expected to disagree, and the test asserts that the hashes differ.

What this means for sync

This got me thinking about the different kinds of data any sync system has to move, because they don't all need the same treatment.

Append-only events are safe to sync directly, because two devices appending can't conflict.

Derived projections (the current state computed from the log) don't need to sync at all. Each device rebuilds its own copy from the log it already has, and the only thing to check is that the rebuild is identical everywhere, which the hash comparison already proves. Derived state never goes over the wire, so there's no wire format for it to be inconsistent across, and the whole kind of bug I hit can't happen.

Mutable rows (things edited in place instead of appended to) are the one category that still needs real conflict detection, because two devices can legitimately make different changes to the same row before either has seen the other's write. That's a harder problem and a different note, but it's a much smaller surface once the append-only data and the derived data are off the table.