Content-addressed storage & deduplication

Twenty-nine terabytes, three of them different

A company's internal registry keeps every image its CI builds: 400 services, built about twice a day each, images kept for six months. The bucket behind it holds 29 TB. When someone finally counts the distinct bytes, they come to under 3 TB. Almost every image starts with the same 180 MB of operating system and language runtime, and the registry stores each image's layers under paths like payments/build-5121/layer-0.tar.gz, so every build writes those 180 MB again under a new name.

The waste comes from who picks the name: the uploader does, so identical bytes get two names and the store cannot tell.

Name the bytes, not the upload

A content address is a name computed from the bytes themselves. Run the layer through a cryptographic hash function such as SHA-256 and use the result, written sha256: followed by 64 hex characters, as its key. That result is the layer's digest. The same 180 MB give the same digest on any machine; change one byte and the digest is unrelated. The blobs still live in an object store (Object storage & blobs explains what one is); only the naming changes, and with it the push:

1. The CI build hashes each layer of the image it has just built.
2. The build asks the registry whether it already holds sha256:4e1f….
3. For the base layers the registry answers yes, and the build skips them.
4. For the new application layer the registry answers no, and the build uploads its 20 MB.
5. The registry hashes what arrived and refuses to store it if the result is not the digest the build claimed.

Each base layer is now written once, however many images list it, and the bucket shrinks towards its distinct bytes. That is deduplication, and it falls out of the naming. Two builds uploading the same new layer at once may both write it, but they write identical bytes under one key, so the race costs a duplicate transfer, not a second copy.

Step 5 gives integrity as well: a reader that hashes what it downloaded and compares it with the name knows whether a disk, a cache or a proxy changed a bit. That differs from the per-part checksums of a resumable upload, which check that a transfer arrived intact (Large file upload covers those): here the hash is the name itself.

Deduplication sees bytes, not meaning. Rebuild the same image from the same source and a layer with identical files can still hash differently, because the archive records file timestamps or was compressed differently; reproducible builds, which pin those and the other inputs that vary, such as file order and ownership, turn the same content into the same bytes.

An object that cannot change under its name

The object behind sha256:4e1f… cannot change and still match its name, and step 5 refuses bytes that do not match. That is immutability, here a consequence of the naming and that check rather than a separate policy, and it makes two things easy. A cache may keep a layer indefinitely without asking whether it is still current, which is how the registry survives 2,000 nodes pulling a new release at once: a CDN in front of the bucket fetches each layer from the origin about once per edge location (CDN & static delivery covers edge caching, and the purge a layer that leaked a key still needs). And a copy in a second region needs no agreement about versions: it either is the object with that name or fails the hash check.

The one name that moves

People deploy payments:1.8.2 or payments:prod, not sha256:4e1f…. An image is described by a manifest, a small JSON document listing the digests of its config and of its layers, in order, and the manifest is itself stored under its own digest. The human names, the tags, are rows in a metadata store, here PostgreSQL: payments:prod points to sha256:c07a…, the manifest's digest. That small table holds the only names whose meaning can change.

It is also where the registry's other incident came from. Twenty payments nodes started from payments:prod in the morning; four more, added under afternoon load, pulled the same tag after a pipeline had pushed a new build to it, and the fleet ran two releases under one name. Every layer was intact; the name had moved. So decide what a tag may do: make tags immutable, refusing a push to an existing one, or let them move and record each move explicitly. Either way, a deploy that pins payments@sha256:c07a… gets the same bytes on every node, because the manifest's digest covers the digest of every layer it lists.

How big a piece to hash

The registry deduplicates whole layers, so one changed config file makes a whole 180 MB layer new; images keep what changes often in the top layers for that reason. A file-sync service stores chunks of each file under their digests instead, and where it cuts matters: with fixed 4 MB chunks, one line inserted near the top shifts every later boundary and every later chunk hashes differently. Content-defined chunking cuts where a rolling hash over the last few dozen bytes matches a pattern, so the boundaries fall back into place shortly after an edit and only the chunks around it are new. That cheap hash only places the cuts; each chunk is still named by its cryptographic digest.

Who still points at this layer?

Deleting the tag payments:1.2.0 cannot delete its layers, since its base layers appear in thousands of other manifests. It removes a pointer; the blobs go later, through garbage collection. The usual form is mark and sweep: mark every manifest reachable from a tag, plus every digest a running deployment has pinned (the deploy system must record those as roots), mark every blob those manifests list, then delete the blobs nothing marked. A reference count per blob is the alternative, but a count that drifts from the manifests deletes a live layer. The sweep has a race of its own:

1. A build uploads a new layer, sha256:9b70…, which no manifest names yet.
2. Garbage collection marks from every tag and finds nothing that references 9b70….
3. The build pushes its manifest, which lists 9b70….
4. Garbage collection deletes 9b70….

Every node deploying the new image now gets a 404 for its last layer. The defence is a grace period: delete only blobs that are unreferenced and that nothing has vouched for recently, say in the last day, comfortably longer than a build takes from first upload to manifest. The clock restarts whenever the registry confirms a blob to a client, because an old orphan a build was just told to skip is about to be referenced again. The registry should also refuse a manifest that lists a blob it does not hold, so a blob deleted before its manifest arrives fails the push, not a deploy. The grace period makes the race rare, not impossible: a blob confirmed after the sweep checked it but before the delete still goes. Registries that must close that window refuse pushes while they collect, or re-check each blob under a lock that pushes also take.

What the digest does not promise

The whole design treats equal digests as equal bytes, which holds because the hash is collision-resistant: for SHA-256 nobody has found two inputs with the same digest, and finding one is believed computationally infeasible. Infeasible is not impossible, and MD5 and SHA-1 have both fallen to practical collisions, so someone who crafts a colliding pair can make a store keyed on either serve one file under the other's name.

Deduplicating across customers leaks, too: an upload that completes without sending its bytes tells the uploader someone already stored exactly that file, so some services deduplicate only within one account, and per-user encryption keys end cross-user deduplication anyway, since one file under two keys is two byte strings. And a chunk that many users share cannot simply be deleted when one of them asks to be forgotten: erasing that user removes the manifests that list it, and the chunk goes only when garbage collection finds nothing else referencing it. Deleting a person's data: erasure across every copy covers the rest of an erasure.

One upload for two builds

The Container & Package Registry Challenge asks for this registry: identical layers uploaded and kept once, tags that change only explicitly, garbage collection that spares running deploys, and pulls that survive a fleet-wide rollout. Your design should show three things. Two builds of different services reach the same base-layer digest one after the other, and only the first uploads it. The metadata store says whether a tag may move. And the collection rule, with its roots and grace period, is written beside the layer storage, since a simulated run cannot watch a sweep go wrong. File Storage & Sync asks for the same with chunks instead of layers.