Content addressing
Naming data by the hash of its bytes, so equal things share a name.
01The intuition
The problem it solves
Two libraries each catalogue a book under their own shelf numbers, 312-A in one and 7Q in the other. Nobody can tell from the numbers that the two books are the same. If instead every book were labelled with its ISBN, a number computed from the book itself and the same everywhere, you could tell at a glance that both libraries hold the same edition, and a third library asking "do you have 978-0-14-…?" would get a plain yes.
Data has the same problem. If a chunk, a file or a build artifact is named by where it was put or when, two identical copies get two names and nobody can prove they are the same without comparing every byte. Content addressing names data by a cryptographic hash of its bytes. The name is then the proof: same name, same bytes; different bytes, different name.
Build it one piece at a time
Step 1: hash the bytes. Run the content through SHA-256 and get 32 bytes, written as 64 hex characters. The same input always gives the same output; changing one bit changes the output entirely; nobody can find two different inputs with the same output in practice.
Step 2: use the hash as the key. Store the object under objects/<hash>. A write becomes "compute the hash, check whether the key exists, upload only if not". A read is "fetch by hash, re-hash what arrived, confirm it matches".
| Operation | Location-addressed store | Content-addressed store |
|---|---|---|
| store the same 100 MB twice | two objects, 200 MB | one object, 100 MB; second store is a lookup |
| verify a download | needs a separate checksum | re-hash and compare to the name |
| cache for how long | until it might change | forever; the name can never point at other bytes |
Step 3: build trees of hashes. A directory is a small object listing names and the hashes of its children. Its own hash therefore covers every byte beneath it. A version of a whole project is one 64-character string, and two versions that share most files share most objects. This is exactly how git stores commits, trees and blobs.
Step 4: use it for caching and skipping work. A build system hashes a step's inputs (source files, compiler, flags); if the hash was seen before, the output is fetched from a cache instead of rebuilt. A deployment system hashes the artifact; a machine that already has that hash skips the download.
Step 5: garbage collection. Content-addressed objects are shared, so nothing can be deleted by name alone. Keep roots (the current versions), walk the trees from the roots, and delete objects no root reaches. The state now: a flat store keyed by hash, trees of hashes on top, a sweep that keeps it from growing forever.
Why it works, with the numbers
The hash is big enough that accidental collision can be treated as impossible:
with 2256 possible SHA-256 values, storing 1015 objects gives a collision probability of about 1030 ÷ 2 × 2−256 ≈ 4 × 10−48
Hashing is cheap: a modern core hashes about 1 GB/s, so a 100 MB file costs a tenth of a second, far less than uploading it. The guarantees: equal content gets one name, a name can be verified by anyone holding the bytes, and an object under a name is immutable, so it can be cached and replicated without any invalidation protocol. The failure modes are a hash that leaks (telling an attacker "yes, someone has stored that exact document"), objects that are never collected because some forgotten root keeps them alive, and small objects where a 32-byte name is larger than the content.
The trade-off you must say out loud
You give up human-readable names and mutability: "the latest report" must be a pointer (a tag or a branch) to a hash, and that pointer is the one mutable thing to guard. Say where the pointers live and how they are updated atomically. The interviewer may ask "what about two different files with the same hash?", and the answer is the arithmetic above, said with the confidence it deserves.
Where it shows up in the 100 Google problems
- Design a source control system: blobs, trees and commits named by hash; a branch is a mutable pointer to a commit hash.
- Design a CI system that runs a million tests in ten minutes: the hash of a test's inputs decides whether it runs at all.
- Distribute large ML model files across a serving fleet: machines fetch missing chunks by hash and verify each one on arrival.
- Move 100 petabytes across the US: a manifest of hashes is how you prove every byte arrived intact.
- Design deduplicated multi-tenant file storage: content addressing is the mechanism; the privacy leak above is the deep dive.