HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

GroupThink

Mechanism: Deleting Things That Stay Deleted

21 min read

A replica set converges by adding: two devices compare what they hold, each ships what the other is missing, and both end up with the union. Deletion is the one operation that shape cannot express — an absent row and a never-seen row look identical from outside, and the helpful answer to both is to send it again. The fix is to stop deleting and start writing a row that says "deleted", which sounds like a dodge until you follow what it buys: a delete that is monotonic, order-independent, and needs no new machinery at all.

Prerequisites: Clocks You Cannot Trust for the version vectors the mutable namespaces merge with, and Reconciling by Digest for the pull round every tombstone rides.

1. The operation that carries no evidence

Start with a trace, because the failure is not obvious until you watch it happen.

You have a phone and an iPad on the same account. Both hold the memory namespace — the append-only event log the agent reads, described in Memory & the Notebook. One agent conversation in it has four MemoryEvent rows, each with a stable UUID, each tagged with the same conversationID.

On the phone you delete that conversation. The obvious implementation is the obvious one: delete the rows.

  phone                                     iPad
  ─────                                     ────
  4 rows in conversation C                  4 rows in conversation C
  user deletes → 0 rows                     (asleep, knows nothing)

  … later, both awake, digests advertised …

  memory digest differs  ───────────────────────────────▶  memory digest differs
  phone: "here are my (key, leafHash) buckets"
                        ◀── iPad: "you're missing 4 rows, here they are"
  phone: insert-if-absent → 4 rows back

The phone's memory root now matches the iPad's. The system has converged. It has converged on the wrong value, and the conversation is back on your screen.

Notice who is at fault, because it is nobody. The iPad's responder does exactly the right thing: it compares its leaf set against the phone's, sees four keys the phone lacks, and ships them — the same code path that lets a sibling that was off for a week catch up. Re-shipping what a peer lacks is the responder's whole job.

The deeper point is that no amount of comparing the two sets can fix this. A set difference is symmetric: "the phone lacks row r" is one fact, and it is produced identically by two completely different histories — the phone deleted r, or the phone has never heard of r. The interpretation lives in the history, and the history is not in the sets. The transport compares sets. So the information has to be put into the set, or it does not exist.

TWO HISTORIES SAME OBSERVABLE SET ONE RESPONSE HISTORY 1 HELD R — DELETED IT MISSING: R RESURRECTED — WRONG IDENTICAL FROM OUTSIDE HISTORY 2 NEVER HELD R MISSING: R CAUGHT UP — CORRECT SIBLING RE-SHIPS WHAT THE PEER LACKS R R THE SET CARRIES NO HISTORY — BOTH ABSENCES GET THE SAME ANSWER

There is a second thing to see in that trace. The merge rule for this namespace is insert-if-absent — in StateReconcile.applyMemory, an incoming row is dropped if its UUID is already present and inserted otherwise, and that is the entire rule, because an append-only log has no conflicts to resolve. Insert-if-absent means the merge computes a union. Union is a beautiful operation to build a distributed system on: it is commutative, associative, and idempotent, so it does not care which device pulls first, how many times a row arrives, or in what order. It has exactly one weakness. Union cannot shrink a set. A delete asks the system to do the one thing its merge operator is incapable of expressing.

2. Making the deletion a thing

If the only operation the transport implements is "add", then a delete has to be encoded as an addition. That is the whole idea, and everything else in this article is consequences.

A tombstone is an ordinary row whose meaning is "the thing named here is gone." In the memory log it is a MemoryEvent like any other, with a kind the schema already had:

public static func tombstone(conversationID: UUID, at date: Date = Date()) -> MemoryEvent {
    MemoryEvent(kind: .tombstone, body: "", occurredAt: date, conversationID: conversationID)
}

Empty body. Its own fresh UUID, so it is its own leaf. The identifier of what it buries travels in conversationID, the field the log already carries.

Now count what had to be built to make that sync. The digest builder, StateHash's memoryLeaves, walks every MemoryEvent row and hashes it — it excludes message-kind and calendar events, and a tombstone is neither, so the marker is a leaf and its arrival moves the namespace root. Divergence detection therefore notices it for free. The reconcile responder ships it as one more row in a mismatched range. The applier inserts it if-absent, exactly like a journal entry. It never touches the wire format: sync_delta carries the same reconcile_resp body it always did.

