System Design Problems
Design a Web Crawler
A web crawler systematically discovers and downloads web pages from the internet. Search engines like Google use crawlers to discover billions of pages, respecting robots.txt, managing politeness, and handling the enormous scale of the web.
- Discovery â Find new pages by following links from known pages
- Politeness â Respect crawl rate limits and robots.txt directives
- Freshness â Recrawl pages periodically to detect changes
The web has over 4 billion pages. A crawler must be distributed, polite, and fault-tolerant while discovering new content efficiently and avoiding duplicate work.
Requirements
Functional Requirements
- Crawl web pages starting from a set of seed URLs
- Extract links from pages and discover new URLs
- Respect robots.txt and crawl rate limits
- Store crawled content for indexing
- Recrawl pages based on change frequency
- Support priority-based crawling (important pages first)
Non-Functional Requirements
- Throughput: Crawl 1 billion pages per day
- Politeness: Max 1 request/second per domain
- Freshness: High-priority pages recrawled every 24 hours
- Robustness: Handle malformed HTML, timeouts, and failures
- Scalability: Horizontal scaling across thousands of machines
Back-of-the-Envelope Estimation
API Design
POST /api/v1/crawl/submit
Request: { "urls": ["https://..."], "priority": "high" }
Response: { "job_id": "j_123", "status": "queued" }
GET /api/v1/crawl/status/{job_id}
Response: { "status": "running", "pages_crawled": 50000, "errors": 120 }
GET /api/v1/crawl/robots/{domain}
Response: { "allow": ["/"], "disallow": ["/admin"], "crawl_delay": 1 }
High-Level Architecture
Detailed Design
URL Frontier
The URL frontier is a priority queue that manages URLs to be crawled:
| Component | Purpose |
|---|---|
| Priority Queue | Order URLs by importance (PageRank, freshness) |
| Politeness Queue | Per-domain queues with crawl delay enforcement |
| URL Dedup Set | Bloom filter or set to avoid re-crawling |
| DNS Resolver Cache | Cache DNS lookups to reduce DNS load |
Politeness
Respect website crawl rate limits:
URL Deduplication
Avoid crawling the same page twice:
Politeness Queue Design
Use a per-domain queue with a delay queue:
- Hash each URL to its domain
- Place URL in the domain's queue
- Domain queue has a timer enforcing crawl_delay
- When timer fires, dequeue next URL and fetch
Practice Exercises
-
Design: How would you handle JavaScript-rendered pages (SPAs) that require a headless browser to render? What are the resource implications?
-
Scale: If the crawler needs to crawl 1 billion pages per day across 1000 machines, estimate the network bandwidth required and the per-machine crawl rate.
-
Freshness: Design a recrawl scheduling algorithm that adapts to page change frequency. How would you prioritize recrawling?
-
Robustness: How would you handle a crawler trap (infinite URL space, recursive redirects)? Design detection and mitigation mechanisms.
What to Learn Next
-> Design Search Engine Inverted indices, relevance ranking, and search infrastructure.
-> Design Web Crawler This article (web crawler design deep dive).
-> Message Queues Async task distribution for crawl workers.
-> Rate Limiting Politeness and per-domain rate limiting strategies.
-> Databases Storing crawled content and URL metadata.
-> Caching Strategies DNS caching and robots.txt caching.