Designing a Web Crawler and Search Engine

Difficulty: Advanced Prerequisites:Message Queues, Consistent Hashing, and Bloom Filters

TL;DR

Two coupled systems in one question: a crawler that discovers and downloads billions of pages, and a search service that indexes them and answers queries in milliseconds. They are joined only by storage — the crawler writes pages, the indexer reads them — which is what lets them scale independently.

The shape of the answer: a two-level URL frontier for politeness, a Bloom filter for dedup, an offline indexing pipeline, and a sharded inverted index fronted by a query aggregator.

The single most important framing: crawling is a write-heavy batch problem, serving is a read-heavy latency problem. Treat them as one system and you will design both badly.

Understanding the Problem

Two coupled systems: a crawler that discovers and downloads billions of web pages, and a search service that indexes that content and answers user queries in milliseconds. The hard parts: crawling politely without hammering any single site, avoiding re-crawling unchanged content, building a massive inverted index, and serving ranked results at sub-200ms latency.

Crawling is throughput-bound and can be arbitrarily slow per page as long as aggregate rate holds. Serving is tail-latency-bound, where a single slow shard ruins the query. Because they share nothing but the page store, the crawler can fall hours behind without the search path noticing.

Naive First Cut

flowchart LR
    SEED["Seed URLs"]:::client
    CRAWLER["Single Crawler"]:::service
    DB[("One DB<br/>pages + index")]:::data
    USER["Search User"]:::client

    SEED --> CRAWLER
    CRAWLER --> DB
    USER --> DB

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Why this breaks:

• Single crawler — at 1 page/sec, crawling 10B pages takes 317 years
• No URL deduplication — the same page is fetched thousands of times via different links
• No politeness — hammering a single domain causes your IP to be blocked
• One database can’t hold billions of documents AND serve as a search index
• No ranking — results are returned in insertion order, not by relevance

The rest of the doc splits this into two independently scalable halves.

Prior Art We’re Drawing From

• Mercator / the original Google crawler — introduced the two-level frontier (front queues for priority, back queues for per-domain politeness) that remains the standard answer to “how do you crawl fast without hammering anyone.” (The Anatomy of a Large-Scale Hypertextual Web Search Engine)
• Apache Nutch / Heritrix — open-source crawlers that show the frontier, fetcher, parser, and dedup as separable services with durable handoffs between them. (Apache Nutch)
• Google’s index serving — document-sharded index with a query aggregator scatter-gathering across shards, which is why P99 depends on the slowest shard rather than the average. (Web Search for a Planet)
• Bigtable — built in large part to store crawled pages and their versions at web scale; the canonical answer for “where do billions of pages live.” (Bigtable paper)

Functional Requirements

Core (top 3)

1. Crawl the web — discover, download, and store web pages at scale (1B+ pages)
2. Build an inverted index — map every word to the pages that contain it
3. Serve search queries — return the top 10 most relevant results for a query in <200ms

Below the Line

• Image/video indexing, real-time freshness (news), autocomplete, personalization, ads

Non-Functional Requirements

• Crawl throughput — 10K pages/second sustained
• Index freshness — popular pages re-crawled within hours; long-tail within weeks
• Query latency — <200ms P99 for search results
• Politeness — respect robots.txt; max 1 request/second per domain

Below the Line

• Real-time indexing (seconds-fresh news)
• Personalized or session-aware ranking
• JavaScript rendering for SPA-heavy sites (a large, separate problem)

Scale Estimation (Back-of-Envelope)

Crawl side:

• Throughput: 10K pages/sec → 864M pages/day → 1B pages in ~1.2 days, 10B in ~12 days
• Fleet size: at ~1 page/sec per worker-domain pair with network waits dominating, 10K pages/sec needs on the order of 10K concurrent fetches — a few hundred workers with high concurrency each
• Raw storage: 10B pages × ~75KB compressed HTML ≈ 750TB, which is object-storage/Bigtable territory, not a database
• Bandwidth: 10K pages/sec × 100KB ≈ 1GB/sec ≈ 8 Gbps sustained ingress
• Dedup filter: 10B URLs in a Bloom filter at 1% false-positive ≈ 12GB RAM — fits in memory, which is the whole reason to use one

Serve side:

