Search typeahead — a full worked answer

Assumptions: global, and suggestions come from historical search queries rather than from a product catalogue: the top queries starting with what has been typed. One search generates several requests, one per keystroke, so request volume is many times the search volume. Suggestions are short strings, so the data is small. Users type on mobile keyboards, with typos.

First question, and it decides whether the answer can be shared: are suggestions personalised, or the same for everyone typing the same prefix? Global suggestions can be precomputed once and cached at the edge for everybody. Personalised ones mean a per-user computation inside a 100 ms budget, and no shared caching. I will assume global, with light personalisation applied on the client from local history.

Second question: do we need to handle typos and near-misses, or exact prefixes only? Fuzzy matching is a much more expensive lookup and would change the data structure. I will assume exact prefix matching first, with a limited typo tolerance as a second layer.

Scope: return ranked suggestions for a prefix, keep them reasonably fresh, and handle trending terms. Out of scope: the actual search results page, spelling correction on submitted queries, and multi-language handling, though I would flag the last as a real complication.

Actors: the person typing, the population of past searchers whose behaviour creates the rankings, and the system, which decides what qualifies as a suggestion, what to suppress, and what counts as trending.

The chain: queries logged → aggregated by frequency → filtered and ranked → built into the prefix structure → served for a prefix → eventually decays out of the rankings.

Failure branches. At logged: bot traffic inflates a query's count, so rankings reflect scripts rather than people. The system must filter obvious automation, or suggestions get poisoned. At filtered: an offensive or harmful query becomes popular, and because suggestions come from raw behaviour, the system will promote it. This is a requirement, not a nicety: it needs a blocklist and a review path, and candidates often forget it. At built: the index build job fails, so suggestions silently go stale. A slightly old index looks normal, so this needs explicit monitoring on index age.

At served: the responses arrive out of order. The user typed "ca", then "cat", and the "ca" response arrives second, overwriting the more specific suggestions with less specific ones. This is a common bug, and the fix belongs in the design: every response carries the prefix it answers, and the client discards anything that does not match the current input.

At served: the user types faster than the round trip, generating requests for prefixes they have already moved past. The client should debounce briefly and cancel in-flight requests.

At served: no suggestions match at all. Return nothing cleanly rather than falling back to unrelated popular queries, which feels broken.

And the decay branch: a query that was hugely popular last month should fade, so ranking must weight recency rather than all-time totals, or the suggestions become a museum.

Requests: assume 100,000 searches per second at peak. At 6 keystrokes per search with debouncing, that is around 600,000 suggestion requests per second. That is a high request rate for a 100 ms budget, and it rules out any expensive work per request.

Distinct queries: people search for a huge variety of things, but the tail is worthless as suggestions. A query searched twice ever should not be suggested. Take the top 10 million queries, which covers nearly everything worth suggesting.

Index size: 10 million queries at roughly 40 bytes each is 400 MB of raw text. Storing the top 10 completions at every prefix node inflates that; call it a few gigabytes with the structure and rankings. That fits in memory on one machine, and this conclusion shapes the design: the suggestion index can be copied onto every serving node rather than sharded and queried over a network.

Build cost: aggregating a day of query logs, maybe 10 billion entries, is a batch job of tens of minutes on a modest cluster. That fits easily inside hours of slack.

Cache effectiveness: prefix popularity is highly concentrated. The top few thousand prefixes account for a large share of all requests, because everyone types the same first two or three characters. So a small cache absorbs most traffic, and short prefixes — the most requested — are also the most cacheable.

So the hard part here is request rate against a 100 ms budget, and the answer is precomputation plus caching. Not index size, not build cost, and not the ranking algorithm.

The data structure is the design. A trie over the top 10 million queries, where each node stores the top 10 completions beneath it, precomputed at build time. Answering a request is then a walk down the prefix, one step per character, and a read of a list that is already there. No search, no ranking, no scoring at request time. Justified directly by the 100 ms budget and the 600,000-per-second rate: anything computed per request would not fit.

That precomputation is the central trade. Building it is expensive and takes hours; serving from it is close to free. With hours of slack on freshness and 100 ms on serving, that is the right way round.

