Search Engine (Google)

Phase 1 — Clarify & Scope

Interviewer: Design a web search engine — think Google. What do you want to clarify?

Candidate: This is an enormous domain. Key questions:

1. Full scope (crawling + indexing + ranking + serving) or a specific component?
2. What's the web scale — how many pages indexed?
3. Index freshness requirements — how quickly should new pages appear?
4. Query volume — searches per second?
5. Should we include personalization and query understanding (autocomplete, spelling correction)?

Interviewer: Full scope — crawling, indexing, ranking, and serving. 50 billion web pages indexed. New pages should appear within 24 hours for important sites, up to 2 weeks for tail pages. 100,000 queries per second. Include basic ranking (PageRank + relevance) but not deep ML personalization.

Candidate: Let me size this:

$\text{Index size} = 50 \times 10^9 \text{ pages} \times 100\text{ KB avg} = 5 \text{ PB raw}$

$\text{Inverted index size} \approx 20\% \text{ of raw} = 1 \text{ PB (compressed)}$

$\text{Crawl rate (to recrawl every 2 weeks)} = \frac{50 \times 10^9}{14 \times 86{,}400} \approx 41{,}336 \text{ pages/sec}$

$\text{Query throughput} = 100{,}000 \text{ QPS}$

$\text{Query latency SLA} < 200\text{ ms p99}$

Phase 2 — High-Level Architecture

Interviewer: Walk me through the high-level design.

Candidate: Search has four independent pipelines: crawling (discover and fetch pages), indexing (build the inverted index), ranking (score pages), and serving (answer queries in real time).

-+ResetFullscreen

Candidate (continued):

URL Frontier is a massive priority queue of URLs to crawl. Priority is determined by:

• PageRank (high PageRank pages refreshed more frequently)
• Freshness signals (news sites crawled every hour; static pages every 2 weeks)
• Discovery priority (new URLs from sitemaps get higher priority than discovered links)

Inverted index is the core data structure: for each term (word), store a list of (document_id, position, score) tuples — the "posting list." A query like "fast database" looks up both terms' posting lists and finds documents where both terms appear.

WHY a distributed inverted index instead of a single machine? 1 PB doesn't fit on one machine. The index is sharded horizontally: each shard holds a subset of the term space (or a subset of documents). Queries fan out to all shards in parallel, each shard returns its top-K results, and a merger selects the global top-10. This "scatter-gather" architecture is what makes sub-200ms queries over a 1 PB index possible.

Phase 3 — Deep Dive & Evolution

Interviewer: Walk me through the inverted index data structure and how it handles a query.

Candidate: The inverted index maps terms to posting lists. Each posting list is a sorted array of document IDs (plus metadata) where that term appears.

Posting list structure:

Term: "database"
Posting list (sorted by doc_id):
  [
    {doc_id: 102, tf: 5, positions: [12, 45, 89], page_rank: 0.87},
    {doc_id: 203, tf: 2, positions: [3, 201],     page_rank: 0.34},
    {doc_id: 501, tf: 8, positions: [1, 2, 5...],  page_rank: 0.92},
    ...  (millions of entries for common terms)
  ]

tf = term frequency (how many times "database" appears in this document)
page_rank = precomputed PageRank score for this document
positions = word/token positions (for phrase queries: "fast database")

Compression (crucial for 1 PB index):

Doc IDs stored as delta-encoded varints:
  Raw:     [102, 203, 501, 789, 1203, ...]
  Deltas:  [102, 101, 298,  288, 414, ...]
  VarInt:  each delta compressed to 1-5 bytes (smaller deltas → fewer bytes)

Result: posting lists for common terms compress 5-10× vs raw integers

Query execution: "fast database"

1. Tokenize: ["fast", "database"]
2. Parallel lookup on all shards:
   Shard 1: posting_list("fast") ∩ posting_list("database")
   Shard 2: ...
   (each shard independent, 100ms budget)

3. Intersection algorithm (two-pointer merge):
   fast_list:     [10, 45, 102, 203, 501]
   database_list: [45, 102, 203, 400, 501, 789]
   Result:        [45, 102, 203, 501]  ← documents containing both terms

4. Score each result:
   score = tf_idf(term, doc) × PageRank(doc) × position_boost + ...
   TF-IDF: terms rare across all docs (high IDF) are more distinctive

5. Each shard returns top-10 local results
6. Merger: merge results from all shards, select global top-10

Phrase query optimization:

Query: "fast database" (exact phrase)
→ Not just co-occurrence — need "fast" immediately before "database"

Extended posting list stores positions:
fast:     doc_102 positions [5, 20, 45]
database: doc_102 positions [6, 46]

Phrase match check:
  For each doc in intersection:
    For each position p in fast_positions:
      If (p+1) in database_positions: phrase match!
  doc_102: fast@5, database@6 → match (adjacent)
  doc_102: fast@45, database@46 → match

Interviewer: How does PageRank work, and how do you compute it at web scale?

Candidate: PageRank models the web as a directed graph where a "vote" from a high-authority page is worth more than a vote from an obscure page.

Algorithm:

$PR(A) = \frac{1-d}{N} + d \sum_{B \in \text{in-links of A}} \frac{PR(B)}{|out\text{-}links(B)|}$

Where:

• $d$ = damping factor (0.85 — probability that a random surfer follows a link vs. jumping randomly)
• $N$ = total number of pages
• Intuition: A page's rank is the probability that a random web surfer is on that page at steady state

Iterative computation:

Initialize: PR(page) = 1/N for all pages

Iterate until convergence (typically 50-100 iterations):
  For each page A:
    PR_new(A) = (1-d)/N + d × Σ PR(B)/|out-links(B)|

