Design a Web Crawler

A crawler is BFS over the web graph, and if it were only that it would not be an interview question. What makes it hard is that the graph is adversarial, infinite in places, and owned by people who will block you.

Requirements

Functional

• Start from seed URLs, fetch pages, extract links, repeat.
• Store page content for indexing.
• Respect robots.txt and crawl rate limits.
• Recrawl pages as they change.

Non-functional

• Scale to billions of pages.
• Be polite — never overwhelm a single host.
• Be robust against traps, duplicates and malformed content.

1B pages/month → ~400 pages/second sustained
Average page 500 KB → 500 TB/month of raw content
URL frontier: tens of billions of URLs, far more than fit in memory

The URL frontier

Not a queue — this is the component the question is really about. It must satisfy two competing goals at once.

                    ┌─ front queues (PRIORITY) ─┐
   new URLs  ───→   │  f1  f2  f3 … fn          │
                    └───────────┬───────────────┘
                                │  prioritiser picks a queue
                    ┌───────────▼───────────────┐
                    │  back queues (POLITENESS) │
                    │  b1  b2  b3 … bm          │  one host per queue
                    └───────────┬───────────────┘
                                │
                          worker threads

Front queues handle priority. Not all URLs are equal: a news homepage deserves crawling

before a forgotten forum post. Priority comes from PageRank-like importance, update frequency, and depth from the seed.

Back queues handle politeness. Each back queue holds URLs from exactly one host, and

a worker takes from a queue only after a delay since that host's last fetch. This is the mechanism that guarantees you never hit one server with 400 parallel requests — a requirement, not a nicety, since the alternative is being blocked or reported.

A heap of "host → next allowed fetch time" drives which back queue is eligible.

Politeness in detail

1. Fetch and cache robots.txt per host (respect its Crawl-delay)
2. One connection per host at a time; add a delay between requests
3. Identify yourself in the User-Agent with contact details
4. Back off on 429 or 5xx

Crucially, politeness is per host, not per URL, and hosts are identified after DNS resolution — thousands of domains can share one server. DNS is itself a bottleneck at this volume, so an aggressive DNS cache is required.

Deduplication

Two distinct problems, and mixing them up is a common mistake.

URL dedup — have I seen this URL? Tens of billions of URLs will not fit in a hash set,

so use a Bloom filter: constant memory, no false negatives, and a small false-positive rate that merely means occasionally skipping a page you have not actually crawled — an acceptable loss. Normalise first: lowercase the host, strip fragments and default ports, sort or remove tracking query parameters.

Content dedup — is this page's content one I already have? Roughly 30% of the web is

duplicated. An exact hash catches identical copies; SimHash catches near-duplicates, because similar documents produce hashes within a small Hamming distance of each other. That is the answer to give — exact hashing alone misses the boilerplate-differs case that dominates.

Traps and hazards

• Infinite spaces — calendars with a "next month" link forever, faceted search with

every filter combination. Defend with a depth limit and a per-host page cap.

• Spider traps — dynamically generated infinite link chains. Same defence, plus URL

pattern detection.

• Huge or non-HTML files — check Content-Type and Content-Length before

downloading; cap the size.

• Redirect loops — cap the redirect chain.
• Soft 404s — pages returning 200 with "not found" content; detect by template

similarity.

Architecture

Frontier (priority + politeness, Kafka/Redis backed)
    ↓
Fetcher workers (stateless, autoscaled)
    ↓
Content processor → dedup check → parser → link extractor
    ↓                                         ↓
Blob storage (raw pages)              new URLs → back to the frontier
    ↓
Indexing pipeline

Fetchers are stateless and I/O-bound, so async I/O with high concurrency beats a thread per request. Partition the frontier by host hash so all URLs for a host go to one partition, which makes politeness enforceable locally without cross-node coordination — the same key-based partitioning idea as a message queue.

Recrawl scheduling

The web changes at wildly different rates. Crawling everything on a fixed schedule wastes most of the budget on pages that never change. Estimate a change frequency per page from observed history and schedule accordingly — a news homepage hourly, a documentation page monthly. Adaptive scheduling is where a crawler's real efficiency comes from, and it is a strong point to raise unprompted.

Follow-ups to expect

• JavaScript-rendered pages — a headless browser is orders of magnitude more expensive;

render selectively based on whether the raw HTML looks empty.

• Duplicate detection at scale — SimHash with LSH bucketing so comparison is not O(n²).
• Freshness vs coverage — a fixed budget must be split between recrawling and

discovering.

• Politeness across a distributed fleet — host partitioning, so one host is one node's

responsibility.

• Legal and ethical limits — robots.txt, copyright, personal data.

Track this problem on the System Design sheet.