Design search autocomplete
Budget 100 ms across the network and the index, cache top-k at every trie node, and defend an hourly offline rebuild against per-keystroke writes.
Autocomplete is a latency problem wearing a data-structure costume. The suggestion list has to be on screen before the user's next keystroke lands, which puts the entire round trip — network, lookup, render — inside roughly 100 ms. That single constraint decides where the index lives, what shape it takes, how often it changes, and how much work the browser has to do on its own. Every other decision in this design is downstream of it.
Step 1 — Requirements
Functional:
- Given a prefix, return the 5 to 10 most popular completed searches that start with it, ranked by popularity.
- Popularity comes from what people actually searched, aggregated over a recent window — not from an editorial list.
- Results are the same for everyone. Personalisation is a separate ranking layer bolted on later; the shared index is the hard part.
Non-functional:
- Under ~100 ms from the last keystroke to a painted list, measured at p99. The mean is useless here: a user who sees the list instantly nine times and waits 400 ms on the tenth remembers the tenth.
- Reads dominate absolutely. Serving must never block on an update.
- Suggestions may be stale by an hour. Nobody can tell whether a term ranks third or fourth.
Out of scope: full-text search over documents (a different index entirely — an inverted index, not a prefix index), spelling correction, and query understanding. Both are natural extensions and both are worth naming in an interview: spelling correction bolts on as an edit-distance lookup over the same term dictionary, and personalisation as a re-rank of the ten candidates the trie returns.
Step 2 — The numbers
Assume 10 million searches/day and an average of 20 characters typed per search. If the client fired on every keystroke:
10,000,000 × 20 = 200,000,000 keystroke-queries/day
200,000,000 ÷ 86,400 s ≈ 2,300 QPS average, and at a 3x peak, ~7,000 QPS.
Now debounce. Suppress prefixes shorter than three characters, and only send after 150 ms with no typing, which collapses each burst of fast typing into one request. Assume that leaves roughly 6 requests per search instead of 20:
10,000,000 × 6 = 60,000,000 requests/day ÷ 86,400 s ≈ 700 QPS average, ~2,100 QPS at peak.
Debouncing is a 3.3x capacity reduction bought with about fifteen lines of client code. It is the cheapest decision in the design and the one candidates most often skip.
Where the 100 ms goes
| Segment | Budget |
|---|---|
| Debounce timer | 150 ms (deliberate, before the clock starts) |
| Client to regional PoP and back | 20 ms |
| Server: parse, traverse, serialise | 5 ms at p99 |
| Browser: parse JSON, render list | 10 ms |
| Slack | ~65 ms |
The debounce delay sits outside the 100 ms because it is the price of not sending the request at all; the user's felt wait is closer to 250 ms, and that is the number to quote honestly.
Two rungs of the latency ladder settle the architecture on their own.
The index must be near the user. A round trip from India to US East is about 200 ms. That is 2x the entire budget consumed before the server has read a byte. No amount of index tuning recovers it. The trie has to be replicated into regional points of presence, the same argument that puts static assets on a CDN, except the payload is an index rather than a file.
The index must be in memory. A main memory reference is 100 ns; an SSD random read is 100 µs, a thousand times more; a spinning disk seek is 10 ms. Walking a ten-character prefix is ten hops: 1 µs in RAM, 1 ms from SSD, and 100 ms from disk — the whole budget spent on one traversal that has not yet ranked anything.
How big is it
Index the 10 million most frequent distinct queries, average 20 characters. The upper bound on nodes is 10M × 20 = 200M; heavy sharing in the first few characters cuts that, so assume ~100M nodes. A bare node (a compact child map plus a terminal count) is roughly 40 B, so the skeleton is 100M × 40 B = 4 GB. That fits on one machine, which is why sharding is a Step 4 concern and not a Step 2 one.
Step 3 — The design
The trie, and why the obvious query is too slow
A trie stores one character per edge, so every node is a prefix and finding the node for new costs exactly three pointer chases — about 300 ns. The problem is what happens next.
The naive answer walks the whole subtree under that node, collects every completion, and heap-selects the top 10. Assume new has 100,000 descendant queries: 100,000 × 100 ns ≈ 10 ms of pure memory traffic, ignoring the heap. By Little's Law, 2,100 QPS × 10 ms = 21 requests in flight, so 21 cores are busy full time doing nothing but scanning. Worse, the cost is unbounded at the top: the prefix a might cover 2 million queries, 2,000,000 × 100 ns = 200 ms, and short prefixes are the most common requests. The tail is where the users are.
Cache the top-k at every node
Store, at each node, the pre-computed list of its 10 best completions. A query becomes: traverse to the prefix node, read the list, return. Ten pointer chases and one array read — call it 2 µs of CPU against the 10 ms scan, five orders of magnitude, and now the cost is flat regardless of how popular the prefix is.
The trade-off is size and write cost. Ten entries of a 4-byte string id plus a 4-byte score is 80 B per node, which would take the trie from 4 GB to 12 GB — 3x. Trim it: only cache at nodes of depth 1 to 12, since deeper prefixes have small subtrees where a scan is bounded and cheap anyway. If ~40% of nodes qualify, that is 40M × 80 B = 3.2 GB extra, landing the whole index near 7 GB. One 32 GB box holds it with room to hold two copies during a swap.
Writes get more expensive in proportion: inserting one query has to touch the cached list of every ancestor, up to 20 nodes. In a system that took writes on the read path, that would be the objection. Here it is irrelevant, and the next section is why.
Rebuild offline, serve immutable
Queries are answered from an in-memory trie that never changes. A batch job rebuilds it from aggregated query logs on a schedule — hourly is a good default — and serving boxes load the new blob and atomically swap a root pointer.
The alternative — mutating a shared trie as searches arrive — fails for a reason that has nothing to do with CPU. A structure being read at 2,100 QPS and written concurrently needs synchronisation, and putting a lock on a 2 µs operation means the lock is most of the operation (distributed locking covers the general shape; here it is in-process, and no cheaper for it). Lock-free tries exist and are a research project, not an interview answer.
The freshness argument is stronger still. Reads beat raw writes 6:1 (60M lookups against 10M completed searches), which is not much. But a search only changes an answer if it moves a term across a ranking boundary. If the tenth-ranked completion under ne has 800,000 hits in the trailing 30 days, a new term needs 800,000 searches to displace it — 0.27% of a month of global traffic. Lookups to effective mutations is millions to one. Paying a synchronisation tax on every read to serve an answer that changes a few times a day is the wrong trade, and saying that ratio out loud is what distinguishes an argued decision from a remembered one.
This is PACELC stated plainly: else — with no partition at all, which is almost always — we choose latency over consistency, and accept an index up to an hour stale.
The build pipeline is ordinary batch processing: aggregate raw searches by string, drop anything seen fewer than ~5 times in the window (which removes the long tail, most bot noise, and most accidentally-pasted personal data in one filter), apply a decay so a term from 28 days ago counts less than one from yesterday, then build the trie and fill the caches bottom-up.
Bottom-up works because of one property worth stating: a node's top-10 is always contained in the union of its children's top-10 lists plus the node's own terminal count. If a term lives under child C and is not in C's top-10, then ten terms in C's subtree already beat it, so it cannot be in the parent's top-10 either. Each node therefore merges a handful of 10-element sorted lists — the whole build is linear in nodes, parallelises by first-character range, and finishes in minutes.
Trending terms
Hourly rebuilds cannot serve a term that did not exist at 09:00. A streaming job counts terms over a 5-minute sliding window and flags any whose rate exceeds its 7-day baseline by, say, 20x. Assume 1,000 such terms at any moment, each contributing ~15 prefixes: 15,000 entries, a few MB, pushed to every serving box every 30 seconds.
At read time the server checks this overlay map first — one hash lookup, ~100 ns — and merges any hit into the top two slots, filling the rest from the trie. The overlay is mutable, but it is replaced wholesale by pointer swap, so the read path still never takes a lock. Same trick, smaller object.
Sharding, and the imbalance it creates
At 7 GB nothing needs sharding. At 10x the corpus it is 70 GB and it does, and the obvious split — one shard per first character — is the wrong one.
First-letter frequency in real query traffic spans about two orders of magnitude. If the busiest letter takes 12% of traffic and the quietest takes 0.2%, then at 2,100 QPS one shard sees 2,100 × 0.12 = 252 QPS and another sees 2,100 × 0.002 = 4 QPS — a 60x spread, and the hot shard also holds the largest subtree, so it is simultaneously the biggest and the busiest.
Two fixes, both cheap because the index is immutable:
- Shard on a two or three character prefix and assign ranges by measured traffic, splitting
sa–shfromsi–szifsis hot. The assignment is recomputed at every rebuild, so rebalancing costs nothing — there is no data to migrate, only a different blob to ship. - Replicate hot shards harder than cold ones. Read-only replicas need no write coordination at all, so this is a config number, not a design.
The third option is to abandon the trie and store prefix → top-10 directly in a key-value store, hash-sharded on the prefix string. Lookup becomes one hash get, sharding is perfectly even, and a cache like Redis does the whole job. The cost is materialising every prefix explicitly — roughly 100M keys instead of 100M shared nodes — and losing the ability to walk down when a deep prefix misses. For a fixed 5-to-10 result contract, it is a perfectly defensible answer, and saying so is better than pretending the trie is the only structure that works.
The client owns half the budget
Three client behaviours, none optional:
Debounce. Fire 150 ms after typing stops, not per keystroke. Worth 3.3x capacity, as computed above.
Cache prefixes locally. Keep a session map of prefix to results. Backspacing from news to new then hits zero network. While a request for a longer prefix is in flight, filter the cached parent results as a placeholder — sometimes wrong, since the top-10 for news is not a subset of the top-10 for new, but a stale list beats an empty one for the 100 ms it is on screen.
Cancel in flight, and tag responses. Requests for ne and new are both outstanding; ne returns second and overwrites the list with results for a prefix the user has already left. Abort the old request via AbortController, and stamp every response with the prefix it answers, dropping any whose prefix is not the current input. Cancellation alone races; the tag is what actually makes it correct.
Also keep the connection warm. A fresh TLS handshake is two round trips — 40 ms on a 20 ms link, 40% of the budget — so autocomplete rides an existing HTTP/2 or HTTP/3 connection or it does not make its number.
Step 4 — Trade-offs
| Decision | Cheap option | Expensive option | Take the cheap one when |
|---|---|---|---|
| Ranking at query time | Scan the subtree, 10 ms and unbounded | Cache top-10 per node, 2 µs flat, +3 GB | Never at this latency target — the scan blows p99 on short prefixes |
| Cache depth | Every node, 12 GB | Depth 1–12 only, 7 GB | Always; deep subtrees are small enough to scan |
| Index updates | Hourly offline rebuild, zero lock cost | Per-keystroke writes, synchronisation on every read | Almost always; add a trending overlay for the exception |
| Sharding key | First character, 60x imbalance | Traffic-balanced prefix ranges | Only below one machine's memory, where there are no shards |
| Placement | One region, 200 ms cross-region RTT | Replicated per region, ~7 GB × regions | Never for a 100 ms budget |
| Client | Fire per keystroke, 7,000 QPS peak | Debounce plus local cache, 2,100 QPS peak | Never — the cheap option here is also the correct one |
Failure modes are mild by construction. A serving box that fails to load a new blob keeps serving the old one, which is stale by an hour and otherwise perfect. If the whole autocomplete tier is unreachable, the client renders no dropdown and the search box still works — autocomplete degrades to nothing rather than to an error, and that is worth designing for deliberately.
In an interview
The interviewer is testing whether a latency budget can drive a design instead of decorating it. Almost every candidate names the trie in the first minute; the trie is table stakes. The signal is the top-k cache, and the read/write split that makes the cache affordable.
Open with the constraint, not the structure: "100 ms end to end means an India-to-US round trip at 200 ms is already 2x over budget, so the index is replicated regionally and it is in memory. That fixes most of the design before I draw anything." Then take the naive path deliberately — traverse to the node, scan the subtree — put 10 ms on it, note it is unbounded for short prefixes, and then cache the top-10 per node. Showing the broken version and pricing it is how the optimisation reads as reasoning rather than recall.
The mistake that loses points is updating the trie per search. It sounds diligent and it is the wrong instinct: it puts a lock in front of a 2 µs read at 2,100 QPS to keep data fresh that changes a few times a day. Say the ratio — millions of lookups per effective ranking change — and then volunteer the exception yourself, because the interviewer's next question is breaking news and the answer is a small real-time overlay merged at read time.
Second mistake: treating the client as out of scope. Half the budget and two thirds of the QPS live in the browser. A candidate who says "debounce at 150 ms, cache prefixes locally, cancel and tag in-flight requests" has answered a capacity question and a correctness question at once.
Check yourself
1. Your product moves the target from 100 ms to 30 ms end to end for users in Mumbai, and the index currently runs only in US East. What changes, and what does it cost?
Nothing on the server side helps. The India-to-US round trip alone is ~200 ms, nearly 7x the new budget, so the only move is a Mumbai PoP holding a full replica. The index is ~7 GB, so that is one 32 GB box for capacity plus two for redundancy per region. Within the region the budget then works out: ~10 ms RTT, 5 ms server, 10 ms render, leaving ~5 ms of slack — tight enough that the debounce should drop to ~80 ms and the response payload should be trimmed to ten strings and nothing else.
2. A colleague proposes dropping the per-node top-10 cache to save 3 GB of RAM, arguing that a scan under a five-character prefix touches only a few thousand entries. Accept or reject, with numbers.
Reject. The average case is not the problem. A five-character prefix may cover 3,000 entries —
3,000 × 100 ns = 300 µs, survivable — but the two and three character prefixes that dominate real traffic cover hundreds of thousands, and2,000,000 × 100 ns = 200 msfor a one-character prefix is 2x the entire end-to-end budget. Since we measure at p99 and short prefixes are the most-requested ones, the tail is the traffic. Three GB costs a few dollars a month; blowing p99 costs the feature.
3. Traffic grows 10x, the corpus reaches 70 GB, and you shard by first character across 26 machines. Peak is 21,000 QPS. What breaks, and what do you do?
Load imbalance. With the busiest letter at ~12% of traffic and the quietest at ~0.2%, the hot shard takes
21,000 × 0.12 = 2,520 QPSwhile the cold one takes21,000 × 0.002 = 42— 60x apart — and the hot shard also holds the largest subtree, so it is the biggest and busiest at once. Shard on two-to-three character prefix ranges assigned by measured traffic, and replicate the hot ranges more heavily. Both are free here: the index is immutable and rebuilt hourly, so rebalancing means shipping a different blob, not migrating live data.