System Design Case Study
Web search
What should Google Search return for a typed question: useful links in a blink? The page feels like one box, but the system already spent hours or days crawling and indexing. Then must finish in well under 200ms.
Search has two halves: prepare answers before users ask, then serve the best few results quickly when a query arrives.
Offline → online journey
Fetch pages without melting sites.
Terms point to posting lists.
Authority + ML + freshness.
Merge shards, rank, cache hot Q.
Try it: query path through the search stack
A query hits edge cache, then the serving leaf index. Indexing is a separate offline pipeline.
- User
- Front end
- Cache
- Root/mixer
- Leaf index
- Cache hits
- 0
- Leaf searches
- 0
- Mode
- cached
- Path hop
- 0
Serving
online0 cache hits, 0 leaf searches.
Indexing
offlineCrawling and index builds do not sit on the query critical path.
Tail latency
hedgedSlow leaves get hedged requests; stragglers dominate p99.
Issue a cached popular query or a fresh query that fans out to leaf shards.
What actually happens
Crawlers pull from a , honor , parse HTML, and dedupe with URL fingerprints plus . Parsed text becomes an : each term owns a .
When a query arrives, servers tokenize it, fetch postings from , merge, score with / BM25 plus and learned rankers, and return top K. Autocomplete walks an of popular prefixes.
Index freshness can lag; query latency cannot. Design crawl/index and serving as related pipelines, not one blob.
How to choose trade-offs
1. Freshness vs politeness? More crawlers across domains beat hammering one host. Hot topics get denser re-crawl budgets.
2. Latency vs completeness? Hedge slow shards and return partial/replica-backed results rather than timing out the whole search.
3. Cache what? A small fraction of queries drives most traffic: cache popular results and hot posting lists.
Simple rule of thumb
Walk crawler → inverted index → query path. Emphasize posting lists, TF-IDF/BM25, PageRank-plus-ML, caching, and the crawl-speed versus freshness trade-off.
In simple terms: build the library offline; when someone asks a question, open only the right shelves: fast.
Case-study upgrade
Web Search Serving Math
Web search has two systems: offline crawling/indexing and online query serving. Keep these paths separate in your design.
Assumptions and formulas
- Queries: 8.5B/day. Indexed pages: 100B. Crawler target: 1B pages/day.
- Online query routers fan out to many index shards and merge partial results.
- Hot normalized queries should be cached, but long-tail queries still need shard search.
Concrete math
- Queries: 8.5B/day = 98K QPS average; peak is 200K to 300K QPS.
- Crawler: 1B pages/day = 11.6K pages/sec. At 500 KB/page, ingress is 5.8 GB/sec or about 500 TB/day raw.
- Index estimate: 100B docs x 500 terms/doc x 10 bytes/posting = about 500 TB postings before extra structures and replicas.
- Query fan-out: 200K peak QPS x 20 shards = 4M shard requests/sec.
- Result cache: 10M hot queries x 5 KB/result page = 50 GB raw before replicas.
Design decisions forced by numbers
- Separate crawler politeness and indexing freshness from online serving latency.
- Use query caches, shard caches, hedged requests, and partial-result fallback.
- Publish index segments safely so old and new versions do not mix incorrectly.
Scaling to millions
- At 1M pages: a simple inverted index and cache are enough.
- At 100M pages: shard index segments and introduce offline ranking features.
- At web scale: tier freshness, compress postings, fan out queries, and serve partial results on shard failure.
Readable flow
Interview follow-ups to expect
- Which data path is offline and which is online?
- How many shards can a query touch before latency breaks?
- What does the user see if some shards are slow?
Operational readiness checklist
After the math, explain how this capacity plan is measured, protected, launched, and evolved.
Observability
- Attach each capacity estimate to a dashboard metric: p99 latency, queue age, cache hit rate, shard skew, error rate, and freshness lag.
- Alert on rate-of-change and saturation, not only hard failures; backlogs and hot keys usually warn before an outage.
Security and abuse
- Budget for auth checks, rate limits, quota isolation, audit logging, privacy filters, and abuse-review side paths.
- Separate trusted internal events from user-controlled input so retries and backfills cannot bypass policy checks.
Degraded modes
- Define the fallback when a dependency is slow: stale cache, partial results, read-only mode, delayed async work, or admission control.
- Protect the invariant first; reduce freshness, personalization, or analytics quality before risking duplicate or corrupt state.
Testing and rollout
- Test average, peak, and hot-object traffic; include retry storms, cold caches, lagging workers, and regional dependency loss.
- Use canaries, shadow reads, dual-write validation, feature flags, and explicit rollback criteria for risky path changes.
Rollout, backfill, and runbooks
- Make migrations and backfills idempotent, resumable, rate-limited, and visible through progress and error metrics.
- Write the runbook before launch: owner, dashboards, paging thresholds, mitigation switches, replay steps, and repair commands.
10x evolution
- For web search serving math, state which number forces the next move: cache memory, shard count, write amplification, queue lag, egress, or failover reserve.
- Add the next layer only when the metric forces it: sharding, regional reads, async replay, hot-key isolation, or stricter backpressure.
Scope you should nail down
Product surface
- Web search: query → ranked results
- Autocomplete as the user types
- Image/video search; knowledge panels / snippets
- Crawl and index new/updated pages
Scale targets
- ~8.5B searches/day ≈ 100K QPS (peaks higher)
- Query latency <200ms p99
- Index 100B+ pages; crawl 1B+ pages/day
Capacity picture
APIs worth sketching
- GET /search?q=: search(query, page, filters: image|video|news)
- GET /autocomplete?prefix=: autocomplete(prefix): top-K suggestions
- POST /crawl: crawl(url): internal; add URL to frontier
Web crawler
The frontier ranks eligible URLs by value and freshness while a host scheduler enforces pacing. A newly discovered link is only a candidate; it may be duplicate, disallowed, low quality, or part of an infinite URL trap. Keep separate per-host queues so a slow or busy site cannot block all crawlers. Refresh priorities from observed change rate and available crawl budget instead of treating breadth-first order as the final policy.
Fetch and apply robots.txt rules for the crawler’s user-agent, then enforce a separate conservative host-rate policy. One request per second is an illustrative starting limit, not a web standard. The Robots Exclusion Protocol standardizes rules such as Allow and Disallow; crawl-delay is an extension some crawlers support. Back off on server errors and overload responses, and recheck eligibility when a queued URL is eventually fetched.
Distributed crawlers: Workers pull from a shared frontier; each owns a subset of domains. Coordinate via distributed locks for URL deduplication.
Duplicate detection
- URL fingerprinting: normalize, hash, Bloom filter for seen URLs
- : near-duplicate pages share similar 64-bit hashes
Indexing and inverted index
- Parse HTML: extract text, strip scripts/styles
- Tokenize: lowercase, stem, remove stop words
- Build inverted index: term → [doc_id, position, frequency]
- Forward index: doc_id → terms for snippets
- Update: merge new postings; handle re-crawls
An inverted index maps a term to a posting list of documents containing it, often with term frequency and positions. For “apple pie,” intersect or otherwise combine the two lists to identify candidates before ranking. Sorted document IDs, gap encoding, and skip data reduce bytes and work. Positions support phrase matching, which distinguishes adjacent words from documents where the words appear far apart.
Term frequency measures how much a term appears in a document, while inverse document frequency gives rarer corpus terms more distinguishing weight. BM25 also limits the benefit of repeated terms and accounts for document length, making it a useful lexical baseline. This retrieves relevant candidates; link, freshness, and learned features can then rerank them. State which stage uses which signal rather than describing one universal relevance score.
// Inverted index example
"apple" → [(d1, tf=3, [0,5,12]), (d2, tf=1, [7]), ...]
"pie" → [(d1, tf=2, [6,13]), (d3, tf=1, [2]), ...]
// TF-IDF score
score(d,q) = Σ tf(t,d) × idf(t)
idf(t) = log(N / df(t))Choose an index-partitioning scheme explicitly. With document partitioning, each shard owns some documents and a local inverted index; a query fans out and merges local top results. With term partitioning, each shard owns posting lists for some terms, so multi-term queries coordinate those lists across shards. The latter can create large transfers for common terms. Keep the document/snippet store aligned with the retrieval plan.
Ranking and query processing
+ ML
Link authority plus learned rankers (LambdaMART, neural models) with features like clicks, dwell, freshness.
Freshness
News and trends need recency. Blend time-decay with relevance; re-crawl hot topics more often.
- Tokenize query (same pipeline as indexing)
- Spell check / "did you mean?"
- Optional synonym expansion
- Fetch posting lists; merge (AND/OR) with skip lists
- Rank candidates; return top K (e.g., 10)
Autocomplete
Prefix tree. Type "goo" → traverse → top-K completions with frequency at nodes.
Top-K per prefix
Precompute from query logs asynchronously. Cache hot prefixes; FST can save memory at scale.
// Trie node
node: { children: Map<char, node>,
top_queries: [(query, freq), ...] }
// On prefix "goo"
traverse("g") → ("o") → ("o")
return node.top_queries[:10]Architecture, caching, sharding
Query result cache
Cache results for repeated queries when their locale, safety policy, personalization, and index version are compatible. A shared cache key that omits those dimensions can return the wrong audience’s answer. Choose expiry from freshness needs: evergreen queries tolerate longer reuse than breaking news. Measure the actual query-frequency distribution instead of assuming a universal 80/20 hit-rate rule.
Index cache
Hot posting lists in memory to cut disk I/O.
CDN
Static assets and autocomplete suggestions at the edge.
Document-sharded indexes are a useful baseline: send the query to relevant shard replicas, retrieve bounded local top-k candidates, and merge them at the query coordinator. Replica selection and slow-shard budgets influence tail latency. If using term partitioning instead, account for distributed posting-list combination and hot terms. Publish immutable index generations consistently so a query does not combine incompatible segment metadata.
Bottlenecks to call out
Long posting lists
Term "the" in billions of docs: skip lists, tiered index, cap results.
Crawl politeness vs speed
Per-domain limits: more domains, prioritize important sites.
Index update latency
Incremental indexing and a separate fresh index for news.
Query latency
Aggressive caching, parallel fetch, early termination under 200ms.
Takeaway
Search spans crawler, indexer, and query-serving paths. Stay polite while keeping the index fresh, and make the query path merge sharded postings, ranking, and caching fast enough for sub-200ms latency.
Review the design
Crawler: URL frontier, politeness (robots.txt, rate limit), BFS/priority, Bloom filter + SimHash for dedup.
Index: inverted index (term → posting list), TF-IDF/BM25, forward index for snippets.
Ranking: PageRank + ML (LambdaMART, BERT), freshness signals.
Query: tokenize → spell check → fetch postings → merge → rank → top K.
Autocomplete: trie, top-K per prefix, async update from logs.
Caching: query result cache, index cache, and CDN; a small query fraction drives most traffic.
Sharding: index by hash(term); document store by doc_id. Parallel fetch and merge.
Compare a starting answer with a more complete design
A starting answer
Separate crawler, parser, index builder, inverted index, query service, ranking, snippet generation, and cache.
Developing the reasoning
Go deeper on shard fan-out, hedged query requests, index segment publishing, freshness versus stability, crawler politeness, spam handling, and partial-result fallback.
Deeper walkthrough
web search deeper walkthrough
Search has an offline discovery and indexing pipeline plus an online query-serving path. Do not mix crawler design and query serving into one generic service.
Requirement refinements
Clarify web search versus site search, freshness goals, personalization, spell correction, snippets, and safe-search requirements.
State that index freshness can lag, but query serving must return bounded-latency results.
API design details
Use query APIs that support pagination cursor, locale, device, safe-search, and experiment metadata.
Use crawler fetch records with robots status, canonical URL, content hash, language, and last_fetch_time.
Data model and storage
Store immutable index segments and publish them with versioning so serving can roll forward or back.
Use inverted indexes for candidate retrieval and separate feature stores for ranking signals.
Scaling strategy
Fan out queries to index shards, merge top-k candidates, and use hedged requests for slow replicas.
Prioritize crawler frontier by freshness, quality, and politeness budgets per host.
Reliability, recovery, and operations
If a shard is slow, return partial or replica-backed results rather than timing out the whole search.
Monitor query p99, slow shard rate, index freshness, crawl error rate, and cache hit rate for hot queries.
Deepening reference
Web Search: realistic production notes
Beginner mental model: Search has an offline crawl/index pipeline and an online query-serving path.
Production scope: The crawler must be polite and fresh. The query path must retrieve candidates from an inverted index, rank them, blend verticals, and serve results quickly.
Choose what the first version must guarantee
Start by deciding which web search capabilities are essential. Describe the main read and write operations before choosing infrastructure. For each operation, identify the stored records it uses and the condition that makes its result correct. A fast response is useful only if it satisfies that condition.
Next, separate work the user must wait for from work that can finish later. Estimate requests per second, storage growth, and the busiest object or customer. Use those estimates to choose one bottleneck to investigate. The calculations below are example workloads with stated assumptions; they are not measured limits of a particular product.
Core flow to walk through
Crawl: schedule URL, respect robots.txt, fetch, parse, dedup, extract links.
Index: tokenize, build inverted index, compute signals, publish immutable index segments.
Query: rewrite query, hit index shards, merge top results, rank, cache, return snippets.
Production readiness
Web Search: ship, operate, and evolve
Now examine the same request flow during failures and deployments. Tie each operational control to the user behavior it protects.
Observability
Track web search p95/p99 latency, error rate, saturation, and user-visible freshness separately for read, write, and async paths.
Alert on leading indicators such as queue age, hot-key skew, cache miss storms, reconciliation mismatches, and error-budget burn.
Security and abuse
Enforce authentication, authorization, rate limits, input validation, audit trails, and privacy checks at the service boundary.
Treat abuse controls as a first-class path: throttling, quota isolation, moderation hooks, revocation, and safe handling of sensitive data.
Degraded modes
Name what still works if cache, search, ranking, stream processing, object storage, or a regional dependency is slow.
Prefer stale-but-safe reads, partial results, async retry, admission control, and feature disablement over corrupting core state.
Testing and rollout
Load test average, peak, and hot-object traffic; add failure-injection for retries, timeouts, backlog growth, and dependency outages.
Ship with canaries, shadow reads or dual writes when useful, rollback switches, schema compatibility checks, and replay validation.
Runbooks
Document dashboards, paging thresholds, owner actions, rollback steps, data repair commands, and customer-impact language.
Keep backfills and replays idempotent, resumable, rate-limited, and observable so repair work does not create a second incident.
10x evolution
Say which metric forces the next architecture change: shard count, cache footprint, write amplification, queue lag, p99 latency, or regional failover reserve.
Evolve one bottleneck at a time: partition by access pattern, isolate hot tenants, regionalize reads, add replayable async pipelines, then harden multi-region behavior.
Hard parts worth deepening
Index freshness competes with stability and serving latency.
Query fan-out must cap tail latency from slow shards.
Crawl politeness prevents accidental denial of service against websites.
Ranking uses many signals; candidate retrieval must narrow the result set first.
Failure modes and recovery
Index shard is slow; use replicas, hedged requests, or partial results.
Crawler enters a spider trap; enforce per-host budgets and URL pattern detection.
Bad index segment published; keep previous segment and support rollback.
Trending query spike; use query/result cache and precomputed hot answers.
Signals to monitor
Query p99 shows the slow search experience. Track how often a shard exceeds its response budget and compare that with cache hit rate to distinguish broad query cost from a few overloaded partitions.
Index freshness measures the delay between a source change and searchable content. Crawl success rate explains whether missing fresh documents come from failed fetching or a later indexing backlog.
| Choice | Best when | Cost |
|---|---|---|
| Frequent incremental indexing | Freshness matters. | More merge and serving complexity. |
| Batch index rebuilds | Simplicity and stable ranking matter. | Staler results. |
| Aggressive caching | Popular queries dominate traffic. | Personalized and fresh results are harder. |
Try this scenario
Describe how a breaking news page gets crawled, indexed, and served for a trending query.
Primary sources
- Brin & Page: Anatomy of a Large-Scale Web Search Engine: seminal search architecture.
- Dean & Ghemawat: MapReduce: batch indexing roots.
- Chang et al.: Bigtable: webtable-style storage.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Build crawl, incremental indexing, inverted shards, query fan-out, distributed top-K, freshness, spam/quality, and generation rollout.
Explain the decision
How does a distributed search tier merge top-K results?
Read the reasoning
Each shard returns scored local candidates; an aggregator merges them using comparable scoring/calibration and returns the global top K.
Apply it to a production scenario
A new index generation has a ranking regression. How do you roll back?
Read one approach
Keep immutable generations, shadow queries, compare relevance/latency, route by generation version, and atomically restore the prior manifest.
Work through the numbers
A query fans to 200 shards and each fails independently 0.01% of time. Approximate chance at least one fails.
Read the worked calculation
1 − 0.9999^200 ≈ 1.98%, motivating partial-result policy, replication, and bounded retries.
Reason through a failure
What must incremental indexing preserve?
Read the recovery reasoning
A document version is either consistently searchable under the new state or superseded; deletes and privacy updates cannot be resurrected by an older segment.
Sources and further study
Continue with Design E-Commerce Marketplace.