Design a Web Crawler
Problem
Design a crawler that downloads web pages for a search engine index. Starting from a set of seed URLs, it fetches pages, extracts links, and keeps discovering new pages. It must crawl 1 billion pages per month, respect robots.txt and avoid overloading any single website, and avoid storing the same URL or the same content twice. Pages should be recrawled periodically, with frequently changing pages (such as news front pages) revisited more often than static ones. Only HTML pages are in scope.
- Is the crawl for a general web search engine, or a focused crawl of specific sites?
- Should we render JavaScript, or is raw HTML enough?
- How fresh must the index be? How often should popular pages be recrawled?
- How long must raw page content be retained?
- Do we need to handle content in many languages and character encodings?
- How should we handle crawler traps, such as calendars that generate infinite URLs?
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Fetch pages starting from seed URLs and follow extracted links.
- Obey
robots.txtrules and per-host rate limits. - Skip URLs already crawled and pages whose content is a duplicate.
- Recrawl pages on a schedule that reflects how often they change.
- Store raw HTML and metadata for the indexing pipeline.
- Prioritize important pages (for example, those with many inbound links) over obscure ones.
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Crawl 1 billion pages per month: about 400 pages per second on average, with headroom to 1,000 per second.
- Never send more than one request every few seconds to the same host by default.
- Storage: at about 100 KB per page compressed to 25 KB, 1 billion pages is about 25 TB per month of raw content.
- The URL seen set holds around 10 billion URLs; storing 8-byte fingerprints is about 80 GB.
- Fault tolerant: a crashed worker must not lose its work or cause pages to be skipped permanently.
- Robust against malformed HTML, slow servers, and crawler traps.
A URL frontier holds URLs to crawl, organized into per-host queues so that politeness is enforced structurally and priority decides which hosts go next. A fleet of fetcher workers pulls URLs from the frontier, resolves DNS through a cache, checks robots.txt, downloads the page, and writes it to content storage. A parser extracts links, filters and normalizes them, drops ones already seen, and feeds the rest back into the frontier, while content fingerprints catch duplicate pages.
Loading diagram...
Fetch a page. A fetcher asks the frontier for work and receives a URL from a host whose politeness delay has passed. It resolves the host through the DNS cache, checks the cached robots.txt rules (fetching them first if missing or older than a day), and downloads the page with a timeout and a size cap. It stores the compressed HTML in the content store keyed by URL hash and fetch time, and passes the page to the parser.
Extract links. The parser computes a content fingerprint and checks it against the dedup index; if the page duplicates one already stored, it records the duplicate and stops. Otherwise it extracts links, resolves them to absolute URLs, normalizes them (lowercase host, remove fragments and tracking parameters), and filters out disallowed schemes, file types, and trap patterns. Each URL's fingerprint is checked against the seen set, and new URLs are added to the frontier with a priority score.
Recrawl. After each fetch, page metadata records whether the content changed since the last visit. The recrawl scheduler uses that history to estimate a change rate per page and reinserts URLs into the frontier when they are due.
Decides which URL to fetch next, balancing priority against politeness.
- A custom service with priority queues and per-host queues, persisted to disk (RocksDB) with in-memory heads for speed.
Diagram
Loading diagram...
API
enqueue(urls[], priority)lease(workerId, n) -> [{ url, leaseId }]complete(leaseId, { status, crawlDelay? })
Scalability
The frontier is partitioned by host hash across many nodes, so all URLs for one host live on one partition, which can enforce that host's delay locally without coordination. Only the heads of queues stay in memory; the bulk of billions of pending URLs sits on disk.
Tradeoffs
A single global priority queue would be simpler but would happily send hundreds of requests per second to one large site. Per-host queues with a next-allowed-time heap make politeness automatic. Leases with timeouts ensure that a URL given to a worker that crashes is handed out again instead of being lost.
Stateless workers that download pages with high concurrency.
- Asynchronous I/O (Go, or Rust with Tokio) handling thousands of concurrent connections per worker.
- Local DNS cache, with a shared resolver tier behind it.
Scalability
Fetching is network bound, not CPU bound, so each worker keeps many requests in flight. At 1,000 pages per second and an average download time of 1 second, about 1,000 concurrent fetches are needed, which a few workers can handle, but tens are deployed for headroom and geographic spread.
Tradeoffs
DNS lookups can take tens of milliseconds and become a bottleneck, so caching them with their TTLs is essential. Rendering JavaScript with headless browsers would capture more content but costs 10 to 100 times more per page, so it is reserved for a separate queue of high-value sites known to need it.
Prevents refetching known URLs and storing duplicate content.
- URL seen set: a sharded key-value store of 64-bit URL fingerprints, with a Bloom filter in front for fast negative lookups.
- Content dedup: exact hashes (SHA-256) plus SimHash for near-duplicates.
Data Model
seen_urls(url_fingerprint PK, first_seen, last_crawled)content_fingerprints(simhash, canonical_url)
Scalability
The Bloom filter answers most lookups for new URLs in memory, so the backing store is consulted only for probable matches. Fingerprints are sharded by value across nodes, keeping each shard's set small enough for RAM.
Tradeoffs
A Bloom filter alone uses less memory but has false positives, which would cause the crawler to skip some new URLs forever. Backing it with an exact store fixes that at modest cost. Near-duplicate detection catches mirrors and pages that differ only in ads or timestamps, which exact hashing misses.
Durable storage for raw HTML, consumed by the indexing pipeline.
- Object storage (S3 or HDFS), writing pages in large WARC-style batch files.
- Page metadata in a wide-column store such as Bigtable or Cassandra.
Data Model
- Batch file object:
crawl/<date>/<worker>/<sequence>.warc.gzcontaining many records. page_metadata(url_fingerprint PK, url, last_fetch, status, content_hash, change_count, fetch_count)
Scalability
Writing in large batches avoids billions of tiny objects and makes downstream processing sequential and efficient. At 25 TB per month, object storage scales without effort, and older crawls move to cold storage.
Tradeoffs
Storing each page as its own object makes random lookups easy but creates enormous per-object overhead. Batch files plus a metadata index pointing at file and offset give both cheap storage and direct lookup when needed.
Decides when each known page should be fetched again.
- A periodic batch job (Spark) over page metadata, writing due URLs back to the frontier.
Scalability
The job processes metadata in partitions and emits only URLs that are due, so the frontier receives a steady trickle instead of a burst of billions.
Tradeoffs
Recrawling everything on a fixed cycle wastes capacity on pages that never change and leaves fast-changing pages stale. Estimating each page's change rate from its history and weighting by importance spends the crawl budget where freshness matters most, at the cost of keeping per-page history.