Design a web crawler

1. Clarify the requirements

Ask what the crawl is for, because it changes priorities: a search index needs breadth and freshness, an archive needs completeness, a price monitor needs a few sites very often. Also ask: HTML only or media too? Do we render JavaScript? How fresh should content be?

Functional requirements

• Start from seed URLs and discover new pages by following links.
• Download and store page content for an indexing pipeline downstream.
• Re-crawl pages periodically, more often for pages that change often.
• Respect robots.txt and crawl-delay directives.

Non-functional requirements

• Politeness: never overload a single host; this is a hard constraint, not an optimisation.
• Scalability: billions of pages per month, horizontally scalable fetchers.
• Robustness: survive malformed HTML, slow servers, infinite URL spaces, and machine failures without losing crawl state.
• Extensibility: new content types and processing steps can be added.

2. Estimates

The throughput is modest per machine; the hard parts are state (frontier and seen set are huge) and coordination (politeness across many workers). That shapes the design more than raw QPS.

3. High-level architecture

Fetchers are stateless workers: take a URL from the frontier, resolve DNS (cached, since resolution is surprisingly slow at this rate), check the cached robots.txt for that host, download with timeouts and a size cap, and write the response to blob storage with metadata (status, headers, fetch time).

Parsers extract links and text, compute a content fingerprint to detect duplicate pages served under different URLs, and hand the links to the URL filter, which normalises them, drops disallowed or unwanted ones (file types, blocked domains, trap patterns), and checks the seen set. Only new URLs go back into the frontier.

4. The URL frontier (the core of the design)

The frontier has to answer "which URL next?" while satisfying two constraints at once: crawl important pages first, and never hit one host too often. The classic design splits it in two:

• Front queues (priority). A prioritiser assigns each URL a score (page importance, how often the page changes, time since last crawl) and puts it into one of N priority queues.
• Back queues (politeness). Each back queue holds URLs for exactly one host. A heap keyed by "earliest time this host may be fetched again" tells workers which back queue is ready. After each fetch, the host's next-allowed time is pushed forward by its crawl delay.

Workers pull from ready back queues; when a back queue empties, it's refilled from the front queues, biased towards higher priorities. Because the frontier holds billions of URLs, queues are disk-backed with in-memory buffers at the head and tail.

To distribute it, partition the frontier by host (hash of the hostname) so that one partition owns all politeness state for a host and no cross-machine coordination is needed. Fetchers are assigned to partitions.

5. Data model

url_state     url_hash (PK), url, host, last_fetch_at, last_status,
              content_hash, change_rate_estimate, next_fetch_at, priority
host_state    host (PK), robots_txt, robots_fetched_at, crawl_delay_ms,
              next_allowed_at, error_count
pages (blob)  key = url_hash + fetch_time → compressed body + headers
seen set      Bloom filter (memory) in front of url_state (disk)

change_rate_estimate is updated each time a page is re-fetched (did the content hash change?), and drives next_fetch_at for re-crawls: news homepages every few minutes, a static documentation page every few weeks.

6. Scaling and robustness

• Deduplication at two levels. URL-level (normalisation plus the seen set) avoids re-fetching; content-level (exact hash for identical pages, SimHash or MinHash for near-duplicates) avoids storing and indexing mirrors.
• Crawler traps. Calendars with infinite "next month" links, session IDs in URLs, and auto-generated paths can create unbounded URL spaces. Cap URLs per host and path depth, detect repeating path segments, and lower priority for hosts that produce many near-duplicate pages.
• Failures. Persist frontier state so a crashed partition resumes where it left off. Retry transient fetch errors with backoff; mark hosts that keep failing and back off further.
• DNS. Run a local caching resolver per fetcher pool; DNS is a frequent hidden bottleneck.
• Geography. Place fetchers in several regions and route hosts to the nearest region to cut latency and egress costs.
• JavaScript. Send pages that need rendering to a separate, much smaller headless-browser pool with its own queue and budget.

7. Trade-offs to call out

• Freshness vs coverage: every re-crawl of a known page is a new page not discovered. The scheduler's priority function is where you set that balance.
• Bloom filter false positives: a 1% false-positive rate means about 1% of genuinely new URLs are wrongly skipped. Acceptable for a broad crawl; not for a crawl that must be complete.
• Politeness vs throughput: big sites can tolerate more parallelism; small sites can't. Adapt crawl rate per host based on response times and errors.
• Store everything vs store what you index: raw HTML is useful for re-processing but costs storage; many crawlers keep only the latest version plus extracted text.

8. Common follow-up questions

1. How do you prioritise which pages to crawl? Combine a link-based importance score (PageRank-like, computed offline), observed change rate, and business rules (e.g. favour certain domains). Recompute periodically.
2. How do you detect that a page changed without downloading it? Use conditional requests (If-Modified-Since, ETag), and sitemaps' lastmod where available.
3. How would you crawl only one large site very fast? You can't exceed what the site allows; negotiate a higher rate or use their API or sitemaps. Parallelism doesn't override politeness.
4. How do you handle redirects and canonical tags? Follow redirects up to a limit, store the final URL, and record canonical links so the index uses the preferred URL.
5. How do you scale the seen set beyond one machine? Partition it by URL hash, the same way the frontier is partitioned by host; see sharding and consistent hashing.