HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

GroupThink

Staying in Sync

21 min read

Two devices on the same account have to agree on what that account contains, and the server carrying their traffic is not allowed to know the answer. So they exchange a few hundred bytes of hashes — enough to prove they match, or to name exactly where they do not — and then each one independently pulls the difference from the other. No leader, no coordinator, and nobody who decides.

Prerequisites: GroupThink for the sealed same-account channel this rides on, and The Relay for what the transport does and does not guarantee.

1. What a sync server normally does for you

Start with the system you would build if you were allowed to.

You would put the authoritative copy on a server. Each device sends its writes up; the server orders them, resolves conflicts by whatever rule you picked, and hands every device the same answer. When a device reconnects it asks "what changed since sequence 4,812?" and the server, which knows, tells it. Every hard question — who is ahead, what changed, is this delete real — has one place to be answered, because one machine can read everything.

We do not have that machine. Everything a Pixie device sends to its own other devices — its siblings — goes as a sealed sync_delta frame: encrypted end-to-end to a specific sibling, and gated on arrival so a device applies a delta only when the envelope's verified sender carries its own account's userIDHash. The relay routes ciphertext it cannot attribute. It cannot order the writes because it cannot read them, and it cannot answer "what changed since 4,812" because it never saw 4,812.

So the devices answer for themselves. The loop they run has five steps — advertise a digest, detect divergence, pull the differing rows, merge them, re-advertise — and the interesting part is not any single step. It is that both devices run all five at once, at each other, and this does not cause a fight.

2. The obvious approach, and why it is not enough

The first thing you would try is broadcasting. Every time this device writes a row, seal that row to each sibling and ship it. Siblings apply what arrives. Done.

Pixie does exactly this for one namespace, and refusing to do it for the others is where the design starts. The one that works is agent memory: an append-only event log. A new event is fanned to the siblings as a live sync_delta of kind memory, and the receiver applies it insert-if-absent. That is safe because the only operation the log supports is insert, and inserting a row you already have changes nothing.

Now try the same trick on the Notebook, which is mutable and deletable. A single-row delta can carry an insert or a wall-clock update, and the source is blunt about what both do: an insert-if-absent delta resurrects a note the other device concurrently deleted, and a wall-clock update disagrees with the causal merge rule the namespace actually uses. So there is no live notebook delta at all. An older build may still send one; the receiving code notes explicitly that it is not applied, and the note converges through the reconcile pull instead.

That is the narrow reason. The broad one applies to broadcasting in general: a broadcast has no completeness signal. The relay is publish/subscribe with no mailbox — if no device is subscribed to the recipient's inbox at the instant a frame arrives, it is dropped. A sender that broadcasts 40 rows and gets no error back has learned nothing about whether the sibling holds 40, 39, or 0. Broadcasting makes devices probably agree. It cannot find out whether they do.

3. Compare summaries, not rows

So the devices need a way to ask "are we the same?" that is cheap enough to ask constantly. Shipping the rows is the wrong shape twice over: it is expensive in the common case, which is that nothing differs — you would transfer an entire account to discover you had nothing to do — and it does not scale with silence, since the quieter the fleet the more wasteful the check.

The alternative is a digest. Each device hashes its own state into one 32-byte Merkle root per namespace and ships the roots. Equal roots mean the two devices provably hold the same content; a differing root names the namespace to look inside. The digest is a version byte plus one root per namespace — thirteen of them today, so 417 bytes — and the advertisement adds eight bytes of a separate generation counter on top, for 425. Either way the size is fixed, regardless of whether the account holds a hundred rows or a hundred thousand.

DEVICE A DEVICE B ANY SIZE ANY SIZE HASH HASH SETTINGS MESSAGES MEMORY NOTEBOOK SAGA CONTACTS PLANS PEERDEVICES FILEINDEX KTIDENTITYLEDGER BLOCKS = = = ≠ = = = = = = = → LOOK INSIDE THIS ONE ONE ROOT PER NAMESPACE + VERSION + GEN A FIXED-SIZE PROOF OF A MATCH, OR THE NAME OF THE DIFFERENCE