• Index size: ~10B docs; posting lists after compression ≈ 100s of TB, sharded across thousands of machines
• Query QPS: assume 100K queries/sec; top 1% of queries drive ~30% of traffic, so cache hit rate is high
• Fan-out per query: a query hits every document shard, so P99 is governed by the slowest shard, not the average — this is why tail latency dominates the serving design

The 750TB figure is the one to state early: it immediately rules out “store pages in Postgres” and justifies object storage plus a separate index.

Core Entities

• URL — address to crawl, domain, last crawled timestamp, crawl priority
• Page — raw HTML content, extracted text, outgoing links, content hash
• Inverted Index Entry — word → list of (page ID, position, frequency)
• Query — user search terms, results with relevance scores

API

POST /v1/crawl/seed
  Body: { urls: ["https://example.com", ...] }
  Response: { queued: 150 }

GET /v1/search?q=distributed+systems&page=1
  Response: { results: [{ url, title, snippet, score }], total: 15000, took: "45ms" }

GET /v1/crawl/status
  Response: { pagesIndexed: 1200000000, crawlRate: "9800 pages/sec" }

High-Level Design

FR1: Crawl the Web

A URL Frontier (priority queue) feeds URLs to a distributed fleet of Crawler workers. Each worker downloads the page, extracts links (new URLs fed back to the frontier), and stores content.

flowchart LR
    FRONTIER["URL Frontier<br/>priority queue"]:::async
    CRAWLER["Crawler Workers"]:::service
    STORE[("Page Store<br/>object storage")]:::data
    DEDUP["URL Dedup<br/>Bloom filter"]:::service

    FRONTIER -->|"1. Dequeue URL"| CRAWLER
    CRAWLER -->|"2. Store page"| STORE
    CRAWLER -->|"3. Extract links"| DEDUP
    DEDUP -->|"4. Enqueue new URLs"| FRONTIER

    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
    classDef async fill:#3a2a4c,stroke:#c084fc,color:#e2e8f0

FR2: Build the Inverted Index

An Indexer reads crawled pages, tokenizes content, and builds the inverted index. The index maps each word to a posting list (pages containing that word, with positions and frequency).

flowchart LR
    STORE[("Page Store")]:::data
    KAFKA["Kafka<br/>new pages"]:::async
    INDEXER["Indexer"]:::service
    INDEX[("Inverted Index<br/>sharded")]:::data

    STORE -->|"1. Change events"| KAFKA
    KAFKA -->|"2. Index new documents"| INDEXER
    INDEXER -->|"3. Return results"| INDEX

    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
    classDef async fill:#3a2a4c,stroke:#c084fc,color:#e2e8f0

FR3: Serve Search Queries

The Query Service receives a user query, looks up each term in the inverted index, intersects posting lists, scores results by relevance (TF-IDF + PageRank), and returns top-K.

flowchart LR
    USER["User"]:::client
    QUERY["Query Service"]:::service
    INDEX[("Inverted Index<br/>sharded")]:::data
    CACHE[("Redis<br/>hot queries")]:::data

    USER -->|"1. Submit search query"| QUERY
    QUERY -->|"2. Lookup cached results"| CACHE
    CACHE -.->|miss| INDEX

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Deep Dives

Deep Dive 1: URL deduplication — avoiding redundant crawls

Bad: Maintain a hash set of all visited URLs in memory. At 10B URLs × 100 bytes each = 1TB of RAM. Doesn’t fit on a single machine. Also, the same page can be reached via different URLs (trailing slashes, query params, anchors).

Good: Use a Bloom filter for fast membership testing (probabilistic: may say “seen” for an unseen URL, but never misses a seen one). False positive rate of 1% at 10B URLs needs ~12GB — fits in memory. Normalize URLs (lowercase, remove fragments, sort params) before checking.

Great: Combine the Bloom filter with content-based dedup. After downloading a page, compute a SimHash (locality-sensitive hash) of the content. Two pages with similar content (mirror sites, syndicated articles) get the same SimHash — dedup at the content level, not just URL level. This eliminates near-duplicate pages that have different URLs but identical content, reducing index bloat by 30-40%.

Deep Dive 2: Politeness and crawl rate management

Bad: All crawler workers hit the same popular domain simultaneously. The site’s servers overload, they block your IP, and you lose access to that domain’s content entirely.

Good: Enforce per-domain rate limiting: max 1 request/second per domain. The URL Frontier maintains a per-domain queue with a “not-before” timestamp. Workers pick the next URL whose domain is eligible to be crawled. Respect robots.txt (fetch and cache it per domain, honor Crawl-delay directives).

