Web Crawler

Problem Statement & Requirements

Functional Requirements

• Given a set of seed URLs, systematically crawl the web by following hyperlinks
• Download and store web page content (HTML, and optionally images/PDFs)
• Discover new URLs from crawled pages and add them to the crawl frontier
• Respect robots.txt and crawl-delay directives (politeness)
• Handle deduplication — don't crawl the same page twice
• Support prioritized crawling (important pages first)
• Re-crawl pages periodically to detect changes

Non-Functional Requirements

• Scalability — crawl billions of pages (the web has ~5 billion indexable pages)
• Throughput — crawl 1,000+ pages/second per worker, 100K+ pages/second cluster-wide
• Politeness — never overload a single web server; respect rate limits
• Robustness — handle malformed HTML, spider traps, infinite loops, timeouts
• Extensibility — pluggable modules for content extraction, URL filtering, storage backends
• Freshness — detect and re-crawl changed pages on a schedule

Out of Scope

• Full-text indexing and search ranking (that's the search engine design)
• Rendering JavaScript-heavy SPAs (requires headless browser — discussed briefly)
• Image/video content analysis

Scale Estimations

Web Scale

Storage

Network

Hardware

This first layer defines the system boundary. The next chapters add application logic and data dependencies. After examining the request paths and tradeoffs, we will add operational safeguards and bring the complete architecture together.

The frontier hands a worker a URL with a lease, host policy, and attempt count. The worker returns a fetch outcome, content reference, and discovered links. Treat a lost acknowledgement as a possible duplicate fetch, not proof that the page was never stored. Keep URL identity and content identity separate: different addresses can serve the same page.

Content Storage

URL Frontier — The Heart of the Crawler

Two-Level Queue Architecture

The frontier must balance two competing goals:

1. Priority — crawl important pages first
2. Politeness — don't hammer any single domain

Priority Calculation

Crawl Workflow — Step by Step

Single Page Crawl Flow

Crawler Worker Internal Pipeline

URL Deduplication

The Challenge

• Billions of URLs to track
• Must check every extracted URL against "already seen" set
• Different URLs can point to the same content

URL-Level Deduplication (Before Fetching)

Content-Level Deduplication (After Fetching)

DNS Resolution

Politeness — robots.txt & Rate Limiting

robots.txt Handling

Per-Domain Rate Limiting

BFS vs DFS Traversal

Distributed Coordination

Partitioning the Crawl Across Workers

Coordination Service (Zookeeper / etcd)

Re-Crawl Strategy (Freshness)

Handling JavaScript-Rendered Pages

Spider Traps & Robustness

Tradeoffs & Design Decisions Summary

Monitoring & Operational Concerns

High-Level Architecture

Detailed Component Architecture

Production Architecture

Try crawling a site with an infinite calendar: every page links to tomorrow. A larger cluster only wastes resources faster. Set a crawl budget, identify repetitive URL patterns, and decide when a new page is worth revisiting. Then introduce a small site that changes hourly and compare the scheduling priorities.

Interview Tips

1. Start with the crawl loop — "Fetch → Parse → Extract URLs → Enqueue → Repeat." Draw this first, then expand each box.

2. Politeness is critical — Interviewers look for this. Show the two-level frontier (priority + per-domain queues), robots.txt caching, and adaptive delays.

3. Deduplication has two layers — URL-level (before fetch, bloom filter) and content-level (after fetch, SHA-256/SimHash). Mention both.

4. Discuss spider traps — This shows real-world awareness. Calendar pages, infinite pagination, and redirect loops are common examples.

5. Partition by domain, not URL — Explain why: politeness enforcement is automatic, DNS cache locality, no distributed rate limiter needed.

6. BFS, not DFS — Quick explanation: BFS discovers high-value pages near the root first. DFS goes deep into one site and misses breadth.

7. Don't forget DNS — A crawler does more DNS lookups than almost any other system. Multi-level caching (in-process → shared → resolver) is essential.

8. Re-crawl strategy — "How do you keep content fresh?" Adaptive scheduling based on change frequency + conditional HTTP requests (If-Modified-Since).

9. Scale the numbers — Walk through: 1B pages/month → 33M/day → 385/second → 1000/s with headroom → 50-100 workers. This shows you can think quantitatively.

10. Mention WARC format — If storage comes up, mentioning the Web ARChive standard shows domain knowledge. "We'd batch pages into WARC files to avoid the small-file problem on HDFS."