HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

GroupThink

Mechanism: The Convergence Barrier and the Cloud Anchor

20 min read

A tombstone is a small permanent object whose only job is to keep a deleted row deleted. Keep them all and they accumulate forever; drop one early and the next device to wake up helpfully un-deletes your data. Collecting them safely means proving something about every device in the account — including the one asleep in a drawer — which is exactly the proof a system with no server is not supposed to be able to construct. Here is how it gets constructed anyway, and the second failure the proof does not cover.

Prerequisites: Deleting Things That Stay Deleted for the tombstone this article is trying to get rid of, and Reconciling by Digest for the state digest the barrier votes with.

1. The bind

A deletion in a replica set is not the absence of a row. It is a tombstone — a real, synced object saying "a row with this key existed here and is now gone," so a sibling that still holds the row drops it instead of shipping it back. Here it is a RowVersion with tombstoned = true: a namespace, a rowKey, a version vector, a flag, no content. It outlives the row it describes.

Now the arithmetic. Every deletion mints one and none are ever removed, so the set grows for the lifetime of the account — one entry per delete, on every device. At ten years of churn that is a store full of markers for things that no longer exist, each a durable record of an act whose whole point was to make something stop existing.

So: collect them. Except you cannot, and the reason is the reason tombstones exist. Your iPad has been off for a week. On your phone you delete a plan; the tombstone reaches your Mac; a month later you judge the tombstones old enough to be safe and both live devices drop them. The iPad wakes up holding the plan, live, with nothing anywhere to contradict it — and the reconcile machinery does exactly what it is designed to do, notices the phone lacks a row the iPad has, and repairs the gap. The plan is back, and nothing errors: inserting a row the fleet was missing is the ordinary case.

ONE ACCOUNT · THREE DEVICES · A MONTH PASSES PHONE MAC IPAD ASLEEP WAKES DELETE MINTS TOMBSTONE NEVER ARRIVES DAY 30 · JUDGED SAFE ∅ ∅ TOMBSTONES DROPPED PLAN · LIVE SYNC REPAIRS THE GAP RESURRECTED INSERTING A ROW THE FLEET WAS MISSING IS THE ORDINARY CASE

That is the bind:

Garbage collection is safe only when no device anywhere still holds a live copy of a tombstoned key. Determining that means knowing the state of every device in the account, including the ones currently asleep — and there is no server holding an authoritative copy that could answer on their behalf.

2. The timer is a bet, not a proof

The reflex is a retention window. Collect tombstones after thirty days. One line of code, and a bet: that no device in the account is offline for longer than thirty days.

Phones lose that bet routinely: an old iPad in a drawer over a summer, a Mac at the repair shop, a second phone you carry only when travelling. The bet is not obviously wrong on any given day, which is what makes it dangerous — it fails rarely, and when it fails it fails silently.

Walk it through. The stale device comes back, advertises its digest, and the reconcile finds a row the rest of the fleet lacks. The merge rule for a missing row is insert-if-absent, and it is correct — that is how a genuinely new note reaches the other devices. There is no field on the incoming row saying "this was deleted in 2026"; the tombstone was the only object carrying that fact, and it was collected. So the fleet cannot distinguish a resurrection from a creation, and it will not try. The user watches something they deleted quietly reappear, with no error and no way to tell which device did it.

The default position is therefore the opposite one, written into RowClock.dropAllTombstones as a comment: outside the barrier, tombstones are retained indefinitely — tiny, and bulletproof. Exactly one caller ever collects them, and reaching it requires evidence.

3. What unanimity actually buys

The naive target is the literal statement — every device has applied the deletion of key k — which needs per-key acknowledgement bookkeeping, a receipt per tombstone per device, and a policy for devices added mid-flight. Buildable, and a lot of machinery.

But that is not what safety requires. Resurrection needs a device that holds k live and ships it, so the property you actually need is: no device holds k live. And that property, for every key at once, falls out of something the fleet already computes.

