📁 topics / 12-web-crawler.md

#Design a Web Crawler (Search Engine Scale)

#1. Problem Statement & Clarifications

A Web Crawler is an automated system that systematically browses the World Wide Web to discover, download, and index web pages. In this design, we focus on a crawler built for a search engine like Google.

#Functional Requirements

  1. Discovery & Crawling: The system must crawl seed URLs, parse HTML pages, extract outbound links, and recursively add new URLs to the crawl frontier.
  2. Content Extraction: Extract page metadata (title, meta tags) and raw text body for downstream search indexing.
  3. Link Extraction: Extract all links (<a href="...">) to build a link graph for page ranking algorithms (e.g., PageRank).
  4. Deduplication: Avoid crawling duplicate URLs and parsing duplicate or near-duplicate web page content.
  5. Politeness (Robots.txt): Strict adherence to robots.txt files, crawl delays, and rate limiting per domain to avoid causing Denial of Service (DoS) on host servers.

#Non-Functional Requirements

Requirement Target
Scale 1 Billion web pages crawled and updated per month.
Throughput (QPS) ~386 pages/sec average crawl rate, with peak handling up to ~1,000 pages/sec.
Storage Handle petabyte-scale data for raw web pages and link graphs.
Extensibility Support different file types (.html, .pdf) and dynamic content rendering.
Robustness Handle dead loops (crawler traps), DNS timeouts, and malformed HTML gracefully.

#Out of Scope

#Assumptions

#2. Back-of-Envelope Estimation

To design the system, we calculate the requirements for bandwidth, storage, memory, and compute.

#Traffic Estimates

Monthly crawled pages: 1B
Crawl rate (avg):      1,000,000,000 / (30 days * 86,400s) ≈ 386 pages/sec
Crawl rate (peak 2x):  ~800 - 1000 pages/sec
Discovered URLs/sec:   386 pages/sec * 50 links/page (avg) ≈ 19,300 URLs/sec (discovery QPS)

#Storage Estimates

Avg Page Size:         100 KB
Raw Storage/month:     1B * 100 KB = 100 TB
Raw Storage/5 years:   100 TB * 12 months * 5 years = 6 PB (Object Store / Cold Storage)

Metadata Database (Cassandra/HBase):
URL record size:       URL string (~100B) + hash (32B) + status (1B) + last_crawl_time (8B) ≈ 150 bytes
Discovered URLs (5yr): 50 Billion URLs
Metadata storage:      50B * 150 bytes = 7.5 TB (distributed DB storage)

#Bandwidth Estimates

Download bandwidth:    386 pages/sec * 100 KB = 38.6 MB/s (or ~310 Mbps)
Peak bandwidth (2x):   80 MB/s (or ~640 Mbps)

#Cache & Memory Estimates

DNS Cache:             10M domains. Hostname (30B) + IP (4B) = 34B per domain. 
                       10M * 34B ≈ 340 MB memory.
Robots.txt Cache:      1M active domains. Avg size 1 KB.
                       1M * 1 KB = 1 GB memory.
Bloom Filter (URL):    Target capacity n = 50B URLs, false positive rate p = 1% (0.01).
                       Bit array size m = - (n * ln p) / (ln 2)^2 ≈ 478 Billion bits ≈ 60 GB RAM.

#3. API Design

The web crawler components communicate via RPC/Internal HTTP endpoints to minimize overhead.

#Worker to DNS Resolver / Cache

resolve_domain(host_name) -> IP Address

#Worker to Robots.txt Parser / Cache

is_allowed(url, user_agent) -> Boolean

#URL Frontier Interface

get_next_urls(worker_id, batch_size) -> List[URL]
ack_url(url, status_code, crawl_duration) -> Void

#Content Parser to Deduplicator

check_and_register_content(document_hash) -> Boolean (True if unique, False if duplicate)

#4. Data Model

A web crawler requires highly scalable storage that handles write-heavy workflows.

#1. URL Frontier & Metadata Store (Cassandra — sharded by Domain Hash)

We use a wide-column store like Apache Cassandra or HBase because they scale horizontally for high-throughput writes and allow efficient lookups by domain.

Table: crawled_urls
Partition Key: domain_hash (UUID)
Sort Key:      url_hash (UUID)

