Problem RestatementProblem
Find all files with identical content in a huge file system or storage fleet: billions of files and petabytes of data. Return groups of duplicates so they can be removed or deduplicated. File names don't matter. Two files are duplicates only if their bytes are the same.
Anthropic asked this with a focus on measuring and fixing bottlenecks as it scales, and OpenAI asked about efficient I/O and correctness.
RequirementsRequirements
1.1 Functional
- Input: one or more root folders (or a list of storage buckets).
- Output: groups of paths with identical content.
- Optional: re-run incrementally, only checking changed files.
1.2 Non-Functional
- Correct: never report two different files as duplicates.
- Efficient: avoid reading every byte of every file when we don't need to.
- Scalable: work across many machines.
- Robust to files that change or disappear during the scan.
1.3 Scale Estimates
- 1 billion files, 2 PB total.
- Reading everything at 500 MB/s per disk would take years on one disk. We must avoid reading data where possible and parallelize the rest.
The Cheap-First Pipeline (single machine first)
The key insight: most files can't be duplicates of each other, and we can prove that cheaply.
- Walk the tree and collect
(path, size, inode, mtime). Metadata only, no content reads. - Group by size. A file with a unique size has no duplicate, so drop it. This alone removes most files.
- Skip hard links: the same inode means the same file, not a copy.
- For each size group, compute a partial hash of the first 4 KB (plus maybe the last 4 KB). Split the groups by that hash, and drop files that become unique.
- For the remaining candidates, compute a full hash (SHA-256, or the faster BLAKE3). Files with the same full hash are duplicates.
- (Optional, for absolute certainty) Compare bytes of files with equal hashes. With SHA-256, a random collision is practically impossible, so most systems skip this.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
W["Walk metadata - path, size, inode"] --> S["Group by size - drop unique"]
S --> P["Partial hash - first and last 4 KB"]
P --> F["Full hash - SHA-256 / BLAKE3"]
F --> G["Duplicate groups"]
G --> A["Report / dedup / hard link"]from collections import defaultdict
import hashlib, os
def find_duplicates(paths):
by_size = defaultdict(list)
for p in paths:
by_size[os.path.getsize(p)].append(p)
groups = []
for size, files in by_size.items():
if len(files) < 2: continue
by_head = defaultdict(list)
for p in files:
with open(p, 'rb') as f: by_head[f.read(4096)].append(p)
for cands in by_head.values():
if len(cands) < 2: continue
by_full = defaultdict(list)
for p in cands:
h = hashlib.sha256()
with open(p, 'rb') as f:
for chunk in iter(lambda: f.read(1 << 20), b''): h.update(chunk)
by_full[h.hexdigest()].append(p)
groups += [g for g in by_full.values() if len(g) > 1]
return groupsScaling to Many Machines
Think of it as a MapReduce-style job with three rounds:
- Scan: many workers walk different parts of the namespace (split by folder or bucket prefix) and emit
(size, path). - Shuffle by size: all files of the same size go to the same reducer. Unique sizes are dropped.
- Hash: for candidate groups, the workers closest to the data (same storage node) compute partial and then full hashes, and emit
(hash, path). - Shuffle by hash → duplicate groups.
Processing data where it lives avoids sending petabytes over the network. Only small hashes travel.
Deep Dive A — Comparing a billion files without reading them allDeep dive
Two files are duplicates only if their bytes match. The obvious ways to establish that all involve reading petabytes, and the design is mostly about avoiding that.
Compare every pair
For each pair of files, compare byte by byte.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
N["1 billion files"] --> P["About 5 x 10^17 pairs"]
P --> IO["Each pair re-reads both files"]
IO --> NEVER["Never finishes - the arithmetic is the answer"]Quadratic in the number of files, and every comparison re-reads data. This rung is worth ten seconds in an interview purely to make the next one obviously necessary.
Hash every file and group by hash
Read each file once, compute a strong hash, group files that share one. Linear in the data instead of quadratic in the pairs.
The cost is now exactly one full read of the entire corpus — petabytes through the disks and the hash function, every run. That is hours to days of I/O, and the great majority of it is wasted: most files have a size no other file shares, so they could never have been duplicates and their bytes never needed reading.
Eliminate by cheap signals first, then hash what is left
Three passes, each one only touching what survived the last:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
ALL["1 billion files"] --> SZ["Group by size - metadata only, no reads"]
SZ --> UNIQ["Unique size - cannot be a duplicate, dropped"]
SZ --> SAME["Same size - a small fraction"]
SAME --> HEAD["Hash the first 4 KB"]
HEAD --> DIFF["Different prefix - dropped"]
HEAD --> CAND["Same prefix - candidates"]
CAND --> FULL["Full strong hash, then byte compare inside a group"]
FULL --> DUP["Duplicate groups"]- Size first. It comes from the metadata walk — no file contents read at all — and it removes the overwhelming majority of files, because sharing an exact byte count is already rare.
- A prefix hash next. Reading 4 KB costs about one disk seek, versus reading a whole file. Files that differ at all usually differ early; this clears most of the remaining candidates for almost nothing.
- Full hash only for survivors, then an actual byte comparison within each group. Use a fast hash (BLAKE3, xxHash) for the earlier rounds and a strong one at the end — and do the byte compare, because grouping people's files by a hash collision is a data-loss bug, not a statistical curiosity.
Then measure which stage is actually the limit before optimising further. If the metadata walk dominates, parallelise by directory and use bulk listing (an S3 inventory report instead of a listing crawl). If disk I/O dominates, read sequentially with large buffers and avoid many threads seeking on one spindle. If CPU dominates, the disks are idle and a faster hash is the fix. Report throughput per stage — files/sec and MB/s — so the next change targets the real bottleneck rather than the one you assumed.
Deep Dive B — Correctness and incremental runsDeep dive
- Files changing during the scan: record
size + mtimeat scan time, and re-check them before and after hashing. If they changed, re-hash or skip, and mark as unstable. - Incremental re-scan: keep a cache
(path, inode, size, mtime) → hash. Next time, only re-hash files whose metadata changed. - Safe action on duplicates: never delete automatically without a policy. Options: report only, replace with hard links (same file system), or deduplicate in a content-addressed store with reference counts (see the object storage design).
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Filtering | Size → partial hash → full hash | Reads a small fraction of data | Full hash every file: huge I/O |
| Hash | SHA-256/BLAKE3 for the final step | Collisions practically impossible | MD5: faster but broken for adversarial data |
| Distribution | Shuffle by size, then by hash | Only candidates get compared | Compare all pairs: impossible |
| Placement | Hash where the data lives | Avoids network transfer | Central hashing: network bottleneck |
Common Follow-up QuestionsFollow-ups
- "Near-duplicates (same photo, different compression)?" Use perceptual hashes or embeddings and similarity search instead of exact hashes.
- "Chunk-level duplicates inside large files?" Split files into content-defined chunks (rolling hash) and deduplicate chunks, as backup systems do.
- "Memory for billions of entries?" Stream and sort to disk (external sort by size, then by hash) instead of holding everything in hash maps.
Wrap-UpWrap-up
Walk metadata only, group by size, then split groups by a cheap partial hash and finally a strong full hash, so only real candidates are ever fully read. Scale it as scan → shuffle by size → hash near the data → shuffle by hash. Measure each stage to find whether disk, CPU, metadata or network is the limit, re-check files that changed, and cache hashes for incremental runs.