The state digest is one Merkle root per namespace over live content. It commits to rows that exist and says nothing about tombstones (deliberately — see Reconciling by Digest). So suppose every device in the account reports a digest byte-identical to yours, and take any tombstoned key k in the fleet. Your device does not hold k live — that is what its tombstone means. Every other device's live content hashes to the same root as yours, so no other device holds k live either. Nobody can ship k, so the tombstone for k has no work left to do — and the argument never depended on which k you picked.

That is why the terminal action is dropAllTombstones rather than a per-key sweep: unanimous live-content identity retires every tombstone at once, measured with the 32-bytes-per-namespace value the devices were exchanging anyway. The barrier adds no new notion of state; it borrows the digest and asks one question about it.

4. The round

The exchange rides three sync_delta sub-kinds — gc_propose, gc_ack, gc_commit — over the same sealed, self-account-gated sibling channel everything else uses. The relay sees ciphertext it cannot attribute; there is no GC service.

Trigger. A round is not on a schedule. scheduleTombstoneBarrier fires from the one place in the digest handler where a sibling's digest came back with no divergent namespaces — the moment the fleet is known to agree about something — debouncing five seconds so a burst of convergence events becomes one attempt.

Leader. startTombstoneBarrier pulls the account's device roster from the identity directory, drops itself and any malformed key, and returns unless its own pubkey lexicographically precedes every sibling's. The lowest pubkey initiates; everyone else only answers. This is not an election — no negotiation, no term, no timeout to tune — because byte order is a total order every device evaluates locally from the same inputs, so the fleet runs one round instead of N. It can be this cheap because nothing breaks if no leader emerges; The Driver's Seat cannot afford that and pays accordingly.

Propose and ack. The leader mints a fresh 16-byte random nonce, records the roster it expects to hear from, and sends {nonce, digest} to every sibling. A sibling receiving gc_propose does not echo that digest back: it recomputes its own, right now, and replies {nonce, my digest} — it is being asked what is true on it at this instant, not whether it agrees with a claim.

Commit. The leader requires an ack from every member of the roster — not every device it has heard from lately, every device the directory says belongs to the account — and every acked digest, including its own freshly recomputed one, must be equal. Miss either and the round dies; a fifteen-second timer abandons anything incomplete and clears the nonce. An offline device is on the roster, never acks, and silently costs you the collection. That is the whole difference from §2: the timer guessed about absent devices, and the barrier waits for them.

COMMIT NEEDS EVERY ROSTER MEMBER · SAME NONCE · EQUAL DIGESTS LEADER LOWEST PUBKEY SIBLING A SIBLING B SIBLING C ASLEEP · NEVER ACKS GC_PROPOSE {NONCE, DIGEST} GC_ACK {NONCE, MY DIGEST} NO ACK ROSTER 3 · ACKED 2 ROUND DIES · 15 S TIMER SAFE: EVERY DEVICE KEEPS ITS TOMBSTONES THE TIMER GUESSED ABOUT ABSENT DEVICES — THE BARRIER WAITS FOR THEM

On success the leader broadcasts gc_commit {nonce, digest, generation + 1}. Each recipient checks that its digest still equals the agreed one — a device that edited in between has moved, keeps its tombstones, and gets collected in a later round — then drops all tombstones and records the new generation. The leader applies the same guard to itself.

5. What the nonce is for

Strip the nonce out and the ack becomes {digest}: a claim with no time attached to it.

That is not enough, and the failure is subtle. Frames here can arrive late — a briefly unreachable sibling flushes a queue, a wake backlog drains. Without a nonce, an ack a device sent during last round is indistinguishable from one it sent during this one, because the digest it carries may well be the same value (the fleet converges to the same digest all the time; that is what converging means). The leader would count the stale ack toward unanimity and declare it had heard from a device that has, in this round, said nothing — quite possibly because it is offline holding the live row. The nonce turns the ack from "I am at X" into "when you asked, in this round, I was at X," which is exactly the freshness the retention timer was pretending to have.

Be precise about the limit, though. The nonce protects the leader's tally. The receiving side of gc_commit does not check it; its guard is the digest equality above. That guard is load-bearing — it is what keeps a diverged device from collecting — but it is a weaker binding than a nonce, because a fleet can legitimately return to a digest it held before, and a gc_commit replayed at that moment would be accepted on its merits. The generation itself is replay-safe (setLocalGeneration refuses to move backward), so the residual is narrow — but the round's identity is implied there rather than checked.

