What deletion actually means in a distributed system

Deleting a file returns a status code. It does not return evidence. The distance between those two things is the whole subject of this article, and it is wider than most architectures assume.

What actually happens when you delete an object

You issue a delete against an object store. You get back a success response. From the application's perspective the object is gone: subsequent reads return not-found, listings omit it, the accounting stops.

Underneath, a sequence of things is now in progress rather than complete.

The object was replicated. Depending on the storage class and the provider, there are copies in two or three physical locations, and the delete has to reach each of them. Providers make durability guarantees about writes propagating; the guarantees about deletes propagating are generally weaker and less precisely worded.

The object was snapshotted. Volume or bucket snapshots run on their own schedule and have their own lifecycle. A snapshot taken before the delete still contains the object, and it will continue to contain it until that snapshot ages out under a policy that was probably configured by someone else for a different reason.

The object was backed up. Backup retention very frequently outlives the retention of the thing being backed up, which is an irony worth sitting with: the mechanism protecting you against data loss is the mechanism keeping the data you were obliged to lose.

There are write-ahead logs, transaction logs, and replication streams, each of which may hold the content or a recoverable representation of it for some window.

And there is provider-side tiering. An object that has not been read in a long while may have been transparently migrated to a colder storage class, in a different physical medium, possibly in a different facility. The delete has to find it there too.

None of this is a criticism of object storage. Every one of these mechanisms exists for a good reason and the alternative is worse. The point is narrower: the delete is an instruction that enters a system whose internal state you cannot observe, and you receive your acknowledgement long before the physical situation resolves.

Why the acknowledgement is not evidence

When a regulator, an auditor, or a data subject asks whether a document is gone, the available answer in most architectures is: we called the delete endpoint and it returned success.

That sentence describes your intent. It does not establish an outcome, and the difference matters to exactly the audience asking.

To see why, consider what the claim rests on. It rests on the storage provider's deletion behaving as documented, on every replica having been reached, on no snapshot or backup retaining a copy, and on no internal process having made one you did not know about. Every one of those is a proposition about a third party's system, taken on trust, and none of them is something you can demonstrate to somebody who does not already believe you.

You can improve your position with contracts and attestations. What you cannot do is convert the provider says so into therefore it is so, which is the conversion the question is actually asking for.

The alternative: make the data depend on something you can destroy

The way out is well established and older than most of the companies currently selling around this problem. Rather than trying to chase bytes across an opaque distributed system, you arrange for the bytes to be meaningless without a key, and then you destroy the key.

The technique is usually called crypto-shredding, and its logic is simple once stated. Encryption transforms data into a form that is computationally infeasible to recover without the corresponding key. If the key ceases to exist, every copy of the ciphertext — in every replica, every snapshot, every backup nobody remembers taking, every cold tier the provider migrated it to — becomes indistinguishable from random noise, permanently and simultaneously.

You have not chased anything. You have changed the status of everything at once by removing one small object.

Why the key has to be per document

The property only holds if the granularity is right, and this is where implementations diverge in quality.

A single master key encrypting the whole archive gives you nothing useful. Destroying it destroys everything, which is not a deletion mechanism but a demolition mechanism. A key per customer is better and still wrong: it means one data subject's erasure and another's retention obligation contend for the same key, and the contention has no good resolution.

The granularity has to match the unit of the obligation. For us that unit is the deposit — one sealed document, one retention regime, one lifecycle. So each deposit gets its own data encryption key, generated at the moment of storage and never shared with another deposit.

That means a lot of keys. It is the reason the key store matters as much as it does, and it is the reason the design is more involved than encrypt the bucket.

Where the key lives, and why that is the whole design

A key held in the same database as the metadata, or in a config file, or in an environment variable, does not give you the property you are after. If the key can be copied, then destroying the copy you know about does not establish that no copy exists.

So the key material lives in a hardware-backed key store, built so that the key cannot be extracted — including by the operator running it. Operations are performed by asking the store to act, not by retrieving material and acting locally. When the deposit is forgotten, the instruction is to destroy the key inside that boundary.

This is the step that makes destruction provable rather than asserted. The claim is no longer the storage provider deleted the object, which you cannot verify. It is the key material was destroyed inside a device designed to make extraction infeasible, which is a much smaller claim about a much smaller object, made against a boundary specifically constructed to support it.

The cost of that property deserves stating plainly, because it is real. A key store that cannot be read from also cannot help you recover from a mistake. Destruction is not reversible, and an accidental destruction is unrecoverable by anyone, including us. That is a property to design guardrails around, not a footnote.

What the operation should produce

A status code is the wrong output for an irreversible operation with legal weight. What forgetting produces at our end is a certificate: a signed record naming the deposit by its content hash, the regime it was held under, the date, and the reason it was forgotten. Human-readable for whoever has to read it, machine-parseable for whoever has to file it.

The original content hash stays in our records after the content is gone. This is worth explaining because it looks like a contradiction. The hash is not the document and nothing about the document can be reconstructed from it. What it lets us do is answer a later question — did a deposit with this fingerprint exist, and what happened to it — without holding anything we were obliged to destroy. Keeping the hash is what makes the certificate mean anything.

Where this is genuinely contested

One thing should be said clearly rather than glossed, because the audience for this article includes people who will know if it is glossed.

Whether key destruction constitutes erasure, as a legal matter, is not settled. Supervisory authority views differ, the analysis varies by jurisdiction and by context, and anyone who tells you the question is closed is overselling. What can be said is that crypto-shredding is a strong technical measure with a well-understood security argument, and that a signed certificate recording precisely what was done is more useful to a controller than a log line saying a delete call succeeded.

We claim the technical property. We do not claim the legal conclusion, and the certificate exists so that the party who does have to make that argument has something concrete to make it with.