Web Crawler

0Problem RestatementProblem

Design a distributed web crawler that can efficiently traverse the internet, download web pages, extract links, and index content for a search engine. The core challenges are avoiding duplicate crawling, respecting politeness policies, handling failures, and scaling to billions of pages.

1RequirementsRequirements

1.1 Functional

• Crawl web pages starting from seed URLs.
• Extract and follow links from downloaded pages.
• Store page content and metadata.
• Respect robots.txt and politeness policies.
• Support incremental and recurring crawls (freshness).
• Handle different content types (HTML, PDF, images, etc.).

1.2 Non-Functional

• Scalability: Crawl billions of pages across millions of domains.
• Politeness: Avoid overloading servers (rate limiting per domain). Example: If you crawl *example.com/page1*, wait 1 second before crawling *example.com/page2*. But you can simultaneously crawl *other-site.com/page1* (different domain)
• Robustness: Handle failures, malformed HTML, redirects, timeouts.
• Efficiency: High throughput (thousands of pages/sec).
• Freshness: Re-crawl important pages regularly.
• Deduplication: Avoid crawling duplicate URLs and content.

1.3 Scale Estimates

• Storage: 10B × 100 KB = 1 PB (raw HTML); ~5–10× less with compression.
• Bandwidth: 10K pages/s × 100 KB = 1 GB/s ≈ 8 Gbps sustained download.
• Full pass: 10B ÷ 10K/s = 10^6 s ≈ 12 days, which fits a monthly recrawl.
• Recrawl interval: Monthly for most pages, hours/days for critical content.

2High-Level ArchitectureArchitecture

2.1 Overview

• Frontier (URL queue) → Crawler Workers → DNS Resolver → Downloader → Content Processor → Storage (HTML, metadata, index).
• Key challenges: URL deduplication, politeness enforcement, distributed coordination, failure recovery.

2.2 Architecture Diagram

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart TB
    %% Seed URLs and Frontier
    Seeds["Seed URLs"] -->|"1. initial URLs"| Frontier["URL Frontier (Priority Queue)"]
    
    %% Main Crawl Loop
    Frontier -->|"2. pop URL(s)"| Scheduler["Scheduler / Coordinator"]
    Scheduler -->|"3. assign URL to worker"| CW["Crawler Workers (Pool)"]
    
    %% DNS and Download
    CW -->|"4. resolve domain"| DNS["DNS Resolver (Cache)"]
    DNS -->|"5. IP address"| CW
    CW -->|"6. HTTP GET"| Web["Web Servers"]
    Web -->|"7. HTML content"| CW
    
    %% Content Processing
    CW -->|"8. raw HTML"| Parser["Content Parser"]
    Parser -->|"9a. extract links"| LinkExtractor["Link Extractor"]
    Parser -->|"9b. extract text"| TextProcessor["Text Processor"]
    
    %% URL Filtering
    LinkExtractor -->|"10a. new URLs"| URLFilter["URL Filter & Dedup"]
    URLFilter -->|"10b. check if seen"| URLStore[(URL Seen Set - Bloom Filter / DB)]
    URLFilter -->|"10c. check robots.txt"| RobotCache["Robots.txt Cache"]
    URLFilter -->|"11. valid, unseen URLs"| Frontier
    
    %% Storage
    TextProcessor -->|"12a. cleaned content"| Storage[(Storage Layer)]
    CW -->|"12b. metadata (URL, timestamp, headers)"| Storage
    
    %% Politeness
    Scheduler -.->|"enforce delay per domain"| Politeness["Politeness Manager (Rate Limiter)"]
    
    %% Analytics and Monitoring
    Storage -.->|"crawl stats"| Analytics["Analytics & Monitoring"]
    
    %% Styling
    classDef core fill:#e0ffe0,stroke:#333,stroke-width:2px;
    classDef storage fill:#ffe0e0,stroke:#333,stroke-width:2px;
    classDef processing fill:#e0f0ff,stroke:#333,stroke-width:2px;
    classDef external fill:#fff8e0,stroke:#333,stroke-width:2px;
    
    class Frontier,Scheduler,CW core;
    class Storage,URLStore storage;
    class Parser,LinkExtractor,TextProcessor,URLFilter processing;
    class DNS,Web,RobotCache,Politeness external;

3Components (what & why)

URL Frontier (Priority Queue)

