How to Delete Data From an Immutable Backup

Here is a contradiction that shows up in almost every architecture review with a privacy component.

The right to erasure assumes data can be removed on request. Modern data architecture is built on the opposite assumption. Append-only event logs. Immutable object storage with object-lock enabled. Replicated backups across regions. Warehouse snapshots retained for year-over-year analysis. Derived models that encode information about individuals without storing a row.

Deleting a user row from Postgres takes one statement. Deleting that user from the system takes an architecture decision you probably made three years ago without knowing it.

Three patterns actually work. They are not equivalent, and the cost of picking one is almost entirely a function of when you pick it.

Pattern 1: Crypto-shredding

Encrypt every subject's personal data under a key unique to that subject. Store keys in a KMS. On erasure, destroy the key.

Every copy of the ciphertext — the primary database, last quarter's backup, the object-locked archive, the warehouse snapshot nobody remembers creating — becomes permanently unreadable. You did not delete the data. You deleted the ability of anyone, including you, to read it, which is functionally equivalent and vastly easier to prove.

What it actually requires:

• A per-subject key hierarchy. Typically a per-subject data key wrapped by a rotating master key, so key rotation does not mean re-encrypting everything.
• Envelope encryption at the field or record level, not full-disk. Disk encryption gives you nothing here — one key protecting everything means erasing one subject erases all of them.
• A key-destruction audit trail. The destruction event is your evidence of erasure, so it must be immutable and timestamped.
• Query planning that survives encryption. This is the real cost: you can no longer filter or join on encrypted fields. Deterministic encryption for equality lookups helps and leaks frequency information; blind indexes are usually the better tradeoff.

Adopt early or regret it. Greenfield, this is a week of design and mostly ordinary work. Retrofitted onto a system with ten years of plaintext personal data across forty tables, it is a multi-quarter migration where the hard part is not encryption but finding every field that needs it.

Pattern 2: Tombstone-and-compact

For event streams, deletion is a write, not a removal.

Publish a tombstone — a null-payload record keyed to the subject — and let a compaction process physically remove prior records for that key on a defined cycle.

Kafka's log compaction does exactly this natively. The failure mode is entirely operational:

• Compaction is not immediate. There is a window between the tombstone and physical removal, and your retention documentation needs to state it honestly rather than imply instant deletion.
• Every downstream consumer must handle tombstones correctly. A consumer that ignores null payloads and keeps its own materialised view has silently defeated the whole mechanism. This is worth an integration test per consumer.
• Topics without a compacted cleanup policy will not compact. Someone will create one. Enforce the policy in your topic provisioning code, not in a wiki page.

Tombstoning composes well with crypto-shredding. Shred the key for correctness and immediate unreadability; tombstone-and-compact for actual space reclamation and to keep the streams honest.

Pattern 3: Reference indirection

Keep personal data in exactly one deletable store. Everywhere else — events, logs, warehouse, caches, search indices — holds only an opaque subject identifier.

Erasure becomes a single operation in a single place. Every other system keeps referring to a subject ID that no longer resolves to anything, which is usually fine: your analytics still count the event, it just cannot be tied back to a person.

This is architecturally the cleanest option and the one with the largest ongoing tax. Every read path that needs personal data becomes a join or a service call. Latency goes up. You will be tempted to denormalise "just this one field" into the event payload, and the moment someone does, the guarantee is gone.

The mitigation is enforcement rather than discipline: schema validation in CI that rejects event definitions containing personal-data-typed fields. Make the wrong thing fail the build, because it will not fail review reliably.

Picking one

Rough decision rule:

• Greenfield? Crypto-shredding plus reference indirection. The combination is cheap now and eliminates most of the cost of every other privacy capability later.
• Existing system, event-stream heavy? Tombstone-and-compact first, since it delivers immediate improvement, then reference indirection for new event types.
• Existing system, monolith and warehouse? Reference indirection for new writes, crypto-shredding scoped to the highest-risk fields. A full retrofit is rarely worth it; a targeted one usually is.

The model layer, honestly

None of these patterns cover trained models. If a model was trained on a subject's data, deleting the source record does not remove their influence on the weights. Machine unlearning research exists; production-grade machine unlearning largely does not.

The currently defensible position is documented retraining cadences plus exclusion lists, stated plainly in your impact assessment. Do not claim erasure from model weights. Regulators are increasingly informed on this point, and a claim you cannot substantiate is worse than a limitation you disclosed.

Deletion as a tested contract

Whichever pattern you choose, make deletion a first-class API on every service that stores personal data, and test it in CI like any other contract.

A service that cannot delete becomes permanent compliance debt, and you want to discover that at merge time rather than during a rights request with a statutory deadline attached.

The wider engineering context — discovery, consent enforcement, rights-request pipelines, generated registers, and where this sits in a full stack — is in the complete guide: GDPR Software in 2026: A CTO's Build vs Buy Playbook.

We build this as part of custom software development work, usually alongside the cloud architecture decisions that constrain which pattern is even available.

Frequently Asked Questions

What is crypto-shredding?

Storing personal data encrypted under a key unique to each data subject, then destroying that key on an erasure request. Every copy of the ciphertext — including immutable backups and object-locked archives — becomes permanently unreadable without deleting or rewriting the copies themselves.

Does full-disk encryption satisfy the right to erasure?

No. One key protecting everything means you cannot erase a single subject without destroying access to all data. Crypto-shredding requires per-subject keys with envelope encryption at field or record level.

How do you delete from a Kafka topic?

Publish a tombstone — a null-payload record with the subject's key — on a topic configured for log compaction. Compaction physically removes earlier records for that key on its cycle. Verify that every downstream consumer honours tombstones, since a consumer maintaining its own materialised view will otherwise retain the data.

Can you delete personal data from a trained machine learning model?

Not reliably in production today. Deleting the source record does not remove its influence on the weights. The defensible approach is documented retraining cadences plus exclusion lists, disclosed as a limitation in your impact assessment rather than claimed as erasure.

What is the performance cost of encrypting personal data per subject?

The encryption itself is negligible; the query cost is not. You cannot filter or join on encrypted fields directly. Deterministic encryption enables equality lookups but leaks frequency information; blind indexes are usually the better tradeoff. Budget for query redesign, not for CPU.

Should deletion be tested in CI?

Yes. Treat deletion as a contract on every service that stores personal data and test it like any other API contract. Services that cannot delete become permanent compliance debt, and merge time is a much cheaper moment to discover that than a rights request with a statutory deadline.