Design search autocomplete
The dropdown that fills in your query is not a search engine — it is a latency machine that must answer faster than you can perceive, which forces every interesting decision in the design.
The hinge: keystroke amplification meets a perceptual budget
Start with the thing that makes this problem forcing, because juniors miss it: autocomplete is a far heavier read workload than search itself. A user typing r-e-s-t-a-u before clicking a suggestion has fired five or six autocomplete requests to run one search. Empirically a completed search corresponds to roughly 7 keystroke requests (people type, pause, delete, retype). So if your product does 50k searches/s, autocomplete sees on the order of 50{,}000 · 7 = 350{,}000 requests/s.
Now layer the deadline. The human perceptual threshold for "instant" is around 100 ms end to end — and that budget already includes the round-trip network time, so the server side has perhaps 30–50 ms to work with. There is no room in that budget to scan a billion historical queries, score them, sort, and return the top 10. The only way to hit 350k QPS at sub-100 ms is to have precomputed the top-k for every prefix in advance and reduced the request-time work to a memory lookup plus a couple of cheap filters. This is the single decision the whole case rotates around; lesson 02's point that latency is a budget you spend, not a property you hope for, is the lens here.
Clarify the contract
Treat the prompt as a product contract before a box diagram. What it must do:
- Given a typed prefix, return the top ~10 ranked completions (by popularity / engagement), ordered.
- Respond inside the perceptual budget — tens of ms at p99, not just p50.
- Reflect locale / language: a Japanese user and a US user typing the same Latin prefix should not see the same list.
- Pull unsafe suggestions fast — an offensive completion must be removable in seconds, not at the next nightly build.
And — just as important in an interview — what it need not do. It does not need to be transactionally consistent: a suggestion that is a few hours stale is fine; nobody is harmed if a trending query takes an hour to appear. It does not need to suggest queries that have never been typed (no spell-correction of novel strings on the hot path). It does not need per-keystroke personalization for anonymous users. Naming these non-goals is what lets you precompute aggressively and cache globally.
Put numbers on it
The arithmetic decides the structure, so do it out loud.
Read volume: 50{,}000 · 7 = 350{,}000 req/s. At that rate, even a 1 ms-per-request CPU cost is 350 core-seconds per second — you need the per-request work to be microseconds, which again means lookup, not compute.
Index size — why a raw trie hurts. Suppose you keep the top 1B distinct queries seen over the retention window. A naïve trie stores one node per distinct character transition; with pointer overhead a node is easily 30–60 bytes, and storing the top-k list at every prefix node multiplies that. A trie over a billion strings with per-node top-k cached lands in the tens to low hundreds of GB — too big to replicate cheaply into the RAM of every serving node. That number is the reason you compress: a finite-state transducer (FST) shares not just common prefixes (like a trie) but also common suffixes, collapsing the automaton and packing it into a flat byte buffer. The same vocabulary in an FST is commonly 5–10× smaller — single-digit GB — which is the difference between "fits in every node's RAM" and "doesn't." This is lesson 04's point that the data structure is the architecture, and DDIA Ch. 3's discussion of in-memory and string-keyed index structures (tries, sorted string tables) is the direct grounding.
Storage of the offline aggregate is a separate, larger number — raw query logs at, say, 50k searches/s × 200 bytes × retention — but that lives in the batch layer (cheap object storage), never in the serving path. Keep the two budgets distinct: the build can be slow and huge; the serve must be tiny and fast.
Data model & API
Keep the surface tiny and make it express the product operation, not the internal index layout.
| API / operation | Why it exists |
|---|---|
GET /suggest?q=resta&locale=en-US | The hot path. Returns an ordered top-k list. Must be a lookup; no ranking here. |
POST /admin/block {term, scope} | Out-of-band safety control. Writes to a serving-time blocklist that takes effect in seconds. |
(internal) batch build_index(logs, locale) | Offline. Aggregates logs → ranks → emits an immutable index artifact for atomic swap. |
The data that matters, and who owns it:
Linearized design
Walk an event and a request through the system; the split between the slow offline path and the fast online path is the whole design.
- 1. Log. Every search (and click) is logged with the normalized query string, locale, and a signal (was it clicked, did it lead to a result). Normalization — lowercasing, Unicode NFC, trimming — happens here and must match serving exactly.
- 2. Aggregate (batch). A periodic job groups logs by
(normalized_query, locale)and sums a popularity score (raw count, or time-decayed count so last week beats last year). - 3. Build. For every prefix that appears, compute and store its top-k completions by score, then pack the whole thing into a compressed FST with the top-k list attached at each prefix node. Output is one immutable artifact per locale.
- 4. Deploy with an atomic swap. Ship the new artifact to serving nodes alongside the live one; flip a pointer so requests move from old → new atomically. No node ever serves a half-built index.
- 5. Serve. A request normalizes
q, walks the FST to the prefix node, reads the cached top-k, then applies cheap filters: the serving-time blocklist and (optionally) a small personalization re-rank. Return. - 6. Patch urgently. A blocked term is written to the mutable blocklist and checked at step 5 immediately — a delta path that bypasses the slow build entirely.
The first bottleneck the linear walk exposes is not serving — serving is a memory read. It is the build: it must run often enough to keep suggestions fresh, over a vocabulary large enough to matter, and it must hand serving an artifact that swaps without a blip. That is why the next two deep dives are about moving ranking off the hot path and about getting fresh indexes out safely.
Deep dives
1. The trick: ranking lives offline; serving is lookup + filter
This is the load-bearing idea, so state it precisely. At request time the only work is: (a) normalize the prefix, (b) walk the FST O(len(prefix)) bytes to reach a node, (c) read the top-k list already stored there, (d) apply small filters. Step (c) is the part that would otherwise be a ranked retrieval — and we paid for it in advance, once per build, instead of per request, 350k times a second. The asymmetry is enormous: ranking a billion queries is a batch job you run hourly; reading a precomputed 10-element list is nanoseconds. Every time the design is tempted to "just check one more thing dynamically," ask whether that thing can be folded into the precompute or kept as a trivial filter — because anything heavier reintroduces the very cost the architecture exists to avoid.
What legitimately stays on the hot path is only what cannot be precomputed: the safety blocklist (changes faster than the build) and a bounded personalization re-rank (depends on the user). Both operate on the small candidate set the FST already returned, so they cost a constant factor, not a scan.
2. Global precomputed top-k vs. personalization — the cache-hit-rate fight
A global top-k per prefix is shared across all users in a locale, which is what makes caching work: lesson 06's arithmetic says hit rate is everything, and the head of the prefix distribution is extremely concentrated — a handful of one- and two-character prefixes account for a huge fraction of traffic. Cache those hot prefixes (in process, and at the edge / CDN) and you absorb most of the 350k QPS before it touches an index node at all.
Now naively personalize: make the suggestion list depend on the user. The cache key becomes (prefix, user_id) instead of (prefix, locale), the keyspace explodes by the number of users, and the hit rate collapses toward zero — every user's "re" is a cache miss. You have re-created the cost problem. The senior move is to keep retrieval global and personalize as a cheap re-rank of the shared candidate set: fetch the global top-k (cacheable), then reorder those ~10–20 items using user features. Retrieval stays shared and hot; personalization is a bounded reshuffle that never changes which list you fetched. This is also why short prefixes (1–2 chars) often skip personalization entirely — there is no signal yet and the cacheability is most valuable there.
3. Batch build + atomic swap, with a delta path for urgency
Freshness comes from rebuilding, not from mutating the index in place — an FST is a compressed immutable automaton; you do not edit it, you replace it. So the build is a classic batch job (DDIA Ch. 10): read the day's/hour's aggregated logs, produce a brand-new index artifact, and ship it. Serving nodes load the new artifact next to the live one and flip an atomic pointer — read traffic moves from v_old to v_new with no node ever exposing a partially-written index. Version the artifacts and canary by locale so a bad build (say, a normalization regression that empties half the lists) is caught on 1% of one language before global rollout.
But batch freshness is bounded by build cadence, and some changes cannot wait. That is the Lambda-architecture contrast (DDIA Ch. 10/11): a slow, complete, correct batch layer for the bulk top-k, plus a fast delta layer for the few things that must change now. The cleanest delta is the safety control: blocking a term writes to a small, mutable, hot store checked at serve time — effect in seconds, no rebuild. You could also stream trending queries into a real-time top-k overlay (a Kappa-flavored streaming approach to keep "breaking news" suggestions fresh), but the pragmatic 80/20 is batch-builds-the-bulk plus a blocklist-delta-for-safety, and only add the streaming overlay if freshness-of-trends is an explicit requirement.
Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Batch-built index vs. live mutable index | Stable, dense, compressible artifact; trivial atomic swap | Freshness lag bounded by build cadence | Suggestions come from popularity logs (almost always) |
| FST / compressed automaton vs. plain trie | 5–10× smaller — fits in every node's RAM | Immutable; build-time cost; harder to mutate | Large vocabulary, read-mostly, latency-critical |
| Global top-k vs. per-user personalized retrieval | High cache hit rate; edge-cacheable | Less per-user relevance | Anonymous traffic, short prefixes, the hot head |
| Serving-time blocklist vs. rebuild-to-remove | Removal in seconds; survives between builds | A hot-path filter check on every request | Safety / legal terms that can't wait for the next build |
The sharpest of these is global vs. personalized retrieval, because it is where candidates most often go wrong. Personalization sounds like pure upside — better suggestions — but moving it into retrieval silently changes the cache key from (prefix, locale) to (prefix, user), and that one change collapses the hit rate that lets you survive 350k QPS at all. The discipline is to let personalization touch only ordering of an already-fetched shared set, never which set you fetch. Stating that boundary explicitly is the senior signal.
Failure modes
| Failure | Mitigation |
|---|---|
| Offensive suggestion surfaces | Serving-time blocklist checked after retrieval; effect in seconds, not at next build. |
| Bad index build (e.g. normalization regression) | Versioned artifacts + canary by locale + atomic swap with instant rollback to v_old. |
| Hot-prefix overload (one/two-char prefixes) | Cache the hot head in process and at the edge (06); coalesce duplicate concurrent lookups. |
| Normalization mismatch (log vs. build vs. serve) | One shared normalization library (NFC, case, trim) applied identically in all three stages. |
| Serving node loses its in-RAM index | Index is immutable + derived; reload the artifact from object storage on startup — no data loss possible. |
Interview Q&A
- Why can't you just rank query matches at request time? (senior answer) Volume × deadline. Keystroke amplification pushes reads to ~7× search QPS (≈350k/s in the worked example), and each must answer inside ~100 ms perceived. Ranking a billion queries per keystroke is impossible in that budget, so ranking moves offline and serving becomes a precomputed top-k lookup.
- Why an FST rather than a plain trie? (senior answer) A trie over ~1B queries with per-prefix top-k lands in the tens-to-hundreds of GB — too big for every serving node's RAM. An FST shares common suffixes as well as prefixes and packs into a flat byte buffer, typically 5–10× smaller, which is what makes "replicate the whole index into RAM" feasible. DDIA Ch. 3's in-memory string index structures.
- Where does the top-k actually get computed? (senior answer) In the offline batch build: aggregate logs by (query, locale), score (time-decayed counts), and for every prefix store its top-k completions at that prefix node. Request time only walks to the node and reads the list.
- How do you keep it fresh without rebuilding the world per change? (senior answer) Lambda-style split: batch builds the bulk index on a cadence and atomically swaps it in; a fast delta path handles the few changes that can't wait — chiefly the safety blocklist, optionally a streaming trending overlay. Don't mutate the immutable FST; replace or filter.
- How do you add personalization without killing performance? (senior answer) Keep retrieval global so the cache key stays (prefix, locale) and the hot head stays cacheable; personalize only as a bounded re-rank of the ~10–20 candidates already fetched. Personalizing retrieval changes the key to (prefix, user) and collapses hit rate.
- An offensive suggestion appears and the next build is hours away — pull it now. (senior answer) Write the term to a mutable serving-time blocklist checked after retrieval, and invalidate affected cached lists. Effect in seconds. Never hot-patch the immutable index; the delta path exists precisely for things that change faster than the build.
- How do you deploy a new index without a serving blip? (senior answer) Atomic swap: load the new versioned artifact beside the live one, flip a pointer so traffic moves old→new with no half-built state, canary by locale first, and keep v_old loaded for instant rollback.
- What's the most common normalization bug? (senior answer) The logging, build, and serving stages normalizing differently (Unicode form, case, accents), so a prefix the user types never matches the indexed key. Fix by sharing one normalization routine across all three stages.
Related foundation lessons
This case leans on a few foundations with specific reasons: lesson 02 supplies the perceptual latency budget that forbids request-time ranking; lesson 06 explains why a global (prefix, locale) key and edge caching of hot prefixes is what lets 350k QPS survive — and why personalized keys destroy it; lesson 04 grounds the FST-vs-trie choice (the data structure is the architecture); and lesson 14 frames the "move work off the hot path" discipline that the whole design embodies.