Web Crawler

Problem statement (interviewer prompt)

Design a polite, scalable web crawler that fetches 1B+ pages over a month. It must respect robots.txt + crawl-delay, deduplicate URLs and near-duplicate content, prioritise important pages, handle JS-heavy sites, and survive worker failures.

flowchart LR
  S[Seed URLs]
  F[(Frontier Queue)]
  FT([Fetcher])
  P([Parser / Link Extractor])
  DD[Dedup<br/>URL + content hash]
  ST[(Page Storage)]
  IX[Indexer]
  S --> F
  F --> FT --> P
  P --> DD
  DD -->|new urls| F
  P --> ST --> IX

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class S,DD,IX service;
    class F,ST datastore;
    class FT,P compute;

flowchart TB
  subgraph Seeds[Seeds & Sitemaps]
    SD[Seed list]
    SM[Sitemaps]
  end

  subgraph Frontier[URL Frontier]
    PRIO[[Priority queues<br/>by importance]]
    HOST[[Per-host queues<br/>politeness]]
    RR([Round-robin scheduler])
    DELAY[Crawl-delay enforcer]
  end

  subgraph Resolve[DNS & Politeness]
    DNS[DNS cache]
    ROB[robots.txt cache]
    HC[Host metadata<br/>rps cap]
  end

  subgraph Fetch[Fetcher Workers]
    FW([HTTP fetcher pool<br/>async / epoll])
    REND[Headless renderer<br/>JS sites - Chromium]
    RETR[Retry / backoff]
  end

  subgraph Process[Processing Pipeline]
    PR([HTML parser])
    NORM[URL normalizer<br/>canonicalize]
    LINK[Link extractor]
    LANG[Lang detect]
    EX[Content extractor<br/>readability]
    DUPC[Content dedup<br/>SimHash / MinHash]
  end

  subgraph Dedup[Seen-URL filter]
    BLOOM[Bloom filter / Cuckoo<br/>billions of URLs]
    URLDB[(URL store<br/>last-seen, fetch state)]
  end

  subgraph Store[Storage]
    WARC[(WARC archive<br/>S3 / HDFS)]
    PDB[(Page DB<br/>HBase / Cassandra)]
    GRAPH[(Link Graph<br/>Pregel / GraphX)]
  end

  subgraph Downstream
    IDX[Indexer -> Inverted index]
    RANK[PageRank / signal builder]
    SPAM([Spam / malware classifier])
  end

  subgraph Ctl[Control Plane]
    SCH([Master scheduler])
    MON[Metrics: pages/s,<br/>per-host QPS]
    LIM[Quotas, kill switch]
  end

  SD --> Frontier
  SM --> Frontier
  Frontier --> Resolve
  Resolve --> Fetch
  Fetch --> Process
  Process --> Dedup
  Dedup -->|new URL| Frontier
  Process --> Store
  Store --> Downstream
  SCH -.assigns shards.-> Frontier
  MON -.observes.-> Fetch

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class DNS edge;
    class SD,SM,DELAY,ROB,HC,REND,RETR,NORM,LINK,LANG,EX,DUPC,BLOOM,RANK,LIM service;
    class URLDB,PDB,IDX datastore;
    class PRIO,HOST queue;
    class RR,FW,PR,SPAM,SCH compute;
    class WARC storage;
    class MON obs;

Politeness & robots

• Respect robots.txt, Crawl-delay, sitemaps.
• Cap per-host concurrency (1-4 connections); identify with User-Agent + contact URL.
• Use exponential backoff on 5xx / 429.

URL canonicalization

• Lowercase host, strip default ports, sort query, drop fragments, follow <link rel=canonical>.

Dedup

• URL: Bloom filter sized for expected URLs (FPR 1%).
• Content: SimHash (64-bit) for near-dup pages, Hamming threshold 3.

Scale design

• Frontier sharded by host hash; one host always served by same node (politeness).
• Workers pull from frontier; processed results emitted to Kafka.
• WARC files stored as 1 GB chunks in S3 / HDFS.

Politeness sticking points

