Knowledge Guide
Home › Hands-On Builds › SD Design Labs

Design Typeahead / Search Autocomplete

Design Typeahead / Search Autocomplete

Here is the answer that sounds complete and is a trap: "keep the queries in a table, and on every keystroke run SELECT query FROM queries WHERE query LIKE 'sys%' ORDER BY popularity DESC LIMIT 10." It compiles, it returns the right rows in a demo with a thousand queries, and it dies the instant it meets real traffic. The reason is a budget you must state out loud before you draw a box: a suggestion has to come back in under ~100ms, on every keystroke, at search-engine query volume. We'll compute below that "every keystroke at volume" is on the order of ~1.16 million requests/second, and that the naive LIKE/re-rank approach needs to sort tens of millions of rows per single keystroke. Those two numbers cannot coexist. This lab derives the design that makes them coexist — the one real interviewers are probing for when they ask "how does Google finish your query as you type" — and the whole thing turns on one insight: do the ranking work offline, once, and store the answer for a prefix directly at that prefix's node so query-time is a walk, not a search.

1. The Trap — why "LIKE 'prefix%' + ORDER BY popularity" detonates on contact

Take the naive design at face value and trace one keystroke through it at real scale. Assume (we derive these in Movement 4) ~5 billion searches/day, so users are typing at roughly 1.16 million keystrokes/second, and each keystroke wants the top-10 completions for the prefix typed so far, back in under 100ms.

Failure mode A — the range scan + sort. The user has typed just s. Your index (even a perfect B-tree on the query string) can find the range of rows starting with s quickly — but that range is tens of millions of rows (any indexed query beginning with "s"). To return the top 10 by popularity you now have to read and rank that entire range, because popularity order is unrelated to alphabetical order. That's an O(matches × log K) heap over ~50M rows — hundreds of milliseconds for one keystroke, already blowing the 100ms budget by itself. A composite index on (prefix, popularity) doesn't save you either: prefixes are unbounded, you can't index every one.

Failure mode B — re-ranking a subtree on every keystroke. Suppose you got smart and put the queries in a trie so you can find the prefix node in O(len). You still have to answer "top 10 under this node," and if you compute that by traversing the whole subtree and heaping it every time, prefix s's subtree holds ~50M queries. That's ~50M operations per keystroke × 1.16M keystrokes/s ≈ 5.8 × 10¹³ operations/second. No cluster you can afford does that. The trie found the node fast, then you threw the win away by re-ranking on read.

Both failures share one root cause: the expensive part (ranking a large candidate set) is being done on the hot, per-keystroke path. Feel that before reading on — the entire design is the removal of that work from the request path.

2. Scope it like a senior (ask before you design)

Don't draw anything yet. Each of these answers moves the design, so pin them down first:

Assume for this lab: prefix-only matching (typo-tolerance is a stretch goal, Movement 7); global popularity ranking (not personalized) — realistic for a first cut and it's what makes the precompute-once idea work; trending must surface within minutes, not next-day; K = 10; ASCII first, Unicode as an extension; 5 billion searches/day, average query length ~20 characters, and we index the ~500 million distinct queries popular enough to matter (a query seen a handful of times a year isn't worth a suggestion slot).

