Design a Web Crawler

The canonical large-scale batch pipeline

A web crawler is the canonical large-scale batch pipeline: discover, fetch, dedup, store, and repeat, across billions of pages, without getting banned. The interview tests whether you can build a distributed producer-consumer loop that is polite, deduplicated, and incrementally fresh.

The frontier

The heart is the frontier: the queue of URLs to fetch. It is not a single FIFO. It must do two jobs at once: prioritize (crawl important, fresh, high-PageRank pages first) and enforce politeness (never hammer one host). The classic design (Mercator style) uses two layers of queues: front queues for priority (a URL is assigned to a priority band) and back queues for politeness (each back queue holds URLs for exactly one host, and a per-host timer enforces a minimum delay, respecting Crawl-delay and robots.txt). A heap of "next-fetch-time per host" tells the fetchers which host is due. This is what keeps you from sending 10,000 requests/sec to one small site and getting your IP blocked.

Interview nuance: politeness is the single most common thing juniors omit and the first thing interviewers probe. Say explicitly: fetch robots.txt per host (and cache it), enforce a per-host rate limit / min delay, identify with a real User-Agent, and back off on 429/503. A crawler without politeness gets banned and is useless.

Dedup at two levels

URL dedup: before adding a URL to the frontier, check whether you have seen it, using a normalized URL (canonicalize scheme/host/case, strip tracking params, resolve relative links). At billions of URLs a hash set in memory is too big, so use a bloom filter (or scalable variant) for a fast "definitely new / probably seen" check backed by a durable seen-set store; a bloom filter's false positives cost you a few dropped new URLs, which is acceptable. Content dedup: many URLs return identical or near-identical content (mirrors, session-id URLs, print pages). Hash the content (or use MinHash/simhash shingling for near-duplicate detection) so you do not index the same page a million times. This also helps with crawler traps (infinite calendars, faceted-search URL explosions) which you additionally bound with max-depth and per-host URL caps.

Fetching and freshness

Fetching is distributed and I/O-bound. Run many fetcher workers pulling due URLs from the frontier, with async I/O for high concurrency per box, DNS caching (DNS lookups are a real bottleneck at scale, cache aggressively), and connection reuse. Fetched pages go to a raw store (S3/HDFS) as the crawl corpus, a link-extraction stage parses out new URLs and feeds them back to the frontier (the loop), and the corpus feeds a downstream indexing pipeline that builds the inverted index.

The crawl loop

Step 1 / 4

Stage 1 of 4: The heart is the frontier: front queues assign priority, each back queue holds one host, and a next-fetch-time heap enforces the per-host delay so you never hammer one small site. Distributed fetchers pull only the hosts that are due.

Freshness needs incremental recrawl, not one-shot. Estimate change rates per page (news changes hourly, an archive never does) and schedule recrawls adaptively, using HTTP conditional GETs (If-Modified-Since / ETag) so unchanged pages cost a cheap 304 instead of a full refetch.

Recap: a two-layer frontier balances priority and per-host politeness, bloom-filter URL dedup plus simhash content dedup avoid redundant work and traps, distributed async fetchers with DNS caching do the I/O, and adaptive incremental recrawl with conditional GETs keeps the corpus fresh.