Design search autocomplete (typeahead)
The suggestions that drop down as you type into a search box. It looks trivial and hides a real systems problem: every keystroke is a request, the answer must come back in tens of milliseconds, and the ranking has to reflect what millions of other people are searching for right now. It's a great case study because it forces a precompute-vs-online split, a specialized data structure, and a read-vs-write-path separation.
📖 Walk me through it — plain English
Autocomplete is two jobs that look like one. The read path: you've typed "rec" and the system must, within ~50 milliseconds, return the most popular completions — "recipes", "records", "reclining chair". The write path: every search anyone runs is a vote that should, over time, change which completions are popular. Beginners try to do both live and choke. The senior move is to separate them: make reads dirt-cheap by precomputing the answers, and let the write path update those precomputed answers slowly in the background.
The shape of the read answer is "given a prefix, give me the top few strings that start with it." The data structure built exactly for "find everything with this prefix" is a trie (a tree where each path of characters spells a word). Walk down the tree following the typed letters, and everything below that point is a candidate. To make it fast, you precompute and store the top suggestions at each node, so answering is just "walk to the node, read its cached top-K" — no searching at request time.
The popularity that drives ranking comes from counting real searches. But you do not update counts on every keystroke — that's a firehose. You log searches, aggregate them every so often (say hourly), and rebuild the trie's cached top-K from the fresh counts. Reads stay instant; freshness lags by an hour, which is completely fine for what's trending.
Step 1 · Clarify & sizing
- Return top 5 completions per prefix, ranked by popularity.
- Latency target < 50ms — it fires on every keystroke, so it must feel instant.
- Read-to-write ratio is extreme: people type far more than the suggestion set changes. Optimize hard for reads; let freshness lag minutes-to-an-hour.
- Prefixes only (matching the start of a phrase) for the core design; fuzzy/typo tolerance is a stretch goal to mention, not build.
Step 2 · The data structure: a trie with cached top-K
A trie (prefix tree) stores strings by sharing common prefixes: the root branches to each first letter, each of those to the next letter, and so on, so the word "car" is the path c→a→r. Every node represents a prefix, and the whole subtree under it is exactly the set of strings starting with that prefix — which is precisely what autocomplete needs.
The naive version walks to the prefix node, then explores the entire subtree to find and sort the most popular completions — too slow for 50ms on a deep subtree. The fix is precomputation: store the top-5 completions directly on each node. Now answering a query is "walk down ≤ (prefix length) nodes, return the stored list." That's O(length of what you typed), independent of how many words match.
Step 3 · Two paths, deliberately separated
Keystroke → load balancer → suggestion service holding the trie in memory (sharded by first letters or replicated whole) → return cached top-5. A front cache (and client-side debouncing — wait ~150ms after typing stops) cuts request volume further. Everything here is read-only and microsecond-cheap.
Every search is logged to a stream (Kafka). A periodic batch job aggregates counts over a window, recomputes each node's top-5, and ships a fresh trie that the read replicas swap in atomically. Freshness lags by the batch interval — acceptable for "what's trending."
This separation is the whole lesson in one move: the expensive, write-heavy ranking work never touches the latency-critical read path. Stating it explicitly — "I'd decouple ranking updates from serving" — is the senior signal here.
Step 4 · Scaling & the curveballs
- Trie too big for one machine? Shard by prefix — node "a…" on one server, "b…" on another. The router picks the shard by first letter(s).
- "Make it personalized." Now you blend global popularity with per-user history — a second, smaller per-user signal merged at read time. Name the added cost (per-user state, more compute on the hot path) — a perfect CBW moment.
- "Handle typos." Prefix tries don't do fuzzy match; you'd add edit-distance tolerance or an n-gram index. Flag it as a meaningfully different, heavier design — don't hand-wave it into the trie.
- "Trending in real time." Shorten the batch window or add a streaming layer that nudges counts faster — trading freshness for more write-path cost.
Takeaway: autocomplete is a read-optimization problem wearing a search costume. Use a trie with precomputed top-K on every node so a query is a short walk plus a constant read; separate the instant read path from a batch write path that recounts searches and rebuilds the trie on an interval; shard the trie by prefix when it outgrows a box. The reusable pattern — precompute the answer offline, serve it trivially online — recurs everywhere reads vastly outnumber writes.
→ Going deeper: the read/write split mirrors the push/pull decision in newsfeed; the batch aggregation rides on a queue from scaling primitives; and a semantic version of this is exactly the embedding search from AI infrastructure.