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
  1. Collect query logs (a stream through Kafka). Log completed searches, not every keystroke.
  2. Aggregate counts per query, by hour or day, with a decay so that recent activity weighs more than old (an exponentially weighted count).
  3. 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).
  4. 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

Client side

The client can save more load than the server:

Trade-offs and edge cases

Sources

Practise this topic: System Design System Design › Case studies

More guides