GroupThink

Mechanism: Reconciling by Digest

21 min read

Two of your devices hold what is supposed to be the same memory, and no server is allowed to know which of them is right. Finding the difference without shipping the data is the whole problem — and the answer is a few hundred bytes that say where to look, a pull that runs from both ends at once, and a hash built to deliberately not notice where your data physically lives.

Prerequisites: Staying in Sync for the loop this sits inside, and The Relay for what the transport guarantees.

1. The question a sync server would have answered

When your laptop syncs a folder with a cloud drive, one participant has an unfair advantage: the server saw every write. It keeps a change journal, hands each client a cursor, and answers "what has changed since 4711?" in one query. Every hard part of sync — what differs, who is ahead, whose edit wins — collapses into a lookup, because one party holds a complete history.

Pixie's devices have no such party. Same-account traffic rides sync_delta frames sealed end-to-end to a specific sibling device and gated on the sender's userIDHash, over a relay that is pure publish/subscribe with no mailbox (Ephemeral Delivery). Nothing in the path retains a journal, because nothing in the path can read a byte. What differs? has to be answered by two replicas that each know only their own contents.

The obvious way to answer it is to enumerate: device A ships its row list, device B diffs it against its own. That works, and its cost is the wrong shape — proportional to the corpus every single time, including the overwhelmingly common case where nothing differs at all. Two idle phones would ship their entire message store back and forth to prove nothing happened. What you want is a check whose cost tracks the difference, and the difference is usually zero.

2. One number per namespace

The primitive is StateHash, in PixieKit/Protocol/StateHash.swift. It partitions the account's synced state into namespaces — thirteen at the time of writing: settings, messages, memory, notebook, saga, contacts, plans, peerDevices, fileIndex, ktIdentityLedger, blocks, posts, agentConversations — and computes one Merkle root over each: rows hashed into 32-byte leaves, sorted by a stable cross-device key, folded pairwise into a root.

The whole thing serializes to a fixed size: a version byte plus one 32-byte root per namespace, 417 bytes as it stands (StateDigest.encoded()). That is the entire "are we in sync?" exchange, whether you have forty rows or forty thousand. divergentNamespaces(from:) compares two digests root-by-root and returns the namespaces that differ.

Why one root per namespace rather than one for everything? A single root would answer only something differs, leaving you to descend the whole store to find where. Ten localize the answer — a divergence in messages never forces you to walk contacts — for 384 extra bytes per advertisement.

Everything else depends on two devices holding the same logical content producing byte-identical leaves, and that is not automatic. Leaves are encoded with CBORWriter in a fixed field order under a per-namespace domain separator ("pixie.state.messages", and so on) before being SHA-256'd, so a leaf from one namespace can never collide with another's. Dates hash at second granularity, because a floating-point timestamp that round-trips through the sync channel can come back a hair off and would otherwise diverge the digest forever. Optionals carry a presence byte, so "absent" and "empty" never hash the same.

3. What a leaf must refuse to commit to

One rule governs every field in the leaf encoding, and it is sharper than it first looks:

A field may be hashed only if the merge can converge it.

Hash a field the merge does not reconcile, and two devices that legitimately disagree about it will diverge on that leaf, diverge on the root, reconcile, change nothing, and diverge again — forever. The codebase calls this a storm, and there is a DEBUG-only per-row diff inside StateReconcile.applyMessage whose entire job is to name the offending field when one appears, which tells you these were found the hard way.

So the leaf commits only to converged content, and the exclusion list is specific: observedAt on a message (when this device first saw it — per-device by design), local row ids wherever a stable cross-device key exists, Contact.systemContactIdentifier, the outbox, and per-device MLS cursors.

The most instructive exclusion is peerPubkey. When a message arrives, InboxService.canonicalPeerPubkey rewrites it to the local contact's pinned key, resolved by the cert-verified userIDHash — so two of your devices can legitimately hold the same messageID with different peerPubkey values, depending on how far each has got in resolving that contact. StateHash's comment is blunt: hashing it "would diverge the digest forever (applyMessage never merges it)". The stable value, peerUserIDHash, is hashed instead, normalized so empty and absent collapse to one encoding, precisely so the backfill can converge them.

