Search system design & serving

The Search capstone. The interviewer says "design Google web search" or "design product search for an e-commerce site." This lesson assembles lessons 40–48 into one end-to-end design, with the serving engine, the latency budget, and the capacity arithmetic you must be able to do out loud. The calculator at the bottom is that arithmetic, made live.

This lesson assembles the whole track

Every prior Search lesson is a stage in the system you are about to draw. This capstone is where they slot together, the same way lesson 11 assembled the recommender/ads track. The difference: lesson 11 covered a recommendation feed (no query) and sponsored search ads (an auction at the end). Here the artifact is organic search serving — a user typed a query, and you return ten blue links (or ten products) ranked by relevance, with no auction and no bid.

The shared-track pointers you will lean on: 17 (real-time streaming) for the indexing pipeline, 18 (deployment & serving) for the model-serving layer, and 19 (large-scale optimization) for the cost levers. We do not re-derive ANN — that's lesson 03 — but we reuse its scatter-gather and sharding framing directly.

Ride the interview rhythm — for search

Same arc as lesson 11; don't fight it. The only thing that changes is what you fill into each slot.

1. Clarify scope. Corpus size, QPS, freshness requirement (news-fast vs catalog-stable), latency target, what "relevant" means for this product. Two minutes.
2. Define metrics. Online (CTR@1, click-through, reformulation rate, zero-result rate, success/abandonment); offline (NDCG on judged queries, lesson 48); guardrails (p99 latency, index freshness lag).
3. Draw BOTH paths. This is the search-specific move. A recsys candidate draws one funnel; a search candidate draws the query path and the indexing path, because in search the index is a living thing and freshness is half the system.
4. Zoom where steered. Sharding & tail latency, freshness/NRT, caching, the rerank cascade, or a failure mode. The remaining time lives here.
5. Failure modes & operations. Zero results, shard down, recall collapse after an index change, query-of-death, rollback. Volunteer these — juniors wait to be asked.

Step 1 · Clarify — five questions

Take a concrete worked instance to anchor every number for the rest of the lesson: web/document search over a 1-billion-document corpus.

• Corpus. N ≈ 10⁹ documents, average ~5 KB analyzed text each. Mixed freshness: most stable, a long tail of news/social that must be searchable within seconds.
• Traffic. ~50,000 QPS at peak. A Zipf head (lesson 40): the top ~1% of distinct queries are a large fraction of traffic, which is why result caching pays off massively here.
• Latency. End-to-end p99 < ~300 ms (the user perceives anything past ~half a second as sluggish; 300 ms leaves headroom for network + render).
• Freshness. Two-tier. A new news article must be findable in seconds (NRT); a re-priced product in tens of seconds; a stable archival doc can lag minutes.
• Relevance objective. Topical relevance + freshness + (for e-commerce) availability/margin. "Relevant" is judged by graded human labels (lesson 48), validated online by interleaving.

Step 2 · Metrics

The search-specific guardrail juniors forget is zero-result rate. A relevance change that quietly raises the fraction of queries returning nothing is a worse user experience than a small NDCG dip, and it won't show up in NDCG (you only judge queries that had results).

Step 3 · Draw both paths

This is the diagram to draw in 60 seconds. The left column is what happens when a query arrives; the right column is what happens when a document changes. They meet at the index.

The two paths are asynchronous and decoupled. A reader never blocks on a writer: the indexing path produces immutable segments, and the query path only ever sees a consistent set of currently-visible segments. That decoupling is the whole reason search engines can serve 50k QPS while ingesting a firehose of updates — which brings us to the engine.

Step 4 · The index serving engine — production reality

The interviewer who has run search will probe here, because this is where "I know retrieval" becomes "I have operated a search backend." Name the substrate: the Lucene → Elasticsearch / OpenSearch / Solr → Vespa lineage. Lucene is the segment-based inverted-index library underneath Elasticsearch and Solr; Vespa is the engine Yahoo built for combined lexical + tensor (dense) retrieval at serving time. These are the production answer; you rarely build the engine yourself.

Sharding by document → scatter-gather

One billion documents do not fit (or serve fast enough) on one machine, exactly the argument from lesson 03's ANN sharding. You partition documents across S shards (each shard a self-contained index over its slice of the corpus). A query is scattered to all S shards in parallel; each returns its local top-K; a coordinator gathers and merges into a global top-K.

