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. The answer has three parts: 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.
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 (a bookmark into that journal) and answers "what has changed since entry 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. Traffic between your own devices rides
sync_delta frames. Each frame is sealed end-to-end: encrypted so that only the
one sibling device it is addressed to can open it. A frame is accepted only when the sender's
userIDHash (the account fingerprint all of your devices share) checks out. The frames travel
over a relay that is pure publish/subscribe with no mailbox: it forwards traffic to whoever is
listening right now and stores nothing (Ephemeral
Delivery). Nothing in the path retains a journal,
because nothing in the path can read a byte. So what differs? has to be answered by two
replicas (two copies of the same account state) that each know only their own contents.
The obvious way to answer it is to enumerate: device A ships its full list of rows, device B diffs it against its own. That works, but its cost is the wrong shape: it is proportional to the whole store 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.
The building block is StateHash, in PixieKit/Protocol/StateHash.swift. It partitions the
account's synced state into namespaces (independent buckets, one per kind of data: settings, messages,
memory, notebook, saga, contacts, plans, peerDevices, fileIndex, ktIdentityLedger,
blocks, posts, agentConversations) and computes one
Merkle root over each. A Merkle tree is a way to stand one small hash in for many items:
each row is hashed into a 32-byte leaf, the leaves are sorted by a stable cross-device
key, and pairs of hashes are folded together, level by level, until a single 32-byte root remains.
Change any row and the root changes; hold identical rows and the roots match.
The whole thing serializes to a fixed size: a version byte plus one 32-byte root per namespace,
a few hundred bytes (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. One root per namespace localizes the answer (a divergence in
messages never forces you to walk contacts) for a few hundred extra bytes per
advertisement, each time a device announces its current digest to its siblings.
Everything else depends on one thing: two devices holding the same logical content must produce
byte-identical leaves, and that is not automatic. Leaves are encoded with CBORWriter: a
compact binary serializer, pinned here to a fixed field order so one row can never encode two
ways. Each encoding is then hashed with SHA-256, a standard cryptographic hash function, under a
per-namespace domain separator, a fixed label mixed into the hash
("pixie.state.messages", and so on), so a leaf from one namespace can
never collide with a leaf from another.
Dates hash at second granularity. A floating-point timestamp that round-trips through the sync channel can come back a hair off, and that tiny drift would otherwise diverge the digest forever. Optionals carry a presence byte, so "absent" and "empty" never hash the same.
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. 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. (MLS, Messaging Layer Security, is the group-messaging
protocol that carries shared threads; a cursor is each device's own position in it.)
The most instructive exclusion is peerPubkey, the sender's public key as this device
currently knows it. When a message arrives, InboxService.canonicalPeerPubkey rewrites that
field to the local contact's pinned key (the one copy of the contact's key this account has
committed to), resolved by the certificate-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 (the later pass that fills the field in) can converge them.
Then there is the exclusion made after a storm rather than before one. Memory events sync by insert-if-absent: they live in an append-only log, and a row is added only if its id is not already present. The log has no per-row tombstone (no record marking one row as deleted), because a deletion travels as just another event, carrying the id of the conversation it buries. There is no way to retract a single row. Into that log, calendar events were being ingested from EventKit, the system calendar store, by a pass that deletes its whole time window and reinserts it with fresh ids each time.
Once 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 now re-derives its own
view from EventKit, which is the source of truth on all of them.
Two frames carry the reconciliation: reconcile_req and reconcile_resp. Neither is a new
envelope type (an envelope being the encrypted wrapper every frame travels in). 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: the amount of code an outsider can
reach. Payload has a couple of dozen variants, and each is a branch in a parser running on
bytes from the network. Every branch is 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 (a rough hint about whether the recipient should be woken, not the precise type tag;
see The Envelope), and
syncDelta maps to .silent. So a digest advertisement, a pull request and a row
transfer all look the same to the relay, and the same as most other traffic.
Riding a shared frame imposes a discipline in return: you cannot break the shape. When version
vectors and tombstones (the per-device edit counters and delete records of Staying in
Sync) were added to Response, they got a custom decoder that reads them
as optional. The compiler-generated decoder would have thrown on the missing keys, and one
missing key would have dropped an un-upgraded sibling's whole response.
A change to the leaf encoding is not tolerated at all. StateDigest.wireVersion gates the
digest, and it is bumped whenever the namespace set or a leaf encoding changes. A real format
change therefore degrades to a clean no-reconcile rather than a false repair.
With the digest in hand, the transfer is one exchange per divergent namespace. Device A,
having seen B's digest diverge in namespace X, sends reconcile_req carrying X and
its range fingerprints: small hashes that each summarize one run of rows (the next section
builds them). B recomputes each range over its leaves, gathers the rows in
the ranges that fail to match, and answers reconcile_resp with those rows, their
version vectors, and the namespace's tombstones. A merges 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 (running two
merges in either order gives the same result) and idempotent (applying the same merge twice is
the same as applying it once), the two properties Staying in Sync turns into the
both-ends argument. Those merges are the subject of Clocks You Cannot
Trust.
settings is the exception: a flat dictionary with no per-row leaves, too small for a tree.
Its request carries no fingerprints, and the responder sends the whole synced dictionary,
per-key version vectors and tombstoned keys included.
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 times the size of
a row; shipping (key, leafHash) pairs costs n × 48 bytes plus framing. That is a saving
of two or three orders of magnitude (a hundred to a thousand times fewer bytes) 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. In other words, the
root does not structurally commit to how many leaves went into it. Producing that collision
would need a leaf hash to equal a node hash, and the two use different domain separators, so
it would take a break of SHA-256 itself rather than being a real hazard. Still, 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. §8 is about what happened when that latency compounded.
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, the one function allowed to make the change.
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:
updatedAt. RowClock (the bookkeeping that
spots local edits) does so 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.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.Tests pin the property down from both sides: 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.
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. Advertisements go through
markStateDirty, which schedules a debounced emit: a short 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, and the iPad's rows change nothing on the phone (applied == 0). 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 device holding the extra row keeps pulling to
no effect, 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.
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 drops the duplicates on merge, but the bytes crossed
the relay. And currentStateDigest() recomputes every root from the live store, cached 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. That is 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.