Make a Web Crawler Concurrent with Thread-Safe Visited State

Start with a single-threaded web crawler, then redesign it for concurrent fetching. Explain how discovered links enter the work queue and how shared visited state remains correct when several workers discover the same URL at once. ### Constraints & Assumptions - The source specifically describes this single-threaded-to-concurrent progression and thread-safe visited handling. It supplies no original fetch API or crawl boundary. - **Practice scope:** crawl reachable pages within a configured origin and finite page/depth budget. A supplied fetch-and-extract operation returns a page's outgoing links or an error. The crawler coordinates work rather than implementing an HTML parser. - **Depth policy for this practice scope:** the seed has depth zero. A URL receives its discovery-tree depth when first reserved, one greater than the reserving parent's depth. Fetch accepted URLs through the depth limit, but expand links only from URLs below that limit. Later discovery through a shallower path does not lower the reserved depth or trigger re-expansion. The concurrent result can depend on discovery order; this budget policy does not promise to visit every URL whose minimum hop distance from the seed is within the limit. - Normalize links against their page URL using a stated URL policy before identity checks. Do not assume different query strings are equivalent. - Use bounded fetch concurrency and define retry limits. A failed fetch and a successfully processed page should not be indistinguishable merely because both have been seen. ### Clarifying Questions to Ask - Is URL identity based on normalized requested URLs, final redirect URLs, or a stronger canonical rule? - What origin, scheme, depth, and page-count limits bound the crawl? - Should transient errors be retried, and does a redirect remain eligible only if its target is in scope? - Must discovered URLs or fetched results be returned in any particular order? ### Part 1 — Establish the Sequential Algorithm Describe the frontier, discovered-state map, and processing loop. Explain how cycles and repeated links are handled before adding concurrency. #### What This Part Should Cover - URL resolution and scope checks before scheduling. - A defined reservation/seen point that prevents repeated scheduling. - Separate success, failure, and retry outcomes under a finite crawl budget. ### Part 2 — Make Discovery and Completion Concurrent Design the synchronization around discovery, scheduling, and termination. Explain why a temporarily empty queue does not necessarily mean the crawl is finished. #### What This Part Should Cover - Atomic check-and-reserve for a normalized URL. - Fetching outside shared-state locks and bounded active work. - Outstanding-work accounting that includes pages currently being fetched and links they may discover. ```hint Follow two workers discovering one link Both workers may check that a URL is absent before either inserts it. Decide which combined state transition must be atomic. ``` ### What a Strong Answer Covers - A sequential crawler whose invariants survive concurrent execution. - Atomic URL reservation, clear retry state, and safe global completion detection. - URL-policy and crawl-budget limits rather than unsupported claims of visiting every page on an unbounded web. ### Follow-up Questions - Why can removing a failed URL from the visited set create a retry storm? - How would you keep per-origin concurrency bounded if the crawl later spans several origins? - What additional durable state would be required to resume after the crawler process crashes?