Convergence check: max|PR_new - PR_old| < ε

Computing at 50 billion pages:

This is a graph problem with 50B nodes and ~500B edges (average 10 links per page):

Graph representation: adjacency list
  Storage: 500B edges × 8 bytes each = 4 TB

MapReduce / Spark implementation:
  Mapper: emit (destination, PageRank_contribution) for each outgoing link
  Reducer: sum contributions for each destination page

Each iteration: reads 4 TB, writes 4 TB → ~100 Spark jobs
50 iterations × 8 TB I/O = 400 TB total I/O → runs over ~6 hours on a large cluster
Runs weekly (not real-time) — PageRank is a structural signal that changes slowly

WHY not recompute PageRank in real-time? PageRank requires the entire web graph — a single new link doesn't meaningfully change rank values for established pages. Weekly batch computation is sufficient. Real-time signals (freshness, user engagement) are handled by separate ranking signals that don't require global graph traversal.

Interviewer: How does the crawl system work at 40K pages/sec while respecting robots.txt and crawl budgets?

Candidate: Web crawling at scale requires careful politeness policies — crawling too aggressively gets IPs banned.

URL Frontier architecture:

URL Frontier = prioritized work queue with per-domain rate limiting

Data structure:
  - Priority queue of domains, ordered by "time to crawl next"
  - Per-domain queue: list of URLs to crawl for that domain

Scheduler:
  For each available fetcher thread:
    Select domain with earliest "next_crawl_time" from priority queue
    Dequeue next URL from that domain's queue
    Dispatch to fetcher
    After fetch: update domain's "next_crawl_time" += crawl_delay
      (crawl_delay: from robots.txt, default 1 second per domain)

robots.txt compliance:

Before fetching any URL from domain X:
  Fetch https://X/robots.txt (cache for 24 hours)
  Parse disallowed paths:
    User-agent: *
    Disallow: /private/
    Crawl-delay: 5

  Apply rules:
    - Skip URLs matching Disallow patterns
    - Honor Crawl-delay: 5 → 1 request per 5 seconds to this domain
    - Sitemap: directive → seed URL frontier with sitemap URLs

Politeness limits:

• Max 1 connection per domain at a time (except for major news sites)
• Max 100 pages per domain per crawl cycle
• Respect crawl-delay from robots.txt (default 1s if not specified)
• Detect 429 (Too Many Requests) and back off exponentially

Freshness prioritization:

Page priority score = f(PageRank, freshness_score, discovery_type)

freshness_score:
  - News sites (nytimes.com): crawl every 15 minutes
  - Frequently updated blogs: crawl daily
  - Wikipedia: crawl weekly
  - Static corporate pages: crawl monthly

Detection: compare hash of current page vs last crawl
  If hash changed: update index, reset freshness clock
  If unchanged: increase crawl interval (exponential backoff on unchanged pages)

Phase 4 — Robustness & Operations

Interviewer: How do you serve 100K queries per second with < 200 ms p99?

Candidate: The key is the scatter-gather architecture — every query touches all shards in parallel.

Index shard sizing:

Total index: 1 PB (compressed)
Target: 200 GB per shard (fits in memory on a high-memory server)
Shards needed: 1 PB / 200 GB = 5,000 shards
Replication factor: 3 → 15,000 server-shard pairs
Physical servers: 15,000 / (10 shards per server) = 1,500 servers

Query latency budget (200 ms):

Query parsing + expansion:    5 ms
Fan-out to all shards:         5 ms  (parallel, network RTT)
Shard index lookup:           50 ms  (p99 — some shards have large posting lists)
Result merge + ranking:       20 ms
Snippet generation:           50 ms  (fetch page excerpts, compute highlighted snippets)
Network + serialization:      20 ms
Total:                       150 ms  (comfortable margin for p99 = 200 ms)

Shard failure handling:

Each shard has 3 replicas (primary + 2 secondaries)
Query fan-out: send to all 3 replicas simultaneously (hedged requests)
  → Take the response from whichever replica replies first
  → Cancel the other 2 requests

Benefits:
  - Eliminates slow replicas (tail latency reduced by ~90%)
  - Handles replica failure transparently (other 2 replicas respond)
  - p99 latency = p99(min of 3 independent samples) ≈ p(78th percentile of single sample)

Interviewer: How do you keep the index fresh — new pages indexed within 24 hours?

Candidate: The index pipeline has two tracks: batch (for bulk crawl updates) and real-time (for high-priority news/events).

Batch track (all pages, 24–336 hour freshness):

Crawl → Store raw HTML in S3 → Kafka event → Parser → Index Builder → Shard update

Kafka event: {url, crawl_time, s3_key}
Parser: HTML → tokens, links (seconds per page)
Index Builder: merges new postings into existing index shards (minutes, background)
Shard update: new delta index merged with base index during off-peak hours

Real-time track (news, trending, < 1 hour freshness):

News sources identified by:
  - High PageRank news domains (nytimes.com, bbc.com, etc.)
  - Sitemap-based discovery with <changefreq>hourly</changefreq>
  - Google News publisher submissions

Real-time pipeline:
  Crawl every 15 min → Parse → Direct index injection (bypasses batch queue)
  Index shard accepts live writes for new documents
  New document immediately queryable (with lower initial PageRank)
  PageRank updated in next weekly batch

Index freshness monitoring:

Canary queries: known test pages crawled and indexed at known times
  → Alert if canary page doesn't appear in index within expected window
  → "freshness_lag" metric dashboarded continuously

Per-domain freshness tracking:
  For top-10K domains: track last-indexed time, alert if > 2× expected crawl interval