Great: Use a two-level frontier. Back queue: per-domain queues with rate limiting (politeness). Front queue: priority queue that selects which domain to crawl next based on importance (PageRank of domain, freshness requirements). This ensures high-value domains (news sites, Wikipedia) are crawled frequently while staying polite. Assign each worker a set of domains via consistent hashing — this ensures DNS caching efficiency and persistent connections per worker-domain pair.

Deep Dive 3: Search ranking — beyond simple TF-IDF

Bad: Rank by keyword frequency (TF-IDF only). SEO spammers stuff keywords into pages and dominate results. Irrelevant but keyword-rich pages rank above authoritative sources.

Good: Combine TF-IDF with PageRank — a page’s authority is proportional to the number and quality of pages linking to it. This boosts authoritative sources (Wikipedia, official docs) above spam. PageRank is computed offline as a batch job over the link graph.

Great: Multi-signal ranking: TF-IDF (text relevance) + PageRank (authority) + freshness (prefer recent content for time-sensitive queries) + click-through rate (learn from user behavior over time). The scoring formula is a weighted combination, tuned via ML. For query latency, pre-compute static scores (PageRank) and combine with query-time scores (TF-IDF) during serving. Cache results for popular queries (top 1% of queries account for 30% of traffic) with a 1-minute TTL.

Deep Dive 4: Sharding the index — by term or by document?

Bad: Keep one index. No single machine holds 100s of TB of posting lists, so this doesn’t exist as an option.

Good: Term-partitioned (each shard owns a subset of words). A query for “distributed systems” touches only the two shards owning those terms, so per-query fan-out is small. The problem: posting lists for common words are enormous and unevenly distributed, so the shard owning “the” is a permanent hotspot, and multi-term queries must ship huge posting lists across the network to be intersected.

Great: Document-partitioned (each shard owns a subset of pages and indexes all their words). Every query goes to every shard, each computes its own local top-K, and an aggregator merges the results. Fan-out is wide but each shard does a small, bounded amount of work with no cross-shard data movement, and load is naturally even. This is what real search engines do.

The cost is tail latency: with 1000 shards, the query is as slow as the slowest one. Mitigate with hedged requests — if a shard hasn’t replied by the 95th-percentile mark, send a duplicate request to a replica and take whichever answers first. Combined with per-shard tiering (put high-PageRank documents in a small “top tier” that is searched first, and only fall through to the long-tail tier if there aren’t enough good results), most queries never touch the full index at all.

Deep Dive 5: Re-crawl scheduling — spending a fixed budget wisely

Bad: Re-crawl everything on a fixed cycle, e.g. every page every 30 days. Wastes most of the crawl budget re-fetching pages that never change, while breaking news sits stale for weeks.

Good: Tier by observed change rate. Track a content hash per URL across crawls; pages that changed last time get a shorter interval, unchanged pages get a longer one, with exponential backoff up to a cap. Use HTTP conditional requests (If-Modified-Since / ETag) so unchanged pages cost a 304 response instead of a full download — often a 10x bandwidth saving on the re-crawl path.

Great: Treat it as budget allocation against a freshness objective. Estimate each page’s change rate (a Poisson model fits well) and weight it by importance (PageRank, observed query and click traffic). Spend the crawl budget where P(changed) × importance is highest, so a news homepage is crawled every few minutes while an archived page drops to yearly. Sitemaps and lastmod hints, plus push protocols like IndexNow, let cooperative sites tell you what changed instead of you polling to find out.

Design Self-Audit

Final Architecture

