Low-level design
Part 3 of 3 · ArchiveSweepArchiveSweep - Concurrency, Symlinks & Hardlink Edge Cases
Which stages parallelize safely, how to aggregate errors without losing groups, symlink policy, hardlink reclaim math, and how to explain the design without overselling hash equality.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
Which stage stays serial?
Answer
The walk. The inode set and directory order are simpler on one thread.
L2
What may run in parallel?
Answer
Sample and SHA-256. Each worker reads its own path.
L3
How do buckets stay deterministic?
Answer
Build them after the futures finish, then sort the groups.
L4
What is the default symlink policy?
Answer
Do not follow. Count and skip. An optional follow-once design needs a visited set and a depth cap.
L5
Why is hard-link reclaim zero?
Answer
Three names, one inode. Unlinking one name leaves the bytes while the link count stays above one.
L6
What does an EACCES do?
Answer
Record the error, mark the record, exclude it from later buckets, continue the other files.
L7
When would you use a process pool?
Answer
CPU-bound hashing on a huge tree. Keep the byte verify in the parent.
Failure modes
Shared dict from workers
Two threads inserting into one bucket map lose entries. Aggregate after join.
Followed symlink
A cycle or a path outside the root gets scanned. The default is not to follow.
Hard links reported as duplicates
Reclaim math is wrong. The sweep keeps one path per inode.
Misconceptions
asyncio reads files without a thread.
Blocking read still needs an offload. Threads or processes are the usual answer.
Raising isolation, or a fancier lock, fixes a symlink cycle.
The cycle is a walk policy. Do not follow the link.
Hash equality is the identity proof.
Say that it is near-final, then compare bytes.
Interviewer traps
Lock every read.
The bytes are independent. Lock the counter, not the disk.
Treat link count as a duplicate group.
That deletes a name and keeps the data.
Design scenario
Same prompt for every reader.
Requirements
No lost errors. No symlink cycles. Hard links are not reclaimable duplicates. Groups stay deterministic.
Traffic / scale
Many files, a small worker pool, one process.
Latency
Overlapped reads for sample and hash. The walk is not the thing you parallelize first.
Consistency
The same tree produces the same sorted groups.
Availability
One EACCES does not abort the sweep.
Failure assumptions
- Workers share a counter.
- A directory entry is a symlink into the tree.
- Three names share one inode.
Constraints
- Do not follow symlinks by default.
- Do not update a shared bucket map from workers without a join or a lock.
Prompt
Explain which ArchiveSweep stages are safe to parallelize and how symlinks and hard links change the answer.
API
What does the caller observe for a skipped symlink versus a hard-link extra?
Data
Which pair identifies an inode?
Architecture
What is shared, and when are buckets built?
What the workers may share
Prefer
Lock the counter, build buckets after join
The reads are independent. The maps are not.
- The walk stays one thread.
- Errors are recorded and the file is excluded.
- Verify stays against the first path.
Alternative
Unsynchronized updates to one dict
Lost inserts and a group list that changes between runs.
- Completion order becomes output order.
- A torn counter under-counts errors.
- The tests pass only when workers happen not to collide.
Overview
Deepen the concurrency and filesystem edge model: which stages parallelize safely, how to aggregate errors without losing groups, symlink policy, hardlink reclaim math, and how to explain the design in an interview without overselling hash equality.
Parallelism map
| Stage | Parallel? | Shared state | Notes |
|---|---|---|---|
| Scan / walk | Usually no | inode set | Walk is I/O bound and ordered; keep simple |
| Sample | Yes | per-file record | Independent reads |
| SHA-256 | Yes | per-file record | Independent reads |
| Byte verify | Optional | pair of paths | Bound workers; verify against first |
Share counters, not buckets
Diagram 1. Guards cover shared counters. Buckets are built when the futures are done.
- 1
Shared counters
Scanned, hashed, and errors move from more than one worker. - 2
Guard them
A lock or a result queue covers that write. The file read does not need it. - 3
Shared buckets wait
Do not insert into the size or digest map from the worker. - 4
Aggregate after join
The parent builds buckets once every future is done, then sorts.
Flow
- 1
Shared counters?
- YesGuard with lock or queue results
- 2
Guard with lock or queue results
- nextAggregate when futures done
- 3
Shared buckets?
- Build after joinAggregate when futures done
- 4
Aggregate when futures done
Lesson map
ArchiveSweep - Concurrency, Symlinks & Hardlink Edge Cases
Which stages parallelize safely, how to aggregate errors without losing groups, symlink policy, hardlink reclaim math, and how to explain the design without overselling hash equality.
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 q["Shared counters?"] l["Guard with lock or queue results"] q2["Shared buckets?"] b["Aggregate when futures done"] q -->|Yes| l q2 -->|Build after join| b l -->|continues| b
Symlinks
- Default: do not follow. Count and skip.
- Optional interview follow-up: resolve once with a visited-inode set and a max depth.
Hard links and reclaim
If three directory entries share one inode, disk reclaim from "deleting duplicates" is zero until you understand link counts. ArchiveSweep collapses to one path so groups mean content clones, not link aliases.
Failure path
Flow
- 1
1. Worker hits EACCES
- next2. Record error string
- 2
2. Record error string
- next3. Mark file record error
- 3
3. Mark file record error
- next4. Exclude from later buckets
- 4
4. Exclude from later buckets
- next5. Continue other files
- 5
5. Continue other files
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
Interview Q&A
Would asyncio help?
Answer
For pure file I/O in CPython, threads (or processes for CPU hash) are the usual answer. asyncio needs thread offload for blocking read.
Process pool?
Answer
Yes for CPU-bound hashing on huge trees; pay pickle/path shipping costs. Keep verify in the parent.
Why not follow symlinks by default?
Answer
A cycle or a path outside the root gets scanned. Follow-once is a follow-up with a visited set and a depth cap.
Why is reclaim wrong if hard links count as duplicates?
Answer
Deleting one name does not free the inode while the link count stays above one.
When is a process pool worth it?
Answer
CPU-bound hashing on a huge tree. Pay the path-shipping cost. Keep verify in the parent.
Would asyncio help?
Answer
Blocking read still needs a thread offload. Threads are the usual answer for this I/O.
Related
The series pager also walks these pages.