• Purpose: Store URLs to be crawled, ordered by priority (e.g., PageRank, freshness).
• Implementation: Distributed queue (Kafka, RabbitMQ) or custom sharded queue.
• Partitioning: By domain to enable politeness (same domain URLs go to same partition).

Scheduler / Coordinator

• Purpose: Assign URLs from frontier to worker nodes.
• Responsibilities:
• Load balancing across workers.
• Enforce politeness constraints (delay between requests to same domain).
• Prioritize high-value URLs.

Crawler Workers

• Purpose: Fetch web pages, parse content, extract links.
• Implementation: Horizontally scalable worker pool.
• Steps per worker:

1. Pop URL from frontier.
2. Resolve DNS (with caching).
3. Download page (HTTP GET).
4. Parse HTML and extract links.
5. Store content and metadata.
6. Enqueue new URLs.

DNS Resolver

• Purpose: Resolve domain names to IP addresses.
• Optimization: Cache DNS results (TTL-based) to reduce latency.
• Scale: Use local DNS cache per worker or shared distributed cache.

Content Parser

• Purpose: Parse HTML, extract text, metadata, and links.
• Tools: Libraries like BeautifulSoup, lxml, or custom parsers.
• Output: Cleaned text, extracted links, page metadata.

URL Filter & Deduplication

• Purpose: Prevent duplicate crawls and filter unwanted URLs.
• Techniques:
• Bloom Filter: Fast probabilistic check if URL seen (low memory). Can be achieved through Redis.
• DB lookup: Store normalized URLs in a DB.
• Content Hash: Detect duplicate content using hash comparison.

Robots.txt Cache

robots.txt is a text file that websites place at the root of their domain to tell web crawlers which parts of the site they are allowed or not allowed to crawl.

• Purpose: Respect site crawling policies (robots.txt).
• Implementation: Cache robots.txt per domain with TTL.
• Enforcement: Check before downloading each URL.

Politeness Manager

• Purpose: Rate limit requests to avoid overwhelming servers.
• Strategy:
• Enforce delay between requests to same domain (e.g., 1 second).
• Use token bucket or leaky bucket algorithm per domain.
• Distributed coordination to ensure global politeness.

Storage Layer

• Purpose: Store downloaded HTML, metadata, and extracted content.
• Components:
• Blob Storage (S3, GCS): Raw HTML and assets.
• Metadata DB: URL, timestamp, HTTP headers, crawl status.
• Inverted Index: For search engine integration.
• Partitioning: By URL hash or domain.

Analytics & Monitoring

• Metrics: Crawl rate, error rate, frontier size, worker utilization.
• Alerts: Detect slow workers, frontier overflow, storage issues.
• Tools: Can use Grafana, DataDog, New Relic, or custom metrics.

4Data ModelData model

URL Entry

URL(url_id, url, domain, priority, last_crawled, crawl_status, depth)
-- crawl_status ∈ {PENDING, IN_PROGRESS, COMPLETED, FAILED}

Page Content

Page(page_id, url_id, html_blob_path, content_hash, http_status, headers, crawled_at)

Domain Metadata

Domain(domain, robots_txt, crawl_delay, last_accessed, error_count)

Crawl Queue (Frontier)

{
  "url": "https://example.com/page",
  "priority": 0.95,
  "depth": 2,
  "timestamp": "2023-10-15T12:00:00Z"
}

5Key FlowsFlows

5.1 Initial Crawl Flow

1. Seed URLs are loaded into the frontier with high priority.
2. Scheduler assigns URLs to available crawler workers.
3. Worker resolves DNS, downloads page, parses content.
4. Extracted links are filtered, deduplicated, and added to frontier.
5. Process repeats until frontier is empty or crawl quota reached.

5.2 URL Deduplication Flow

1. Normalize URL: Remove fragments, sort query params, lowercase domain.
2. Check Bloom Filter: Fast probabilistic check if URL seen.
3. If new: Add to Bloom Filter, enqueue to frontier.
4. If duplicate: Skip.

5.3 Politeness Enforcement Flow

1. Scheduler maintains last access time per domain.
2. Before assigning URL, check if delay elapsed (e.g., 1 second).
3. If delay not elapsed, hold URL in domain-specific queue.
4. When delay elapsed, assign URL to worker.
5. After download, update last access time for domain.

5.4 Failure Handling Flow

1. Download Failure (timeout, 5xx error): Retry with exponential backoff (max 3 retries).
2. Permanent Failure (404, 403): Mark URL as FAILED in DB.
3. Worker Crash: Reassign in-progress URLs to other workers (heartbeat mechanism).
4. Storage Failure: Buffer content locally, retry upload.

