AdvancedSystem Design · Lesson 16 of 19 · Updated ·
System Design Case Study — Design Search Autocomplete (Typeahead)
Type "jav" into a search box and, before you finish the word, it suggests "java tutorial", "javascript", "java interview questions". This is autocomplete (also called typeahead). The interview question is: return the top 5 most popular searches that start with what the user has typed — on every keystroke, within about 100 ms.
The interesting part is that the answer must be ready before the request arrives. Let's design it.
Step 1 — Requirements
Functional
- For a typed prefix, return the top 5 suggestions, ranked by popularity.
- Suggestions come from what users have searched before.
- Only prefix matching (no spelling correction in the first version).
Non-functional
- Very fast: the whole round trip should feel instant, so the server should answer in a few milliseconds.
- Highly available: if autocomplete fails, search still works, but the product feels broken.
- Suggestions can be a little out of date — refreshing popularity every hour or every day is fine.
- Filter offensive or unsafe suggestions.
Step 2 — Estimates
Assume 10 million daily active users, 10 searches each per day, about 6 typed characters per search before they pick a suggestion — each character is a request.
| Quantity | Calculation | Result |
|---|---|---|
| Requests / day | 10 M × 10 × 6 | 600 million |
| Requests / second | 600 M ÷ 86,400 | ≈ 6,944 (peak maybe 2–3×) |
That is a lot of tiny requests, each wanting an answer in milliseconds. A database query like SELECT ... WHERE query LIKE 'jav%' ORDER BY count DESC LIMIT 5 on billions of rows will not keep up. We need a data structure built for prefixes.
Step 3 — The trie
A trie (prefix tree) stores strings character by character. Each node represents a prefix; its children add one more character. All searches that start with "ja" live under the node for "ja".
A plain trie still has a problem: to find the top 5 under "j", you would have to visit every word below it — maybe millions. The standard fix is to store the top-k suggestions at every node when the trie is built. A lookup then only walks down the prefix (a few nodes) and returns the list already stored there.
class Node:
def __init__(self):
self.children = {}
self.top = [] # best (count, query) pairs for this prefix
class Autocomplete:
def __init__(self, k=3):
self.root, self.k = Node(), k
def add(self, query, count):
node = self.root
for ch in query:
node = node.children.setdefault(ch, Node())
node.top.append((count, query))
node.top.sort(key=lambda p: (-p[0], p[1])) # highest count first, then A-Z
del node.top[self.k:] # keep only the top k
def suggest(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
return [q for c, q in node.top]
searches = {"java": 700, "javascript": 900, "java interview questions": 400,
"jam": 50, "joy of python": 120, "python": 1500, "pytorch": 300}
ac = Autocomplete(k=3)
for q, c in searches.items():
ac.add(q, c)
for prefix in ["j", "jav", "java ", "py", "x"]:
print(f"{prefix!r:8} -> {ac.suggest(prefix)}")
'j' -> ['javascript', 'java', 'java interview questions']
'jav' -> ['javascript', 'java', 'java interview questions']
'java ' -> ['java interview questions']
'py' -> ['python', 'pytorch']
'x' -> []
Cost of a lookup: walk len(prefix) nodes and return a stored list — O(length of prefix), no matter how many searches exist. The price is memory: every node keeps k entries. With k = 5 and short strings, that is acceptable, and it is what makes millisecond answers possible.
Step 4 — Where the counts come from: an offline pipeline
Updating the trie on every single search would mean millions of writes to a structure that must stay fast for reads. Instead, separate the write path from the read path:
- Every search is written to a log (through a queue such as Kafka).
- A batch job (hourly or daily) counts queries — often weighting recent days more, so trending searches rise.
- It removes unsafe or blocked terms and very rare queries.
- A builder creates a fresh trie with top-k at each node and saves a snapshot.
- Suggestion servers load the new snapshot into memory and swap it in, while still answering from the old one until the switch.
Reads never wait for writes. For breaking news, a smaller real-time pipeline can boost a few trending terms between full rebuilds.
Step 5 — Scaling the read path
- Replicate: each suggestion server holds a full copy of the trie in memory; add servers behind a load balancer as traffic grows.
- Shard when the trie is too big for one machine: split by first letters (
a–fon shard 1,g–mon shard 2…). Prefixes are uneven — far more searches start with "s" than "x" — so balance shards using the real query counts, not the alphabet. - Cache aggressively: short prefixes like "j" or "py" are requested constantly and change only when the trie is rebuilt. Cache them in the server, in a CDN, and even in the browser with a short TTL.
- Fewer requests from the client: wait about 100–200 ms after the last keystroke before sending (called debouncing), and reuse earlier results — the suggestions for "java" are a subset of those for "jav" when the list is long enough.
Step 6 — Extras interviewers like
- Personalisation: blend global suggestions with the user's own recent searches on the client side.
- Languages: support Hindi and other scripts by building the trie over Unicode characters; also handle transliteration ("namaste" vs "नमस्ते") as a separate mapping.
- Safety: a blocklist applied when building, and a fast kill switch to remove a bad suggestion without waiting for the next rebuild.
Common mistakes
- Running
LIKE 'prefix%'withORDER BY counton the main database for every keystroke. - Storing only words in the trie and searching the whole subtree for the top results on each request.
- Updating counts in the serving trie on every search, so reads compete with millions of writes.
- Sharding by first letter without checking how uneven the letters are.
Quick recap
- About 6,944 requests per second of tiny, latency-critical reads.
- A trie with the top-k suggestions stored at every node answers in O(prefix length).
- Build the trie offline from aggregated search logs; swap snapshots into in-memory servers.
- Replicate, shard by prefix using real counts, cache short prefixes, debounce on the client.
- Filter unsafe suggestions at build time and keep a kill switch.