6. The failure the barrier cannot see

Everything so far is a statement about a moment: at round N, these devices existed and held this content. Now restore one of them from a backup taken before the deletion.

Nothing above is violated. Every device that was asked answered honestly, unanimity was real, the tombstones were collected against a correct proof. And the restored device re-enters the account holding the pre-deletion row, live, with a local store that has no memory of ever having participated in a barrier — because that memory was part of what got rolled back. Its next digest exchange offers the deleted row to a fleet with nothing left to bury it with.

The barrier is a consensus among the devices as they are; a restore edits what a device was. No round-based protocol among current participants can catch that, because the adversary is not a lying participant — it is time. What is needed is a value a restore cannot roll back, held somewhere the account can still reach.

7. Two substrates that fail differently

The anchor is built on an asymmetry in Apple's storage model. An OS device backup captures the app's container and its UserDefaults, and a restore reverts them. It does not revert an app-managed file in the user's iCloud Drive container: that file is cloud-synced rather than device-backed-up, and stays where the fleet last put it. So put the same counter on both sides.

The generation is a monotonically increasing integer. BackupAnchor keeps this device's copy in UserDefaults.standard — deliberately .standard, so it rides the device backup and reverts on a rollback, because the asymmetry is the mechanism. The fleet's copy sits in the cleartext header of a sealed archive in iCloud Drive, so the check costs one download and no key at all.

The comparison is pure:

decide(local, anchor):
    anchor == nil        →  .noAnchor
    anchor >  local      →  .rolledBack(anchor)
    otherwise            →  .current

Why does anchor > local read as rolled back rather than behind? The generation advances only at a barrier, and a barrier commits only on unanimity across the full roster — so if the anchor stands at g, this device was present at the round that produced g and recorded g locally. A local value below g is not "I missed an update," it is "I un-saw one." That is the whole detection, and it separates exactly the case §6 needed from the merely offline device, which has an equal generation and a divergent digest.

SUBSTRATE 1 · DEVICE BACKUP SUBSTRATE 2 · ICLOUD DRIVE USERDEFAULTS.STANDARD GEN 7 GEN 5 RESTORE OLD BACKUP · GEN 5 RESTORE STOPS HERE GEN 7 · CLEARTEXT SEALED SNAPSHOT AN OS RESTORE CANNOT REVERT THIS FILE ANCHOR 7 > LOCAL 5 → ROLLED BACK, NOT BEHIND THE ASYMMETRY IS THE MECHANISM

The generation rides the existing digest advertisement — eight bytes, big-endian, after the roots — so "I am behind a barrier" is just another out-of-sync signal on a channel that already exists. A gap then suppresses content reconcile in both directions: the behind device does not pull, and the ahead sibling declines to serve it. Pulling across the gap is the exact operation that would resurrect.

Recovery is catchUpToAnchorIfBehind: decrypt with the BackupKey (an AES-GCM 256-bit key that rides iCloud Keychain, so no passphrase is involved), hard-delete the recoverable entities so the insert-only importer lands in the empty store it requires, import, and only then advance the generation — a failed import deliberately leaves it alone, since marking an incomplete store as current would suppress further recovery.

One detail there only shows up in a live fleet: the causal clock is re-seeded empty for the recovered rows. Otherwise the didSave observer would read a store full of rows it has no RowVersion for as a store full of brand-new local edits, bump each to {thisDevice: 1}, and let a merely-restored device out-version the fleet and win the merge with stale content — the exact corruption recovery exists to prevent.

The anchor's sealed body is a full snapshot of the account's content, so it also is the user's backup — and the code carries a pointed comment about why plans had to be in it: .plans is one of the four namespaces the barrier collects, so an anchor without them recovers a rolled-back device into a state that resurrects a plan the fleet already buried.

8. Anchor before GC

tryCommitBarrier writes the anchor at nextGen and waits for it to land before it broadcasts a single gc_commit or drops one of its own tombstones. The comment marking it says CRITICAL ORDER, and the reason is worth deriving rather than accepting.