5.5 Recrawl Flow

1. Priority Queue stores URLs with last crawled timestamp.
2. Freshness Scorer periodically promotes stale URLs (e.g., news sites).
3. Scheduler assigns recrawl URLs with adjusted priority.
4. After crawl, update last crawled timestamp.

6Deep Dive A: URL Frontier & Prioritization (~10 mins)Deep dive

Problem

With billions of URLs, we need an efficient queue that supports:

• High throughput enqueue/dequeue.
• Priority-based ordering (important pages first).
• Domain-based partitioning (for politeness).
• Persistence (survive crashes).

Solution: Multi-Level Frontier

6.1 Front Queue (Priority Queue)

• Purpose: Order URLs by priority (PageRank, freshness, user-defined).
• Implementation: Min-heap or priority queue per priority band.
• Example Bands:
• HIGH: Homepage, popular sites (priority > 0.9).
• MEDIUM: Linked from high-value pages (priority 0.5–0.9).
• LOW: Deep crawl, low-value pages (priority < 0.5).

6.2 Back Queue (Domain-Based FIFO)

• Purpose: Group URLs by domain to enforce politeness.
• Implementation: FIFO queue per domain (hash partitioning).
• Flow:

1. Pop high-priority URL from front queue.
2. Route to domain-specific back queue.
3. Scheduler dequeues from back queues with politeness delay.

6.3 Diagram: Two-Tier Frontier

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
    %% Front queues
    High["High Priority Queue"] --> Router["Domain Router"]
    Medium["Medium Priority Queue"] --> Router
    Low["Low Priority Queue"] --> Router
    
    %% Back queues
    Router --> D1["Domain: example.com Queue"]
    Router --> D2["Domain: news.com Queue"]
    Router --> D3["Domain: wiki.org Queue"]
    Router --> DN["Domain: ... Queue"]
    
    %% Scheduler
    D1 --> Scheduler["Scheduler (with Politeness)"]
    D2 --> Scheduler
    D3 --> Scheduler
    DN --> Scheduler
    
    Scheduler --> Workers["Crawler Workers"]
    
    classDef front fill:#ffe0e0,stroke:#333,stroke-width:2px;
    classDef back fill:#e0ffe0,stroke:#333,stroke-width:2px;
    
    class High,Medium,Low front;
    class D1,D2,D3,DN back;

6.4 Persistence

• Approach: Store frontier in distributed queue (Kafka) or database (DynamoDB, Cassandra).
• Checkpoint: Periodically snapshot in-memory state to disk.
• Recovery: On restart, reload from checkpoint + replay queue.

6.5 Priority Scoring

• PageRank: Use precomputed graph analysis.
• Freshness: Prioritize pages with high change frequency.
• User Signals: Clicks, bookmarks, social shares.
• Formula: priority = w1 * PageRank + w2 * Freshness + w3 * UserSignal

7Deep Dive B: Deduplication (~8 mins)Deep dive

Problem

With billions of URLs, we must efficiently detect duplicates to avoid redundant crawls.

Challenges

• URL Variations: example.com, www.example.com, example.com/index.html may point to same content.
• Scale: Storing 10B URLs requires ~500 GB+ (assuming 50 bytes/URL).
• Lookup Speed: Need sub-millisecond checks.

Solution: Three-Layer Deduplication

7.1 URL Normalization