Be precise about what this buys. It does not hide more from the relay: a digest and a row transfer both ride the same sealed sync_delta, and the outer envelope shows the relay only a coarse routing class — silent — that a dozen unrelated payload kinds also collapse into. The relay cannot tell one from the other.

What the digest changes is how much the devices move, and how often there is any traffic at all. A device advertises when its state actually changes, and the emit is suppressed when the payload is byte-identical to the last one that reached every sibling — added because writes that touch a hashed entity without changing any hashed field are common (bookkeeping saves, residency flips), and each one used to cost a full fan-out. The emit count is tracked as digestEmitCount so that "a quiesced fleet emits rarely" is measurable rather than hoped for. A pair that keeps advertising is a pair with a bug.

4. One namespace, one independent answer

Hashing all of your state into one root would work and would be nearly useless. A single root tells you that you differ. If your messages table has 40,000 rows and your settings have twelve, a settings change and a message change are indistinguishable, and either one sends you descending the whole store.

So state is partitioned into independently hashed namespaces — thirteen at the time of writing: settings, messages, memory, notebook, saga, contacts, plans, peerDevices, fileIndex, ktIdentityLedger, blocks, posts, agentConversations. Comparing two digests is one 32-byte comparison per namespace, and the result is not a yes/no but a list — precisely the namespaces to reconcile, and no others. A busy namespace never drags a quiet one along with it.

The localisation goes further on the responding side: a sibling asking about a namespace sends range fingerprints over its own rows rather than the rows themselves, and only a range that fails to match causes the responder to fetch the underlying table at all. (How those fingerprints are built is Reconciling by Digest.)

One detail is worth pulling out because it is a refusal. The digest carries a version byte, bumped whenever the set of namespaces or a leaf encoding changes, and a device that receives a version it does not recognise ignores the whole advertisement rather than attempting a partial comparison. Skew degrades to "no reconcile happened," never to "a repair happened against a mis-parsed digest" — the second failure is silent, and the first merely leaves you where you were.

5. The loop

Put together, the steady state is this, where A and B are two devices of one account:

A                                                B
│
│  local write → coalesce a burst
│
├── sync_delta{ state_digest, 10 roots + gen } ──▶
│                                                 compare with own roots
│                                                 → divergent namespaces
│                                    ◀── sync_delta{ reconcile_req, ns, ranges }
│  recompute B's ranges over A's rows
│  → ship rows in the ranges that don't match
├── sync_delta{ reconcile_resp, ns, rows } ──────▶
│                                                 merge each row by the
│                                                 namespace's rule
│                                    ◀── sync_delta{ state_digest, … }
│  compare again …

Two things about the wire are worth noticing. First, state_digest, reconcile_req and reconcile_resp are not new envelope types — they are kind strings inside the already-sealed, already-self-gated sync_delta payload. The whole reconciliation protocol added nothing the relay can see, and nothing it can distinguish from the sibling traffic that already existed.

Second, the last arrow fires after every round, including one that changed nothing. That looks like waste; §8 explains why it is load-bearing.

6. One pull, run from both ends

Here is the step that carries the design.

The exchange in §5 is a pull, and a pull is one-directional. A asks; B answers; A merges. B, having answered, has learned nothing and changed nothing — if B was the one missing rows, that round accomplished exactly zero for B.

Which is fine, because B is running the same loop. When B receives A's digest, B compares, finds divergence, and fires its own reconcile_req at A. Neither device is a client and neither is a server; each is both, in whichever role the current frame put it.

Why not make the exchange bidirectional, so one round fixes both sides? Because that would require the responder to know something it does not. A reconcile_req contains fingerprints of the requester's rows. From those the responder can compute which of its rows the requester lacks or holds differently — but not the reverse, because a fingerprint mismatch says the ranges differ, not which side is short.

So the productive direction of a pull is always "the device that lacks the row is the one that pulls it." And here is the difficulty: no device can tell, from a digest, which direction it is in. A mismatched root says the two states differ. It does not say who is ahead — and for a namespace edited on both sides, both are ahead, in different rows.

There are two ways out. Elect someone to decide — a leader, a coordinator, a tie-break on device identity — and now you own an election, a failure mode when the leader is offline, and a new question about what the server must learn to run it. Or let both devices fire unconditionally and make cross-firing safe. Pixie takes the second; the price of admission is the next section.

