Design a Web Crawler

A web crawler collects web pages and follows links to discover new content. Use cases: search engine indexing, web archiving, web mining, web monitoring.

Step 1 of 4: Understand the problem and establish design scope #

Goal: lock in requirements and scale numbers.

Requirements:

1. Purpose: search engine indexing
2. 1 billion pages/month, HTML only
3. Consider newly added/edited pages
4. Store HTML pages for 5 years
5. Ignore duplicate content pages

Key characteristics of a good crawler:

1. Scalability: parallelized crawling of billions of pages
2. Robustness: handle bad HTML, unresponsive servers, crashes, malicious links
3. Politeness: don't overwhelm a single host with rapid requests
4. Extensibility: easy to add support for new content types (images, etc.)

Back of the envelope estimation:

1. QPS: 1B / 30 days / 24h / 3600s = ~400 pages/s
2. Peak QPS: 2× = 800 pages/s
3. Avg page size: 500 KB → 500 TB/month
4. 5-year storage: 500 TB × 12 × 5 = 30 PB

Step 2 of 4: Propose high-level design and get buy-in #

Goal: agree on the pipeline and each component's job.

Components:

1. Seed URLs: starting points. Divide URL space by locality (country) or topic
2. URL Frontier: FIFO queue storing URLs to be downloaded
3. HTML Downloader: downloads pages via HTTP; uses DNS Resolver for IP resolution
4. Content Parser: validates and parses downloaded HTML pages (separate component to avoid slowing crawls)
5. Content Seen?: eliminates duplicate content (~29% of web is duplicated). Uses hash comparison for efficiency
6. Content Storage: disk for bulk data, memory for popular content
7. URL Extractor: parses links from HTML; converts relative paths to absolute URLs
8. URL Filter: excludes blacklisted sites, unwanted file types, error links
9. URL Seen?: tracks already-visited URLs using Bloom filter or hash table to avoid infinite loops

Workflow:

1. Add seed URLs to URL Frontier
2. HTML Downloader fetches URLs from Frontier → DNS resolution → download
3. Content Parser validates HTML
4. Content Seen? checks for duplicates → discard if duplicate
5. URL Extractor extracts links → URL Filter → URL Seen? → add new URLs to Frontier

Step 3 of 4: Design deep dive #

Goal: the URL frontier, downloader optimizations, robustness, and traps.

DFS vs BFS #

• DFS can go infinitely deep → not suitable
• BFS (FIFO queue) is standard, but has problems:
  1. Many links point to the same host → floods that host (impolite)
  2. Doesn't prioritize URLs by importance (PageRank, traffic, update frequency)

URL Frontier (solves BFS problems) #

Politeness: one page at a time per host. Implemented via:

1. Queue router ensures each FIFO queue has URLs from only one host
2. Mapping table: host → queue
3. Each worker thread bound to one queue, downloads with a delay between requests

Priority: prioritizer computes URL usefulness (PageRank, traffic, update frequency). High-priority queues selected with higher probability.

Full URL Frontier design:

1. Front queues: manage prioritization
2. Back queues: manage politeness

Freshness: recrawl based on update history; prioritize important pages.

Storage for URL Frontier: hybrid: majority on disk, buffers in memory for enqueue/dequeue. Hundreds of millions of URLs.

HTML Downloader #

Robots.txt (Robots Exclusion Protocol): check before crawling to see allowed/disallowed paths. Cache results to avoid repeated downloads.

Performance optimizations:

1. Distributed crawl: partition URL space across multiple servers with consistent hashing
2. Cache DNS Resolver: DNS latency 10–200ms; maintain cached domain→IP mapping updated by cron jobs
3. Locality: place crawl servers geographically close to website hosts
4. Short timeout: avoid hanging on slow/unresponsive servers

Robustness #

1. Consistent hashing: distribute load, allow adding/removing downloaders
2. Save crawl states and data: restart interrupted crawls from saved state
3. Exception handling: graceful error handling without crashes
4. Data validation: prevent system errors

Extensibility #

Plug in new modules (PNG Downloader, Web Monitor) without rearchitecting.

Detect and avoid problematic content #

1. Redundant content: detect duplicates using hashes/checksums
2. Spider traps: infinite loops (e.g. endless directory nesting). Mitigate with URL max length; manual verification for known traps
3. Data noise: exclude ads, code snippets, spam URLs: little value for indexing

Step 4 of 4: Wrap up #

Additional talking points:

1. Server-side rendering: execute JavaScript to capture dynamically generated links
2. Anti-spam filters: filter low-quality/spam pages
3. Database replication and sharding
4. Horizontal scaling: keep servers stateless
5. Availability, consistency, reliability (Ch.1)
6. Analytics: data collection for fine-tuning