Design a web crawler

Start from a few seed pages, download them, find their links, and keep going until you've fetched a billion pages, without downloading the same page twice, without hammering any one website, without getting stuck in infinite link mazes, and without losing progress when machines fail. A crawler is a giant, carefully scheduled queue, which makes it an excellent exercise in Level 4 thinking. It follows the interview framework phase by phase.

1. The prompt

"Design a web crawler that fetches a billion pages a week for a search engine (or for training data). The output is the raw HTML of each page, stored for later processing."

There are no users waiting on a response, so latency barely matters. What matters is throughput under a politeness constraint, deduplication at the scale of billions, and a pipeline that keeps going when individual machines, websites and DNS servers misbehave.

2. Frame the problem

3. What it must do

1. The crawler fetches pages, starting from seed URLs and following extracted links.
2. It stores each page's content and metadata for downstream indexing.
3. It recrawls pages periodically, more often for pages that change often.

Not now:

• Indexing and ranking: another system reads the stored pages.
• Heavy JavaScript rendering: mentioned as an extension.
• Crawling behind logins.

4. How well it must do it

5. Numbers that change the design

6. The nouns

• URL task: a URL in the frontier.
• Host: with its robots rules and rate limit.
• Page record.
• Content: the raw HTML.
• Seen set: URLs already discovered.

url task   normalised_url, host, priority, depth, discovered_at
host       host, robots_rules + expiry, crawl_delay, next_allowed_at, error_count, ip (cached)
page       url, fetched_at, status, content_hash, storage_key, out_links, change_rate, next_crawl_at
content    object storage: crawl/{date}/{hash} → compressed HTML

7. The contract

No public API. Internally, components pass messages, and operators get a small admin API.

frontier.add(url, priority)                    // from parsers and the recrawl scheduler
frontier.next(node) → url task                 // a fetcher asks its node for a host that's ready
page.stored {url, content_hash, storage_key, links[]}   → parser, metadata store
admin: POST /v1/seeds {urls}  ·  POST /v1/hosts/{host}/block  ·  GET /v1/crawl/stats

Data flow: (1) seed URLs enter the frontier → (2) a fetcher takes a URL whose host is allowed now → (3) robots.txt and DNS from cache → (4) download, store raw HTML → (5) parse links, normalise, check the seen set → (6) new URLs go back to the frontier; repeat.

8. First working version

One queue of URLs, a pool of fetcher workers, a parser, and a set of seen URLs.

8.1 The crawl loop

A worker takes the next URL from the queue, downloads it, stores the HTML, extracts links, and adds every link it hasn't seen to the back of the queue.

8.2 Storing pages

Raw HTML goes to object storage under a key derived from its content hash; a metadata row records the URL, status and storage key.

8.3 Recrawling

Version one re-adds every page to the queue a week after it was fetched.

9. Make it hold up

9.1 The frontier: priority and politeness together polite · throughput

Partition the frontier by hash of the host across crawler nodes, so each host's queue, rate limit and robots.txt live on exactly one node.

9.2 Don't fetch twice efficient

• Normalise URLs first: lowercase the host, remove default ports and fragments, sort or strip tracking parameters, resolve ../. Otherwise one page has dozens of URLs.
• URL-seen check: a Bloom filter answers "definitely not seen" or "probably seen" in a few bits per URL. A false positive means skipping a URL that wasn't actually crawled: acceptable at a 1% rate for most crawls. For exactness, back it with a key-value store. Size it in section 13.
• Content dedup: mirrors and copies are common. Store a hash of the normalised content and skip exact duplicates; near-duplicate detection uses fingerprints such as SimHash, where similar pages get similar fingerprints.

9.3 Robots.txt, DNS and slow servers polite · robust

• Fetch /robots.txt per host before crawling it, cache it (for example for a day), and obey its rules and any crawl delay (RFC 9309). Identify the crawler with a clear user agent and contact URL.
• DNS is a hidden bottleneck: thousands of lookups a second. Run a local caching resolver and cache results per host.
• Set connect and read timeouts, cap page size (say 10 MB), and back off hosts that error repeatedly (a per-host circuit breaker, Module 24).

9.4 Crawler traps robust · efficient

Some sites generate endless URLs: calendars with a "next month" link forever, session ids in every URL, faceted search with millions of filter combinations. Defences:

• a maximum depth per host;
• a cap on URLs per host per crawl;
• a cap on URL length;
• detecting repetitive path patterns;
• noticing when many "different" pages share the same content hash.

9.5 Not losing progress robust

The frontier is durable (a log such as Kafka, or a disk-backed queue per node), so a crashed node's work resumes. A fetch task is acknowledged only after the page is stored (at-least-once; the content hash makes repeats harmless). If a crawler node dies, its host partitions move to another node, which rebuilds those queues from the durable frontier.

9.6 Recrawling efficient · throughput

The web changes constantly, but not uniformly: a news homepage changes every minute, an old blog post never.

• Learn each page's rate: track how often it actually changed between visits, and schedule its next crawl accordingly.
• Cheap checks: use conditional requests (If-Modified-Since, ETag), so an unchanged page costs only a tiny response.
• Sitemaps: give their lastmod hints some weight.

Every recrawl spends politeness budget that could discover a new page, so the split between freshness and coverage is an explicit choice.

9.7 The whole design after the deep dives

One URL through the final crawler: front queue, host queue, fetch, store, parse, and back to the frontier.

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• A Mercator-style two-stage frontier (priority plus politeness).
• Partitioning by host.
• A Bloom filter with a known false-positive cost.
• At-least-once fetching with content hashes.
• Adaptive recrawling.
• Plain HTML first, rendering only where needed.

What we'd watch:

• Pages fetched per second.
• Ready hosts.
• Frontier size.
• Duplicate rate.
• Errors by host.
• DNS latency.
• Freshness of top pages.

At 10×:

• More nodes per host partition.
• Multi-region fetchers.
• Stricter priorities.

Common mistakes:

• A single FIFO queue.
• An exact in-memory seen set at 10 billion URLs.
• Forgetting URL normalisation.
• Ignoring robots.txt and DNS.
• No trap defences.
• Recrawling everything equally.

13. Try it, check yourself, read more

Size the URL-seen Bloom filter

Formulas: bits m = −n·ln(p) / (ln 2)², hash functions k = (m / n)·ln 2. An exact set is estimated at ~60 bytes per URL (a hash plus overhead).

How fast can politeness let you go?