System Design HLD-15.02
Typeahead and autocomplete
Suggestions in tens of milliseconds per keystroke: tries, top-k completions stored per prefix, offline precomputation from query logs, and caching.
The big idea
A user types "s", then "y", then "s" into a search box, and after each keystroke a list of suggestions must appear: "system design", "system design interview", "systems thinking". People type fast, so each answer has a budget of a few tens of milliseconds end to end, and a popular site gets a request for every keystroke of every user. A full search query per keystroke is too slow and too expensive.
The trick is that autocomplete is a much narrower problem than search. The answer depends only on the prefix typed so far, and the set of good suggestions changes slowly. So the work is done ahead of time: a trieA tree that stores strings character by character so that all strings sharing a prefix share a path from the root; also called a prefix tree. organizes all candidate queries by prefix, and each node stores its best few completions, precomputed. Answering a keystroke becomes "walk a few characters down the tree and read a short list".
Think of a well-organized phone book with tabs for every letter combination, and on each tab a sticky note listing the five most-called names under it. You never scan the pages; you flip to the tab and read the note.
How it works
Step 1: A trie of past queries
Each edge is a character, and every query is a path from the root. All queries starting with "sys" live in the subtree under the node for "sys", so finding them starts with walking just three edges, no matter how many millions of queries the trie holds.
Step 2: Store the top k at every node
Collecting all completions under a short prefix such as "s" would mean visiting a huge subtree on every keystroke. Instead, an offline job computes the top k (say 5 to 10) completions for every node, ranked by popularity from query logs (often weighted toward recent searches), and stores them at the node. A lookup is then one walk plus one list read.
Try it
Try this:
- Step through "s", "sy", "sys", "syst". The path grows by one node per keystroke and the suggestions narrow.
- Switch to walk the subtree for the prefix "s" and note how many nodes are visited, compared with "sys". In a real trie with millions of queries, short prefixes are the expensive ones.
- Try "ca" and "cac". Popular queries like "calculator" dominate "ca", while "cac" surfaces rarer completions such as "cache".
Going deeper
Precompute offline, serve read-only
A batch pipeline aggregates query logs (counting, filtering offensive or personal queries, applying time decay), builds the trie with top-k lists and ships it to serving nodes, for example hourly or daily. Serving nodes hold it in memory and only read it, which keeps latency low and makes scaling trivial: add identical replicas. Trending queries that cannot wait for the next build can be merged in from a small, frequently refreshed side index.
Caching at every layer
Popular prefixes are asked constantly: "s", "sy", "f", "fa". Cache responses per prefix in the CDN and the browser with short TTLs ( Content Delivery Networks ). Clients also cut load: wait a few tens of milliseconds after a keystroke before sending (debounce), cancel stale requests, and reuse results already fetched for a longer prefix by filtering them locally.
Scaling the data
A trie of every query ever made is too big for one machine. Shard it by prefix range (a to f on one shard, and so on), being careful with skew, since far more queries start with "s" than "x" ( Hot partitions and the celebrity problem ). Compress it by merging single-child chains into one edge (a radix tree) and by keeping only queries above a popularity threshold.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Query the main search engine per keystroke | Small sites with little traffic | Latency and cost at scale |
| Trie with precomputed top-k | Fast, predictable lookups at any scale | Suggestions only as fresh as the last build |
| Plus a real-time trending index | Surfacing breaking queries within minutes | A second pipeline to merge and maintain |
| Personalized suggestions | Relevance for each user | Per-user data and less cacheable responses |
Common mistakes
- Computing suggestions on each keystroke by scanning the whole subtree.
- No debouncing, so every character of every user hits the backend.
- Forgetting to filter offensive, private or low-quality queries from the logs.
- Not caching popular short prefixes, which receive most of the traffic.
- Sharding by first letter without accounting for very uneven letter popularity.
In the wild
Search boxes on web search engines, shopping sites, maps and app stores all use variations of this design: prefix structures built offline from query logs, ranked by popularity and freshness, served from memory, and cached at the edge for common prefixes. Many search engines, including Elasticsearch and OpenSearch, provide completion suggesters built on prefix data structures.
Check yourself
-
Why does looking up the prefix 'sys' in a trie not depend on how many queries are stored?
Show answer
B. The walk takes one step per typed character, and the node then holds precomputed results Cost is proportional to the prefix length plus reading a short stored list.
-
Without stored top-k lists, which prefix is the most expensive to answer?
Show answer
B. A short prefix such as 's', whose subtree contains a huge number of queries Short prefixes cover enormous subtrees that would need to be scanned.
-
What is debouncing in an autocomplete client?
Show answer
B. Waiting briefly after a keystroke before sending a request, so fast typists send fewer requests It cuts backend load without noticeably hurting responsiveness.
-
A breaking news query surges but does not appear in suggestions for hours. Why, and what helps?
Show answer
B. Suggestions come from a periodic offline build; a small real-time trending index merged in helps Precomputed data is only as fresh as its last build.
Recap
- Autocomplete answers per keystroke within tens of milliseconds, so work is done ahead of time.
- A trie stores queries by prefix; a lookup walks one node per character typed.
- Each node stores its top-k completions, precomputed from query logs.
- Build offline, serve read-only from memory, and merge in a trending index for freshness.
- Cache popular prefixes at the edge and in the browser, and debounce on the client.