So the answer to "what did the tombstone cost" is: one enum case that was already in EventKind, and a reader. No new wire kind, no second merge operator, no branch in the reconcile, no CRDT redesign.

The delete path in ChatView shows the ordering that matters:

modelContext.insert(MemoryTombstones.tombstone(conversationID: id))
let events = allEvents.filter { $0.conversationID == id && $0.kind != .tombstone }
for e in events { modelContext.delete(e) }

The marker goes in before the rows come out, and the filter is careful not to delete the marker it just wrote. The local deletes still run — they reclaim space — but they are no longer what makes the deletion real. The tombstone is.

Reading is a pure function over the log. MemoryTombstones.live(_:) collects the buried conversation ids, then returns the events minus the markers themselves and minus everything they bury. Every consumer of the log goes through it rather than filtering by hand, so that "deleted" means one thing everywhere — ChatView for what you see, HuddleContextRetriever for what the agent packs into a huddle, SagaService for what gets summarised.

3. Monotonic, order-independent, and why that is enough

Two properties fall out of that design, and together they are the proof that it works.

A tombstone is monotonic. Once inserted it is never un-inserted. No ordinary code path removes a memory tombstone event; the reconcile only ever inserts. Each device's tombstone set can therefore only grow, and it grows toward the union of everyone's, carried by the same insert-if-absent path as the data. There is no window in which the marker is absent again and the buried rows are visible again.

A tombstone is order-independent. live(_:) computes the buried set from the whole log first, then filters. It never asks when a row arrived. So a row that a sibling re-ships long after the tombstone converged is buried the moment it lands, and a tombstone that arrives long after the rows it buries takes effect the moment it lands. The test suite pins exactly this, in both directions:

#expect(MemoryTombstones.live([tombstone, resurrected]).isEmpty)
#expect(MemoryTombstones.live([resurrected, tombstone]).isEmpty)

Now the convergence argument, which you can do in your head. Let device A hold event set E_A and device B hold E_B. The pull round is insert-if-absent and is run independently from both ends, so after they exchange, both hold E_A ∪ E_B — union, so it does not matter who pulled first or whether both pulled at once. The visible state is live(E), a pure function of that set. Same set in, same view out. The two devices agree.

That is why the tombstone needs no coordination, no timestamp comparison, and no leader. It converts a request the merge operator cannot serve ("remove this") into one it serves natively ("add this"), and it moves the deletion semantics from the storage layer, where order and timing bite, to the read layer, where they cannot.

Follow the trace from §1 again with the marker in place. The phone tombstones and deletes its four rows. The iPad still holds them and re-ships them, and the phone still re-inserts them, because nothing in the applier consults the tombstone set. The rows come back to disk. They do not come back to the screen, on either device, ever — and the iPad, which pulls the marker on its own next round, buries its copies too. Section 8 returns to what that means, because "converged and invisible" is not the same claim as "erased."

THE SCREEN — WHAT EVERY READER SEES CONVERSATION C ∅ NOT SHOWN — EVER LIVE( ) — MINUS THE MARKERS, MINUS WHAT THEY BURY ROWS OF C TOMBSTONE RE-INSERTED THE LOG — UNION, ONLY GROWS RE-SHIPPED BY A SIBLING RESURRECTION REACHES THE DISK — NEVER THE SCREEN

4. When the tombstone cannot live in the table

The memory log is append-only, so its rows are immutable and a marker row is a natural fit. Four namespaces are not like that: notebook, saga, plans and contacts hold rows you edit on more than one device, and they merge causally — each row carries a version vector in a RowVersion bookkeeping row, and a merge asks whether one side's history dominates the other's or whether they are concurrent (this is Clocks You Cannot Trust).

You cannot bury a note with another note. So the tombstone goes where the row's causal history already lives: RowVersion outlives the row it describes. It is keyed by (namespaceRaw, rowKey), holds the vector, and holds a tombstoned flag.

Detection is not per-write-site. RowClock.observe runs at the ModelContext.didSave chokepoint, diffs the live rows against the RowVersion entries, and closes with one loop:

for (key, e) in entries where !e.tombstoned && !liveKeys.contains(key) {   // deleted
    bump(e, deviceID); e.tombstoned = true; e.syncedAt = .distantPast; changed = true
}

A key with bookkeeping and no row is a deletion. The vector is bumped on the deleting device's own dimension before the flag is set, which is what makes the tombstone dominate what the sibling holds: the sibling's copy carries the vector this device had just seen, and this device's is now strictly ahead of it. Deletion is a causal event like any other edit.

