Deletion Propagation

Deleting a record from the operational database is the smallest part of the work. The data also exists in search indexes, caches, analytics stores, warehouse copies, machine learning training sets, partner exports, event logs and backups.

Deletion propagation is the mechanism that reaches all of them, and it is what makes an erasure obligation provably satisfied rather than optimistically assumed.

Why it is a distributed state change

Each copy is a separate system with its own owner, deletion capability and latency. Some can delete a record directly; some can only rebuild from source; some — immutable event logs and backups — cannot delete at all without a different technique.

That makes deletion an asynchronous fanout requiring the same properties as any distributed operation: idempotency, retry, acknowledgement and a way to see what has not completed.

Implementation patterns

• A deletion event on a durable stream, consumed by every downstream store, so the fanout is explicit rather than implicit in a script.
• Acknowledgement per consumer, so completion is provable. Without it, the answer to "has this subject's data been erased" is a belief.
• Idempotent handling, since a deletion event will be redelivered and a second deletion must be harmless.
• Tombstones rather than hard deletes where references exist, preserving referential structure while removing content — a reply to a deleted post still needs somewhere to point.
• [[crypto-shredding]] for immutable stores and backups, destroying the per-subject key so the ciphertext is unrecoverable without editing the archive.
• Legal hold evaluated as a blocking pre-check, because a hold arriving after deletion is unrecoverable.
• A maintained inventory of every copy, which almost never exists and is the reason erasure programmes overrun their estimates by large multiples.

Industry example

Platforms implementing content deletion at scale consistently find the same surprises: aggregates stop reproducing from retained data, so historical figures and recomputed figures permanently disagree; downstream readers were never written to handle a missing referent and fail in unexpected ways; and a restored backup resurrects data that was deleted months earlier.

The lesson that generalises is that deletion capability is an architectural property that must be designed in early. Retrofitting it after copies have proliferated across an estate is a multi-year programme, and the inventory step alone routinely takes longer than the engineering.

Failure scenarios

• Primary-only deletion, leaving the data in every derived store.
• No acknowledgement, so completion cannot be evidenced to a regulator or an auditor.
• Hard deletes where references exist, breaking readers that assumed presence.
• Backups untreated, so a restore undoes the erasure.
• No copy inventory, so the propagation reaches the systems someone remembered.
• Deletion racing with ingestion, where a pipeline in flight re-creates the record after erasure — which needs a suppression list, not just a delete.

Trade-offs

Full propagation is expensive to build and operate, and tombstones plus suppression lists mean retaining some record of a subject in order to prove they were removed — which is uncomfortable and generally accepted as necessary.

The scoping judgement is which copies genuinely require record-level deletion and which can rely on crypto-shredding or bounded retention. Short retention on derived stores is frequently cheaper than building deletion into them, and it removes the obligation rather than satisfying it repeatedly.

Interview question

"A user exercises their right to erasure. Walk me through every place their data exists and how each one is handled — including the ones you cannot delete from."