Critically, you shard by document, not by term. Term-partitioning (each shard owns some terms' full posting lists) sounds appealing but is a disaster at serving time: a multi-term query must hit several shards and ship enormous posting lists between them, and load is wildly skewed toward shards holding common terms. Document-partitioning gives each shard a balanced slice and a self-contained query; the only cost is that every query fans out to every shard — which is exactly the tail-latency problem we quantify in Step 6.

Replication for QPS & HA

Each shard is replicated across R replicas. Replication does two jobs: it multiplies read throughput (search is read-heavy, so replicas are cheap and linear in QPS), and it is your high-availability story — if one replica of a shard dies, others still serve that shard's slice. Lose all replicas of one shard and you lose that slice of the corpus, not the whole system — you degrade to partial results (Step 7), you don't go dark.

The segment-based NRT model

An index is not one mutable file — it is a set of immutable segments, each a mini-index (its own posting lists, doc store, term dictionary). This is the single most important mechanism to articulate:

• Writes append. New/updated docs go into a fresh in-memory segment. You never edit an existing segment — immutability is what lets readers run lock-free against a frozen view.
• A refresh makes a segment visible. Periodically (Elasticsearch default ~1 s) the in-memory buffer is flushed to a new searchable segment. This is the "near-real-time" in NRT: the lag between a doc arriving and being findable is one refresh interval, not one full index rebuild.
• Deletes are tombstones. You can't remove a doc from an immutable segment, so a delete just marks it; the query path filters tombstoned docs out of results.
• Merge reclaims. Segment count grows with every refresh; too many small segments slows queries (each must be searched). A background merge compacts small segments into larger ones and physically drops tombstoned docs. Merging is the dominant background-IO cost and the thing that competes with query latency for disk/CPU.

Tiered indexes: hot recent + cold archival

Not all documents are equal. A small hot tier holds recent/popular docs on fast hardware (lots of RAM, NVMe, frequent refresh); a large cold tier holds the archival bulk on cheaper, denser storage with infrequent refresh. Most queries are satisfied by the hot tier; only deep or archival queries reach cold. This mirrors the two-tier freshness pattern from lesson 03's ANN section (small online index + large nightly index) and is the same idea Elasticsearch ships as hot/warm/cold node roles. It is also a cost lever (lesson 19): you pay for fast hardware only on the small slice that needs it.

Step 5 · Latency budget & the tail

End-to-end p99 < ~300 ms. Break it down per stage (representative, document-search profile):

Notice the stages do not simply add at p99: the end-to-end p99 is not the sum of per-stage p99s (that would be pessimistic — it's unlikely every stage is simultaneously at its own p99). But within retrieval, the scatter-gather has a structural problem that makes its tail far worse than any single shard's tail.

Scatter-gather tail amplification — the number to compute live

A query is only as fast as its slowest shard, because you must gather all of them before merging. If each shard independently meets its p99 at 40 ms — i.e. each shard is fast (≤ 40 ms) with probability 0.99 — then a query fanned out to S shards is fast only if all shards are fast:

P(query ≤ 40 ms) = 0.99^S

For S = 20 shards:

0.99²⁰ ≈ 0.818  ⇒  ~18% of queries hit at least one slow shard

So a per-shard p99 of 40 ms produces a query-level p82 of 40 ms — the query's p99 is dragged out toward the worst shard's tail, not 40 ms. Concretely: what's a per-shard 99th percentile becomes only the ~82nd percentile at the query level. Fan out to 100 shards and 0.99¹⁰⁰ ≈ 0.366 — barely a third of queries dodge a slow shard. The more you shard, the worse your tail, all else equal. This is the single most counter-intuitive serving fact and the one interviewers love.

Step 6 · Caching — where the Zipf head pays off

Lesson 40's defining fact: search queries follow a Zipf distribution, so a small set of head queries is a large share of traffic — and identical queries return identical results (modulo personalization). That makes caching far more valuable in search than in a personalized feed. Two layers:

• Query-result cache. Key on the normalized query (+ filters + any coarse personalization bucket); value is the SERP. A head query served from cache skips the entire query path — understanding, scatter-gather, LTR, rerank. This is the big one.
• Posting / segment cache. Inside the engine, hot posting lists and segment pages live in the OS page cache and the engine's filter/query caches. Even on a cache-miss query, the term postings for common words are already in RAM, so retrieval doesn't hit disk.

Effective backend QPS after caching — the arithmetic

Suppose the result cache serves a 30% hit rate (a conservative number for a Zipf head). Then only misses reach the backend:

QPS_backend = QPS × (1 − hit_rate) = 50,000 × (1 − 0.30) = 35,000 QPS

A 30% hit rate cut backend load by 30% — you provision for 35k, not 50k. Head-heavy products see 50–70% hit rates, turning 50k of front-door QPS into ~15–25k of backend QPS. The cache is often the cheapest QPS you will ever buy. The two costs to name: staleness (a cached SERP can be served after the underlying docs changed — bound it with a short TTL on fresh-intent queries) and personalization (a per-user SERP is uncacheable; the common pattern is to cache the shared ranking and apply personalization on top, or cache per coarse bucket, not per user).

Step 7 · Freshness — how fast a doc becomes searchable

"Freshness" is the indexing-path SLA: the lag from a document arriving to it being returnable by a query. It is a per-tier decision, not a single number:

The mechanism is the segment refresh from Step 4, and the trade-off is the refresh↔merge↔cost triangle: you buy freshness with CPU. The senior point is to route freshness — fast tier for fresh-intent content, slow tier for the bulk — rather than pay news-speed refresh costs on a billion stable docs.

Step 8 · Capacity planning — the napkin math

Given QPS, corpus size, and per-shard capacity, derive the cluster. Show every step.

Shard count from doc volume

A shard should hold roughly as many docs as it can search within its latency slice — call it 50M docs/shard for this profile (a common Elasticsearch rule of thumb is "tens of GB / tens of millions of docs per shard"):

S = N / docs_per_shard = 10⁹ / 50×10⁶ = 20 shards

Replica count from QPS

Every query hits one replica of every shard, so the per-replica query rate equals the backend QPS (35k after caching). If one node serves one shard-replica at, say, 2,000 QPS within the latency budget, then per shard you need:

R = ⌈QPS_backend / per_node_QPS⌉ = ⌈35,000 / 2,000⌉ = 18 replicas per shard

Round up and add HA headroom (you must survive losing a node and a deploy at once) → say R = 20. Total serving nodes:

nodes = S × R = 20 × 20 = 400 nodes

RAM for the index

The hot working set wants to live in RAM (page cache + dense ANN graph). Inverted index ≈ a fraction of raw text; dense vectors are the heavy part (lesson 03): 10⁹ docs × one 768-dim fp32 vector = 10⁹ × 768 × 4 B ≈ 3 TB raw — which is exactly why you'd quantize (PQ → 8–32× smaller) or keep dense only on the hot tier. Across 20 shards that's ~150 GB of vectors per shard before compression: comfortably a per-node RAM budget once PQ'd, and the reason the cold tier may stay lexical-only.

Rough $/query

If 400 serving nodes cost on the order of $1/hour each (commodity instance, blended), that's $400/hour for 35,000 × 3,600 ≈ 1.26×10⁸ backend queries/hour:

$/query ≈ 400 / (1.26×10⁸) ≈ 3×10⁻⁶  ⇒  ~$3 per million queries

This is order-of-magnitude only — it ignores the cross-encoder GPU fleet (lesson 18), the indexing cluster, and storage — but it's the shape of the answer, and notice the cache directly scaled it: a 50% hit rate halves backend nodes and roughly halves $/query. That linkage (caching → fewer nodes → lower $/query) is what the widget below makes live.

Step 9 · Failure modes a senior volunteers

Interactive · search capacity & latency-budget calculator

This is the arithmetic from Steps 5, 6, and 8, made live — the search analogue of lesson 11's latency-budget simulator. Set your QPS, corpus size, docs-per-shard (which fixes the shard count and therefore the fan-out), replica count, per-shard p99, and cache-hit rate. The KPIs show the derived shard count, the fan-out, the effective backend QPS after caching, and an estimated query p99 that includes scatter-gather tail amplification — then a verdict.

Junior vs senior, distilled (search edition)

Interview prompts you should be ready for