The transfer has a subtlety worth deriving, because it is the kind of thing that looks like over-sending until you see why it is not. A reconcile response ships rows for the key ranges whose Merkle fingerprints did not match — but it attaches the entire tombstone set for the namespace, unscoped. The comment in StateReconcile.respond explains: a tombstone's key is in no live leaf, so the range comparison — computed over live leaves only — can never flag it. Scope the tombstones to mismatched ranges, and the keys deleted on both sides fall into ranges that match perfectly (neither side has them live), so their tombstones would never travel, and the two devices' vectors for those keys would stay permanently different. A third sibling that later re-ships a live copy of such a key could then resolve it differently on each device. Shipping the whole set costs nothing real — applying a tombstone is idempotent, and deletes are rare — and closes that hole by construction.

On the receiving end, applyTombstones deletes a local row only when the incoming tombstone causally dominates the local copy, and records the merged vector either way so both sides' histories converge whether or not the row went.

5. Delete-wins, stated precisely

It is tempting to summarise all of this as "delete-wins." That is not what the code does, and the difference is the interesting part.

Where causality can decide, causality decides. VersionVector.resolveMerge returns .delete only when the incoming tombstone's vector dominates the local vector. When the two are genuinely concurrent — a device deleted a note while another device was editing it, neither having seen the other — the rule is add-wins: the live value beats the tombstone, and the note comes back.

case (false, true):  return (.adopt, merged)             // add-wins: live beats tombstone
case (true, false):  return (.keep, merged)              // add-wins: keep our live value

That is deliberate, and it is the weaker of the two available rules on purpose. A delete that happened after seeing your edit should destroy it — you deleted the thing you were looking at. A delete that happened without seeing your edit is not a decision about your edit at all, and silently discarding work nobody knew existed is the worse error. A surviving note is recoverable; a destroyed one is not.

THE DELETE SAW THE EDIT NOTE EDIT ON A [A:1] SYNC — B SEES IT DELETE ON B [A:1 B:1] DOMINATES [A:1] ∅ .DELETE — ROW GONE THE DELETE RACED THE EDIT NOTE EDIT ON A DELETE ON B [A:1] [B:1] NEITHER SAW THE OTHER ADD-WINS — THE NOTE SURVIVES A SURVIVING NOTE IS RECOVERABLE — A DESTROYED ONE IS NOT

