Search Engine

Problem Statement & Requirements

Functional Requirements

• Web crawling -- discover and fetch billions of web pages continuously
• Indexing -- build an inverted index mapping terms to documents
• Query processing -- parse and understand user queries (spell correction, synonyms, intent)
• Ranking -- return the most relevant results using signals like PageRank, content relevance, freshness
• Snippet generation -- extract and highlight relevant text snippets for each result
• Autocomplete / suggestions -- suggest queries as user types (covered in separate design)
• Image / video / news verticals -- blend different content types into results
• Ads integration -- serve relevant ads alongside organic results
• Personalization -- tailor results based on user history, location, language
• Knowledge panels -- structured answers for entities (people, places, companies)
• Safe search / content filtering -- filter explicit or harmful content

Non-Functional Requirements

• Ultra-low latency -- search results in < 200 ms (end-to-end)
• High availability -- 99.99% uptime, search must never go down
• Massive scale -- index 100B+ web pages, serve 100K+ QPS
• Freshness -- breaking news indexed within minutes; general web within days
• Relevance quality -- users find what they need in first 3 results (high precision)
• Fault tolerance -- no single point of failure; graceful degradation
• Global distribution -- low latency for users worldwide

Scope Boundaries

Scale Estimations

Index & Content

Crawling

Query Traffic

Storage Summary

Bandwidth & Compute

This first layer defines the system boundary. The next chapters add application logic and data dependencies. After examining the request paths and tradeoffs, we will add operational safeguards and bring the complete architecture together.

A search request carries the query, locale, filters, and pagination context. The response should distinguish no matches from incomplete results caused by a failed shard. Keep internal ranking features out of the public contract, and use a stable cursor or search snapshot when deep pagination must remain consistent.

Data Storage Architecture

Storage Layer Summary

Index Server Architecture (Single Machine)

Ranking System

Multi-Phase Ranking Architecture

Key Ranking Signals

BM25 Scoring Formula

BM25(D, Q) = Σ  IDF(qi) × [ f(qi, D) × (k1 + 1) ]
            qi∈Q           [ f(qi, D) + k1 × (1 - b + b × |D|/avgdl) ]

Where:
  qi        = i-th query term
  f(qi, D)  = term frequency of qi in document D
  |D|       = document length (in terms)
  avgdl     = average document length across corpus
  k1        = 1.2 (term frequency saturation parameter)
  b         = 0.75 (document length normalization)
  IDF(qi)   = log((N - n(qi) + 0.5) / (n(qi) + 0.5) + 1)
  N         = total number of documents
  n(qi)     = number of documents containing qi

PageRank Algorithm

PageRank(A) = (1 - d) + d × Σ  PageRank(T) / OutLinks(T)
                              T∈BackLinks(A)

Where:
  d = damping factor = 0.85
  T = pages that link to page A
  OutLinks(T) = number of outbound links from page T

Computation at scale:

Optimizations:

• Partition by host: Pages on same host tend to link to each other → locality
• Dead-end handling: Pages with no outlinks distribute rank to all pages (random surfer)
• Spam resistance: TrustRank propagates trust from seed set of known-good pages
• Topic-sensitive PageRank: Compute per-topic PageRank vectors for better relevance

Indexing Pipeline

Document Processing Flow

Inverted Index Structure

Posting list encoding (compression):

• DocID gaps: Store delta-encoded DocIDs (42, +1295, +8662) instead of absolute
• Variable byte encoding (VByte): Small gaps = 1 byte, large gaps = 2-4 bytes
• Block-based compression: Group 128 DocIDs per block, compress with PForDelta
• Skip pointers: Every 128 docs, store a skip pointer for fast intersection

Index size math:

• 100B documents x 500 unique terms/doc = 50 trillion postings
• Average posting size (compressed): ~8 bytes (docID gap + TF + positions compressed)
• Total: ~400 TB raw, ~500 TB with skip pointers + term dictionary

Index Sharding Strategy

Two sharding approaches:

Google's choice: Document-partitioned indexing

• ~10,000-100,000 shards, each holding ~1M-10M documents
• Each shard is replicated 3-5 times for availability + load balancing
• Query is broadcast to all shards; each returns top-K results; aggregator merges

Incremental Indexing

• Base index: Rebuilt every few days via MapReduce over entire corpus
• Real-time index: Streaming pipeline (like Percolator) for fresh content
• Merge: At query time, results from both are unioned and ranked together
• Freshness target: Breaking news pages indexed in < 2 minutes

Query Processing Pipeline

End-to-End Query Flow

Query Understanding Details

Spell correction:

• Edit distance (Levenshtein) against dictionary of known terms
• Noisy channel model: P(correct | misspelled) ∝ P(misspelled | correct) × P(correct)
• Training data: query logs with user reformulations ("appel pie" → user clicked "apple pie" results)

Query expansion:

• Synonym expansion: "car" → also search "automobile", "vehicle"
• Stemming: "running" → "run" (Porter stemmer or language-specific)
• Phrase detection: "New York" treated as single token, not "New" AND "York"

Intent classification:

Posting List Intersection (Core Algorithm)

For query "apple pie recipe", we intersect 3 posting lists:

apple:   [2, 5, 12, 42, 55, 100, 1337, ...]      (1M docs)
pie:     [5, 12, 20, 42, 88, 1337, ...]            (500K docs)
recipe:  [12, 42, 67, 1337, 5000, ...]              (2M docs)

Algorithm: Two-pointer intersection with skip pointers

Step 1: Start with shortest list (pie: 500K docs)
Step 2: For each docID in pie, binary search / skip in apple and recipe
Step 3: If found in all three → candidate

Result: [12, 42, 1337, ...]    (intersection)

Optimization: WAND (Weighted AND) algorithm
- Don't require ALL terms to match
- Score threshold: skip docs that can't beat current top-K score
- Upper bound per term: max contribution any doc can get from that term
- Skip entire blocks of posting list when upper bound sum < threshold

WAND Algorithm (Weak AND):

For each term t in query:
    upper_bound[t] = max TF-IDF score any doc can get for t

sorted_terms = sort terms by current posting list pointer (ascending docID)

while not done:
    // Find pivot: first term where cumulative upper bounds >= threshold
    cumulative = 0
    for i, term in sorted_terms:
        cumulative += upper_bound[term]
        if cumulative >= threshold:
            pivot_doc = posting_ptr[term].current_doc
            break

    // Advance all terms before pivot to pivot_doc
    // If all terms reach pivot_doc, fully score it
    // If score > threshold, add to top-K heap, update threshold

Cache popular queries only with the context that changes their answer: language, filters, permissions, and index version where needed. Shards can keep frequently accessed index blocks warm. Bound candidate counts before expensive reranking so an unusually broad query cannot consume an unbounded share of serving capacity.

Web Crawling Subsystem

URL Frontier (Priority Queue)

The URL frontier determines what to crawl next. It must balance freshness, importance, and politeness.

Priority assignment:

• P0 (minutes): Major news sites, trending topics, high-PageRank pages
• P1 (hours): Popular sites, frequently updated content
• P2 (days): Medium-traffic sites, blogs
• P3 (weeks-months): Long-tail pages, rarely changing content

Politeness policy:

• Respect robots.txt -- fetch and cache per domain
• Max 1 request per domain per second (configurable)
• Back-queue per host ensures sequential per-host fetching
• Exponential backoff on errors (429, 503)

Crawler Worker Flow

Deduplication Strategy

SimHash for near-duplicate detection:

1. Tokenize page into shingles (3-grams of words)
2. Hash each shingle to 64-bit value
3. Compute weighted sum -> 64-bit fingerprint
4. Two pages with Hamming distance ≤ 3 are near-duplicates
5. Use multi-probe lookup table for efficient comparison

PageRank & Link Graph

Link Graph Storage

PageRank Convergence

Iteration   Max ΔPageRank    Time per iteration
    1          0.50              ~2 hours
    5          0.10              ~2 hours
   10          0.02              ~2 hours
   20          0.005             ~2 hours
   40          0.0001            ~2 hours
   50          < 0.00001         CONVERGED

Total compute: ~100 hours on 10,000 machines
Frequency: Recomputed weekly (or continuously with incremental updates)

Beyond Basic PageRank

Snippet Generation

Snippet Selection Algorithm

For each result document (top 10):

1. Fetch cached page content (from content store or cache)

2. Split page into sentences / passages

3. For each passage, compute relevance score:
   - Term overlap with query (weighted by IDF)
   - Position in document (earlier = higher weight)
   - Proximity of query terms to each other
   - Is passage in a heading, list, or structured element?
   - Does passage form a complete thought?

4. Select best passage (highest score)

5. Truncate to ~160 characters, respecting word boundaries

6. Bold query terms in snippet:
   "The best <b>apple pie recipe</b> uses Granny Smith <b>apples</b>
    with a flaky butter crust..."

7. Cache snippet for this (query, docID) pair

Featured Snippets (Position Zero)

Ads Integration

Ad Serving in Search Results

Ad Rank = Bid × Quality Score

