Syncing State with an Immutable Trie

In August 2019 I wanted a goal tracker I’d actually open, on whichever device was nearest, without watching it disagree with itself. Nothing off the shelf fit, so I built one over a couple of weekends. The tower metaphor was the part friends saw; the part that aged well was the sync model that fell out of needing the same state in three places at once.

The problem in one paragraph

Pick any non-trivial mutable object graph, sync it across devices, and you end up either sending the whole thing on every change (wasteful) or writing ad-hoc diff logic per shape (brittle). I wanted a representation where the shape of the data made the diff fall out for free.

The trie, concretely

A goal in Life Towers is a path of strings. Health / Running / 5k. Tasks under a goal hang off the leaf. A user’s whole state is a tree, and a trie is exactly the data structure that makes that tree’s identity manipulable.

Two properties did the heavy lifting:

• Structural sharing. When you tick off a task under Health / Running / 5k, the new root reuses every untouched subtree by reference. The Career branch and the Reading branch are the same objects they were before. Comparing the old and new roots is mostly pointer equality; only the path that actually changed gets walked.
• Immutability. Updates produce new structure instead of mutating. “Where I was” and “where I am” become two pointers, not two snapshots. The diff between them is whatever’s not shared, and that walk is O(changes), not O(state).

The sync loop falls out:

1. Client holds the last root the server acknowledged plus its own current root.
2. To send: walk only the unshared paths, emit one op per changed leaf. In practice that’s a handful of bytes for a typical edit, no matter how large the rest of the tree is.
3. Server applies, returns its new root.
4. Client rebases any in-flight edits by replaying them on top.

There’s no conflict resolution layer because the operations commute on the structure. Two clients adding tasks under different branches produce non-overlapping deltas that compose trivially. The hard cases (two clients editing the same leaf) are tiny and obvious, because they’re the only place the deltas touch the same path.

What I’d change

• Property tests around the rebase. The reconcile path is exactly where a generator finds bugs that hand-written tests never think to write. I had hand-written cases; I’d start with proptest now.
• A standalone spec for the wire format. The part worth lifting out was the protocol, not the goal tracker. A short spec would let me (or anyone) reimplement it in a different stack without re-deriving everything from the Python source.
• Strip the visual experiment. The tower visualisation was fun but it bound the storage to a UI metaphor. The sync model should be a library; the towers should be a separate toy.

If you take one idea from this

Most sync problems are diff problems pretending to be transport problems. Pick the data structure that makes the diff free, and the protocol almost writes itself. The corollary: if you’re writing a lot of “if this changed, send that” code, you’re using the wrong structure.