{
  domain_hash:      "8f7c9e...",
  url_hash:         "1a2b3c...",
  url_string:       "https://example.com/page1",
  status:           "CRAWLED | FAILED | PENDING",
  http_code:        200,
  last_crawled_at:  1716982400,
  content_hash:     "a1s2d3f4...",
  depth:            2,
  priority:         50
}

#2. Raw Web Page Storage (Object Storage — S3 / Google Cloud Storage)

To optimize costs at PB scale, raw web pages are compressed (e.g., GZIP/Zstandard) and stored as large blob files inside object storage.

Bucket Path: s3://crawler-page-archive/{year}/{month}/{day}/{domain_hash}/{url_hash}.html.gz
Metadata:
  - original-url: "https://example.com/page1"
  - crawl-timestamp: "1716982400"

#3. URL Deduplication Registry (Distributed Redis Cluster)

To prevent crawling duplicate URLs, we use a distributed Bloom Filter hosted in a Redis cluster to check if a URL is already discovered.

#5. High-Level Design (HLD) & Scale Evolution

#High-Level Architecture Diagram

The following diagram details the decoupled, queue-driven architecture of the distributed web crawler:

graph TD
    subgraph Core Frontier
        FrontQueues[Front Priority Queues] -->|Queue Selector| DelayRouter[Delay Router]
        DelayRouter -->|Politeness Mapping| BackQueues[Back Domain Queues]
    end

    subgraph Worker Pool
        Worker[Crawl Worker] -->|Get URLs| BackQueues
        Worker -->|DNS Resolve| DNSCache[(Local DNS Cache)]
        Worker -->|Robots Check| RobotsCache[(Robots.txt Cache)]
        Worker -->|Fetch HTML| Internet((World Wide Web))
    end

    subgraph Processing Pipeline
        Worker -->|Raw HTML| Parser[Content Parser]
        Parser -->|Text Content| ContentDedup{Content Deduplicator}
        ContentDedup -->|Unique Page| ObjectStore[(Raw Page Archive - S3)]
        
        Parser -->|Extracted URLs| URLFilter[URL Filter / Normalizer]
        URLFilter -->|Filtered URLs| URLDedup{URL Deduplicator}
        
        URLDedup -->|New URLs| FrontQueues
    end

    subgraph State Registries
        URLDedup <-->|Bloom Filter Lookup| RedisBloom[(Redis Bloom Filter Cluster)]
        ContentDedup <-->|SimHash Registry| Cassandra[(Cassandra Metadata DB)]
    end

#Scale Evolution

#Stage 1: Single-Instance Crawler (1K DAU / 100K Pages/month)

#Stage 2: Multi-threaded / Single Node (10M Pages/month)

#Stage 3: Distributed FAANG-Scale (1B Pages/month)

#6. Deep Dive — Core Components

#1. URL Frontier & Politeness Policy

To satisfy both priority and politeness constraints, the URL Frontier is designed with two distinct queue layers:

                  ┌───────────────────────────────┐
                  │        Incoming URLs          │
                  └───────────────┬───────────────┘
                                  ▼
                    ┌───────────────────────────┐
                    │       Prioritizer         │
                    └─────────────┬─────────────┘
                                  │ (Assigns priority 1..N)
                                  ▼
                    ┌───────────────────────────┐
                    │  Front Queues (Priority)  │
                    │  ┌─────┐ ┌─────┐ ┌─────┐  │
                    │  │ Q1  │ │ Q2  │ │ QN  │  │
                    │  └─────┘ └─────┘ └─────┘  │
                    └─────────────┬─────────────┘
                                  │ (Weighted Round-Robin)
                                  ▼
                    ┌───────────────────────────┐
                    │      Queue Selector       │
                    └─────────────┬─────────────┘
                                  ▼
                    ┌───────────────────────────┐
                    │  Back Queues (Politeness) │
                    │  Domain A  Domain B       │
                    │   ┌───┐     ┌───┐         │
                    │   │   │     │   │         │
                    │   └───┘     └───┘         │
                    └─────────────┬─────────────┘
                                  │ (Checks delay timers)
                                  ▼
                    ┌───────────────────────────┐
                    │      Crawl Workers        │
                    └───────────────────────────┘

