Design Typeahead Suggestions (Autocomplete)

Typeahead suggests completions as the user types: type "sys" and you see "system design", "system of a down", "sysadmin jobs". The service must answer on every keystroke within about 100 milliseconds end to end, and the suggestions should reflect what people actually search for.

Requirements#

• Return the top 5 completions for a prefix, ranked by popularity.
• Respond in under 100 ms including network time, ideally under 20 ms on the server.
• Handle tens of thousands of queries per second, since each search produces several keystrokes.
• Suggestions can be a little stale: updating hourly or daily is fine.

The core data structure: a trie#

A trie stores strings character by character. Every node represents a prefix. To answer "top 5 for sys", walk to the node for s → y → s and return the best completions below it.

Walking the whole subtree on every request is too slow for short prefixes, so we precompute the top K at every node:

(root)
 └─ s           top: [system design, spotify, ...]
    └─ y        top: [system design, sydney weather, ...]
       └─ s     top: [system design, system of a down, sysadmin jobs]

A lookup is now O(length of prefix), with the answer already sitting at the node.

Architecture#

• Read path: the suggest service holds the trie in memory and answers from it.
• Write path: search queries are logged, aggregated into counts per phrase over a time window, and used to build a new trie offline. Servers load new snapshots and swap atomically.

Ranking#

Raw counts favour old evergreen phrases. Better ranking blends:

• Recency: weight recent searches more, with exponential decay.
• Personalisation: boost the user's own history and location.
• Filtering: remove offensive or dangerous suggestions before they ship.

Personal and trending signals can be merged at request time with the global top list, keeping the trie itself simple.

Scaling#

• Sharding: partition by prefix, for example a-f, g-m... Splitting by first letter is uneven (many words start with "s"), so split by observed traffic instead.
• Caching: popular prefixes like "a" or "the" are requested constantly. Cache responses at the CDN and in the browser for short periods.
• Client tricks: debounce keystrokes (wait about 50 ms of quiet), and drop responses that arrive for an outdated prefix.

Trending queries#

Breaking news needs suggestions within minutes, not after the next hourly build. Run a streaming job that tracks fast-rising phrases over a short window, and merge those into results at request time.