7. Why racing pulls cannot fight

Two devices pull from each other at once over an unordered transport. A's rows may land at B before or after B's land at A; a row may be delivered twice; a round may accomplish nothing. For this to be safe rather than usually-fine, every merge rule has to satisfy two properties.

Commutative: the merged result does not depend on which version you call "mine" — merge(a, b) == merge(b, a).

Idempotent: applying a version you already absorbed changes nothing — merge(a, merge(a, b)) == merge(a, b).

Take those as given and the safety argument is two lines. A ends the round holding merge(a, b); B ends it holding merge(b, a). Commutativity says those are the same value, so the two devices land on the same state without either being told what the other did. Idempotence says the redundant traffic — the row A shipped that B already had, the whole no-op round — is not merely harmless but invisible: it produces no change, so it produces no new divergence to chase.

DEVICE A DEVICE B a b a b MERGE(a, b) MERGE(b, a) =SAME STATE WITHOUT EITHER BEING TOLD WHAT THE OTHER DID RE-DELIVERED ROWS MERGE TO NO CHANGE — REDUNDANCY IS INVISIBLE CROSS-FIRING PULLS LAND ON THE SAME STATE — NO COORDINATOR

That is the whole reason there is no coordinator: with those two properties, there is nothing left for a coordinator to decide.

