Designing a Web Crawler

Like explaining to a 5-year-old: Imagine you want to read every book in every library in the world. You start with one book, and at the end of each book there’s a list of other books it references. You write those down, then go find each one. Each new book gives you more references. You keep following the trail until you’ve visited every book. That’s a web crawler — it follows links from page to page until it’s seen the whole web.

Google crawls billions of pages continuously. The web is a directed graph of ~60 trillion pages. Traversing this graph efficiently, politely, and without duplicating work is a fascinating systems problem that blends distributed computing, scheduling, and data deduplication.

Requirements

Functional

• Start from a set of seed URLs
• Download each page’s HTML
• Extract new links and add them to the crawl queue
• Store page content and metadata for indexing
• Respect robots.txt and crawl-delay directives
• Handle redirects, dead links, and malformed HTML

Non-Functional

• Scale: crawl 1 billion pages in one month (~400 pages/second sustained)
• Politeness: no more than 1 request per domain per 5 seconds
• Deduplication: don’t crawl the same page twice (URLs can be the same under different canonical forms)
• Freshness: re-crawl popular pages more frequently than obscure ones
• Fault tolerance: crawler workers can die; queue state must be persistent

Capacity Estimation

Metric	Value
Target	1B pages / month
Required throughput	~400 pages/sec
Avg page size	100 KB
Total download	~100 TB/month
Extracted links per page (avg)	~50
New unique links to process/sec	~20,000

400 pages/second means you need hundreds of crawler workers. URL deduplication across 1B URLs requires careful data structure selection.

High-Level Architecture

Seed URLs
    │
    ▼
┌──────────────────┐
│   URL Frontier   │  ← priority queue of URLs to crawl
│   (distributed)  │
└────────┬─────────┘
         │ pop next URL
         ▼
┌──────────────────┐
│  Crawler Workers │  ← hundreds of worker processes
│  (stateless)     │
└────────┬─────────┘
         │ fetched HTML
    ┌────┴──────────────────────────┐
    │                               │
    ▼                               ▼
┌────────────────┐        ┌──────────────────┐
│  Content Store │        │   Link Extractor │
│  (S3 / HDFS)   │        │   + Deduplicator │
└────────────────┘        └────────┬─────────┘
                                   │ new unique URLs
                                   ▼
                          ┌──────────────────┐
                          │   URL Frontier   │  ← back into the queue
                          └──────────────────┘

URL Frontier Design

The frontier is the heart of the crawler. It needs to:

1. Prioritize: crawl important pages first (high PageRank, news sites, sitemaps)
2. Be polite: don’t hit the same domain twice within 5 seconds
3. Be persistent: survive worker crashes

The DMV analogy: Imagine a waiting room with different lines for different services. The “driver’s license” line (important pages) moves faster than the “address change” line (obscure blog posts). A rule says each counter (domain) can only serve one customer at a time every few seconds. The frontier is this scheduling system.

Two-tier queue design

