Q: You wrote a single threaded crawler (BFS from a start URL, same host only). The interviewer asks you to make it concurrent. Talk through the changes.

Keep the BFS shape, then change four things. Workers: a fixed pool sized for I/O (tens of workers, or an async loop with a semaphore), pulling from a shared frontier queue. Dedup: an atomic insert into visited (putIfAbsent or a lock around check and add) done when a URL is enqueued, not when it is fetched. Termination: a pending counter: increment for each new URL before decrementing for the finished one, and stop when it reaches zero; then send poison pills or close the queue so workers exit. Failure handling: timeouts per fetch, a retry limit, and an exception in one fetch must still decrement pending. Follow ups: per host politeness, bounded frontier for memory, and measuring the speedup against the single threaded version.

Question 1

Crawler workers share a thread safe set. Two workers sometimes fetch the same URL. What is the fix?if url not in visited:
 visited.add(url)
 fetch(url)

Accepted Answer

Make the check and the add one atomic step, such as add returning whether it inserted, or a lock around both Each set call is atomic, but the gap between contains and add is not: both workers can see the URL missing and both proceed. An atomic insert that reports whether it won (putIfAbsent, add returning a boolean, or a lock covering both calls) closes the window. The thread safe set alone is exactly the code shown, so the race stays. Visibility (volatile) does not make two operations one. Adding after the fetch widens the race window instead of closing it.

Question 2

A multithreaded crawler uses a shared queue of URLs and N workers. When should the crawl be declared finished?

Accepted Answer

When the queue is empty and no worker is still processing a page A worker that is mid fetch can still discover and enqueue new URLs, so an empty queue alone is not the end. Track pending work (queued plus in flight) under a lock or an atomic counter and finish when it hits zero. Stopping on an empty queue exits early whenever the queue briefly drains. A timeout guesses and breaks on a slow host. A visited set that did not grow between two samples says nothing about pages still being fetched.

Question 3

Crawler workers decrement a shared pending counter after finishing a page, and the coordinator stops when pending is 0. When must a worker increment pending for each new link it finds?

Accepted Answer

Before it decrements pending for the page it just finished If the worker decrements first, pending can momentarily reach 0 while new links are known but not yet counted, and the coordinator stops early. Incrementing for children first keeps pending above zero for as long as any work exists. Decrementing first is exactly the early exit bug. Counting only after a fetch means unfetched links are invisible to termination. An atomic counter makes each update safe but does not fix the ordering between two updates.

Question 4

A crawler must fetch about 10 million pages with at most 64 concurrent requests on one machine. Which design fits?

Accepted Answer

A fixed pool of 64 workers pulling from a shared frontier queue A fixed pool caps concurrency at exactly the limit and reuses threads, and the frontier queue absorbs bursts of discovered links. A thread per URL creates millions of threads, exhausts memory and file descriptors and blows past the request limit. Sleeping between starts only slows creation; the number alive is still unbounded when fetches are slow. Unbounded fan out per page has the same problem recursively.

Question 5

A concurrent crawler with 64 workers must send at most one request per second to each host, and most frontier URLs belong to a few hosts. Which design keeps the workers busy while obeying the limit?

Accepted Answer

Per host queues with a next allowed time, and workers pick any host whose time has passed Per host queues let a worker skip hosts that are cooling down and fetch from hosts that are ready, so the rule holds per host without idling the pool. A global lock held across a sleep serialises the whole crawler to one request per second total. A global rate is not a per host limit and can hit one host 64 times a second. Per worker sleeps do not coordinate across workers, so 64 workers can still hit the same host 64 times a second.

Question 6

You wrote a single threaded crawler (BFS from a start URL, same host only). The interviewer asks you to make it concurrent. Talk through the changes.

Accepted Answer

Keep the BFS shape, then change four things.

Workers: a fixed pool sized for I/O (tens of workers, or an async loop with a semaphore), pulling from a shared frontier queue.

Dedup: an atomic insert into visited (putIfAbsent or a lock around check and add) done when a URL is enqueued, not when it is fetched.

Termination: a pending counter: increment for each new URL before decrementing for the finished one, and stop when it reaches zero; then send poison pills or close the queue so workers exit.

Failure handling: timeouts per fetch, a retry limit, and an exception in one fetch must still decrement pending.

Follow ups: per host politeness, bounded frontier for memory, and measuring the speedup against the single threaded version.

Question 7

The concurrent crawler now needs to run on 100 machines. How do you partition work and dedup URLs across them?

Accepted Answer

Partition by host: hash the host to pick the owning machine, so politeness and robots state stay local and each machine dedups its own URLs. Routing: a machine that finds a link it does not own sends it to the owner through a queue (Kafka or RPC batches). Dedup: the owner keeps the visited set, in memory with a Bloom filter in front, or in a shared key value store if machines are stateless. Failure: consistent hashing so a lost machine moves only its share, and the frontier persisted so work is not lost. Termination: a global pending count is expensive, so most real crawlers run continuously and track freshness rather than detecting a global end.

Concurrent web crawler interview questions

More operating systems topics

Practise these on your commute