# Design a Large-Scale Polite Web Crawler Design a distributed web crawler for a search-indexing pipeline. The target corpus is on the order of ten billion pages, pages must be revisited periodically, and a future requirement may demand a complete recrawl within 24 hours. JavaScript rendering is out of scope. Cover the full loop from URL discovery through scheduling, fetching, parsing, deduplication, storage, and returning newly discovered URLs to the frontier. Explain how the design remains polite to each host while still prioritizing important pages. Address crawler traps, URL and content deduplication, distributed ownership, failure recovery, DNS behavior, and the likely bottlenecks in a 24-hour recrawl. ### Constraints & Assumptions - Requests to one host must obey that host's crawl policy and an enforced delay; aggregate throughput must come from safe parallelism across hosts. - The frontier and progress state must survive worker failure and restart. - The same content may be reachable through several URLs, and some pages may differ only slightly. - Infinite calendars, generated query combinations, and other unbounded URL spaces must not consume the crawl indefinitely. - The downstream consumer is a search index, and fetched pages must retain enough metadata for freshness and provenance. ### Clarifying Questions to Ask - How often should different page classes be revisited, and which pages deserve priority? - Which schemes, content types, domains, and authentication states are in scope? - What are the default crawl-delay and robots-policy rules, and how quickly must robots changes take effect? - Is missing an unseen URL worse than recrawling duplicates, and does that change for high-priority domains? - What durability, geographic distribution, and data-retention requirements apply? ```hint Schedule hosts, not just URLs A single priority queue cannot by itself express both global importance and a separate next-allowed-fetch time for every host. ``` ```hint Treat deduplication errors asymmetrically A false positive in a probabilistic “already seen” structure can suppress a page that was never fetched. ``` ### What a Strong Answer Covers - A closed architecture: discovery and normalization, persistent frontier, fetchers, parsers, URL/content deduplication, storage, and feedback of new links. - A two-level frontier or equivalent scheduler that combines priority queues with per-host queues and next-eligible times. - Robots-policy caching with an explicit refresh strategy, per-host rate limiting, backoff, and fair scheduling. - URL canonicalization and exact/probabilistic dedup trade-offs, plus checksum and near-duplicate content detection. - Trap controls based on per-domain budgets, depth, URL-pattern growth, repeated content, and operator overrides. - Host-based partitioning, durable leases or checkpoints, idempotent fetch processing, and safe reassignment after failure. - Capacity reasoning for ten billion pages and a 24-hour pass, including bandwidth, response size, DNS, storage writes, parser CPU, and remote-host limits. ### Follow-up Questions 1. How long would you cache `robots.txt`, and how would a policy change invalidate queued work? 2. What damage can a Bloom-filter false positive cause, and where would you require an exact set? 3. How would you repartition hosts when a crawler node fails without violating politeness? 4. How would you identify an infinite calendar without blocking legitimate deep content? 5. If a 24-hour recrawl misses its target, how would you determine whether bandwidth, DNS, parsing, storage, or host delays are responsible?