flowchart LR
    SEED["Seed URLs"]:::client
    FRONTIER["URL Frontier<br/>front priority queues<br/>back per-domain queues"]:::async
    FETCH["Fetcher Workers"]:::service
    ROBOTS[("robots.txt<br/>cache")]:::data
    PARSE["Parser<br/>extract text and links"]:::service
    DEDUP["Dedup<br/>Bloom filter plus SimHash"]:::service
    STORE[("Page Store<br/>object storage 750TB")]:::data
    KAFKA["Kafka<br/>new and changed pages"]:::async
    INDEXER["Indexer"]:::service
    PAGERANK["PageRank<br/>batch job"]:::async
    INDEX[("Inverted Index<br/>document sharded")]:::data
    USER["Search User"]:::client
    AGG["Query Aggregator"]:::service
    CACHE[("Redis<br/>hot queries")]:::data

    SEED --> FRONTIER
    FRONTIER -->|"1. Dequeue eligible URL"| FETCH
    FETCH -->|"2. Check crawl rules"| ROBOTS
    FETCH -->|"3. Store raw page"| STORE
    FETCH -->|"4. Hand off content"| PARSE
    PARSE -->|"5. Check if seen"| DEDUP
    DEDUP -->|"6. Enqueue new URLs"| FRONTIER
    STORE -->|"7. Change events"| KAFKA
    KAFKA -->|"8. Tokenize and index"| INDEXER
    PAGERANK -->|"9. Static authority scores"| INDEXER
    INDEXER -->|"10. Write posting lists"| INDEX
    USER -->|"11. Submit query"| AGG
    AGG -->|"12. Check hot cache"| CACHE
    CACHE -.->|"miss: scatter gather"| INDEX

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
    classDef async fill:#3b1f5e,stroke:#c084fc,color:#e2e8f0

How it works end-to-end (crawl path):

1. Frontier selects the next URL — front queues decide which domain deserves attention by priority; back queues enforce when that domain may next be hit
2. Fetcher checks crawl rules — robots.txt is fetched once per domain and cached, honoring Crawl-delay
3. Raw page lands in object storage — 750TB of HTML belongs in a blob store, not a database
4. Parser extracts text and outgoing links — the links are the crawler’s fuel; this is how discovery continues
5. Dedup filters what’s already known — Bloom filter for URL-level dedup, SimHash for near-duplicate content
6. New URLs return to the frontier, closing the discovery loop

How it works end-to-end (index and serve path):

1. Page store changes publish to Kafka — this queue is the seam that decouples crawling from indexing, so either side can lag without breaking the other
2. Indexer tokenizes and builds posting lists — entirely offline, never in a user’s request
3. PageRank supplies static authority scores — computed as a batch job over the link graph and folded in at index time, so it costs nothing at query time
4. Posting lists written to a document-sharded index — each shard owns a slice of the corpus
5. Query aggregator receives the user query
6. Hot query cache answers ~30% of traffic outright; on a miss the aggregator scatter-gathers across shards, merges each shard’s local top-K, and returns the global top 10

Key Technologies

What’s Expected at Each Level

🎯 Key Takeaways

• These are two systems, not one. Crawling is write-heavy and throughput-bound; serving is read-heavy and tail-latency-bound. The page store and Kafka are the seam that lets each scale and fail independently
• The frontier is the design. Two levels — priority in front, per-domain politeness behind — is the answer to crawling fast without getting blocked
• Bloom filter trades 1% completeness for 100x memory (12GB vs 1TB). Knowing what you gave up matters more than naming the structure
• Dedup twice: by URL (Bloom) and by content (SimHash), because mirrors and syndicated articles have different URLs and identical text
• Shard the index by document, not by term — wide fan-out but even load; then fight the resulting tail latency with hedged requests and tiering
• Do expensive work offline. PageRank, indexing, and re-crawl scheduling are batch jobs; query time only combines pre-computed scores
• Re-crawling is budget allocation, not a fixed cycle — spend where P(changed) × importance is highest

Related Designs

• Search Autocomplete - prefix serving in front of a search system
• Q&A Forum - full-text search and relevance ranking at smaller scale
• News Aggregator - content ingestion and freshness-based ranking
• Job Scheduler - the scheduling machinery behind re-crawl timing
• Rate Limiter - the per-domain politeness mechanism, generalized

Related Concepts

Understand the building blocks used in this design:

• Bloom Filters → — URL dedup for 10B URLs in 12GB of RAM
• Message Queues → — the frontier and the crawl-to-index seam
• Consistent Hashing → — pins domains to workers for DNS and connection reuse
• Object Storage → — holds 750TB of raw pages cheaply
• Database Sharding → — document-partitioning the inverted index
• Batch vs Stream → — PageRank and indexing as offline jobs
• Rate Limiting → — per-domain crawl politeness
• Retry & Backoff → — handling fetch failures and unreachable hosts

Written by SystemCraft Interview Prep Platform

Free system design, LLD, and DSA resources built by engineers who went through the interview grind at Indian and international tech companies.