The properties are not free. Each namespace gets the weakest rule that holds them:

  • messages: the delivery flag is monotonic — false can become true and never the reverse — so whichever device saw the acknowledgement wins in either direction, and re-applying is a no-op. Edits and deletes fold through one rule (delete wins; otherwise the newer edit, tie-broken by the edit's own id) rather than by arrival order. Reactions merge as a per-reactor last-writer-wins map with removal tombstones, and the test suite asserts the commutativity directly: merging two reaction sets in either order produces identical bytes.
  • memory: insert-if-absent over an append-only log. Trivially commutative, trivially idempotent.
  • notebook, saga, plans, contacts: the mutable ones, and the only ones needing real machinery. Each row carries a version vector — a map from device id to a counter — encoding causality rather than time: whether one version descends from the other, or whether the two are genuinely concurrent. Descendants win. Concurrent versions are broken by taking the lexicographically greater encoded row bytes, which is arbitrary but identical on both devices, so both pick the same winner without consulting a clock either could be wrong about. That is Clocks You Cannot Trust.
  • peerDevices, fileIndex: single-writer per key, so last-writer-wins on the writer's own timestamp, an exact tie resolving revoke-wins and delete-wins respectively. ktIdentityLedger is append-only and immutable per key; a same-key conflict converges to the smaller entry hash.
  • settings: no per-row leaves, so it travels whole and merges per key by version vector with a value tie-break. It also shows the both-ends property doing real work: a merge iterates the incoming keys, so a key only the receiver holds is untouched by that round — not lost, just converged later, when the roles swap and the other device pulls the snapshot containing it.

Deletion is conspicuously missing, because "absence" is not something a row can carry. It gets its own article: Deleting Things That Stay Deleted.

8. The failure mode this shape actually has

The derivation in §7 assumes something specific: that every field the digest hashes is also a field some merge rule resolves. Break that and you get the characteristic failure of this design.

Suppose a message's reaction list is committed to the leaf hash — so a reaction changes the row's fingerprint — but the merge rule treats message content as immutable and ignores reactions. A reacts. A's root moves. B compares and diverges. B pulls; A ships the row; B's merge looks at it, decides nothing needs changing, applies zero. B's root has not moved. B re-advertises. A diverges. A pulls. Forever.

ROOTS DIVERGE PULL THE ROW THE SAME ROW, AGAIN MERGE APPLIES ZERO RE-ADVERTISE ROOT NEVER MOVED REACTIONS: IN THE HASH IGNORED BY THE MERGE EVERY STEP BEHAVES AS DESIGNED — AND THE LOOP RUNS FOREVER

Nothing errors. Both devices behave exactly as designed, at relay speed, on the main thread. This is why the source calls it a storm, and why the reaction CRDT in §7 exists at all — the comment records precisely this case: treating reactions as immutable "diverged the digest the moment anyone reacted or un-reacted after the sibling already held the message."

Two pieces of machinery exist purely because of this class of bug. In debug builds the message merge diffs the incoming row against the local one field by field and logs any field still differing after the merge, so a reproduction points at the offending field instead of at "sync is broken." It is careful about which differences count — a body that differs while an edit is still propagating is normal, and is flagged only once the edit state matches — and it names a subtler case: fields merged fill-if-empty, where the empty-versus-present case converges but two different non-empty values never will.

The second is a circuit breaker. If a pair runs more than eight reconcile rounds in ten seconds without converging, the loop logs the divergent namespace names and backs off for thirty seconds. It pointedly does not dismiss the "Syncing…" indicator when it does: a storm means the devices are genuinely not in sync, which is exactly when the user should be told.

One more consequence of §7 is easy to miss. A merge that changes nothing produces no new digest, so a no-op round would end the conversation — wrong whenever the responder is the one holding data the requester lacks. So the requester re-advertises after every round, no-op included, handing the turn back so the other device can discover it should pull. Without that, the comment notes, "the side that holds the data no-op-pulls forever and the other side never learns to pull from us."

9. Where the loop does not apply

Two cases sit outside it, worth naming so you know the boundary.

A device with nothing. Reconciliation is a diff engine, and a diff against an empty store is not a diff — it is a full transfer wearing a diff's clothing, negotiated range by range. So a freshly enrolled device does not reconcile its way into existence. It asks a sibling for a whole snapshot: the sibling exports its store, seals it, uploads it to a blob service and returns a sealed offer carrying the blob id, the key, the nonce and a SHA-256; the new device fetches, checks the hash, decrypts and imports wholesale. The request rides a wake class that can actually surface on a sleeping sibling, and is re-sent every five seconds up to seven times, because the device holding your data may not be awake yet. The steady state's trust rule still applies: a device serves a snapshot request only from its own userIDHash. That path is Absorbing a New Device.

A device across a generation boundary. The advertisement carries not only the roots but a generation counter, and when two devices disagree on it the content reconcile is skipped entirely — the behind device catches up to a separately anchored snapshot instead. Pulling content across that boundary is exactly what would resurrect rows the fleet already agreed to forget. That is The Convergence Barrier and the Cloud Anchor, the hardest problem in the series.

10. What "eventually consistent" actually promises here

The honest statement of the guarantee is narrower than the phrase suggests.

The guarantee is pairwise and conditional on contact. Two devices converge when they are both online at the same time and their digests reach each other. The fleet converges because every pair does; there is no fleet-level primitive underneath.

While one device is off, nothing happens at all. Not a delay — an absence. The relay has no mailbox: a digest published to a sibling with no live socket is dropped. If that sibling's app is suspended but installed, the relay's push wake can bring it back to reconnect and receive — but a silent wake cannot relaunch an app the user force-quit, and cannot reach a powered-off device. Those devices are not "behind." They are not participating, and they rejoin on their next launch, which advertises a fresh digest once the device roster is refreshed.

A device learns it is behind only when a sibling's digest reaches it. There is no timer that periodically re-asks. Advertisements are event-driven — a local write, a reconnect, or the tail of a reconcile round — with a bounded retry ladder (roughly 2, 8, 30 and 120 seconds) behind a failed send, after which the device waits for the next real event. In a fleet being used that is constant; in one where a device is idle and the other off it is nothing, which is the right amount of work.

There is no global order and no snapshot. Nothing here can tell you what the account looked like at a moment in time, or which of two concurrent edits "really" happened first. The tie-break in §7 picks a winner both devices agree on; it does not claim that winner is the right one. Edit the same Notebook note on two offline devices and one edit loses, deterministically and silently.

Equal roots prove equal hashed content, not identical databases. The leaf encoding deliberately excludes anything inherently per-device — when this device first saw a message, local row identifiers where a stable cross-device key exists, local contact linkages, the outbox. Converged devices are not byte-identical stores; they agree on everything the account is defined to contain.

And convergence is not evidence. The loop tells a device that its state now matches a sibling's. It never tells it that every device in the fleet has absorbed something — which is exactly the fact you need before you can safely forget a deletion. That evidence has to be gathered deliberately, in a round of its own, and The Convergence Barrier and the Cloud Anchor is about how.

References & further reading