CS Fundamentals Trainer · Guides
Design search autocomplete (typeahead): tries, top-k and latency
A case study in serving suggestions within 100 ms: requirements and numbers, a trie with cached top-k results at each node, how the data pipeline builds it from query logs, caching and sharding, handling freshness and trending queries, and the client-side details (debounce, prefix cache) that matter as much as the server.
4 min read
The problem. As a user types "how to", the search box shows the ten most likely completions. The suggestions must appear while the user is typing, so the response budget is about 100 ms including the network, and the system gets a request for every keystroke.
Requirements and numbers
Functional: return the top 5 to 10 completions for a prefix, ranked by popularity (later: personalisation, language, location), with no offensive suggestions. Non-functional: very low latency, high availability, and freshness measured in hours (a breaking news term should appear quickly, but not instantly).
Assume 10 million daily users, 10 searches each, and about 20 characters per query typed: 10,000,000 x 10 x 20 = 2 billion keystrokes a day, which is 2,000,000,000 / 86,400 ≈ 23,000 requests per second on average and perhaps double at peak, though a good client cuts this a lot (see below). The data is small: 5 million distinct popular queries of about 30 bytes is roughly 150 MB. It fits in memory on one machine; the problem is the request rate and latency, not storage.
The data structure: a trie with precomputed top-k
A trie stores strings by shared prefixes: each edge is a character, and the node reached by "how" represents the prefix "how". To find completions you walk to the prefix node and then gather all words below it. For a popular prefix like "a" that subtree has millions of words, so scanning it per request is far too slow.
The standard fix: store the top-k completions at every node. Each node keeps a small list of (query, score) for its best k (say 10). A lookup is then O(length of the prefix) to find the node plus O(k) to read the list: microseconds. The cost is memory (k entries per node), which is acceptable here, and updates (a new query changes the lists of all its prefix nodes), which is why the trie is built offline rather than updated live.
An alternative that is easier to operate: a key-value store mapping every prefix string to its precomputed top-k list ("how t" -> [...]). It uses more space (every prefix is a key) but needs no custom structure, caches perfectly and shards by key.
Data pipeline
search logs --> aggregation job (counts per query per window) --> ranking and filtering
--> build new trie / prefix table --> publish snapshot --> servers load it
- Collect query logs (a stream through Kafka). Log completed searches, not every keystroke.
- Aggregate counts per query, by hour or day, with a decay so that recent activity weighs more than old (an exponentially weighted count).
- Filter unsafe, private and spam queries with blocklists and a minimum count (a query searched by one person is not a suggestion, and may be personal data).
- Build a new snapshot every few hours and push it to the serving fleet, which swaps it in atomically. A trending side path can update a small, separate, frequently refreshed list that is merged into the results.
Serving
- Stateless servers load the snapshot into memory. A load balancer spreads requests; any server can answer any prefix.
- Caching is very effective because prefixes repeat: a CDN or edge cache keyed by the prefix, with a short TTL (minutes to an hour), absorbs most traffic. The browser can cache too.
- Sharding is needed only if the data outgrows memory or for geography: shard by prefix range (a-f, g-m, …), but beware that popularity is skewed (far more words start with "s" than "x"), so split ranges by measured load, not alphabet length. Replicate each shard.
- Personalisation and location are an extra ranking layer: take the top 20 from the global list and re-rank with the user's history, or keep a separate lookup per region.
Client side
The client can save more load than the server:
- Debounce keystrokes (wait about 100 to 200 ms after the last one) so fast typing does not send a request per character.
- Cancel in-flight requests when a new one is sent, and ignore out-of-order responses.
- Cache results per prefix and reuse them when the user deletes a character.
- Start suggesting after one or two characters, and prefetch.
Trade-offs and edge cases
- Freshness versus cost: rebuild hourly or daily; trending queries use the fast path.
- Typos: serve exact prefix matches first, with fuzzy matching (edit distance, or a n-gram index) as a second step, because it is expensive.
- Multiple languages: use Unicode normalisation, and a tokeniser where words are not separated by spaces.
- Abuse: attackers can pump queries to place a suggestion; require a minimum number of distinct users, and rate-limit by client.
Sources
- Alex Xu, System Design Interview, chapter "Design a search autocomplete system".
- Trie (Wikipedia).
- Google, How Google autocomplete predictions are generated.
Practise this topic: System Design System Design › Case studies