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:
- Full scope (crawling + indexing + ranking + serving) or a specific component?
- What's the web scale — how many pages indexed?
- Index freshness requirements — how quickly should new pages appear?
- Query volume — searches per second?
- 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:
Size the crawl rate
Recrawling 50 billion pages every two weeks requires about 41,336 page fetches per second.
Size the crawl from the page count and recrawl window.
Text version
- Size the crawl from the page count and recrawl window.
- Two weeks gives fourteen days times eighty-six thousand four hundred seconds per day.
- Divide fifty billion pages by the number of seconds in that window.
- The crawler must fetch about forty-one thousand three hundred thirty-six pages each second.
- The architecture diagram describes this as about forty thousand fetches per second.
- Use the full two-week window in the denominator, not one day.
A search engine indexes 50 billion web pages, each averaging 100 KB. Engineers estimate the compressed inverted index will be roughly 20% of the raw storage size. If they need to fully recrawl all pages within a 14-day window, approximately how many pages per second must the crawler sustain?
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).
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 the full index for a subset of documents (document ). 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.
Scatter the query, gather the results
The Query Processor queries document shards in parallel; the Result Merger selects the global top-10 before snippets are added.
A user searches for fast database.
Text version
- A user searches for fast database.
- The Query Processor parses, spell-corrects and expands the query.
- The Query Processor sends the lookup to every document shard in parallel.
- Each shard returns the best results from its own part of the index.
- The Result Merger compares the shards' scores and selects the global top ten.
- The Snippet Generator adds excerpts, then returns ten results to the user.
A search engine needs to answer the query 'fast database' against a 1 PB inverted index in under 200ms. The index is horizontally sharded across hundreds of machines, with each shard holding a subset of terms. Which approach correctly describes how a query is executed against this distributed index?
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: 2, positions: [6, 46], 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 integersQuery 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-10Phrase 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 → matchInterviewer: 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:
Where:
- = damping factor (0.85 — probability that a random surfer follows a link vs. jumping randomly)
- = 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 slowlyWHY 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 URLsPoliteness limits:
- Max 1 connection per domain at a time (except for major news sites)
- Max 100 pages per domain per crawl cycle
- Respect
crawl-delayfrom 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 every 2 weeks
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)Intersect two sorted posting lists
Advance the smaller document ID; equal IDs enter the intersection and advance both pointers.
Pointer i scans the sorted fast list, and pointer j scans the sorted database list.
Text version
- Pointer i scans the sorted fast list, and pointer j scans the sorted database list.
- Ten is smaller than forty-five, so advance pointer i.
- Forty-five matches, so keep it and advance both pointers.
- One hundred two matches, so keep it and advance both pointers.
- Two hundred three matches, so keep it and advance both pointers.
- Four hundred is smaller than five hundred one, so advance pointer j.
- Five hundred one matches, so keep it and advance both pointers.
- The fast list is exhausted, so stop without checking the remaining database entry.
A search engine stores posting lists for common terms like 'the' that appear in hundreds of millions of documents. Instead of storing raw document IDs as 32-bit integers, the system stores delta-encoded variable-length integers (varints). Why does this approach compress common-term posting lists so effectively compared to storing raw integers?
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 serversQuery 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 hoursReal-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 batchIndex freshness :
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 intervalTake the first replica response
Send the lookup to all three replicas together, accept the first response, and cancel the other two requests.
The Query Processor sends the same lookup to the primary and both secondaries at once.
Text version
- The Query Processor sends the same lookup to the primary and both secondaries at once.
- The primary is slow, so the query relies on the secondaries.
- Secondary one replies first, so the Query Processor takes that result.
- The Query Processor cancels the other requests because it already has a result.
- With three independent replicas that share the same timing pattern, the shard's ninety-ninth percentile is near one replica's seventy-eighth.
A distributed search system sends each query to 3 replicas of every index shard simultaneously, accepts the first response, and cancels the remaining requests. Which of the following best describes why this 'hedged requests' strategy reduces tail latency so effectively?