Design a concurrent web crawler

##### Question Design and implement a concurrent web crawler. Starting from one or more seed URLs, the crawler should fetch pages, extract links, deduplicate visits, stay within a configured scope (a single domain, a set of allowed domains/subdomains, optionally the seeds' exact origin, and/or a maximum link depth), and respect `robots.txt`. Assume the workload is primarily network-bound (most time is spent waiting on HTTP responses). Along with your code, give a brief architecture description: the components you would split the crawler into, how they interact, and why you drew the boundaries where you did. Address the following sub-parts: 1. **Single-threaded baseline.** Build a single-threaded crawler that, given seed URLs, fetches pages, extracts and normalizes links, deduplicates visits, respects `robots.txt`, and stops at a configurable depth and/or domain scope. 2. **URL frontier.** How do you structure the frontier of URLs waiting to be visited so that ordering (e.g. BFS) and per-host fairness are preserved? 3. **Deduplication across concurrent workers.** How do you prevent duplicate fetches when many workers run at once? Cover URL normalization (including which transforms are safe and which can wrongly merge distinct pages) and why the `visited` check-and-insert must be effectively atomic and done at *schedule* time, not after fetching. Also explain how redirects fold into deduplication: a URL can turn out to be a duplicate when it is discovered (several parents link to it before it is fetched) and again when it is fetched (two different URLs redirect to the same final page). Where in the lifecycle does each check happen, and what key does each one use? 4. **Concurrency model: async I/O vs. multithreading vs. multiprocessing.** Discuss which model you would choose and why for an I/O-bound workload. Then extend the baseline into a concurrent version and compare three concrete implementations: - (a) manual multithreading using queues and locks, - (b) a fixed-size thread pool, and - (c) an asyncio / event-loop model. For each, explain how you maintain the frontier, enforce per-host politeness/rate limits, avoid duplicate fetches, handle failures/retries/backoff, manage back-pressure, and perform graceful shutdown. 5. **Completion detection.** How do you reliably detect that the crawl is finished (not merely that the queue momentarily emptied)? Whatever you track for this, where do you update it relative to enqueueing an item and finishing it, so that no item slips through the gap, and what backstop guarantees shutdown if that tracking is ever wrong? 6. **Failures, timeouts, retries, and back-pressure.** How do you handle transient vs. permanent errors, set timeouts, retry with backoff, and bound memory/concurrency under load? When a `429` or `503` response carries a `Retry-After` header (delta-seconds or an HTTP-date), how do you back off that host without losing the URL? How do you make sure one malformed page or unexpected exception never kills a worker, and how do you keep a crawler trap (a site that generates an effectively endless supply of distinct URLs) from consuming the whole crawl? 7. **Politeness and rate limiting.** How do you enforce per-host throttling and `robots.txt` crawl-delay so you do not overload a target site? How do you select the `robots.txt` rules that apply to your crawler's user-agent, and what do you key the rules cache on? Fetching `robots.txt` is itself a request to the host: how does it interact with your rate limiter, and what does the crawler do when `robots.txt` returns 404, 403, or a persistent 5xx? 8. **Analysis.** Discuss the relevant data structures (visited sets, frontier queues, per-host buckets) and synchronization primitives, how you prevent deadlocks/starvation, the time/space complexity, and the correctness/liveness/performance trade-offs across the three concurrency models. Also estimate how much memory your dedup structures need for a crawl of about a million unique URLs (count every set you keep), and say what you would switch to once they no longer fit in RAM. 9. **Redirects, content type, and origin scope.** How do you follow redirects safely, which of your checks must run again once you know where a redirect actually landed, and why? By default, parse only `text/html` responses for links: how do you filter by content type, cap the number of bytes you read from any one response, and make sure every early exit (error status, wrong content type, throttling) still releases its connection? Finally, support an optional mode that restricts the crawl to the seeds' origin, where an origin is the `(scheme, host, port)` tuple rather than just the hostname. How do default ports affect that comparison, and how does a URL discovered several hops from a seed get checked against the right seed's origin? 10. **Testing.** How would you test the crawler? Describe the unit, integration (against a local fixture server), concurrency, and fault-injection tests you would write. How do you test the rate limiter and backoff deterministically, and which failure paths would you deliberately inject? 11. **Monitoring.** For a real run, what would you monitor? Name the metrics, the structured log events, and the alert conditions you would set, including how you would notice a crawl that is stuck or quietly degrading. ### Constraints & Assumptions Treat these numbers as defaults you may revise after asking clarifying questions, not hard limits. - **Scale:** plan for up to about a million unique URLs in a single in-memory run; beyond that, the dedup structures may need to change. - **Concurrency:** a configurable cap on concurrent fetches (on the order of tens of worker threads, or a comparable limit on in-flight async requests). - **Politeness defaults:** at most one request per host per configurable interval (about one second) unless `robots.txt` specifies a different crawl-delay. - **Content scope:** by default only `text/html` (and equivalent XHTML) responses are parsed for links; other responses are not parsed. - **Single machine:** assume one machine unless you choose to discuss distribution as an extension. ### Clarifying Questions to Ask 1. **Goal of the crawl:** are we indexing a single site (same origin) or crawling the open web from arbitrary seeds? Is coverage or freshness the priority? 2. **Scale and budget:** roughly how many URLs or pages, and is there a wall-clock, page-count, or byte budget the crawl must respect? 3. **Politeness requirements:** must we strictly honor `robots.txt` and `Crawl-delay`, and what default per-host rate is acceptable? 4. **Persistence:** is this a one-shot in-memory run, or must the frontier and visited state survive a process restart? 5. **Output:** what do downstream consumers need (raw HTML, extracted links, a normalized URL list, page metadata)? 6. **Environment:** one machine or a distributed crawl? Are we free to use libraries such as `requests` or `aiohttp`, or is this a from-scratch exercise? ### Follow-up Questions 1. **What breaks first as you scale this to many millions of URLs on one box:** the dedup sets, the frontier, the connection pool, or something else? What do you change? 2. **How would you make the crawl distributed** so that per-host politeness stays correct across several crawler nodes? 3. **How would the design change if it had to survive a process restart** mid-crawl without re-fetching everything or violating politeness?