3. Reason to the design (derive it, don't recite it)

Attempt 1 — query the source of truth per keystroke. This is the Trap. Whether it's LIKE 'prefix%' on a SQL table or a subtree scan on a trie, the ranking work lands on the hot path and the numbers (Movement 1) make it impossible. The lesson: the candidate set for a short prefix is enormous, and ranking it is what's expensive.

Attempt 2 — put queries in a trie so lookup is fast. A trie (prefix tree) turns "find everything under prefix sys" into a walk of len("sys") = 3 pointer hops to the sys node — genuinely O(prefix length), independent of how many queries exist. That fixes finding the node. But it does not fix ranking: the node just marks a position; the top-10 still live somewhere in the subtree below it, and computing them on read is Failure Mode B. The trie is necessary but not sufficient.

Attempt 3 — the key insight: precompute and cache the top-K AT each node. Nothing forces us to compute the top-10 when the user asks. Popularity comes from query logs, which we already have, and it changes slowly. So do the ranking offline, once: for every node in the trie, precompute the top-10 most popular completions that pass through it and store that list right on the node. Now a keystroke is: walk to the node (O(prefix len)), read the list already sitting there (O(K)), return. No scan, no sort, no candidate set at query time — the work that was 50M ops/keystroke is now ~23 pointer reads. The hard part didn't disappear; it moved off the request path into a batch job.

Attempt 4 — serve it all from memory, build it from logs, shard for size. The precomputed trie is a read-only, in-memory structure (a disk seek per keystroke would blow the budget). We build it with a batch pipeline: aggregate the last N days of query logs (a map-reduce sum with time-decay so last month's fad doesn't outrank today), construct the trie with each node's top-K, and publish an immutable snapshot the serving tier loads. It's too big for one box (Movement 4: ~1.28 TB), so shard it by prefix. And because reads concentrate on short prefixes (everyone's first keystroke is one of 26 letters), a small front cache of hot prefixes absorbs most traffic. That is the whole architecture, and every piece of it exists to keep the per-keystroke path a memory walk.

Why this is the right shape: typeahead is a textbook read-heavy, staleness-tolerant workload. Suggestions can be a few minutes stale with zero user harm, but they must be instant. That asymmetry is exactly what "precompute offline, serve from memory" is built for — you trade freshness (bounded, controllable) for latency and cost (enormous wins). Get that trade-off articulated and the rest is mechanics.

4. Build it — the design worksheet

This is the artifact you'd produce on the whiteboard in a 45-minute round. Numbers are traced, not asserted — recompute them yourself before an interview.

Requirements

Functional: (1) suggest(prefix) → ordered top-K completions; (2) rankings reflect global query popularity; (3) trending queries surface within minutes; (4) new/rare queries eventually enter the index. Non-functional: (1) p99 < 100ms per keystroke end-to-end; (2) extremely high read availability (suggestions degrading gracefully is fine, hard-erroring is not); (3) eventual consistency / bounded staleness is acceptable (this is the freedom the whole design spends); (4) horizontally scalable in both memory footprint and QPS.

Back-of-envelope estimation (BOTE)

API sketch

GET /suggest?q={prefix}&k=10&lang=en
    -> 200 { suggestions: ["system design", "systems", "sysadmin", ...] }   // <100ms, from memory
    -> 200 { suggestions: [] }   // prefix past the last indexed node — empty, not an error

// OFFLINE control plane (NOT on the keystroke path):
updateFrequencies(logWindow)     // batch: aggregate + time-decay query counts
rebuildTrie(freqTable) -> snapshot   // build trie, precompute top-K per node, publish
patchTrending(hotPrefixes)       // delta: recompute only trending nodes, merge into live trie

Data model & partitioning

High-level diagram — offline build plane vs online keystroke plane

Two planes. The offline plane (purple) turns raw query logs into a precomputed, sharded trie snapshot on a batch cadence, with a fast delta lane that patches just the trending prefixes in minutes. The online plane (green) serves each keystroke from memory: debounce → route by prefix → hit the front cache for hot prefixes, or fall through to the in-memory trie shard, which walks to the node and returns its already-computed top-K. The ranking work never touches the green plane.

Typeahead mechanism: an offline batch plane turns raw query logs into a precomputed sharded trie snapshot (aggregate frequencies with time-decay, build trie storing top-K at each node, publish immutable snapshot), with a fast delta lane that finds trending queries via count-min-sketch heavy-hitters and patches just those nodes' top-K; an online per-keystroke plane debounces on the client, routes by prefix at the gateway, serves from a front cache of hot prefixes or falls through on a miss to the in-memory trie shard, which walks to the prefix node and returns its precomputed top-K in O(prefix length) with no scan or re-rank.
Typeahead mechanism: an offline batch plane turns raw query logs into a precomputed sharded trie snapshot (aggregate frequencies with time-decay, build trie storing top-K at each node, publish immutable snapshot), with a fast delta lane that finds trending queries via count-min-sketch heavy-hitters and patches just those nodes' top-K; an online per-keystroke plane debounces on the client, routes by prefix at the gateway, serves from a front cache of hot prefixes or falls through on a miss to the in-memory trie shard, which walks to the prefix node and returns its precomputed top-K in O(prefix length) with no scan or re-rank.

Rubric — what a strong answer hits

5. Break it — three concrete failures, traced

1. Rebuilding the whole trie per update is too slow — the freshness-vs-cost wall. Naive freshness plan: "just rebuild the trie whenever popularity changes." Trace it: the build reads ~1 TB of logs, aggregates 500M distinct queries, and constructs ~5B nodes each with a top-K — that's a multi-hour map-reduce + build job. If trending must surface within minutes (Scope It), a job that takes hours can never deliver it: by the time the snapshot is built and hot-swapped, "trending" is history. And you can't run it more often — back-to-back multi-hour full rebuilds burn a cluster continuously for a result that's still hours stale. This is the failure that forces the delta pipeline: don't rebuild everything, recompute only the handful of prefixes whose counts moved and patch those nodes' top-K into the live trie (Movement 7). Full rebuild stays as the slow, correct nightly baseline; deltas handle minutes-fresh trending.

2. Hot shard for popular first-letters — the uneven-load trap. Shard by first letter and you'd love it to be 1/26 of traffic per shard. It isn't. The first keystroke everyone sends is a single letter, and letters like s, a, t, c start a wildly disproportionate share of English queries — the s shard can see many times the load of the z shard. At ~290K/s aggregate, a hot shard taking (say) 8× its fair share is ~90K/s slamming one machine while others idle — that shard browns out and its p99 blows past 100ms while the fleet looks "half utilized." Fix: sub-partition hot ranges (sa–sm / sn–sz) and give them extra read replicas, and lean on the front cache, which absorbs exactly these short hot prefixes. Load must follow the traffic distribution, not the alphabet.

3. Unbounded memory — the "index everything" blowup. Tempting: index every query ever seen so no one ever gets an empty suggestion. Trace the cost: the query long-tail is effectively unbounded (billions of unique one-off strings, typos, pasted junk), and each adds nodes at ~256B. Indexing 5B distinct queries instead of 500M is ~10× the nodes → ~12.8 TB → ~200 shards — a 10× cost increase to serve suggestions for queries almost nobody types. The trie also grows without bound over time as new junk arrives, so memory creeps until a shard OOMs. Fix: a popularity floor — only index queries seen above a threshold in the window — and evict nodes whose decayed score drops below it. Bounded index, bounded memory, and you drop only suggestions no one would have clicked.

6. Optimise — with trade-offs vs named alternatives

DecisionOption AOption BPick when
Where ranking happens Precompute top-K per node (offline) Traverse-on-read (rank subtree per keystroke) Precompute almost always — it's the whole point: O(prefix len + K) reads vs O(subtree size). Buys sub-ms query time at the cost of build compute + memory + bounded staleness. Traverse-on-read only makes sense for a tiny, low-QPS corpus (an admin search box over a few thousand items) where the build machinery isn't worth it.
Freshness / update strategy Incremental delta + weighted-decay (patch trending nodes) Full periodic rebuild only Delta when trending must surface in minutes (news, viral) — buys minutes-fresh at the cost of a second, more complex pipeline and approximate counts between full builds. Full-rebuild-only is fine when next-day freshness is acceptable (a product-catalog autocomplete) — simpler, exactly correct, but can't do real-time trending. Most real systems run both: nightly rebuild as ground truth + deltas for trending.
Serving structure In-memory sharded trie Inverted index / Elasticsearch edge-ngram In-memory trie when prefix-only + ultra-low latency + huge QPS dominate — buys the tightest latency and cheapest per-query cost, at the price of building/operating a bespoke serving tier. Reach for Elasticsearch (edge-ngram / completion suggester) when you also need full-text/fuzzy/multi-field relevance and your QPS is modest — you trade some latency and per-query cost for a general engine you don't have to build, and you get typo-tolerance closer to free.
Top-K accuracy Exact top-K (from full aggregation) Approximate top-K (count-min-sketch heavy-hitters) Approximate for the trending/delta path — a count-min sketch tracks heavy hitters in sublinear memory over a fast stream, buying real-time-ish freshness at the cost of small count errors (which barely matter for "is this suddenly popular?"). Exact for the nightly baseline, where you have the whole log and time to aggregate precisely. The pairing is the design: exact-but-slow baseline, approximate-but-fast deltas.
Client request cadence Debounce (~80ms) + cancel in-flight Fire on every keydown Debounce essentially always — it cuts wire QPS ~3–4× and drops stale in-flight responses for free, at the cost of ~80ms added latency on the final keystroke (imperceptible). Fire-on-every-keydown only if you're on a LAN with trivial QPS and want the snappiest possible feel — almost never worth the 4× load at scale.

7. Defend under drilling

Q1 — "Walk me through exactly what happens when a user types the third character of 'sys'."
The client debounced the first two keystrokes; ~80ms after s, y, s settles it fires GET /suggest?q=sys and cancels any in-flight request for sy. The gateway routes by first letter(s) to the s-range shard. The front cache is checked for key sys; on a hit (likely, it's a short prefix) we return in single-digit ms. On a miss, the shard walks its in-memory trie root→s→sy→sys (3 pointer hops), reads that node's precomputed topK list, resolves the 10 ids to strings, populates the cache, and returns. No candidate set is ever materialized, no sort runs. Total: a handful of memory reads.

Q2 — "How do you surface trending queries within minutes without rebuilding the whole trie?"
A separate delta pipeline off the live query stream. A streaming job maintains a count-min sketch to find heavy hitters (queries whose rate just spiked) in sublinear memory over a rolling few-minute window. For each spiking query, we know its prefixes (n, ne, net, …), so we recompute the top-K for just those nodes — a few thousand nodes, not 5 billion — and patch them into the live serving trie (or overlay them in the front cache). The expensive full rebuild still runs nightly as ground truth with exact counts and eviction; the delta only ever touches the handful of nodes that moved. This is the exact-baseline + approximate-fast-path pairing from the trade-off table, and it's why "just rebuild it" (Break It #1) is the wrong instinct.

Q3 — "The interviewer now wants typo-tolerance: 'netflx' should suggest 'netflix'. How?"
A pure prefix trie can't do this — netflx has no node. Three escalating options, stated as trade-offs: (a) cheapest — run the prefix against a small set of edit-distance-1 variants generated client- or server-side and union the results (covers most single-char typos, bounded cost); (b) index-side — a deletion neighborhood / symmetric-delete approach or a trie augmented for fuzzy walk (bounded edit distance via a DFA over the trie), which finds near-matches in the structure itself at higher build/memory cost; (c) switch the serving tier to Elasticsearch's completion/fuzzy suggester, which gives typo-tolerance closer to out-of-the-box but trades away the trie's latency and per-query cost. I'd start with (a) as an add-on and only move to (b)/(c) if fuzzy is a first-class requirement, because it changes the whole serving structure.

Q4 — "Personalize it — blend in the user's own history."
You can't precompute a single shared top-K per node anymore, so keep the global precomputed list as the base and merge a small per-user layer at query time: fetch the user's recent/frequent queries (a tiny per-user structure, cached), and re-rank the ~10 global candidates against a handful of personal ones with a blend function. Crucially the expensive part (finding good global candidates) stays precomputed; personalization is a cheap O(K) merge over an already-small list, so the <100ms budget holds. Full per-user tries would be prohibitively expensive and is the wrong instinct.

Q5 — "How do you keep the offline build correct as query popularity drifts over months?"
Time-decay in the aggregation: weight recent searches more (exponential decay / sliding window), so last year's viral query fades instead of permanently occupying a suggestion slot. Pair it with the popularity floor + eviction from Break It #3 so decayed-out queries release their nodes. The nightly full rebuild recomputes decayed scores from scratch over the window, keeping counts exactly correct; the delta pipeline only ever adds recency, never lets the index grow unbounded.

Q6 — the 100× escalation: "Now it's 500 billion searches/day, ~116M keystroke QPS raw."
Nothing about the shape changes — that's the point of precompute-and-shard — but three levers scale out: (1) more shards, and route by 2–3 char prefixes instead of 1 so the hot-letter skew (Break It #2) is spread across far more machines; (2) the front cache does even more work — at 100× volume the concentration on short hot prefixes is higher, so a modest cache still deflects the majority of traffic; push it to CDN/edge PoPs per region so a keystroke for a globally-hot prefix never leaves the region. (3) The build plane scales as ordinary batch (more map-reduce workers over more log volume). The invariant that saves you at 100× is the same one that saved you at 1×: the per-keystroke path is a memory walk with zero ranking work, so it scales horizontally on QPS, and the expensive ranking is offline where throughput, not latency, is the concern.

8. You can now defend

Re-authored/Deepened for this guide.

🤖 Don't fully get this? Learn it with Claude

Stuck on Design Typeahead / Search Autocomplete? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Design Typeahead / Search Autocomplete** (Hands-On Builds) and want to truly understand it. Explain Design Typeahead / Search Autocomplete from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Design Typeahead / Search Autocomplete** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Design Typeahead / Search Autocomplete** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Design Typeahead / Search Autocomplete** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Design a Metrics / Log PipelineDesign Instagram / News Feed →