Front Queues (priority-based):
  Queue F1 (high priority): news.ycombinator.com, nytimes.com, ...
  Queue F2 (medium priority): medium.com/*, github.com/*, ...
  Queue F3 (low priority): random blogs, old pages, ...

Back Queues (one per domain, politeness-enforced):
  Queue B1: all pending URLs for nytimes.com
  Queue B2: all pending URLs for github.com
  ...

Selector:
  For each free worker:
    1. Pick a front queue (weighted by priority)
    2. Pop a URL from it
    3. Route to the correct back queue for that domain
    4. Only release a URL from back queue if domain's last-crawl > 5s ago

This guarantees politeness per domain while maximizing throughput across many domains.

URL Deduplication

The biggest challenge: with 1B pages crawled and 20K new URLs/second, how do you know if a URL has been seen before without storing all 1B URLs in memory?

Option A: HashSet in distributed cache

seen = Redis SET
if redis.SADD(seen, url) == 0:
    # already exists, skip

Problem: 1B URLs × ~50 bytes each = ~50 GB in Redis. Expensive but feasible.

Option B: Bloom Filter (Recommended)

The bouncer analogy: A nightclub has a list of banned guests. Instead of a huge printed list (slow to check), the bouncer memorizes a pattern: “if their name creates a certain sound when spoken, they might be on the list — go check the real list.” That pattern-matching is a Bloom filter — fast, uses little memory, but might have false positives.

A Bloom filter is a probabilistic data structure that can say:

• “This URL has definitely NOT been seen” (no false negatives)
• “This URL has PROBABLY been seen” (small false positive rate)

For 1B URLs with 1% false positive rate, a Bloom filter uses only ~1.2 GB — vs 50 GB for a hash set.

from pybloom_live import BloomFilter

# 1B items, 0.1% false positive rate → ~1.7 GB
seen = BloomFilter(capacity=1_000_000_000, error_rate=0.001)

def is_new_url(url: str) -> bool:
    normalized = normalize(url)  # lowercase, strip params, canonical form
    if normalized in seen:
        return False  # probably seen (0.1% false positive)
    seen.add(normalized)
    return True

False positives just mean you occasionally skip a valid URL — acceptable for crawling.

URL Normalization

Two URLs can point to the same page:

http://example.com/page
https://www.EXAMPLE.com/page?
https://example.com/page#section  ← same content, different fragment

Normalize before deduplication:

1. Lowercase scheme and host
2. Remove default port (:80, :443)
3. Remove fragment (#...)
4. Sort query parameters alphabetically
5. Remove tracking parameters (utm_source, fbclid, etc.)
6. Resolve relative URLs

Politeness and robots.txt

Every crawler must respect robots.txt:

# https://example.com/robots.txt
User-agent: *
Disallow: /private/
Disallow: /api/
Crawl-delay: 10

User-agent: Googlebot
Allow: /
Crawl-delay: 2

Cache robots.txt per domain for 24 hours. Before crawling any URL, check the cache.

Crawl-delay is a polite request: wait N seconds between requests to this domain. Honor it — hammering a site is unethical and will get your IP banned.

Content Deduplication

Different URLs can have identical content (mirrors, syndication). Store a hash of the content and skip re-processing duplicates.

def process_page(url: str, html: str):
    content_hash = sha256(html.encode()).hexdigest()

    if content_store.exists(content_hash):
        # canonical URL for this content is already indexed
        content_store.add_alias(url, content_hash)
        return

    content_store.store(content_hash, html, url)
    # proceed to extract links and index

Crawl Scheduling: Fresh vs Stale

Not all pages need to be crawled at the same frequency. News homepages change every minute; a Wikipedia article from 2008 might not change for years.

Freshness model: track last-modified time (from HTTP headers) and re-crawl interval per URL:

def next_crawl_time(url_record) -> datetime:
    change_rate = estimate_change_rate(url_record.history)
    if change_rate > 100:   # changes many times/day
        return now + timedelta(hours=1)
    if change_rate > 1:     # changes daily
        return now + timedelta(days=1)
    return now + timedelta(weeks=2)

Priority = f(importance, staleness). High-importance + stale = crawl next.

Handling Failures

Worker crashes: URL frontier is persistent (Kafka or Redis Streams). A URL is only removed from the queue after the worker confirms successful processing (ack). If the worker crashes, the URL is re-queued after a timeout.

Trap pages: some websites generate infinite URLs (calendars, search result pages with arbitrary parameters). Detect: if URL depth > 20, skip. Track URL path components — if same pattern repeats (e.g. /date/2024/01/01/date/2024/01/02/...), it’s a trap.

Slow sites: use connection timeouts (5s connect, 30s read). A slow domain should not block crawler workers.

Trade-offs & Decisions

Decision	Choice	Reason
URL deduplication	Bloom filter	50x smaller than hash set; 0.1% false positive is acceptable
Frontier	Two-tier priority queue	Politeness + priority simultaneously without complex locking
Content storage	S3/HDFS	Cheap, durable, scales to petabytes
Scheduling	Change-rate-based	Crawl budget is finite; spend it on frequently-changing pages
Fault tolerance	Persistent queue (Kafka)	Worker crashes don’t lose URLs

---

A web crawler looks like a simple BFS loop but hides deep complexity: you’re building a system that must be fast, polite, fair, and correct simultaneously across billions of URLs and thousands of machines. The URL frontier scheduler is where the real system design lives.