Where causality cannot decide — a tie in a namespace that has no vectors — deletion is the side chosen. Three instances, all in the same shape:

  • peerDevices (a contact's roster of their own devices) merges last-writer-wins on the owner's lastAdvertisedAt, and an exact tie resolves revoke-wins.
  • fileIndex merges last-writer-wins on indexedAt, and an exact tie resolves delete-wins.
  • Message reactions are a per-reactor CRDT whose total order is "newer wins; on a tie, a removal beats a reaction; then the larger emoji" — so a tie un-reacts.

And peerDevices records a rejected alternative worth reading twice. It is not causal, and the architecture notes say why: causal add-wins would resurrect a device the owner deliberately dropped, the instant a stale advertisement raced the drop. That namespace has a single writer (the contact owns their own roster), so there is no concurrent-edit case to protect and nothing add-wins would buy — only a hole. The same rule that is right for your notebook is wrong for someone else's device list, and the deciding question is not "which rule is safer" but "who writes this row."

6. Why a delete must beat an edit

Messages get their own fold, and here deletion is absolute. MessageFold ranks delete scope everyone (2) above me (1) above live (0), the stronger scope always wins, and — the line that matters — a row with any delete scope stops accepting edits entirely:

if row.deletedScope != nil { return changed }
// 2) Edit LWW.

Messages are event-sourced: a message's rendered state is a fold over an append-only set of immutable MessageOp rows, and edits among themselves are last-write-wins on (editedAt, editOpID) — the op id breaking a same-second tie byte-lexicographically so every device picks the same winner. Deletes do not join that ordering. They dominate it. Three independent reasons force that direction, and any one of them alone would be enough.

The content is gone. A delete:everyone purges the plaintext — row.body = "", row.mediaJSON = nil. If a later edit could win, the fold would have to converge on content that no longer exists on the device that deleted it. An absorbing state is the only consistent one once you have destroyed the material.

The digest would never converge. A deleted row's leaf is canonicalised to identity alone — messageID, directionRaw, postedAt, and the scope — and MessageFold clears editedAt and editOpID on delete. Derive why: those fields are hashed into the messages leaf. A device that edited a message and then deleted it would hold editedAt = T; a device that only ever saw the delete would hold editedAt = nil; both agree the message is deleted, and their digests would differ forever, re-triggering a reconcile that can never resolve anything. Making the delete absorbing and canonical is what stops a row everyone agrees about from diverging on the details of how it got there.

Deletion has a second escape route that is not sync at all. An undelivered outbound message keeps a cooperative-delivery duty: any device of yours that holds one keeps trying to send it. If a delete did not dominate, deleting a message that had not yet gone out would leave the retry machinery cheerfully delivering it. reconcileOutboxDuty closes that by deriving the duty from the folded row rather than from independent per-device state:

if row.isDelivered || row.deletedForEveryone {
    for item in existing { modelContext.delete(item) }

Because the duty is a pure function of the (already-converging) messages namespace, a delete that converges to a sibling also cancels that sibling's obligation to send. The recall rides the same convergence as the deletion.

One more property comes from the ops being immutable: an op that arrives before the message it targets — routine on a relay with no mailbox and independent retries — is stored as an orphan with applied == false and re-folded when its target lands, and the pending ops are folded in (opTime, opID) order rather than receipt order. Order-independence again, one layer down.

7. When a tombstone is the wrong tool

There is a class of state that tombstones cannot save, and the way it was handled is instructive.

Calendar events were once synced as memory events. Every device re-derives them from EventKit on a schedule, and the ingester deletes its window and re-inserts with fresh UUIDs each pass. Under insert-if-absent that is a machine for making duplicates: each device mints new ids every cycle, ships them, and receives everyone else's just-deleted rows back. The memory root never converged — a permanent reconcile storm.

A tombstone does not fix that. The identifiers being buried are regenerated with new values on every pass, so the marker set would grow once per ingest cycle and never catch what it was chasing. The problem is not that deletion is hard to express; it is that this state is derived, and derived state that is cheap to recompute has no business in a replicated set at all. So calendar events were excluded from the memory digest outright, and each device owns its own view, with EventKit as the source of truth on each of them.

The rule that generalises: a tombstone is for state whose identity is stable and whose loss is real. For state that any device can regenerate from a local source, the correct move is to keep it out of the shared set.

8. What this does not give you

Four limits, and none of them are small print.

A tombstone is a durable record that something existed. Deleting a conversation leaves a row saying "a conversation with this UUID was deleted, at this time," on every device, permanently. The marker carries no content — body is empty by construction — so what leaks is existence, count, and timing, not substance. It is only reachable by someone who can read a device's decrypted store, since the relay sees ciphertext it cannot attribute. It is still a real property, and it is the direct price of the design: the only way to make an absence travel is to make it a presence, and a presence is a record.

Deletion is invisibility, not erasure — in the memory namespace. As §3's trace showed, a sibling that still holds the buried rows re-ships them and the deleting device re-inserts them, because the applier does not consult the tombstone set. The source anticipates this exactly — a resurrected row stays hidden because the tombstone converges too — so the guarantee on offer is a read-time one, and it is honestly stated. The consequence is still worth naming: the plaintext of a "deleted" agent conversation can persist on disk on every device in the fleet, filtered out of every read. The causal namespaces do not behave this way — applyTombstones genuinely deletes the local row — so how thoroughly a delete removes data currently depends on which namespace you deleted from.

Deleting for everyone is best-effort at the peer. delete:everyone ships an op to a person running their own copy of the software. The fold does the right thing on an honest client, and there is no way to make it do the right thing on a dishonest one. delete:me does not even try — it self-echoes to your siblings only, and the peer keeps its copy, which is the honest version of the same promise.

Tombstones accumulate without bound. Every one of them is retained indefinitely by default, and the retention is not laziness — it is the safe baseline, because a delete cannot resurrect while its tombstone is present. The RowVersion tombstones have exactly one collection path, RowClock.dropAllTombstones, and it runs only as the terminal step of an explicit fleet-wide agreement. Memory tombstone events and deleted message rows have no collection path at all today.

Which sets up the question this article cannot answer. Dropping a tombstone is only safe once every device has provably absorbed the delete — and "provably" is the hard word, because the obvious evidence (a digest that looks caught up, an ack that might be stale) is exactly what resurrects rows. That is The Convergence Barrier and the Cloud Anchor, and it is the hardest problem in this series.

References & further reading