Ranking happens at build time: score each query by frequency weighted toward recent days so popularity decays, apply blocklists, and store the ordered top 10 at each node. Justified by the Stage 2 branches on decay and offensive content, which can both be handled at build time.

Serving: the whole index is replicated to every serving node, held in memory. Nodes are stateless with respect to each other and scale horizontally behind a load balancer. Justified by the size estimate: a few gigabytes per node is cheap, and it removes any network hop from the lookup.

Caching: an edge cache in front, keyed by prefix, with a TTL of minutes. Because short prefixes dominate traffic and are identical for everyone, the hit rate is very high, and most requests never reach a serving node. This box saves more work than any other, justified by the concentration observed in Stage 3.

Index building: a batch job reads query logs, aggregates, filters, ranks, and produces a new index artefact. Deployed by building the new index alongside the old one and switching an atomic pointer. Nothing is mutated in place, so there is no window where the index is half-updated. Justified by the Stage 2 branch about failed builds: with an atomic switch, a failed build leaves the previous index serving.

Trending overlay: a small, separately-updated layer of terms rising sharply in the last few minutes, merged into results at serve time. Kept small and separate on purpose, so the fast-moving part does not force the whole system to be real-time. Justified by the carve-out in the slack analysis.

Client behaviour is part of the design: debounce by about 50 ms, cancel superseded requests, discard responses whose prefix does not match the current input, and cache locally so backspacing does not re-request. That last one matters more than it sounds. Backspacing is common, and the client has already seen the response for every shorter prefix.

Hard part one: freshness against precomputation, the main tension in this design. The base index rebuilds hourly, which is fine for the long tail. Trending is the exception, so I keep a separate small structure updated every minute or two from a stream of recent queries, holding terms whose rate has risen sharply. At serve time the two are merged, with trending items boosted. Keeping this small (thousands of terms, not millions) is what makes it affordable. Cost: two ranking sources merged at serve time, so the ordering logic is more complex and the results are harder to explain when someone asks why a suggestion appeared.

Deploying a new index has a memory cost worth naming: to switch atomically you hold both the old and new index in memory briefly, so peak memory is roughly double steady state. If nodes are not sized for it, the swap itself can run a node out of memory. Cost: sizing every node for 2x, or accepting a brief window of reduced capacity while nodes rebuild in rotation.

Hard part two: typo tolerance without abandoning the structure. A trie is exact by nature. Options: precompute common misspellings as additional entries pointing at the correct query, which is cheap and covers most real typos because they cluster heavily; or fall back to a fuzzy search only when the exact prefix returns too few results, which is slower but rare. I would take both: precomputed misspellings for the common cases, fuzzy fallback when the exact lookup comes back nearly empty. Cost: a larger index, and the fallback path has a much worse latency profile, so it needs a tight timeout and must degrade to returning nothing rather than blowing the budget.

Hot prefix protection: single-character prefixes are requested constantly. Those are cache hits at the edge, so they rarely reach a serving node. I would give the shortest prefixes long TTLs, since their answers barely change. Cost: a trending term takes slightly longer to appear under a single-letter prefix, which users are unlikely to notice.

Abuse and rate limiting: an automated client can generate enormous request volume cheaply here, since every keystroke is a request. Per-client rate limiting is needed here, because without it one script can consume capacity meant for real typists. Cost: an aggressive typist on a shared network could hit a limit, so the limit must be generous and keyed carefully.

Multi-language, raised because it complicates this a lot in practice: tokenisation and prefix semantics differ by script. In languages written without spaces (Chinese, Japanese, Thai), or typed through an input method, "prefix" does not mean the same thing. I would build per-language indexes and route by locale rather than pretend one structure handles everything. Cost: N indexes to build and hold, and ambiguity for multilingual users.

Consistency per feature: suggestions are eventually consistent by up to an hour and that is by design. Trending is eventually consistent by a minute or two. Blocklists must apply immediately, which means they are checked at serve time as well as at build time. A filter that only runs at build time leaves an offensive suggestion live until the next rebuild.

What I would monitor: p99 latency per request, cache hit rate by prefix length, index age (the silent failure), trending pipeline lag, and the rate of empty-result responses, which is the earliest signal that an index build produced something wrong.