A file storage platform must permanently delete a user's data on request, while maintaining backups, replicas, caches and search indexes. What makes this genuinely difficult, and how is it designed?

Why deletion is hard

Deleting the primary record is trivial. The difficulty is everywhere the data also exists, each with a different deletion story:

• Replicas — eventually consistent; a delete propagating during a partition may be lost.
• Backups and snapshots — immutable by design, retained for months, and often the whole point of a backup is that it cannot be modified.
• Caches and CDNs — copies with independent lifetimes at many locations.
• Search indexes — separate stores updated asynchronously, which may fail silently.
• Derived data — thumbnails, previews, extracted text, embeddings, analytics aggregates.
• Logs and telemetry — often containing identifiers, retained by a separate policy.
• Deduplicated blocks shared with other users, which must not be deleted at all.

That last one is the deepest problem in a deduplicating store: the user's file may be one reference to a block that other users also reference. Deleting the block would corrupt their data.

The design

1. Reference-counted content, deleted by reference not by content. Removing a user's file decrements references on its blocks; blocks are collected only at zero. The user's access ends immediately, which is what the request is about; physical reclamation follows garbage collection.

2. Crypto-shredding for the backup problem. Encrypt each user's data with a per-user key held in a key store. Deleting the key renders every copy — replicas, backups, snapshots, offline media — permanently unreadable, without modifying immutable backups. This is the standard resolution of the otherwise irreconcilable conflict between "delete on request" and "backups are immutable", and it is worth knowing as the canonical answer.

3. A deletion orchestrator with a durable manifest. Deletion is a distributed workflow: mark inaccessible immediately, then fan out to each store with retries, tracking completion per target. It must be resumable, auditable, and able to answer "is this deletion complete, and if not, which store is outstanding?"

4. Immediate inaccessibility, eventual erasure. Access is revoked synchronously; physical removal is asynchronous with a stated maximum. This is both what regulation generally expects and what is physically achievable — and it should be stated in the policy rather than implied.

5. Tombstones with retention. A delete must beat a concurrent write or a delayed replica resurrecting the data. Tombstones retained longer than the maximum replication lag prevent the classic zombie-record failure.

6. Verification, not assumption. A periodic job that samples deleted identifiers and checks every store for their absence. Deletion is a compliance claim; unverified claims are how organisations end up making false statements to regulators.

The failure modes

• The forgotten store. A derived dataset, an analytics warehouse, a vendor integration. Every new store must be registered with the deletion orchestrator, which requires it to be a platform requirement rather than a checklist.
• Backups restored after a deletion, resurrecting data — which crypto-shredding prevents and reference deletion does not.
• Silent partial failure, where three of five stores confirm and nobody notices.
• Deduplication leaking existence. If uploading a file that already exists is measurably faster, that is an information leak about other users' content, independent of deletion.

The lesson

Deletion is not an operation; it is a distributed workflow with a compliance obligation and a verification requirement. Systems that treat it as a DELETE statement discover the gap during an audit, which is the most expensive possible time.