System Design: Design a Web Crawler at Scale

A web crawler systematically browses the internet, downloading pages and extracting links to discover new content. Search engines like Google crawl billions of pages daily. The core challenge is doing this efficiently, politely, and without getting stuck in infinite loops or duplicate content.

Functional Requirements

• Given a set of seed URLs, crawl the web breadth-first.
• Download HTML content and extract outgoing links.
• Store downloaded pages for indexing or analysis.
• Respect robots.txt rules for each domain.
• Handle URL deduplication — don’t crawl the same page twice.
• Support re-crawling pages that change frequently.

Non-Functional Requirements

• Scale to crawl 1 billion pages per day (~12,000 pages/second).
• Politeness: no more than 1 request per second per domain.
• Distributed: run across hundreds of worker machines.
• Fault tolerant: resume crawling after worker failures.
• Extensible: support different content types (HTML, PDF, images).

High-Level Architecture

Seed URLs
│
▼
┌─────────────────┐
│   URL Frontier   │  (priority queues + politeness queues)
│   (distributed)  │
└────────┬────────┘
│
┌────┴────┐
▼         ▼
┌────────┐ ┌────────┐
│Worker 1│ │Worker N│   (fetch, parse, extract links)
└───┬────┘ └───┬────┘
│          │
▼          ▼
┌─────────────────┐
│  Content Store   │  (S3 / distributed file system)
└─────────────────┘
│
▼
┌─────────────────┐
│  URL Seen Filter │  (Bloom filter + DB)
└─────────────────┘

The URL Frontier

The frontier is the most critical component — it determines what to crawl next. It has two concerns:

Priority: important pages (high PageRank, news sites, frequently updated) should be crawled first. Use multiple priority queues; a prioritizer assigns each URL to a queue based on signals like domain authority or update frequency.

Politeness: never overwhelm a single domain. Group URLs by domain into per-domain FIFO queues. A scheduler ensures at most one request per domain within a configurable time window (typically 1 second).

Priority Queues:         Politeness Queues:
┌─── High ───┐          ┌─── example.com ───┐
│ url1, url4  │    →     │ url1, url5         │
├─── Medium ──┤          ├─── blog.org ───────┤
│ url2, url5  │    →     │ url2               │
├─── Low ─────┤          ├─── news.site ──────┤
│ url3, url6  │    →     │ url3, url4, url6   │
└─────────────┘          └────────────────────┘

A URL passes through priority selection first, then enters the appropriate politeness queue.

Worker Pipeline

Each worker executes this pipeline:

1. Fetch: download the page via HTTP. Handle redirects (follow up to 5), timeouts (10 seconds), and retries (exponential backoff).
2. Parse: extract text content and metadata. Use a robust HTML parser that handles malformed markup.
3. Link extraction: find all <a href> links, resolve relative URLs to absolute, normalize (lowercase domain, remove fragments, sort query params).
4. URL filtering: discard URLs matching blocked patterns (login pages, calendars that generate infinite URLs, file types you don’t want).
5. Dedup check: query the URL-seen filter. If new, add to the frontier.
6. Store: write the downloaded content to the content store with metadata (URL, timestamp, HTTP headers, content hash).

URL Deduplication

At 1 billion pages, a naive hash set won’t fit in memory. Two-layer approach:

Bloom filter (in-memory): a probabilistic filter with ~1% false positive rate. Uses about 1 GB of RAM for 1 billion URLs. If the Bloom filter says “not seen,” the URL is definitely new. If it says “maybe seen,” check the database.

Persistent store (on-disk): a database or sorted file of URL hashes. Only queried for Bloom filter positives.

Content Deduplication

Different URLs can serve identical content (mirrors, URL parameters that don’t change content). Compute a content fingerprint using SimHash or MinHash — these detect near-duplicate content, not just exact matches.

URL: /page?utm_source=twitter  →  content hash: 0xABCD1234
URL: /page?utm_source=email    →  content hash: 0xABCD1234
→ Same content, skip the second crawl

Robots.txt and Politeness

Before crawling any page on a domain, fetch and cache its robots.txt. Respect Disallow directives and Crawl-delay headers. Cache robots.txt per domain with a TTL (typically 24 hours).

Rate limiting is critical for being a good citizen. Maintain a per-domain timestamp of the last request and enforce minimum intervals.

DNS Resolution

At 12,000 pages/second, DNS lookups become a bottleneck. Run a local DNS cache (like dnsmasq) on each worker machine and batch DNS prefetching for URLs in the frontier.

Scaling the Crawler

Partition by domain hash: assign each domain to a specific set of workers using consistent hashing. This ensures politeness is enforced locally (one worker handles example.com) and keeps the per-domain state on a single machine.

Checkpointing: periodically save the frontier state and Bloom filter to durable storage. On worker failure, another worker picks up from the last checkpoint.

Monitoring: track pages crawled per second, error rates by type (timeout, 404, 503), frontier size, and domain queue depths. Alert on drops in crawl rate.

Handling Traps

Spider traps generate infinite URLs — calendars with infinite future dates, session IDs in URLs, or dynamically generated content. Mitigations:

• Cap the URL length (e.g., 2048 characters).
• Cap the crawl depth per domain (e.g., 15 levels deep).
• Detect and throttle domains producing an abnormal number of unique URLs.
• Use URL pattern detection to identify parameterized duplicates.

Interview Tips

• Draw the frontier as the centerpiece and explain priority vs politeness separately.
• Mention Bloom filters for URL dedup — it shows you think about memory at scale.
• Discuss robots.txt compliance without being asked — it shows maturity.
• If asked about re-crawling, explain that pages get different re-crawl intervals based on how frequently they change (news = hours, Wikipedia = days, static pages = weeks).
• The politeness constraint is the bottleneck, not bandwidth. 1 req/sec/domain means you need many domains in your frontier to keep workers busy.