50. Walkthrough: Design Web Search (Google)
The prompt. "Design Google Search" or "Design a web search engine." The interviewer doesn't expect PageRank internals. They're checking whether you can organize an enormous system into crawl → index → serve, and go deep on index partitioning, fan-out serving with tail-latency control, and freshness. Crawling is §43. This walkthrough focuses on indexing and serving.
Step 0 — Clarify the business goal
🎤 Candidate: Search monetizes through ads next to results. The user outcome is finding the answer fast, so relevance and latency drive usage (and revenue). Is this a general web search engine, or search over our own corpus such as a site or product catalog? And which features: web results only, or also images, news, and answers?
🧑💼 Interviewer: General web search, ten blue links. Freshness matters for news-like queries.
Step 1–2 — Requirements
| Functional | Non-functional |
|---|---|
| Query → top 10 ranked results with title, URL, snippet | Index: ~100B+ documents (the public figure for Google is "hundreds of billions" of pages) |
| Spelling correction, query understanding | ~100k QPS average (order of the widely cited ~8.5B queries/day), peaks higher |
| Freshness: news indexed within minutes | Latency p99 < 300 ms server-side |
| Safe search, spam/abuse resistance | Available 99.99%+; degrade gracefully (partial results beat errors) |
Step 3 — Estimates
Docs: 100B × avg 20 KB extracted text ≈ 2 PB of text; compressed inverted index ≈ 20-30% of text
→ ~0.5 PB of postings (+ forward index for snippets, + replicas) → must be sharded across 10,000s of machines
Queries: 100k QPS × fan-out to EVERY index shard (doc-partitioned) → each shard sees full query rate
→ replicate each shard ×N to carry QPS; shard count chosen so each shard's index fits RAM/SSD with latency
Result cache: query popularity is Zipfian → a cache of popular queries serves a large fraction of traffic
Step 5 — High-level architecture
Crawler (§43) ─▶ document store (raw + extracted) ─▶ Indexing pipeline:
parse, language, dedupe (SimHash), link graph → static quality scores (PageRank-like),
tokenize → posting lists (term → [doc_id, positions, features])
├─ BATCH main index: rebuilt/merged continuously in large segments
└─ FRESH index: small, updated in near real time for new/changed important pages
Serving:
User ─▶ Front end ─▶ result cache (by normalized query + locale) ─hit─▶ respond
─▶ Query understanding: spell correction, synonyms, intent, rewrite
─▶ Root/aggregator ─fan-out─▶ mid-level aggregators ─▶ leaf shards (index shard replicas)
each leaf: retrieve candidates via posting-list intersection, cheap scoring, return top-k
◀─ merge top-k across shards ─▶ expensive re-ranking (ML on top ~1000)
─▶ fetch snippets from doc servers (forward index) ─▶ assemble page ─▶ respond
Step 6 — Deep dives
- Document-partitioned vs term-partitioned index. Document-partitioned: each shard holds a complete index for a subset of documents. Every query goes to every shard (fan-out), but each shard works independently, load is even, and adding documents is easy. This is the standard choice for web search. Term-partitioned: each shard holds whole posting lists for some terms. A query touches only a few shards, but multi-term intersections need large data transfers, and hot terms create hot shards.
- Tail latency with fan-out to thousands of leaves (§22.2): tree-shaped aggregation, replicas per shard with hedged requests, per-leaf deadlines, and returning results when ~99% of shards have answered, because a slightly incomplete result beats a slow one.
- Tiered index: the most important documents (high quality score) sit in a small, fast tier that is queried first. Lower tiers are consulted only if there aren't enough good results. Most queries never touch the long tail.
- Freshness: the main index is updated in large batches or merges; a separate fresh tier takes recently crawled important pages within minutes. Results are merged across tiers. Google's Caffeine (2010) moved to continuous incremental indexing, enabled by Percolator (OSDI 2010), which runs incremental processing over Bigtable with observers and cross-row transactions.
- Ranking funnel: cheap per-leaf scoring (term matches, static quality) → global top ~1000 → ML re-ranking with many features → top 10.
Step 7 — Failure modes & corner cases
| Issue | Response |
|---|---|
| A "query of death" (a query that crashes leaf servers, e.g. by triggering a parser bug) fanned out to every shard takes down the whole serving tier | Canary the query against a few leaves first; if they crash, block it (Jeff Dean described this in his WSDM 2009 keynote) |
| Index skew: one shard with huge posting lists for a hot term | Balance by document count and postings size; replicate hot shards more |
| Breaking news: a query spike for a term not in the cache | The result cache absorbs repeats after the first; the fresh tier ensures relevance |
| Spam and SEO manipulation | Link graph analysis, quality classifiers, demotion at indexing time |
| Deleted or removed content (legal takedowns) | A fast removal path at serving time (filter list), independent of index rebuilds |
🌍 Real-world references
- Brin & Page, "The Anatomy of a Large-Scale Hypertextual Web Search Engine" (1998): the original Google architecture.
- Jeff Dean, "Challenges in Building Large-Scale Information Retrieval Systems" (WSDM 2009 keynote): a decade of Google index and serving evolution: in-memory indexes, encoding schemes, canary requests, and the query of death.
- Percolator (OSDI 2010) and Caffeine: incremental indexing.
- The Tail at Scale (2013): the fan-out latency techniques used in search serving.