Chapter 69: Design Web Crawler

Requirements

Functional Requirements

• Crawl billions of pages: Must handle massive scale (billions of web pages)
• Politeness: Respect robots.txt, rate limits, and crawl-delay directives
• Freshness: Re-crawl pages based on update frequency to keep index fresh
• Deduplication: Avoid crawling duplicate URLs and storing duplicate content
• Content extraction: Parse HTML, extract links, store content
• Prioritization: Crawl important pages first (PageRank, domain authority)

Non-Functional Requirements

• Scalability: Handle billions of pages, petabytes of data
• Reliability: Handle failures gracefully, resume interrupted crawls
• Extensibility: Support multiple content types (HTML, PDF, images)
• Performance: High throughput while respecting politeness constraints

High-Level Design

Core Components

1. Seed URLs

Starting point for the crawler. High-quality seeds lead to better crawl coverage. Sources: popular domains, site directories, previously crawled URLs.

2. URL Frontier

Queue of URLs to be crawled. Manages both priority (important pages first) and politeness (rate limiting per domain). Hybrid data structure combining priority queue and per-domain queues.

3. Fetcher Pool

Worker threads that download web pages. Each fetcher checks DNS cache, robots.txt, applies rate limits, and handles HTTP requests. Typically 100-1000 parallel fetchers.

4. HTML Parser

Extracts links from downloaded pages, normalizes URLs, and extracts content for storage. Validates HTML and handles malformed pages gracefully.

5. URL Filter

Applies rules to determine which URLs to crawl: blacklist (spam, malicious sites), file type filters (skip .exe, .zip unless needed), URL normalization (remove tracking parameters).

6. Content Store

Distributed storage system (S3, HDFS) for crawled content. Typically compressed and deduplicated. Supports both archival and fast retrieval for indexing.

URL Frontier

Architecture

The URL Frontier is the heart of the crawler, managing which URLs to crawl next. It must balance two competing goals:

• Priority: Crawl important pages first (PageRank, freshness, domain authority)
• Politeness: Avoid hammering the same domain (rate limiting, crawl-delay)

Two-Layer Queue System

Layer 1: Priority Queues (Front Queues)

URLs are assigned priority scores (0-100) based on:

• PageRank or domain authority
• Time since last crawl (freshness)
• Content change frequency
• User-defined rules (news sites get higher priority)

URLs are distributed into N priority buckets (e.g., 5 buckets: 90-100, 70-90, 50-70, 30-50, 0-30).

Layer 2: Politeness Queues (Back Queues)

Each queue corresponds to a single domain (or IP address). This ensures URLs from the same domain are crawled sequentially with delays, never in parallel.

• One queue per domain (e.g., queue for example.com, queue for site.org)
• Each queue has a minimum delay between requests (from robots.txt crawl-delay or default 1-2 seconds)
• Selector uses round-robin to pick from domain queues, ensuring fairness

BFS vs DFS

Recommendation: Use BFS for general web crawling. It naturally discovers high-quality pages first and provides better coverage.

Politeness

Why Politeness Matters

A poorly designed crawler can overwhelm target servers, causing:

• Server crashes or degraded performance
• IP bans or rate limiting by target sites
• Legal issues (violating terms of service)
• Wasted resources (getting blocked after initial requests)

Politeness Mechanisms

1. Robots.txt

Standard protocol where websites specify crawl rules in /robots.txt:

User-agent: *
Disallow: /admin/
Disallow: /private/
Crawl-delay: 2

User-agent: Googlebot
Crawl-delay: 1

• Disallow: Paths that should not be crawled
• Crawl-delay: Minimum seconds between requests
• Cache robots.txt files (TTL: 1 day) to avoid fetching on every request
• Respect the rules for your user-agent identifier

2. Rate Limiting Per Domain

Implement token bucket or leaky bucket algorithm per domain:

• Default: 1-2 requests per second per domain
• Override with crawl-delay from robots.txt
• Track last request time per domain in Redis or in-memory cache
• Use domain-level queues (back queues) to enforce delays naturally

3. DNS Caching

Cache DNS lookups (TTL: 1 hour) to reduce load on DNS servers. DNS queries can become a bottleneck at scale.

4. User-Agent Identification