• Quality Score = f(expected CTR, ad relevance, landing page experience)
• Winner pays: (next ad rank / winner's quality score) + $0.01

Advanced Topics

Semantic Search (Neural Retrieval)

Real-Time Indexing Pipeline (Google Caffeine)

Handling Scale: Tiered Index

Tier 1: "Hot" index (top 10B pages by PageRank)
  - Fully in-memory posting lists
  - Serves 80% of queries (popular terms + high-quality pages)
  - Fastest response time

Tier 2: "Warm" index (next 40B pages)
  - SSD-backed posting lists, cached in memory when hot
  - Queried only if Tier 1 doesn't return enough results
  - Slightly slower

Tier 3: "Cold" index (remaining 50B pages)
  - SSD/HDD-backed
  - Only queried for rare/long-tail queries
  - Slowest but most comprehensive

Query flow:
  1. Always query Tier 1
  2. If < 10 good results, also query Tier 2
  3. If still < 10, query Tier 3
  4. Merge and re-rank across tiers

A document can change after retrieval but before the reader opens it. Preserve a version or crawl timestamp so snippets are explainable. Deleted or access-restricted documents need prompt filtering, and a slow shard needs an explicit timeout policy rather than holding every other shard’s results indefinitely.

Key Tradeoffs

Freshness vs. Index Quality

Precision vs. Recall

Document-Partitioned vs. Term-Partitioned Index

Pre-computation vs. On-the-fly

Latency vs. Quality

Budget: 200 ms total

If we spend MORE time on ranking:
  + Better result quality (more features, deeper models)
  - Higher latency → users leave (Google data: +200ms = -0.6% searches)
  - More compute cost

If we spend LESS time on ranking:
  + Faster results → happier users
  + Lower compute cost
  - Worse relevance → users reformulate / leave

Solution: Multi-phase ranking
  - Cheap phases process many candidates quickly
  - Expensive phases only run on small candidate set
  - Strict timeout per phase with fallback to simpler model

Fault Tolerance & Reliability

Replication Strategy

Failure Scenarios & Handling

Graceful Degradation

When the system is under stress:

1. Drop neural re-ranking (Phase 3) -- fall back to ML tree model (saves ~30ms)
2. Reduce shard fan-out -- query subset of shards (partial results, still useful)
3. Increase cache TTL -- serve slightly stale results
4. Shed low-priority queries -- deprioritize bot traffic, prefetch requests
5. Disable personalization -- serve generic results (cheaper to compute)

Monitoring & Operational Concerns

Key Metrics to Monitor

Operational Runbook Scenarios

High-Level Architecture

Detailed Architecture

Serving Infrastructure

Global Distribution

Caching Layers

Layer 1: Result Cache (in-memory, per DC)
  Key: normalized_query + locale + page
  Value: serialized search results (top 10 + snippets)
  TTL: 5-15 minutes
  Hit rate: ~30% (head queries)
  Size: ~100 GB per DC

Layer 2: Posting List Cache (in-memory, per index server)
  Key: term
  Value: compressed posting list (or partial)
  Policy: LRU, prioritize high-IDF terms
  Hit rate: ~80% for popular terms
  Size: ~64 GB per machine

Layer 3: Document Cache (in-memory)
  Key: doc_id
  Value: title, URL, cached snippet, metadata
  Size: ~32 GB per machine

Layer 4: DNS Cache
  Resolved hostnames cached for crawlers
  TTL: follow DNS TTL headers

Latency Budget Breakdown

Tail Latency Management

Search for a breaking news event a minute after it starts. Compare a fresh but noisy incremental index with yesterday’s more thoroughly processed index. Work through how they merge, how duplicates disappear, and how ranking avoids treating freshness as a universal substitute for relevance.

System Design Interview Tips

What interviewers are looking for

1. Crawling at scale -- URL frontier design, politeness, deduplication
2. Inverted index internals -- posting lists, compression, skip pointers
3. Ranking pipeline -- multi-phase architecture, key signals, BM25 + PageRank
4. Serving at scale -- sharding, replication, caching, latency budgets
5. Tradeoff reasoning -- freshness vs quality, precision vs recall, cost vs latency

Common follow-up questions

Suggested 45-Minute Interview Structure

0-5 min:   Clarify requirements (web search? scale? real-time?)
5-10 min:  Scale estimations (pages, QPS, storage)
10-20 min: High-level architecture (crawl → index → serve)
20-30 min: Deep dive into ONE area:
           - Option A: Inverted index + query processing
           - Option B: Crawling + URL frontier
           - Option C: Ranking pipeline
30-40 min: Tradeoffs + scaling concerns
40-45 min: Monitoring, failure handling, future extensions