Katkat
Back

Parallelize a Directory Walker With Thread-Safe Visited Tracking

AnthropicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Turn a sequential directory walker into a bounded-concurrency one, using an atomic reserve-before-expand step so two worker threads that reach the same directory at once never process it twice.

Start with a single-threaded recursive directory walker, then redesign it to use a bounded pool of worker threads. Explain how discovered subdirectories enter the work queue, and how the shared "already visited" state stays correct when two workers discover the same directory at the same moment.

Scope

  • A supplied list_children(path) -> list[str] operation returns the immediate subdirectory paths of path, or raises on error. The walker coordinates work; it does not implement its own filesystem traversal primitive.
  • Walk every directory reachable from a given root, subject to a maximum depth. The root has depth 0.
  • Treat directories reached via a symlink or hard link alias as a different concern — assume list_children already returns canonical, de-aliased paths.
  • Two directories are "the same" if their canonical paths are equal.

Clarifying Questions

  • Should the walk return directories in any particular order, or is any order acceptable as long as every reachable directory under the depth limit appears exactly once?
  • What should happen when list_children raises for one directory — does it fail the whole walk, or just skip that subtree?
  • Is there a bound on total worker threads, and should that bound be configurable?
  • If the same directory is reachable from two different parents at different depths, which depth does it get assigned?

Part 1 — Sequential walker

Describe the frontier (stack or queue), the visited set, and the main loop. Explain how a directory that's reachable by two different paths from the root is only processed once.

What This Part Should Cover

  • Resolving and checking each discovered path against the visited set before adding work for it.
  • A single, well-defined point at which a path is marked "seen" so that even a sequential, single-threaded walker doesn't re-process the same directory via two different parents.

Part 2 — Bounded concurrency

Convert the design to N worker threads pulling from a shared queue. The same directory can be discovered by two workers running at literally the same instant — your design must guarantee only one of them ever expands it.

What This Part Should Cover

  • The exact operation that "reserves" a path (check-and-mark) and why it must be atomic with respect to other workers doing the same thing.
  • What goes into the shared queue, and how a worker decides there is no more work left (all workers idle and the queue is empty — not just "my queue poll timed out once").
  • How a single slow or erroring directory doesn't block the rest of the walk.
  • The time and space complexity of the concurrent version relative to the sequential one.

Hints

Hint 1

In the sequential version, decide on the exact moment a path gets added to the visited set — before or after you've finished listing its children — and carry that same moment forward unchanged into the concurrent version.

Hint 2

The race to avoid is two workers both calling list_children on the same directory; make 'check if visited, and if not, mark it' a single atomic operation guarded by one lock, not two separate steps.

Hint 3

A worker finding its queue empty doesn't mean the walk is done — another worker might still be about to enqueue more work. Track an in-flight work counter alongside the queue.

Hint 4

Let one worker's failure on one directory skip that subtree and record the error, rather than crashing or blocking the whole pool.

Follow-up questions

  • How would you bound memory if the tree is far larger than fits in the in-flight queue at once?
  • How would you detect and handle a true cycle (e.g., a symlink loop) if list_children isn't guaranteed to de-alias paths?
  • How would you add a global timeout for the whole walk without leaking worker threads?
  • How would this change if listing children were an async I/O call instead of a blocking one?