Search typeahead
Design search suggestions that appear as the user types. Every keystroke should produce updated suggestions, ranked by what people actually search for.
Where’s the slack?
Per keystroke: ~100 ms. Index freshness: hours.A hundred milliseconds per keystroke, because a person types the next character in about 200. And hours of slack on how fresh the suggestions are.
The latency budget is set by typing speed. A moderate typist produces a character every 150 to 250 ms, so a suggestion arriving after 300 ms is already answering a question the user has moved past. Above about 100 ms, the list visibly lags behind the cursor. That budget rules out almost any approach that searches at request time.
The freshness budget, by contrast, is huge, and this is the asymmetry to exploit. Suggestions come from what people searched for in the past, and yesterday's popularity predicts today's very well. An index rebuilt once an hour, or even once a day, gives results that look the same as real-time ones to almost every user. So you have hours to precompute whatever you need.
The exception is trending: a breaking news event makes a term explode in minutes, and suggestions that ignore it feel broken. That is a narrow, high-value exception. It calls for a small fast-moving layer over a slow-moving base, not for making the whole system real-time.
Hours of build slack plus 100 ms of serve budget makes this one of the clearest precompute-versus-compute-on-read decisions on the site.
So: You precompute the answer for every prefix ahead of time and serve it from memory. You do not search at request time. The only live component is a small trending overlay.
Work it through
Five stages, gated. You write your answer for each stage before its model answer unlocks. That is the core of the method.
Reference material for this problem. The diagrams below are here to check your own against once you have drawn it, not to read first.
The lifecycle
The numbers
The index fits on one machine, so replicate it to every serving node and take the network out of the hot path entirely. So the hard part is request rate against a 100 ms budget, which precomputation solves and per-request search does not.
The architecture
The mechanism
The decision this turns on
- —A request is a short prefix walk plus a list read: microseconds.
- —All ranking, filtering and decay happen offline where time is free.
- —Index is a few GB, so every node can hold the whole thing.
- —New queries are invisible until the next rebuild.
- —Fresh immediately, and fuzzy matching comes for free.
- —No build pipeline, no artefact management, no atomic swaps.
- —Scoring per request will not hold 100 ms at 600,000 requests/sec.
- —Cost scales with request volume rather than with data size.
Follow-ups you should expect
Many interviews are decided in the follow-ups, not the first diagram.
Same shape, other products
The user gives you a fragment and expects the right answer ranked first.
Two systems: one that narrows millions to dozens, one that ranks the dozens. Confusing them is a common mistake.
Others with this shape: Typeahead · Product search · Log search
How it is really built
Write your own answer first. Then read how teams who run this at scale describe it. Their constraints were real, and the write-ups often say what their choices cost.
- Elasticsearch — Suggesters ↗Prefix completion as an actual implementation, with its memory cost.