Duplicate File Detection at Scale

0) Problem Restatement

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.

1) Requirements

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.

2) 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.

1. Walk the tree and collect (path, size, inode, mtime). Metadata only, no content reads.
2. Group by size. A file with a unique size has no duplicate, so drop it. This alone removes most files.
3. Skip hard links: the same inode means the same file, not a copy.
4. 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.
5. For the remaining candidates, compute a full hash (SHA-256, or the faster BLAKE3). Files with the same full hash are duplicates.
6. (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.

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 groups

3) Scaling to Many Machines

Think of it as a MapReduce-style job with three rounds:

1. Scan: many workers walk different parts of the namespace (split by folder or bucket prefix) and emit (size, path).
2. Shuffle by size: all files of the same size go to the same reducer. Unique sizes are dropped.
3. Hash: for candidate groups, the workers closest to the data (same storage node) compute partial and then full hashes, and emit (hash, path).
4. Shuffle by hash → duplicate groups.

Processing data where it lives avoids sending petabytes over the network. Only small hashes travel.

4) Deep Dive A — Find the bottleneck by measuring

Before optimizing, measure where time goes:

• Metadata walk slow? Too many small stat calls, so parallelize by directory and use bulk listing APIs (e.g., S3 inventory reports instead of listing).
• Disk I/O bound (the hash rate equals disk throughput)? Read sequentially with big buffers, avoid reading the same disk from many threads at once (spinning disks hate seeks), and use more disks or machines.
• CPU bound (disks idle while hashing)? Use a faster hash (BLAKE3/xxHash for the first round), and hash multiple files in parallel.
• Network bound? Move the computation to the data.

5) Deep Dive B — Correctness and incremental runs

• Files changing during the scan: record size + mtime at 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).

6) Trade-offs & Alternatives

7) Common Follow-up Questions

• "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.

8) Wrap-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.