Collection is irreversible: once tombstones are gone fleet-wide, the anchor is the only object capable of correcting a resurrection. So ask what each ordering costs when the step that can fail — the network write to iCloud — fails.

GC first, anchor second. The fleet drops its tombstones; the upload fails. The fleet is at generation g+1 with the anchor still at g. A device later restored to g reads the anchor, computes decide(local: g, anchor: g) = .current, and does nothing — the detection has been fed a value that agrees with it. Meanwhile the generation gap has switched off content reconcile in both directions, so the restored device can neither be repaired nor repair anyone: no tombstones to bury its stale rows, no anchor to overwrite them, no path back into the fleet. A failed upload has produced a permanently broken device.

Anchor first, GC second. The upload fails, the round aborts, and every device keeps every tombstone it had. The cost is one wasted round and a retry.

Now the other side of the ledger. Suppose the upload succeeds and the round is then abandoned — a slow write outlived the fifteen-second timer, or a newer round superseded it. There is now an anchor at g+1 and no device at g+1, because the barrier passes recordLocalGeneration: false on purpose: the write must not advance even the leader's own generation, or a late-completing upload would strand it ahead of a fleet that never committed. So the anchor is a floor nobody stands on, and nothing consults it, because the recovery check is driven by a sibling advertising a higher generation and none will. The next successful round computes localGeneration + 1, arrives at the same g+1, overwrites it.

That asymmetry is the whole argument: a dangling anchor is harmless, a missing anchor is not. The order follows from which failure you can afford.

One detail rides along: after the upload the leader re-checks its own digest before dropping its own tombstones, because a delete made during the upload window has not been through any barrier.

9. What this does not give you

The guarantee is real and contingent, and the contingencies deserve stating in full.

It is contingent on iCloud backup being enabled — per device. backupToiCloudEnabled is a device-local UserDefaults flag, deliberately not in the synced settings list, so each device answers for itself. handleGCBarrier refuses at its first guard when the flag is off, so such a device never acks — and since the leader requires an ack from every roster member, one device with the switch off means the account never collects a tombstone again. The correct direction to fail, and a genuine cost: the user opted out of a cloud file and pays for it in storage, with nothing in the UI connecting the two.

A single-device account never collects either — startTombstoneBarrier returns on an empty roster — and only four namespaces are ever collected. dropAllTombstones walks the causal namespaces: notebook, saga, plans, contacts. The settings CRDT keeps its own tombstone set in UserDefaults, which the barrier does not touch; that set grows unbounded by the same argument and has no collector at all.

There is a deadlock shape, and the code does not resolve it. A device that is behind the fleet generation and cannot reach the anchor — iCloud signed out, the backup toggle since turned off, the BackupKey missing because iCloud Keychain is disabled — fails catchUpToAnchorIfBehind at its first guard, while the generation gap has already excluded it from content reconcile in both directions. So it is safe (nobody will pull from it) and permanently stuck. There is no fallback route, no retry budget after which it re-enters normal reconcile, and no user-facing signal: the launch "Syncing…" overlay is armed only by a same-generation root mismatch, so a gap does not even raise it. The device reports itself as fine and quietly stops converging. Closing this needs a recovery path that does not depend on iCloud — most plausibly the sibling-served snapshot absorbing a new device already uses, gated on the same generation check.

Recovery is triggered by a sibling, not by launch, so a restored device with no sibling online holds its stale state — harmlessly, but indefinitely — until one appears. And the round's identity is only implied on the receiving side, as §5 set out: the commit is authorized by digest equality, not by the nonce it carries.

10. The shape of the answer

Two ideas do the work, and both generalize past this mechanism.

The first is replacing a bet about time with a proof about membership. "Thirty days" is a guess about the worst-case device; "every device on the roster acked this nonce" is a measurement. It costs collections — most rounds die because someone is asleep — and buys the property that when one does happen, no bet was placed.

The second is that a proof about the present cannot bind the past, and the fix is a second substrate with different failure semantics rather than a better protocol. Neither half suffices, and writing the durable one first is what stops them failing in the same direction at once.

References & further reading