Design search autocomplete
Read firstCaching patterns
Type six characters into a search box and you have made six requests, each of which has to come back before your finger reaches the next key. Nobody clicks a suggestion that appears after they have finished typing.
That gives you a latency budget of about fifty milliseconds and a request rate several times higher than the searches themselves. The interesting part is that this is not a search problem at all. It is a precomputation problem, and once you see that, the whole design falls out.
Step 1: Understand the problem#
The trap here is designing a search engine. Ask enough questions to establish that you are not.
| You ask | They say | What it settles |
|---|---|---|
| How many suggestions, and how are they chosen? | Top five, by popularity of past searches. | Everything. If the answer is popularity of a fixed corpus, the top five for any prefix can be computed in advance, and serving becomes a lookup rather than a search. |
| What is the latency budget? | Under 50ms at p99, from the user's device. | No disk, no ranking at query time, and the whole index in memory. It also means suggestions get served from the edge, close to the user, because 50ms does not leave room for a trip across a continent. |
| How fresh do suggestions have to be? | Hours is fine for most, minutes for breaking news. | Permission to precompute. This one answer is what separates a lookup table from a live aggregation, and it is the question most candidates never ask. |
| Personalised to the user? | No, apart from their own recent searches, which the client can hold. | The results are shared, so they cache. Personalisation would multiply the key space by the user count and make the whole precomputed design impossible. |
| Do we need typo tolerance? | Basic. "restrant" should still find restaurants. | A second lookup path for fuzzy matches, kept off the main one, because edit distance search and prefix lookup want completely different structures. |
| Can anything offensive or unsafe be suggested? | Never. Suggestions are seen as endorsements. | A filter applied at build time and again at serve time, plus a manual block list. This is a real requirement with legal consequences and it belongs in the design, not in a postscript. |
What you are building, and what you cut#
- Return the top five completions for a prefix. Ranked by popularity, in under 50ms.
- Collect what people actually search for. The suggestions are made of yesterday's queries.
- Rebuild the suggestion index regularly. Hourly for the long tail, minutes for what is trending.
- Filter unsafe and blocked terms. At build time and again at serve time.
- 100,000 prefix lookups a second at peak.
- Under 50ms at p99, measured at the device.
- Suggestions may be hours stale, but must never be wrong or unsafe.
- A rebuild must never take the serving path down.
- The search itself. Autocomplete suggests queries, it does not run them, and that is a separate page.
- Full personalisation. Worth naming as a client side merge of the user's own history with the global list.
- Multi language tokenisation beyond the basics. Real, deep, and its own specialism.
- Spell correction of the final query. Different problem, later in the funnel.
Back of the envelope#
The multiplier is the point. Every search costs you 4.2 autocomplete requests, so this endpoint is busier than search itself by almost an order of magnitude. And 1GB of precomputed answers fits in memory across a modest fleet, which is what makes the precomputation approach viable rather than clever.
Almost everyone computes the search rate and designs for that. The autocomplete rate is five to ten times higher, because every keystroke past the second one is a request. Before anything else, debounce on the client: wait 50 to 100ms after the last keystroke and cancel the in flight request. That single client side change removes about a third of your traffic and costs nothing, and mentioning it early tells an interviewer you have shipped one of these.
Step 2: Propose the high level design#
The API#
One endpoint, and every design decision is in the headers.
{ "query": "distributed systems", "at": "...", "lang": "en" }The data model#
The build side and the serve side store completely different things, which is the whole trick.
| prefix | string | PK | Every prefix of every kept term, up to about 20 characters. "dis", "dist", "distr" are three separate entries. |
| top_k | array of 5 | The answer, precomputed. Stored at the node, so a lookup is a walk to the node and a read, with no traversal of the subtree below it. | |
| scores | array of 5 | Kept alongside so a merge across shards can rank correctly without recomputing. | |
| blocked | boolean | Safety filter applied at build time. Checked again at serve time, because a term can be blocked between builds. | |
| version | int | The build this node came from. Whole builds are swapped in atomically, never patched in place. |
The whole system on one whiteboard#
Walking Figure 1:
- The client debounces, then asks. A large share of these never reach you at all, because the answer for a prefix is identical for every user and caches beautifully.
- The gateway routes by prefix to the shard holding that part of the trie, walks to the node, and reads the five strings sitting there. No ranking, no subtree traversal, no sorting. This is the entire hot path and it is a memory read.
- Separately, the client logs what was actually searched.
- Those events flow into an aggregator.
- Which maintains counts per term over a rolling window.
- An hourly build reads the counts and constructs new trie shards from scratch.
- Finished shards are swapped in whole. A serving node either has build 41207 or build 41208, never half of each, which makes a bad build a one line rollback.
Two boxes beside the main path are the exceptions that make it usable. A fuzzy index, consulted only when the exact prefix returns nothing. And a safety filter that can block a term between builds, without waiting an hour for the next one.
Step 2 reads five strings sitting at the node. The obvious alternative is to walk the subtree under the prefix and rank what you find. What does storing the answer at every node cost you, and why is it still the right call?
Step 3: Design deep dive#
Why the answer lives at the node#
A trie gives you the prefix walk for free. What it does not give you is the ranking, and the difference between the two implementations is the difference between fifty milliseconds and five.
The general principle worth stating out loud, because it transfers to half the other questions in this course: when reads outnumber writes by orders of magnitude, move the work to the write side. Here the write side is an hourly batch job, which is the most comfortable place work can possibly live.
"How much memory does that cost?" Five strings of about 40 bytes at a few million nodes is single digit gigabytes, before compression. Then say the two optimisations: store references into a string table rather than the strings themselves, since "distributed systems" appears at every one of its prefixes, and stop storing top-k below a depth where the subtree is small enough to walk. Both are real, both are what a production implementation does, and knowing them separates reading about tries from building one.
Rebuilding without going down#
The index is immutable and gets replaced wholesale, which sounds heavy until you compare it to the alternative of mutating a live trie while a hundred thousand requests a second walk it.
The build runs on its own machines: read the term counts, filter blocked and unsafe terms, construct the shards, verify them against a set of known queries, and publish. A serving node downloads the new shard, builds it in memory alongside the current one, and flips a pointer. Memory usage doubles briefly, which is the price, and the swap is atomic, which is the point.
Two things this buys you that are worth naming. A bad build is rolled back by pointing at the previous version, which takes seconds and needs no code change. And because nothing is ever mutated, a serving node needs no locks at all on the read path, so a lookup is genuinely just a memory walk.
The fast path for trending terms is the exception, and it should be built as an exception rather than by making the whole pipeline faster. A small separate structure holds terms that spiked in the last ten minutes, the gateway merges it into the results, and it is allowed to be approximate. When a plane goes down, people search for it within seconds and an hourly build is useless, but that is a few hundred terms, not a few million.
Typos, and why they get their own path#
Prefix lookup and fuzzy matching want different structures. A trie answers "what follows this prefix" in five hops and answers "what is one edit away from this" not at all.
Pick the deletion index if you can afford the build, and say why: eight lookups on the query side instead of fifty, paid for with offline storage. Then add the important qualifier, which is that none of this runs on the common path. Exact prefix first, always, and fuzzy only on an empty result.
Break it#
Read every step as text
- 100k/s · Healthy. Design load. A large share is answered at the CDN because prefixes are shared across users, and what gets through is a memory walk. Nothing is warm, let alone hot.
- 400k/s · Degraded. The gateway saturates first, on request parsing and TLS rather than on anything to do with tries. This is the good bottleneck: it holds no state, so you add instances.
- one letter · Down. A new product launches and everyone types the same first letter. Every request for prefixes starting with that letter lands on one shard, which is at 100% CPU while the others idle. Sharding by prefix range has the same hot partition problem as every other range sharding scheme.
- rebuild · Degraded. A new build lands. Memory usage on each serving node roughly doubles while both versions are resident, and if you sized the machines with no headroom, the swap is when you find out.
- repaired · Healthy. Replicate every shard rather than only partitioning them. Short prefixes are the hottest and the smallest, so keeping the first two levels of the trie on every node costs almost nothing and removes the hot shard entirely. Stagger rebuilds across the fleet so no more than a fraction is doubling memory at once.
The repair is worth remembering as a pattern. When the hot keys are also the small keys, replicate them everywhere instead of trying to spread them.
Trade-offs#
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| Precomputed top-k at each node | A lookup is a prefix walk and an array read, with no ranking on the request path. | Several gigabytes of memory, and suggestions only change when you rebuild. | Whenever reads outnumber index updates by orders of magnitude, which for autocomplete is always. |
| Immutable index, swapped whole | No locks on the read path, and a rollback is pointing at the previous version. | Memory doubles during a swap, and the smallest possible change costs a full build. | Any index that is rebuilt on a schedule rather than updated continuously. |
| Separate trending path | Breaking terms appear in minutes without making the hourly pipeline run every minute. | Two sources merged at serve time, and the merge can produce odd rankings for a while. | Any domain where an event can make a term go from unknown to the most searched thing in an hour. |
| Fuzzy only on empty results | The common path never pays for typo tolerance. | A prefix that legitimately has few results gets a slower response than one that has none. | Always. Making every request pay for the rare case is the most common way this design gets slow. |
Interview replay#
Checkpoint#
1. Why is the autocomplete request rate several times higher than the search rate?
2. What does storing the top five at every trie node actually buy you?
3. Same design, but suggestions must now be personalised per user. What breaks first?
- Six keystrokes per search means autocomplete runs 3 to 4 times hotter than search itself.
- 50ms at p99 including the network. That budget is why nothing is ranked at request time.
- Top five stored at every trie node. A lookup is five pointer hops and an array read.
- Hourly builds, plus a ten minute trending path for the handful of terms that cannot wait an hour.
Autocomplete looks like search and is really a precomputation problem. Every keystroke past the first is a request, so this endpoint runs several times hotter than search itself, and the budget is about fifty milliseconds including the network. So nothing is computed at request time. An hourly batch job reads a log of what people actually searched, counts terms over a rolling window, and builds a trie where the top five completions are stored at every node. A lookup is a five hop walk and an array read, out of memory, with no locks because the index is immutable and swapped in whole. Responses are identical for every user, so a CDN absorbs a large share of the traffic before it reaches us. Two exceptions sit beside the main path: a small trending structure for terms that spiked in the last ten minutes, since an hourly build is useless when news breaks, and a fuzzy lookup that runs only when the exact prefix returns nothing. The failure mode I would call out is that prefix sharding puts one popular letter on one shard, and the fix is to replicate the short prefixes everywhere, because the hottest data here is also the smallest.