DevOps NetworkDevOpsNetwork
Join Free
Practical infra coding

Find duplicate files by content

mediumFiles and filesystem Must-do

Problem statement

A shared backup volume has collected copies of the same files under different names. Find every group of files with identical content, and report how many bytes could be reclaimed by keeping one copy of each. Largest waste first; paths inside a group sorted.

  • Compare content, not names. Files with the same size and different bytes are not duplicates.
  • Skip empty files, since every empty file trivially matches every other, and report how many you skipped.
  • Some files are tens of GB, so never read a whole file into memory, and avoid reading files that cannot possibly match.
  • Do not follow symlinks.

Sample tree

TEXT
photos/a.jpg 5000 bytes of "A"
photos/b.jpg 5000 bytes of "B"
backup/a-copy.jpg 5000 bytes of "A"
backup/old/a.jpg 5000 bytes of "A"
configs/app.yaml "replicas: 3\n" (12 bytes)
configs/app.yaml.bak "replicas: 3\n" (12 bytes)
configs/db.yaml "replicas: 1\n" (12 bytes)
tmp/empty1.txt empty
tmp/empty2.txt empty

Examples

Example 1

Input: `python solution.py` (the demo builds the tree above in a temporary directory)

Output: 3 copies, 5000 bytes each, 10000 bytes wasted: backup/a-copy.jpg backup/old/a.jpg photos/a.jpg 2 copies, 12 bytes each, 12 bytes wasted: configs/app.yaml configs/app.yaml.bak skipped 2 empty file(s)

Explanation: photos/b.jpg has the same size as the A files but different bytes. configs/db.yaml has the same size as app.yaml but different content. Neither is a duplicate.

Hints

Approach

Filter from cheapest to most expensive, and only pay for the next stage when the previous one leaves more than one candidate.

  1. Size. Walk with os.lstat, keep regular non-empty files, and group paths by st_size. Groups of one are dropped without opening anything.
  2. Partial hash. For each same-size group, hash the first 4 KiB. group_by drops groups that are left with one member.
  3. Full hash. Hash the remaining candidates completely, 1 MiB at a time. Only files that match here are reported.
  4. Sort groups by bytes wasted, size * (copies - 1).

group_by catches OSError per file, so one unreadable file is a warning rather than a crash. On typical data most files are removed by the size check, so only a small fraction of the bytes is ever read.

ComplexityTime O(bytes of same-size candidates)Space O(f)
Python
import hashlib
import os
import stat
import sys
import tempfile
from collections import defaultdict
from pathlib import Path
CHUNK = 1 << 20 # read 1 MiB at a time: memory stays flat for 50 GB files
def file_hash(path, limit=None):
h = hashlib.sha256()
remaining = limit
with open(path, "rb") as f:
while remaining is None or remaining > 0:
block = f.read(CHUNK if remaining is None else min(CHUNK, remaining))
if not block:
break
h.update(block)
if remaining is not None:
remaining -= len(block)
return h.hexdigest()
def group_by(paths, key):
groups = defaultdict(list)
for p in paths:
try:
groups[key(p)].append(p)
except OSError as e: # unreadable or vanished: leave it out, say so
print(f"warning: {e}", file=sys.stderr)
return [g for g in groups.values() if len(g) > 1]
def find_duplicates(root):
by_size = defaultdict(list)
empty = 0
for dirpath, _dirs, files in os.walk(root, onerror=lambda e: print(f"warning: {e}", file=sys.stderr)):
for name in files:
path = os.path.join(dirpath, name)
try:
st = os.lstat(path)
except OSError:
continue
if not stat.S_ISREG(st.st_mode):
continue
if st.st_size == 0:
empty += 1 # every empty file "matches" every other; not useful
continue
by_size[st.st_size].append(path)
dupes = []
# 1. only files that share a size can be identical (costs no reads)
for size, same_size in by_size.items():
if len(same_size) < 2:
continue
# 2. cheap filter: hash the first 4 KiB
for candidates in group_by(same_size, lambda p: file_hash(p, 4096)):
# 3. confirm with a full hash, streamed in chunks
for group in group_by(candidates, file_hash):
dupes.append((size, sorted(group)))
dupes.sort(key=lambda d: (-(d[0] * (len(d[1]) - 1)), d[1]))
return dupes, empty
def report(root):
dupes, empty = find_duplicates(root)
for size, group in dupes:
wasted = size * (len(group) - 1)
print(f"{len(group)} copies, {size} bytes each, {wasted} bytes wasted:")
for p in group:
print(f" {Path(p).relative_to(root).as_posix()}")
print(f"skipped {empty} empty file(s)")
SAMPLE = {
"photos/a.jpg": b"A" * 5000,
"photos/b.jpg": b"B" * 5000,
"backup/a-copy.jpg": b"A" * 5000,
"backup/old/a.jpg": b"A" * 5000,
"configs/app.yaml": b"replicas: 3\n",
"configs/app.yaml.bak": b"replicas: 3\n",
"configs/db.yaml": b"replicas: 1\n",
"tmp/empty1.txt": b"",
"tmp/empty2.txt": b"",
}
def build_sample(base):
for rel, data in SAMPLE.items():
p = Path(base, rel)
p.parent.mkdir(parents=True, exist_ok=True)
p.write_bytes(data)
if __name__ == "__main__":
if len(sys.argv) > 1:
report(sys.argv[1])
else:
with tempfile.TemporaryDirectory() as tmp:
build_sample(tmp)
report(tmp)

Follow-up questions

  • Replace duplicates with hard links instead of reporting them. What can go wrong? (Different owners and permissions; editing one edits all.)
  • The volume has 10 million files. Hash in parallel with a thread pool; why do threads help here despite the GIL? (Hashing and I/O release it.)
  • Cache hashes between runs keyed by (path, size, mtime), and re-hash only changed files.

Frequently asked questions

Either is fine for finding accidental duplicates, and MD5 is faster. SHA-256 matters if someone could deliberately craft two different files with the same hash, which is practical for MD5. For a tool whose output someone might act on by deleting files, the safe option costs little. For complete certainty, compare the matching files byte by byte before deleting.

Two hard links to the same inode look like two identical files, but deleting one reclaims nothing. Group by (st_dev, st_ino) first and treat each inode as one file. Tools such as rdfind and jdupes do this.

Storage cleanup, artifact deduplication and backup verification all come down to the same size, partial hash, full hash pipeline. Interviewers use it to see whether you avoid unnecessary I/O, which usually dominates, and whether you stream large files.