• Canonical Form:
• Lowercase the scheme and host (HTTP://Example.COM → http://example.com).
• Keep the path's case: paths are case-sensitive on most servers, so /Page and /page can be different pages.
• Remove default ports (:80 for http, :443 for https).
• Remove fragments (#...).
• Sort query parameters, and drop known tracking parameters (utm_*, session IDs).
• Don't strip trailing slashes blindly — /docs and /docs/ can differ; rely on redirects and <link rel="canonical"> instead.
• Example: HTTP://Example.com:80/Page?b=2&a=1&utm_source=x#frag → http://example.com/Page?a=1&b=2

7.2 Bloom Filter (First Pass)

• Purpose: Fast probabilistic check (O(1) lookup).
• Size: For 10B URLs with 1% false positive rate: ~12 GB.
• Trade-off: False positives are acceptable (small % of duplicate crawls).
• Implementation: Distributed Bloom Filter (sharded by URL hash).

7.3 Canonical URL Store (Second Pass)

• Purpose: Authoritative check for URLs that pass Bloom Filter.
• Implementation: Distributed key-value store (Cassandra, DynamoDB).
• Key: Normalized URL or URL hash.
• Value: {url_id, last_crawled, crawl_count}
• Lookup: If Bloom Filter says "maybe seen", query store.

7.4 Content Hash (Third Pass - Optional)

• Purpose: Detect duplicate content with different URLs.
• Approach:
• Compute hash of extracted text (e.g., SimHash, MD5).
• Store hash in content dedup store.
• If hash match found, skip detailed indexing but update URL metadata.
• Use Case: Mirror sites, copied content.

7.5 Deduplication Flow Diagram

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart TD
    Start["New URL extracted"] --> Normalize["Normalize URL"]
    Normalize --> BloomCheck["Check Bloom Filter"]
    
    BloomCheck -->|"Definitely NOT seen"| AddBloom["Add to Bloom Filter"]
    AddBloom --> AddStore["Add to URL Store"]
    AddStore --> Enqueue["Enqueue to Frontier"]
    
    BloomCheck -->|"Maybe seen"| DBCheck["Check URL Store"]
    DBCheck -->|"Not in Store (false positive)"| AddStore
    DBCheck -->|"In Store"| Skip["Skip (Duplicate)"]
    
    classDef new fill:#e0ffe0,stroke:#333,stroke-width:2px;
    classDef dup fill:#ffe0e0,stroke:#333,stroke-width:2px;
    
    class AddBloom,AddStore,Enqueue new;
    class Skip dup;

7.6 Crawler Traps

• Problem: Some sites generate infinite URLs — calendars with a "next month" link forever, session IDs in URLs, endlessly nested paths (/a/a/a/a/...). Dedup can't catch them because every URL is new.
• Mitigations: Cap URL length and path depth; cap pages crawled per domain per cycle (a crawl budget sized by the site's importance); detect repeating path segments; strip session parameters during normalization; stop following a pattern whose pages are near-duplicates by content hash.

8Deep Dive C: Politeness & Rate Limiting (~7 mins)Deep dive

Problem

Crawling too aggressively can overload servers, violate terms of service, or get IP banned.

Requirements

• Per-Domain Delay: Wait 1–5 seconds between requests to same domain.
• Respect robots.txt: Honor crawl-delay directive.
• Distributed Coordination: Multiple workers must coordinate on same domain.

Solution: Distributed Rate Limiter

8.1 Token Bucket per Domain

• Algorithm: Each domain has a token bucket.
• Tokens refill at rate 1 / crawl_delay (e.g., 1 token/second).
• Each request consumes 1 token.
• If no tokens, request is queued.
• Storage: Store bucket state in distributed cache (Redis).

8.2 Coordinator-Based Approach

• Architecture:
• Politeness Coordinator: Central service managing domain access.
• Workers request permission before crawling a domain.
• Coordinator tracks last access time and grants permission with delay.
• Trade-off: Single point of failure; use replicated coordinators.

8.3 Decentralized Approach (Partitioned Domains)

• Partition Strategy: Assign each domain to specific worker(s) via consistent hashing.
• Benefit: No central coordinator; each worker self-enforces politeness for assigned domains.
• Challenge: Load imbalance if some domains have many URLs.

8.4 Robots.txt Enforcement

• Cache: Store robots.txt per domain in distributed cache.
• Validation: Before crawling URL, check:
• Is path allowed by robots.txt?
• Is crawl-delay specified? Use it instead of default.
• Refresh: Reload robots.txt periodically (e.g., daily).

8.5 Politeness Architecture

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart TD
    Worker["Crawler Worker"] -->|"request: crawl example.com/page"| Coord["Politeness Coordinator"]
    Coord -->|"check last access time"| Cache["Redis Cache (Domain State)"]
    
    Cache -->|"last_access: 2s ago, delay: 5s"| Coord
    Coord -->|"delay not elapsed"| Wait["Return: WAIT 3s"]
    
    Cache -->|"last_access: 10s ago, delay: 5s"| Coord
    Coord -->|"delay elapsed"| Grant["Return: GRANTED"]
    Grant --> Worker
    Worker -->|"download page"| Update["Update last_access in Cache"]
    
    Wait --> Worker
    Worker -->|"retry after delay"| Coord

9Scaling & Performance (~5 mins)Scale

Horizontal Scaling

• Workers: Add more crawler worker nodes; queue distributes load.
• Frontier: Shard queue by domain or URL hash.
• Storage: Partition by URL hash; use distributed blob storage.

Bottlenecks & Mitigations

• DNS Lookups: Cache aggressively, use local DNS servers, prefetch for common domains.
• Network I/O: Use async I/O (e.g., asyncio, aiohttp in Python).
• Frontier Contention: Use multiple priority queues, shard by domain.

Throughput Optimization

• Batch Processing: Download multiple pages in parallel per worker.
• Connection Pooling: Reuse HTTP connections for same domain.
• Compression: Request gzip encoding to reduce bandwidth.

Monitoring & Metrics

• Crawl Rate: Pages/second, grouped by domain and priority.
• Frontier Size: Depth of queue (detect stalls).
• Error Rate: HTTP errors, timeouts, parsing failures.
• Worker Health: CPU, memory, network usage per worker.

10Failure Modes & Recovery

Worker Failure

• Detection: Heartbeat mechanism; coordinator marks worker dead if no heartbeat for N seconds.
• Recovery: Reassign in-progress URLs to healthy workers.

DNS Failure

• Fallback: Use public DNS (8.8.8.8) if local DNS fails.
• Retry: Exponential backoff for transient failures.

Network Partition

• Impact: Workers can't reach coordinator or storage.
• Mitigation: Local buffering of content; retry upload when network restored.

Storage Outage

• Buffer: Workers cache content locally (disk or memory).
• Retry: Periodic retry to upload buffered content.

Frontier Corruption

• Checkpoint: Regular snapshots of frontier state.
• Recovery: Reload from last checkpoint; may re-crawl some URLs (acceptable).

11Trade-offs & AlternativesTrade-offs

Centralized vs Distributed Frontier

• Centralized: Simpler to manage, single source of truth.
• Distributed: Higher scalability, no single point of failure.
• Choice: Use distributed queue (Kafka) for scale, with coordination layer.

Breadth-First vs Depth-First Crawl

• BFS: Crawl wide (all links from homepage before going deep). Better for completeness.
• DFS: Crawl deep (follow single path). Faster for specific content.
• Choice: BFS with priority (important pages first).

In-Memory vs Persistent Frontier

• In-Memory: Faster, but lost on crash.
• Persistent: Durable, but slower.
• Choice: Hybrid (in-memory with periodic checkpoints).

Bloom Filter vs Full URL Store

• Bloom Filter: Low memory, fast, but false positives.
• Full Store: Accurate, but higher memory/cost.
• Choice: Use both (Bloom Filter + DB).

12Security & Compliance

robots.txt Compliance

• Mandatory: Check robots.txt before crawling.
• User-Agent: Identify crawler (e.g., "MyCrawler/1.0").

Rate Limiting

• Politeness: Avoid DDoS-like behavior.
• When a site pushes back (HTTP 429/503, Retry-After): slow down for that domain. Don't rotate IPs to get around a site's limits — that's evasion, and it's exactly what politeness is meant to prevent. Multiple crawler IPs are for total throughput, and per-domain limits apply across all of them.

Data Privacy

• Sensitive Data: Only crawl publicly reachable pages; never submit forms or use credentials, and honor noindex / robots rules.
• GDPR: Respect right-to-be-forgotten (remove URLs on request).

SSL/TLS

• HTTPS: Support secure connections.
• Certificate Validation: Verify SSL certificates.

13Interview Time Allocation (45 min)

• 5 min: Requirements & scope (functional, non-functional, scale).
• 10 min: HLD & architecture diagram (components, data flow).
• 5 min: Data model & key flows (URL frontier, crawl flow).
• 10 min: Deep dive on URL frontier, prioritization, and deduplication.
• 8 min: Deep dive on politeness and rate limiting.
• 5 min: Scaling, failure handling, and trade-offs.
• 2 min: Wrap-up, Q&A.

14SummaryWrap-up

• Core Challenges: Scale (billions of URLs), politeness (rate limiting), deduplication (Bloom Filter + DB), and failure resilience.
• Key Components: URL Frontier (priority queue + domain partitioning), Crawler Workers (async download), Deduplication Layer (Bloom Filter + canonical URL store), Politeness Manager (token bucket per domain).
• Scaling Strategy: Horizontal scaling of workers, sharded frontier, distributed storage, and aggressive caching (DNS, robots.txt).
• Correctness: Ensure no overload (politeness), no duplicates (multi-layer dedup), and fault tolerance (checkpoints, retries).

This design can scale to crawl the entire web while respecting server resources and maintaining high efficiency.