Web Crawler

Distributed crawling

Design a crawler that downloads about a billion web pages a day for a search index, without overloading any website, fetching the same page twice, or getting lost in endless URLs.

Overview

A web crawler starts from a list of known URLs (the seeds), downloads each page, finds the links in it, and adds the new ones to its list of URLs to fetch. Repeat that for weeks and you have a copy of a large part of the web, which a search engine then indexes.

The loop is simple. What makes the interview question hard is doing it at a billion pages a day while being a good guest. Websites did not ask to be crawled: a crawler must follow each site's robots.txt rules, never flood a server with requests, avoid downloading the same thing twice, and not wander forever through sites that generate endless URLs.

Questions to ask first

What is the crawl for? — A general web search index, HTML pages only
How many pages, how fast? — About 1 billion pages a day; the index knows about 10 billion URLs
New pages or keep old ones fresh? — Both: discover new URLs and re-fetch known pages as they change
Render JavaScript? — No; fetch the HTML as served
How polite? — Follow robots.txt; at most one request at a time to a host, and a pause between requests
Keep the raw pages? — Yes, compressed, so the indexer can be re-run without re-crawling

What you will be able to do

Size a crawl: fetch rate, bandwidth, storage and the memory for the seen-URL set.
Design a URL frontier that orders URLs by priority and still never overloads a host.
Apply the robots.txt rules of RFC 9309, including what to do when the file cannot be fetched.
Detect repeated URLs and near-duplicate pages cheaply at a scale of billions.
Keep pages fresh and escape crawl traps.

Key concepts

URL frontier
Politeness
robots.txt (RFC 9309)
URL normalization
Bloom filter
SimHash
Conditional GET
Crawl traps
Host partitioning

Functional requirements

Start from seed URLs and follow links to discover new pages
Download HTML pages and store them, compressed, for the indexer
Obey each site's robots.txt rules
Never fetch the same URL twice in one pass; skip pages whose content is a duplicate
Re-fetch known pages on a schedule that follows how often they change

Non-functional requirements

About 1 billion pages a day (a target we chose), about 11,600 a second
Polite: at most one request in flight per host, with a pause between requests (a policy we chose)
Robust to slow servers, broken HTML, redirect loops and endless URL spaces
Survives the loss of any machine without losing the frontier
Scales by adding fetcher machines

Interview questions

How do you make the crawler polite?
How does the URL frontier work?
How do you avoid fetching the same URL twice?
How do you detect near-duplicate pages at the scale of billions?
What do you do when robots.txt cannot be fetched?
How do you keep the index fresh without re-downloading everything?
How do you scale the crawler across many machines?
What are crawl traps and how do you escape them?