Always identify your crawler with a descriptive User-Agent header and contact information:

User-Agent: MyCrawler/1.0 (+http://example.com/bot.html; bot@example.com)

Deduplication

Deduplication is critical for efficiency. Without it, the crawler would waste resources re-crawling the same pages and storing duplicate content.

1. URL Deduplication

Prevent crawling the same URL multiple times:

Bloom Filter

• How it works: Probabilistic data structure that tests set membership. Can have false positives (thinks URL was seen when it wasn't) but never false negatives.
• Space efficiency: 10 billion URLs ~ 1.2 GB (0.1% false positive rate)
• Usage: Quick first-pass check. If Bloom filter says "not seen", definitely add to frontier. If it says "seen", do secondary check.

Secondary Check

For URLs that pass Bloom filter, check authoritative data store:

• Hash set in distributed cache (Redis cluster)
• Database with indexed URL column
• Only needed for false positives from Bloom filter (rare)

URL Normalization

Before deduplication, normalize URLs to canonical form:

• Convert scheme and host to lowercase: HTTP://EXAMPLE.COM → http://example.com
• Remove default ports: http://example.com:80/ → http://example.com/
• Remove fragment identifiers: page.html#section → page.html
• Remove tracking parameters: page?utm_source=x&id=1 → page?id=1
• Resolve relative URLs to absolute

2. Content Deduplication

Detect duplicate or near-duplicate content (copied pages, mirrors):

SimHash (Recommended)

• How it works: Generates 64-bit fingerprint where similar documents have similar fingerprints (Hamming distance)
• Process: Tokenize content → Weight tokens (TF-IDF) → Hash each token → Merge into fingerprint
• Comparison: If Hamming distance between two fingerprints ≤ 3, content is near-duplicate
• Scalability: Can index billions of fingerprints, fast lookup

MinHash

• How it works: Estimates Jaccard similarity between document sets
• Use case: Better for finding similar documents for clustering, not exact deduplication

Checksum (MD5/SHA-256)

• Use case: Exact duplicate detection only (same byte-for-byte content)
• Limitation: Misses near-duplicates (e.g., page with added ad is considered different)

Distributed Crawling

Why Distribute?

Single-machine crawlers hit limits around 1-10 million pages. For billions of pages, you need horizontal scaling.

Partitioning Strategy

Domain-Based Partitioning (Recommended)

• Method: Hash domain name → assign to worker node. All URLs from example.com go to same worker.
• Advantage: Politeness is local to each worker (no coordination needed for rate limiting). Worker maintains its own per-domain queues.
• Challenge: Load imbalance if few domains have majority of pages (use consistent hashing to mitigate)

URL-Based Partitioning

• Method: Hash full URL → assign to worker
• Advantage: Better load distribution
• Challenge: Politeness requires coordination (workers must communicate to rate limit per domain)

Architecture

Components

1. Coordinator

• Assigns domain ranges to workers (consistent hashing)
• Monitors worker health (heartbeats)
• Reassigns work if worker fails
• Provides seed URLs and priority signals

2. Workers

• Each worker is a mini-crawler (frontier, fetcher, parser)
• Responsible for assigned domain range
• Writes crawled content to shared storage
• Publishes extracted URLs to distributed queue

3. Distributed Queue (Kafka/SQS)

• When worker finds URL for domain it doesn't own, publishes to queue
• Other workers consume URLs for their assigned domains
• Decouples workers, enables fault tolerance

4. Shared Metadata DB

• Tracks URL status (pending, crawled, failed), last crawl time, priority
• Distributed database (Cassandra, DynamoDB) partitioned by URL hash
• Workers query to check if URL already crawled, update after crawl

Freshness

The Challenge

Web content changes constantly. News sites update every minute, blogs weekly, archived pages never. A one-time crawl quickly becomes stale.

Re-Crawl Strategy

1. Prioritize by Change Frequency

Track how often each page changes and adjust re-crawl frequency:

• High frequency (news, social media): Re-crawl hourly or daily
• Medium frequency (blogs, product pages): Re-crawl weekly
• Low frequency (documentation, archived content): Re-crawl monthly

2. Change Detection

Detect if page has changed since last crawl:

• HTTP Headers: Check Last-Modified or ETag. If unchanged, skip download (HTTP 304 Not Modified).
• Content Hash: Compare hash of new content with stored hash. If same, no update needed.
• SimHash Comparison: Detect significant changes vs minor edits (ads, timestamps)

3. Historical Analysis

Learn change patterns from history:

• If page changed every time in last 10 crawls, likely high-frequency update
• If page unchanged for 6 months, reduce re-crawl frequency
• Use machine learning to predict optimal re-crawl schedule

4. Sitemap and RSS

• Sitemap.xml: Websites provide list of URLs with last modification dates and change frequency hints
• RSS/Atom feeds: Subscribe to feeds for real-time updates (news, blogs)
• Use these as priority signals to crawl updated pages first

Priority Formula

Combine multiple signals to compute re-crawl priority:

priority = (changeFrequency * 0.4) +
           (pageImportance * 0.3) +
           (timeSinceLastCrawl * 0.2) +
           (userDemand * 0.1)

Scalability

Scale Calculations

Scenario: Crawl 1 billion web pages per month

• 1 billion pages / 30 days = 33 million pages/day
• 33 million / 86,400 seconds = ~380 pages/second
• Assuming 100 KB average page size: 380 * 100 KB = 38 MB/second = ~300 Mbps bandwidth
• Storage: 1 billion * 100 KB = 100 TB/month (before compression)

Bottlenecks and Solutions

1. Network Bandwidth

• Problem: 300+ Mbps continuous bandwidth required
• Solution: Distribute workers across multiple data centers, use CDN endpoints when available, compress content during transfer

2. DNS Resolution

• Problem: Millions of DNS queries can overwhelm resolvers
• Solution: Aggressive DNS caching (1-24 hour TTL), run local DNS resolver cluster, pre-resolve common domains

3. URL Frontier Size

• Problem: Frontier can grow to billions of URLs (100+ GB in memory)
• Solution: Hybrid frontier - hot URLs in memory (Redis), cold URLs on disk (RocksDB), lazy load from disk to memory

4. Storage

• Problem: 100+ TB/month, petabytes total
• Solution: Distributed object storage (S3, HDFS), compress content (gzip, brotli), deduplicate aggressively, tier old content to cold storage (Glacier)

5. Deduplication at Scale

• Problem: Bloom filter for 10 billion URLs = 1.2 GB, but needs to fit in memory across all workers
• Solution: Partition Bloom filter (each worker maintains filter for its domain range), use distributed cache (Redis cluster) for authoritative dedup checks

Fault Tolerance

• Worker Failures: Coordinator detects via heartbeat, reassigns domain range to healthy worker, worker pulls pending URLs from metadata DB
• Checkpoint Progress: Workers periodically checkpoint frontier state to disk/DB, resume from checkpoint after crash
• Idempotent Operations: Re-crawling a URL is safe, metadata updates are conditional (only update if timestamp is newer)

Monitoring

• Throughput: Pages crawled per second per worker
• Frontier Size: URLs pending (should be stable, not growing unbounded)
• Error Rates: HTTP errors, timeouts, DNS failures per domain
• Politeness Violations: Track if any worker exceeds rate limits
• Freshness: Average age of crawled content

Interview Summary

Key Talking Points

1. URL Frontier: Two-layer design (priority + politeness queues) is the core pattern
2. Politeness: Robots.txt, rate limiting, domain-based partitioning
3. Deduplication: Bloom filter (URL) + SimHash (content)
4. Distributed Crawling: Domain-based partitioning, consistent hashing, Kafka for URL routing
5. Freshness: Adaptive re-crawl based on change frequency and importance

Common Follow-Up Questions

• How do you handle JavaScript-rendered pages? Headless browser (Puppeteer, Playwright) or specialized service. Adds latency and cost.
• How do you detect spam or malicious sites? Blacklists, reputation scores, content analysis (ML classifiers).
• How do you handle redirects? Follow up to N redirects (e.g., 5), track redirect chains to avoid loops, normalize final URL.
• How do you prioritize which pages to crawl first? PageRank, backlink count, domain authority, sitemap priority hints, user engagement signals.
• How do you handle rate limiting or getting blocked? Respect 429 responses, exponential backoff, rotate IP addresses (proxy pool), identify as legitimate crawler.