#Politeness Implementation:

  1. Domain-to-Queue Mapping: All URLs from a single domain (e.g., wikipedia.org) are routed to the same Back Queue.
  2. Active Queue Table: Keeps track of domain queues that are currently being processed or are on hold.
    • Schema: (queue_id, last_crawled_time, delay_required)
  3. Queue Selector Logic:
    • The selector pulls a queue ID from the queue.
    • It checks the last_crawled_time. If the time elapsed is less than the delay_required (e.g., 1 second since the last hit), the queue ID is put on a temporary sleep queue or re-queued with a delay.
    • This ensures that a domain is never hit by more than one worker thread at a time and maintains the politeness interval.

#2. URL Deduplication (Bloom Filters)

Every page contains dozens of outbound links. To prevent re-crawling pages:

#3. Content Deduplication (SimHash / MinHash)

Websites often replicate content under different URLs (e.g., printers-friendly layouts, mirror sites). Crawling duplicate content wastes bandwidth and storage.

#7. Low-Level Design (LLD)

#Page Fetching Flow Chart

Below is the sequence of decisions made by a Crawl Worker when processing a single URL.

       [URL fetched from Back Queue]
                    │
                    ▼
          [Check Robots.txt Cache]
             /            \
       (Miss)              (Hit)
           /                \
[Fetch robots.txt]       [Is URL allowed?]
         │                 /          \
   [Update Cache]       (Yes)         (No)
         │               /              \
         └─────────────►/              [Discard & Ack]
                       │
                       ▼
             [DNS Resolution Cache]
             /            \
       (Miss)              (Hit)
           /                \
[Query Public DNS]       [Fetch HTML Page]
         │                       │
   [Update Cache]                ▼
         │             [Parse HTML & Links]
         │                       │
         └───────────────────────┴────────► [Write Output]

#Robots.txt Parser Pseudocode

import urllib.robotparser
import time

class RobotsTxtCache:
    def __init__(self, ttl_seconds=86400):
        self.cache = {}  # domain -> (robot_parser, cached_at)
        self.ttl = ttl_seconds

    def is_allowed(self, url, user_agent="Googlebot"):
        domain = self.extract_domain(url)
        now = time.time()
        
        # Check cache
        if domain in self.cache:
            parser, timestamp = self.cache[domain]
            if now - timestamp < self.ttl:
                return parser.can_fetch(user_agent, url)
                
        # Cache miss: Fetch and Parse robots.txt
        parser = urllib.robotparser.RobotFileParser()
        parser.set_url(f"https://{domain}/robots.txt")
        try:
            parser.read()
        except Exception:
            # Default to permissive if robots.txt cannot be fetched (e.g., 404)
            parser.allow_all = True
            
        self.cache[domain] = (parser, now)
        return parser.can_fetch(user_agent, url)

    def extract_domain(self, url):
        from urllib.parse import urlparse
        return urlparse(url).netloc

#8. Failure Handling & Edge Cases

#9. Monitoring & Observability

Observability is crucial for detecting performance issues and misbehaving crawlers.

#Key Metrics

#Alerting Strategy

#10. Trade-off Summary

Decision Chose Over Because
Crawl Strategy Breadth-First Search (BFS) Depth-First Search (DFS) BFS avoids getting stuck in a single deep website and discovers broader high-quality links.
Deduplication Store Redis Bloom Filter HBase/Database lookup Redis is in-memory and provides sub-millisecond lookups, avoiding disk bottlenecks.
SimHash vs. Cryptographic Hash SimHash SHA-256 SimHash allows near-duplicate content detection (e.g., templates with different ads), which SHA-256 cannot do.
Frontier Queue Storage Distributed Queues (Kafka) Relational Database (SQL) SQL databases suffer from locks and slow indexing when polling queues at 20,000+ QPS.

#11. Extensions & Follow-ups

#Dynamic Content Rendering (Single Page Applications)

Modern websites render content using JavaScript frameworks (React, Vue) after the initial HTML is loaded.

#Crawl Prioritization (Freshness vs. Discovery)

How do we decide when to re-crawl a page?

#12. Cross-References

#Building Blocks Used