Design a Scalable, Polite Web Crawler

Design a web crawler. Starting from a set of seed URLs, the system downloads each page, extracts the links it contains, adds newly discovered URLs to its work, and keeps going, storing the pages it fetches for later use. ```hint Think about the busiest host Suppose a large share of the URLs you discover belong to a single site. What in your design stops the workers from sending that site all of those requests at once, while still keeping the workers busy with other sites? ``` ```hint Seen before? Two different URLs can return the same page, and one site can generate an endless supply of new URLs. Decide where in the pipeline you check for each problem and what you need to store to do it. ``` ### Constraints and Clarifications - The round was a conventional crawler design, and no scale, content types or freshness targets were reported. Ask for them, or state your own assumptions and size the design from them. - The crawler fetches pages from sites it does not control, so it must follow each site's robots.txt rules and must not overload any site. ### Clarifying Questions - What is the crawl for: building a search index, archiving pages, or collecting data for analysis? The answer decides what is stored and how often pages are revisited. - Roughly how many pages, over what period? Is this a one-time crawl or a continuous one that keeps stored pages fresh? - Only HTML, or also images, PDFs and pages that build their content with JavaScript? - The whole public web, or a fixed list of domains? - How quickly must a newly published page be discovered, and how stale may a stored copy become? ### What a Strong Answer Covers - Clarifies purpose, scale, freshness and content types, and turns them into rough numbers for pages per second, bandwidth, concurrency and storage - A component breakdown: URL frontier, DNS resolution, fetchers, parsing and link extraction, URL and content deduplication, page and metadata storage - Politeness: robots.txt handling and per-host rate limits enforced by the frontier while the fetchers stay busy - Partitioning the work across machines, and recovery from worker or node failures without losing the crawl state or re-fetching endlessly - Defenses against crawler traps, duplicate content and slow or hostile servers, a re-crawl policy for freshness, and the metrics that show crawl health ### Follow-up Questions - How would you decide how often to revisit each page? - A site serves a calendar whose "next month" link never ends. How does your crawler notice and stop? - Some pages create their links only when JavaScript runs. What changes in cost and architecture? - How would you split the crawl across several data centers, and which state must they share?