Design a Web Crawler
HardAsked at: Google, Amazon, Microsoft, Meta
A distributed system that discovers, fetches, and indexes web pages at scale, respecting politeness policies (robots.txt, rate limits). Core challenges: URL frontier management, duplicate detection, distributed coordination, and respectful crawling (not DDoS-ing target sites).
Request flow
Functional Requirements
- Given a seed list of URLs, fetch pages, extract links, and recursively crawl discovered URLs.
- Parse and store page content for downstream indexing/search.
- Respect robots.txt, crawl-delay directives, and avoid overloading any single domain.
- Handle URL normalization and duplicate detection (don't re-crawl the same page).
Non-Functional Requirements
- Scalability: must crawl billions of pages across millions of domains.
- Politeness: limit request rate per domain to avoid being blocked or harming target sites.
- Robustness: handle transient failures, malformed HTML, timeouts, redirects gracefully.
- Freshness: re-crawl pages periodically to detect updates, prioritizing frequently-changing content.
Capacity Estimation
- Target: crawl 1 billion pages/month ≈ ~385 pages/sec average (design for ~4,000 pages/sec peak with burst capacity).
- Average page size ~500KB (HTML + embedded resources) → 1B * 500KB ≈ 500TB/month raw, but we only store parsed/compressed content and metadata, reducing to ~50TB/month.
- URL frontier (queue of pending URLs): billions of URLs at steady state, constantly churning — needs a persistent, distributed queue that can handle high enqueue/dequeue throughput.
- Assume ~10M distinct domains → need per-domain rate-limiting and politeness queues.
Design Walkthrough
1. High-level architecture
URL Frontier: a prioritized, distributed queue of URLs to crawl, partitioned by domain/host to enable per-domain politeness enforcement. Each partition is a FIFO queue for one domain, dequeued by Crawler Workers.
Crawler Workers: stateless fetcher instances that pull URLs from the frontier, fetch the page (HTTP GET), parse HTML, extract links, and enqueue discovered URLs back into the frontier.
Content Store: stores fetched HTML (or parsed/cleaned content) keyed by URL hash — often a distributed object store or a database sharded by URL.
Duplicate Detection: a Bloom filter or a distributed URL-seen cache (keyed by normalized URL hash) to skip URLs already crawled, avoiding infinite loops and redundant work.
Politeness Manager: enforces per-domain crawl rate limits (e.g. 1 req/sec per domain) and robots.txt rules, typically implemented via per-domain locks or leaky-bucket rate limiters.
2. URL Frontier design — the heart of the crawler
Challenge: billions of URLs must be prioritized (crawl important/fresh pages first) while also being grouped by domain for politeness (don't hammer one host with parallel requests).
Solution — two-level queue: a Prioritizer assigns each URL to a priority tier (based on PageRank, historical update frequency, or user-defined importance), and within each tier, URLs are further partitioned by domain into per-domain FIFO queues.
When a worker is ready for work, it picks the highest-priority non-empty domain queue that hasn't been accessed recently (respecting crawl-delay), dequeues a URL, and crawls it. After fetching, the worker waits (or releases the domain lock) for the politeness delay before that domain can be dequeued again.
Persistence: the frontier must survive restarts — typically backed by a distributed queue (Kafka, RabbitMQ) or a fast database (Redis/Cassandra) with sharding by domain hash.
3. Duplicate detection & URL normalization
Normalization: canonicalize URLs before checking duplicates (lowercase host, strip default ports, resolve relative paths, remove tracking params, sort query strings) — otherwise http://example.com, http://EXAMPLE.COM, and http://example.com:80 are treated as different URLs.
Bloom filter: a space-efficient probabilistic set to answer 'have we seen this URL?' with zero false negatives (never misses a duplicate) but rare false positives (might skip a novel URL, acceptable tradeoff for huge memory savings).
Exact deduplication: for critical correctness, back the Bloom filter with a distributed URL-seen database (keyed by hash(normalized_url)) to confirm on Bloom-positive before skipping.
4. Content parsing & link extraction
Parse HTML (handle malformed/broken HTML gracefully with a lenient parser like BeautifulSoup/jsoup), extract <a href> links, resolve relative URLs to absolute, normalize, and enqueue into the frontier.
Extract structured metadata (title, description, publish date) and text content for downstream indexing, discarding boilerplate (ads, nav, footers) using heuristics or a trained model.
Handle redirects (3xx) by following the chain (up to a max depth) and recording the final canonical URL to avoid duplicate content.
5. Politeness & robots.txt compliance
Before crawling any URL from a domain for the first time, fetch and cache robots.txt for that domain. Parse disallow rules and skip forbidden paths.
Respect Crawl-Delay directive (if present) as a per-domain minimum request interval.
Implement a per-domain rate limiter (token bucket or leaky bucket) so even if robots.txt doesn't specify a delay, the crawler self-limits to e.g. 1 req/sec per domain to avoid overloading small sites.
Bottlenecks & Mitigations
- URL frontier throughput: billions of enqueue/dequeue operations → solved by sharding by domain (consistent hashing) and using a fast distributed queue (Kafka for persistence + throughput, or Redis for speed).
- Duplicate detection at scale: a single Bloom filter can't fit billions of URLs in one machine's memory → partition the Bloom filter by URL hash across multiple nodes, each responsible for a keyspace shard.
- Crawler workers overwhelming a small domain → per-domain politeness queues and rate limiting described above prevent this by design.
- Slow/hanging target sites blocking worker threads → workers must use timeouts (e.g. 10s connection, 30s total) and fail fast, moving to the next URL without blocking the fleet.
Likely Follow-Up Questions
- How would you prioritize crawling pages that change frequently (news) vs. static content? (Maintain a 'last_modified' timestamp per URL and re-prioritize based on historical change frequency — adaptive refresh scheduling.)
- How do you handle JavaScript-heavy sites (SPAs) where content is rendered client-side? (Run a headless browser (Puppeteer/Playwright) instead of a simple HTTP fetch — much slower and more resource-intensive, so reserve for a subset of high-value URLs.)
- How do you detect and avoid crawler traps (infinite generated URLs like calendar pages)? (Limit crawl depth per domain, detect URL patterns with incrementing IDs, cap total pages crawled per domain per cycle.)
- How would you distribute the crawler across multiple datacenters globally? (Partition URL frontier by geographic region or domain TLD; crawl .de domains from EU datacenter to reduce latency and respect data locality laws.)