Design search autocomplete (typeahead)
As you type, the search box suggests completions in milliseconds. We design the data structure, ranking and update pipeline.
Goal: as the user types a prefix, return the top suggestions (for example 5-10) within about 100 ms.
Requirements
- Suggestions for a typed prefix, ranked by relevance (usually popularity).
- Very low latency, since it fires on nearly every keystroke.
- Suggestions refresh as search trends change, but not necessarily instantly.
Estimates
If 10 million users each type 10 searches a day, and each search triggers about 5 requests, that is 500 million requests a day, about 6,000 requests/s and several times more at peak. Reads dominate, and the data (popular queries) is much smaller than the web.
Data structure: the trie
A trie (prefix tree) stores queries character by character. Each node represents a prefix. To get suggestions for "pay", walk to that node and read the best completions below it.
Walking the subtree at query time is slow, so each node stores its top-K completions (precomputed, with scores). Lookup becomes: follow the prefix, return the stored list. That is fast, at the cost of more memory.
Alternatives: a prefix index in a key-value store (key = prefix, value = top suggestions) or a search engine's edge n-gram index.
Ranking
Rank by query frequency, recency (trending boosts) and, if allowed, personalisation and location. Filter out offensive, illegal or unsafe suggestions with a blocklist.
Building the data
Suggestions come from search logs:
- Log queries to a stream.
- A batch (or streaming) job aggregates counts per query per period, often hourly or daily.
- Build a new trie or prefix table from the top queries.
- Deploy it to serving nodes by swapping in the new version.
Real-time updates for every query are not needed; periodic rebuilds with a quick path for breaking trends are enough.
Serving at low latency
- Keep the structure in memory on suggestion servers.
- Cache results for popular prefixes (even short ones like "a" or "how") in Redis or the CDN.
- Browser side: debounce keystrokes (wait about 100-200 ms), cancel outdated requests and cache earlier results.
- Only start suggesting after 1-2 characters.
Scaling
Replicate the structure across many servers. If it grows too large for one machine, shard by prefix range (a-g, h-n...), keeping load balanced since some prefixes are hot.
Other concerns
Typos (fuzzy matching), multilingual input (Bengali and English), and privacy: don't suggest one user's private queries to others.
Takeaway: a precomputed top-K trie or prefix table in memory, built from query logs, cached aggressively and debounced on the client.
System Design series, Part 3 (case studies): 9 of 16. Previous: Design a notification system: push, SMS and email.