• *.akamai.com masking many hosts behind one IP - limit by IP too.
• Sitemap honesty - verify timestamps before re-crawl.
• Crawler traps (infinite calendar, faceted search) - depth limit + URL pattern dedup.

Glossary & fundamentals

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
HLD	CDN	edge caching for static assets	cdn
HLD	Sharding	horizontal partitioning across nodes	database-sharding
HLD	Pub/Sub & message brokers	topics, consumer groups, delivery semantics	pub-sub-pattern
HLD	CAP / PACELC	C vs A under partition; L vs C otherwise	cap-pacelc
HLD	Probabilistic data structures	Bloom, HLL, Count-Min, MinHash, t-digest	probabilistic-data-structures
HLD	Idempotency & retries	safe re-execution, backoff + jitter	idempotency-retries
HLD	Observability	metrics, logs, traces, SLOs	observability
HLD	Search internals	inverted index, BM25, embeddings, ANN	search-internals
LLD	Creational patterns	Singleton, Factory, Builder, Prototype	creational-patterns

Quick reference

Functional

• Start from seeds, fetch HTML, extract links, recurse.
• Respect robots.txt, sitemaps, crawl-delay.
• Re-crawl with freshness policy (popular = faster).
• Deduplicate URLs and content.

Non-functional

• 1B+ pages crawled.
• 1k+ fetchers in parallel.
• Politeness: ≤ 1 connection / host by default.
• Resumable on failure.

Capacity (10B pages, 1 month)

• 10B pages / 30 days = ~4,000 pages/s avg.
• Avg page 500 KB → 2 GB/s = 16 Gbps inbound.
• Storage: 10B × 500 KB = 5 PB raw; 1 PB compressed (gzip ~5×).
• URL frontier: 100B URLs × 50 B → 5 TB → Bloom filter 100 GB at 1% FPR.

Data

• URL store: (url, host, depth, last_fetched, fetch_state, http_code, content_hash).
• Page store: WARC files on S3 (immutable, append-only).

Trade-offs

• BFS = better coverage, DFS = bias to one site.
• Priority crawl by PageRank/freshness for limited budget.
• Politeness vs throughput: per-host queue trims throughput on big hosts but is the law.
• Headless rendering essential for SPA sites but 10-100× cost; do selectively.

Refs

• Mercator (1999), UbiCrawler, Heritrix (Internet Archive), Common Crawl, "Designing Data-Intensive Applications" ch.10, ByteByteGo web crawler.

FAQ

What is a URL frontier in a web crawler?

The frontier is the priority queue of URLs to fetch. It enforces per-host politeness, deduplicates URLs, prioritizes important pages, and feeds fetcher workers.

How do crawlers respect robots.txt?

Workers cache the parsed robots.txt per host, apply crawl-delay between requests, and skip disallowed paths. A scheduler queues per-host so polite delays are enforceable.

How do you deduplicate URLs at scale?

Hash the canonicalized URL and check a Bloom filter or KV set before queueing. Bloom filters give compact membership tests with a tunable false positive rate.

How do crawlers detect near-duplicate content?

Compute simhash or minhash signatures on the visible text and compare against an index of seen pages. Pages within a small Hamming distance are treated as duplicates.

How do crawlers handle JavaScript-heavy sites?

Route those URLs to a separate fleet of headless browsers like Chromium. The cost per page is 10 to 100x higher, so most crawlers do this only for whitelisted hosts.

Related Topics

• Probabilistic Data Structures: Bloom filters deduplicate URLs without storing the full frontier set
• Storage Engines: LSM and B-Tree: the storage engine choice determines crawl-frontier write and compaction performance
• Pub/Sub Pattern: crawl tasks and extracted URLs flow through message queues for distributed processing

Further reading

Curated, high-credibility sources for going deeper on this topic.

• 📄 Paper - Najork & Heydon - High-Performance Web Crawling (Mercator)
• 📑 Docs - Common Crawl - Open-source web corpus
• 📑 Docs - Apache Heritrix - Internet Archive's crawler

Video walkthrough

System Design Interview: Design a Web Crawler : via Hello Interview