Then there is the exclusion made after a storm rather than before one. Memory events sync insert-if-absent over an append-only log with no tombstone — and calendar events were being ingested into that log from EventKit by a pass that deletes its window and reinserts with fresh ids each time. Synced, each device resurrected the rows its siblings had just deleted while minting new ids of its own: unbounded duplicates, and a memory root that could never converge. The fix was not a cleverer merge. Calendar events were dropped from the leaf entirely, and dropped again on apply so a stale sibling cannot reintroduce them; every device re-derives its own view from EventKit, the source of truth on all of them.

4. Why the round rides an existing wire type

Two frames carry the reconciliation: reconcile_req and reconcile_resp. Neither is a new envelope type. Both are string values in the kind field of a sync_delta — two of roughly two dozen sub-kinds sharing that single payload variant, alongside state_digest, heartbeat, gc_propose, infer_chunk and the rest.

That was deliberate, and the reason is attack surface. Payload has 27 variants, and each is a branch in a parser running on bytes from the network — reachable by anyone who can address an envelope to you, before anything about the sender is established. A sync_delta sub-kind is reachable only after the envelope is unsealed and the frame passes the self-gate in InboxService: senderUserIDHash == myUserIDHash. Anything failing that check never reaches the switch on kind at all. Sub-kind dispatch is parsing you do for yourself, on your own account's plaintext; a type tag is parsing you do for the world.

There is a metadata argument too: the relay reads only a coarse WakeClass on the outer envelope, not the precise type tag (The Envelope), and syncDelta projects to .silent — so a digest advertisement, a pull request and a row transfer are indistinguishable to it from each other and from most other traffic.

Riding a shared frame imposes a discipline in return: you cannot break the shape. When version vectors and tombstones were added to Response, they got a custom decoder reading them as optional — a synthesized one would throw on the missing keys and drop an un-upgraded sibling's whole response. A change to the leaf encoding is not tolerated at all: StateDigest.wireVersion (currently 6) gates the digest, so a real format change degrades to a clean no-reconcile rather than a false repair.

5. The round itself

With the digest in hand, the transfer is one exchange per divergent namespace:

A  (saw B's digest diverge in namespace X)
    ── reconcile_req { X, A's range fingerprints } ──▶  B
                                                        B recomputes each range
                                                        over ITS leaves; gathers
                                                        rows in the ranges that
                                                        don't match
    ◀── reconcile_resp { X, rows, vectors, tombstones } ──  B
A: merge each row under X's rule.

It is a one-directional pull — B learns nothing from A's request except which ranges to check. What makes that sufficient is that both devices run it: each pulls when it receives the other's digest, so the pair converges with no leader and no agreement about who goes first. Cross-firing is safe because every merge in StateReconcile.apply is commutative and idempotent, the subject of Clocks You Cannot Trust.

settings is the exception: a flat dictionary with no per-row leaves, too small for a tree, so its request carries no fingerprints and the responder sends the whole synced dictionary, per-key version vectors and tombstoned keys included.

6. Fingerprints out, rows back

A message row is the message: body text, media JSON, reactions, reply pointers, sender name, timestamps — hundreds of bytes to a few kilobytes. Its leaf is 32 bytes and its key is a 16-byte messageID. For a store of n messages, shipping rows costs n × |row|; shipping (key, leafHash) pairs costs n × 48 plus framing. Two or three orders of magnitude — and, more importantly, the response then costs only the rows that actually differ.

The code goes one step further than a flat pair list. StateReconcile.bucketize partitions the sorted leaves into key-range buckets, each carrying lo, hi, a Merkle root over the leaves in that range, and a count. With fineThreshold = 256, a namespace of 256 rows or fewer gets a group size of 1 — one bucket per row, whose lo is that row's key and whose root is that row's leaf hash (a lone leaf is promoted unchanged, so the root is the leaf). At small sizes the buckets are the (key, leafHash) list. Above the threshold the group size becomes ceil(n / 256), so the request stays at roughly 256 buckets however large the namespace grows: constant-size, at the cost of shipping a whole bucket's rows when that bucket mismatches.

Two details in the layout are worth deriving rather than accepting.

The buckets tile the entire key space. The first bucket's lo is empty (unbounded below), the last one's hi is nil (unbounded above), and each bucket's hi is the next one's lo. That is necessary, not tidy. The responder may hold keys the requester has never seen — the most common kind of divergence there is. If the request described only tight ranges around keys the requester holds, a row existing only on the responder's side would fall into no range and be invisible. Because the buckets tile, every key the responder holds lands in exactly one, and its presence changes that bucket's recomputed root.

The count is compared alongside the root. The Merkle build promotes an odd node unchanged rather than padding, so merkleRoot([X]) == X — meaning a one-leaf range whose leaf equalled the internal node of a two-leaf range would have the same root. The root does not structurally commit to how many leaves went into it. That collision needs a leaf hash to equal a node hash, and the two use different domain separators, so it is a SHA-256 break rather than a real hazard; comparing one integer makes the check structural rather than collision-dependent.

What all of this costs is a round trip: bytes converted into latency. Instead of one push carrying data you have digest → request → response, three relay hops before a single row moves. Section 8 is about what happened when that latency compounded.

7. The digest commits to content, not residency

This is where the mechanism stops being a hash comparison and starts encoding a claim about what sync is for.

Your Notebook accumulates indefinitely; a phone's disk does not. So Pixie lets you offload a note's body to a Mac running as a Homebase: the phone keeps title, tags and a content hash, the bytes live on the big disk, and they come back on demand.

Now suppose the notebook leaf hashed the note's body text, which is the obvious thing to do. An offloaded note has an empty body; the same note resident on your iPad does not. The leaves differ, the root differs, and offloading a hundred notes advertises a hundred-row divergence to every sibling — for a hundred rows whose content nobody touched. The pull then dutifully tries to repair it, shipping resident bodies back at the device that just freed the space. A deliberate act of reclaiming storage would present to the sync layer as data loss.

The fix is one function, StateHash.noteBodyLeafDigest(clearBody:contentHash:). A resident body contributes noteBodyDigest(body) — SHA-256 under the fixed separator "pixie.notebook.body". An offloaded pointer contributes its stamped contentHash, which is that same digest, computed from the body before it was cleared. Identical content therefore produces an identical leaf whether or not this device holds the bytes.

Continuity is enforced at the mutator: NotebookStore.markOffloaded refuses unless StateHash.noteBodyDigest(note.clearBody) == contentHash, stamps the hash, and then clears the body — so there is no instant at which the leaf's body contribution changes. The residency fields themselves, bodyOffloaded and offloadHolderPubkey, are excluded from the leaf exactly like observedAt, so two devices whose pointers name different holders still agree on the root.

Two further consequences follow, and both are load-bearing:

The offload mutators never touch updatedAt. RowClock detects local edits by watching updatedAt; bumping it would advance the row's version vector and move the digest through the back door — the precise storm the residency-independent leaf exists to prevent. Residency is not an edit, and the code refuses to let it look like one.
A sibling's offload must never evict your copy. When a pointer arrives whose contentHash matches a body you hold resident, applyNotebook keeps your bytes and drops the pointer state — safe precisely because the leaf commits the content hash either way, so keeping the body cannot diverge the digest.

Four tests pin the property down: an offloading device and a fully-resident one compute the same notebook root; the offload and un-offload transitions leave the digest bit-identical; two pointers naming different holders agree; and a pointer to different content still diverges the root.

The general statement is worth keeping: the leaf is a claim about what the account knows, not about what this disk holds. Every field where those two differ belongs on the exclusion list, or the digest quietly becomes a report on storage layout.

8. Why re-advertising on apply collapses the settle

A reconcile is rarely one round. Coarse buckets cover only what the exchange described; the other device may hold rows you lack; a tombstone may arrive after the row it deletes. So convergence is a loop: apply rows → your digest has moved → advertise it → the peer re-compares → next round.

Whatever gates the advertisement therefore sets the loop's period, and advertisements go through markStateDirty, which schedules a debounced emit — a coalescing window so an agent committing forty notebook rows produces one advertisement instead of forty. That window used to be three seconds. Instrumentation on a real two-device fleet found the data transfer itself taking about 60 ms; everything else was the wait. Each round cost three seconds, so a sibling reconnect needing several rounds took 6 to 16 seconds to settle, over a relay that had already delivered every byte.

Two changes fixed it, and only one is interesting. The debounce dropped from 3 s to 400 ms (SocialServices.stateDigestDebounce), which still folds a tight write burst into one emit while no longer dominating anything. The real fix is that handleReconcileResponse now emits the digest to the active sibling immediately — targeted, bypassing the debounce entirely.

That is worth following, because it explains why a debounce was right in one place and wrong in the other. Coalescing protects against a burst of independent writes, where you do not yet know whether more are coming. A reconcile apply is not that: you already know something moved, and exactly who you are converging with. The wait bought nothing there and was paid on every round. Removing it turns N rounds × debounce into N rounds × relay latency. Measured end to end: converged in 16,291 ms before, 316 ms after.

Speeding the loop up then exposed a stall the slow version had been hiding. The pull runs only in the direction of whoever receives a digest. Suppose your phone holds a reaction your iPad lacks, and the phone is the one that received the iPad's digest. The phone pulls, the iPad's rows change nothing (applied == 0), and if the re-advertisement is gated on applied > 0 the phone never tells the iPad anything — so the iPad never learns to pull from the phone, and the holder no-op-pulls forever. With three-second rounds that limped along on unrelated emits; with relay-fast rounds it tripped the storm guard and stuck for minutes. So the re-advertisement fires after every round, including a no-op — and convergence is what stops it, since matching roots leave the sibling nothing to do.

Two guards keep that from becoming noise: an emit whose payload matches the last one that reached every sibling is skipped, and on reaching matching roots a device that was actively reconciling returns its now-matching digest exactly once — enough for a one-directional puller to learn the pair converged, without settled devices ping-ponging forever.

9. What the digest does not tell you

A digest reports that, never what. Equal roots prove equality; unequal roots prove inequality and nothing more — not how many rows differ, not which, not in which direction. So every diverged namespace costs a full key-list exchange: bucketize walks every leaf on the requester, respond walks every leaf again on the responder, and one changed message in a store of twenty thousand costs two full scans. The response is proportional to the difference; the detection is proportional to the namespace, always.

Coarse buckets over-ship, and there is no persisted tree. Above 256 leaves, one differing row ships its whole bucket; the requester dedups on merge, but the bytes crossed the relay. And currentStateDigest() recomputes every root from the live store, memoized only until the next write — defensible at this emit cadence, but a full scan each time. A much larger corpus would want an incrementally maintained tree; this design deliberately has none.

A responder with nothing to give is silent. When neither rows nor tombstones diverge, handleReconcileRequest sends no frame, so a round whose divergence lies entirely in the requester's favour produces no reply and no prompt; closing it depends on the requester's own advertisement, which the write that created the divergence already scheduled.

Version skew degrades to no sync at all. A digest whose wireVersion byte does not match is rejected outright, so a fleet spanning a leaf-encoding change does not reconcile until every device updates — the right failure direction, since a false repair is far worse than none, but a device left on an old build stops converging silently.

The storm guard bounds a bug; it does not fix one. More than eight rounds with the same sibling inside ten seconds and the pair backs off for thirty, logging the divergent namespaces. The launch "Syncing…" overlay is deliberately not dismissed when that fires: a storm means you are still out of sync, which is exactly when the user should see it. The underlying cause is always the same shape — a field hashed but not mergeable — and the only real repair is to change the leaf or change the merge.

References & further reading

RFC 6962, Certificate Transparency — Merkle trees used the way this article uses them: a small root standing in for a large set, with the tree structure making disagreement locatable.
RFC 8949, Concise Binary Object Representation (CBOR) — including deterministic encoding, which is why the leaf encoder pins field order rather than trusting a serializer.
The rsync algorithm, Tridgell & Mackerras — the classic statement of this trade: exchange checksums first, transfer only what differs.
Merkle tree and gossip protocols — background on hash trees and anti-entropy, the family this reconcile loop belongs to.
Mechanism: Clocks You Cannot Trust — the merge rules that make a pull running from both ends safe, and why the version vector stays out of the leaf.
Mechanism: Deleting Things That Stay Deleted and Mechanism: The Convergence Barrier and the Cloud Anchor — where the tombstones in a response come from, and why they are never collected inside this loop.
The Homebase — offloaded notes and the invariants the residency-independent leaf exists to serve.
The Envelope — what the relay sees of this traffic.