Low-level design
Part 1 of 3 · ArchiveSweepArchiveSweep (File Deduplication) LLD - Spec, Pipeline & Concepts
Machine-coding LLD: recursively scan a directory tree, skip symlinks, collapse hard links to one inode, then find byte-identical duplicate groups with a staged pipeline (size -> sample prefix -> streaming SHA-256 -> byte verify).
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What does archive_sweep return?
Answer
Groups of paths with length at least 2, plus stats and errors. It does not delete anything.
L2
Why group by size first?
Answer
Size is metadata. Most files never share a size, so they never earn a read.
L3
What does the sample buy?
Answer
Same-size files often differ in the first 4KiB. A short read rejects them before a full hash.
L4
Why hash and then compare bytes?
Answer
The digest buckets survivors. byte_equal catches a truncated read or a bug. Hash equality is not the proof.
L5
What happens to a symlink?
Answer
Do not follow it. Count it and skip it so a link cycle cannot escape the tree.
L6
What happens to a hard link?
Answer
Keep one path per device and inode. Two names for one inode are not reclaimable duplicates.
L7
Which stages can run in parallel?
Answer
Sample and hash. The walk stays single-threaded so the inode set stays simple.
Failure modes
Symlink cycle
Following links walks the same tree forever or leaves the root. The scan does not follow them.
Permission error
One unreadable file is an error string and is dropped from later buckets. The rest of the tree continues.
Hard link counted twice
Two directory entries for one inode look like a duplicate and overstate reclaim.
Misconceptions
SHA-256 equality means the files are identical.
It is near-final. The coding solution still compares bytes before it emits a group.
A hard link is a duplicate you can delete for free space.
The second name is another link to the same inode. Unlink does not free the bytes while the link count stays above one.
Load every file, then hash.
Streaming 1MiB chunks and dropping singleton sizes avoids that memory spike.
Interviewer traps
Start with a distributed content-defined chunker.
Ship the single-host pipeline and the tests. Multi-host is a follow-up.
Sort the group by mtime.
Path order is stable. Clocks are not.
Design scenario
Same prompt for every reader.
Requirements
Stdlib only. Skip symlinks. One path per inode. Size, sample, streaming SHA-256, then a byte verify. Stable group order.
Traffic / scale
One host. The tree can be large. Create rate is not the point. Read amplification is.
Latency
Metadata first. A full read only for files that still share a size and a sample.
Consistency
A group means byte-identical content, not two names for one inode.
Availability
One unreadable path becomes an error and does not fail the sweep.
Failure assumptions
- A symlink points at a file inside the tree or at a cycle.
- Two names share one inode.
- Two files share a size and a prefix and differ in the tail.
Constraints
- Do not follow symlinks.
- Do not load whole files into memory.
- Do not delete files in this version.
Prompt
Report duplicate files under a directory without deleting them.
API
What does a group contain, and what is not a group?
Data
Which key collapses hard links, and which key buckets a sample?
Architecture
Which stages are safe to run in a thread pool?
How to spend the reads
Prefer
Size, sample, stream hash, then bytes
Most files die on metadata. A group is emitted only after the bytes match.
- Symlinks are skipped.
- Hard links collapse on device and inode.
- Group order is sorted and stable.
Alternative
Hash every file into memory
Correct for a toy tree and the wrong cost model for an interview.
- No early exit.
- A symlink cycle is still your problem.
- Hard links look like reclaimable copies.
Overview
Machine-coding LLD: recursively scan a directory tree, skip symlinks, collapse hard links to one inode, then find byte-identical duplicate groups with a staged pipeline (size -> sample prefix -> streaming SHA-256 -> byte verify). Prefer streaming and early exits over loading whole files. Expose a clean archive_sweep(root) -> groups API with stats and error collection.
Spec summary
| Concern | Rule |
|---|---|
| Scan | Recursive, no follow symlinks; skip non-regular files |
| Hard links | One path per (dev, ino) |
| Stages | size > 1 -> sample(4KiB) -> sha256 stream -> byte_equal verify |
| Output | Groups of paths (len>=2), sorted; stats + errors |
| Concurrency | Thread pool for sample/hash; deterministic group order |
Step-by-step design
- Clarify: report only, no deletes; stdlib only; must survive partial read errors.
- Walk with
os.walk(followlinks=False); prune symlink dirs. - Bucket by size; drop singleton sizes.
- Sample first N bytes; bucket by (size, sample).
- Stream SHA-256 in 1MiB chunks; bucket by digest.
- Verify survivors with pairwise (or against first) byte compare.
- Sort groups by first path for stable output.
- Tests: identical, same-size-different, same-prefix-different-tail, symlink skip, hardlink collapse, empty files.
Scan, filter, then prove
Diagram 1. A file that is alone at any stage is dropped. A group is emitted only after the byte verify.
- 1
Scan and skip symlinks
Walk with followlinks off. A symlink file or directory is counted and skipped. - 2
Collapse hard links
Keep one path per device and inode. Extra names are not duplicates. - 3
Group by size
Singleton sizes are dropped before any content read. - 4
Sample the prefix
Read 4KiB. A unique sample is dropped. - 5
Stream SHA-256
Hash the survivors in chunks. A unique digest is dropped. - 6
Byte verify or drop
Matching bytes become a sorted group. A mismatch or a read error does not.
Decisions
- 1
1. Scan files skip symlinks
- next2. Collapse hard links by inode
- 2
2. Collapse hard links by inode
- next3. Group by size
- 3
3. Group by size
- next4. Size group size greater than 1?
- ?
4. Size group size greater than 1?
- No5. Drop
- Yes6. Sample prefix
- 5
5. Drop
- 6
6. Sample prefix
- next7. Sample collision?
- ?
7. Sample collision?
- No5. Drop
- Yes8. Stream SHA-256
- 8
8. Stream SHA-256
- next9. Digest collision?
- ?
9. Digest collision?
- No5. Drop
- Yes10. Byte verify
- 10
10. Byte verify
- next11. Emit duplicate group
- 11
11. Emit duplicate group
Lesson map
ArchiveSweep (File Deduplication) LLD - Spec, Pipeline & Concepts
Machine-coding LLD: recursively scan a directory tree, skip symlinks, collapse hard links to one inode, then find byte-identical duplicate groups with a staged pipeline (size -> sample prefix -> streaming SHA-256 -> byte verify).
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1. Scan files skip symlinks"] b["2. Collapse hard links by inode"] c["3. Group by size"] d["4. Size group size greater than 1?"] z["5. Drop"] e["6. Sample prefix"] f["7. Sample collision?"] g["8. Stream SHA-256"] h["9. Digest collision?"] i["10. Byte verify"] j["11. Emit duplicate group"] a -->|continues| b b -->|continues| c c -->|continues| d d -->|No| z d -->|Yes| e e -->|continues| f f -->|No| z f -->|Yes| g g -->|continues| h h -->|No| z h -->|Yes| i i -->|continues| j
Concepts used, learn more
Read the underlying idea on its own study page. This lesson applies it. It does not replace those pages.
- Hashing, Frequency Maps & Counting — Two Sum Family & Anagrams
- Mutexes, Condition Variables, Deadlocks & Happens-Before
- Atomics vs Locks
- Mutex vs RWLock
- When Locks Win — Contention, Fairness & Hybrid Designs
- Consistent Hashing: Rings, Virtual Nodes & Replica Placement
- Low-Level Design Under Time — Interfaces, State & Tradeoffs
| Concept | Role | Study page |
|---|---|---|
| Hashing / frequency maps | Digest bucketing intuition | Hashing, Frequency Maps & Counting — Two Sum Family & Anagrams |
| Mutex / thread pool safety | Concurrent sample and hash | Mutexes, Condition Variables, Deadlocks & Happens-Before |
| Atomics vs locks | When shared counters need locks | Atomics vs Locks |
| Consistent hashing (analogy) | Partitioning work by key | Consistent Hashing: Rings, Virtual Nodes & Replica Placement |
| Interview LLD interfaces | Service boundary and invariants | Low-Level Design Under Time — Interfaces, State & Tradeoffs |
Comparative: early filters
| Stage | Cost | False positives | Why keep |
|---|---|---|---|
| Size | Cheap metadata | High | Eliminates most pairs |
| Sample prefix | One small read | Medium | Cheap reject |
| SHA-256 | Full file read | Extremely low | Near-final |
| Byte verify | Full file read again | Zero | Hash collision / bug insurance |
Interview Q&A
Why verify after SHA-256?
Answer
Defense in depth: implementation bugs, truncated reads, and theoretical collisions. Interviewers like the honesty that hash equality is not a identity proof until bytes match.
How would you scale to multi-host?
Answer
Content-defined chunking or rolling hashes, a central digest index (object store / RocksDB), and remote workers. Start with single-host correctness.
Soft links vs hard links?
Answer
Symlinks: skip (or optionally resolve once with cycle guard). Hard links: same inode, one logical file; counting both as duplicates is wrong for reclaim math.
Why not load the whole file?
Answer
The hash streams 1MiB chunks. Loading the tree into memory is the cost you are trying to avoid.
What does a permission error do?
Answer
Record the path, drop that file from later buckets, and keep scanning.
Where does consistent hashing fit?
Answer
It is the analogy for partitioning work by a key on a later multi-host design. This page is still one tree on one host.
Pitfalls
- Following symlinks into cycles.
- Loading entire files into memory.
- Treating hard-linked paths as reclaimable duplicates.
- Non-deterministic group order across runs.
Related
The series pager also walks these pages.