Deduplicate files by size then content hash

Clarify first. Return what, exactly? Here: a list of groups, each a sorted list of two or more paths whose bytes are identical, groups sorted by their first path. Follow symlinks? No: a symlink is skipped, otherwise a link to a directory can loop and a link to a file is reported as its own duplicate. Empty files? They are all identical; report them as one group (and say so, because some interviewers want them excluded). Can files change while we scan? Assume no, then come back to it in follow-ups.

Why size first. Two files with different sizes cannot be equal, and stat is nearly free compared with reading the file: one metadata lookup versus reading every byte. On a typical disk most sizes are unique, so most files are never opened at all.

The funnel, cheapest filter first.

1. Walk and group by size. os.walk plus os.lstat per file. Drop every size bucket with one file.
2. Group by a hash of the first 4 KB. Files of the same size often differ early (headers, timestamps). Reading 4 KB is one disk read. Drop singleton buckets again.
3. Group by a hash of the whole file, read in 1 MB chunks so memory stays flat for a 50 GB file. What is left with two or more members are the duplicates.

Hash choice. Use SHA-256 or BLAKE2b. The point is collision resistance: with a 256-bit hash, the chance that two different files collide is around 2⁻¹²⁸ even across billions of files, far below the chance of a disk error. MD5 is fine against accidents but a crafted pair can collide, which matters if users upload the files. A byte-for-byte compare after the hash removes any doubt, at the cost of a second read; offer it as an option.

Numbers worth saying out loud. 1M files, 2 TB total, on a disk that reads 500 MB/s:

• Hashing everything: 2 TB / 500 MB/s = 4,000 s, about 67 minutes, I/O-bound.
• Size-first: say 5% of bytes sit in size-colliding buckets. Phase 2 reads 4 KB from those files (fast). Phase 3 reads maybe 50 GB: 100 s.
• The CPU side: SHA-256 runs at roughly 500 MB/s to 1 GB/s per core, so on one core hashing and reading are about the same speed. Phase 3 benefits from a few worker threads (the hash functions in hashlib release the GIL on large buffers).

Hard links. Two paths with the same (st_dev, st_ino) are the same file. Read it once and reuse the digest.

import hashlib
import os
import stat
from collections import defaultdict

CHUNK = 1 << 20  # 1 MB reads keep memory flat for huge files
HEAD = 4096


def _digest(path, limit=None):
    h = hashlib.blake2b(digest_size=32)
    remaining = limit
    with open(path, "rb") as f:
        while remaining is None or remaining > 0:
            size = CHUNK if remaining is None else min(CHUNK, remaining)
            block = f.read(size)
            if not block:
                break
            h.update(block)
            if remaining is not None:
                remaining -= len(block)
    return h.hexdigest()


def _files(root):
    """(path, size, inode key) for every regular file; symlinks skipped."""
    for dirpath, dirnames, filenames in os.walk(root):
        dirnames.sort()
        for name in filenames:
            path = os.path.join(dirpath, name)
            try:
                st = os.lstat(path)
            except OSError:
                continue  # vanished or unreadable
            if stat.S_ISREG(st.st_mode):
                yield path, st.st_size, (st.st_dev, st.st_ino)


def _split(groups, key_fn):
    """Refine each group by key_fn; keep only buckets with 2+ members."""
    out = []
    for group in groups:
        buckets = defaultdict(list)
        for item in group:
            try:
                buckets[key_fn(item)].append(item)
            except OSError:
                pass  # unreadable now: cannot prove it is a duplicate
        out.extend(b for b in buckets.values() if len(b) > 1)
    return out


def find_duplicates(root):
    by_size = defaultdict(list)
    for path, size, inode in _files(root):
        by_size[size].append((path, size, inode))
    groups = [g for g in by_size.values() if len(g) > 1]

    cache = {}  # (inode, limit) -> digest, so hard links are read once

    def hashed(limit):
        def key(item):
            path, size, inode = item
            if size <= HEAD and limit is None:
                limit_used = HEAD  # the head hash already covered the whole file
            else:
                limit_used = limit
            k = (inode, limit_used)
            if k not in cache:
                cache[k] = _digest(path, limit_used)
            return cache[k]
        return key

    groups = _split(groups, hashed(HEAD))
    groups = _split(groups, hashed(None))
    result = [sorted(path for path, _, _ in g) for g in groups]
    return sorted(result)

Small files (at most 4 KB) are fully covered by the head hash, so phase 3 reuses that digest instead of reading them again.

Let N be the number of files and B the bytes in files whose size collides with another file's.

• Time: O(N) stat calls, plus O(B) bytes read and hashed in the worst case. Files with a unique size are never opened.
• Space: O(N) for the size buckets and digests. File contents are never held in memory beyond one 1 MB chunk.
• Wall clock is I/O-bound: disk throughput for phase 3, and metadata latency (seek per stat) for phase 1 on spinning disks or network filesystems.

1. Billions of files across many machines. Make it a two-stage map-reduce. Stage 1 emits (size, path) and keeps sizes with two or more paths. Stage 2 hashes only those, reading the file on the machine that holds it, and groups by (size, digest). Only digests cross the network, never file contents.
2. Files change during the scan. Record (size, mtime) at stat time and again after hashing. If either changed, rehash or mark the file as unstable. For a live system, hash on write instead (content-addressed storage) so dedupe is a lookup.
3. Incremental re-runs. Cache (path, size, mtime, inode) -> digest in SQLite. The next run only rehashes files whose metadata changed.
4. Similar, not identical. Content-defined chunking (rolling hash such as Rabin or FastCDC) splits files at content boundaries, so an insertion near the start shifts only one chunk. Shared chunks then measure overlap. For text or images, MinHash or perceptual hashes find near-duplicates.
5. Parallelism. Phase 3 is I/O-bound on one disk and gains little past 2–4 threads on an SSD. On a network filesystem with high latency, 16–64 threads help. Processes are not needed, because hashlib releases the GIL while hashing large buffers.

Mid-level (L4)

• Walks the tree, groups by size, then hashes, and returns only groups of two or more.
• Reads files in chunks rather than whole into memory.
• Handles empty directories and unreadable files without crashing.

Senior (L5)

• Adds the partial-hash stage and explains each stage as the cheapest filter that removes candidates.
• Picks a hash with a reason (collision resistance versus speed) and quantifies the I/O cost.
• Thinks about symlinks, hard links and files that change mid-scan.

Staff (L6+)

• Sizes the job (bytes read, disk throughput, CPU hash rate) and says which resource is the bottleneck.
• Scales it out as a two-stage map-reduce that moves digests, not data, and adds an incremental cache.
• Extends to near-duplicate detection with content-defined chunking or MinHash and explains when it is worth it.