Design Typeahead (Autocomplete) — the walkthrough in full
A written version of the interactive walkthrough above — the same steps, decisions and trade-offs, laid out for reading, reference and search.
The big idea
What is typeahead?
You start typing in a search box and a list of completions appears — and updates on every keystroke. It feels instant, but behind it you’re searching millions of possible queries, ranking them, and returning the best ten, in the time between two letters.
The trick is to do almost no work at request time. We precompute the best completions for every prefix and look them up by walking a tree — turning “search” into a near-instant lookup, not a scan.
How to read this: We add one piece at a time, each starting with a problem then the smallest fix. Watch the diagram grow — by the end you’ll have built the whole machine. Hit Begin.
Step 1 · The skeleton
Prefix in, matches out
At its core there’s one operation: given a prefix like sys, return the most likely full queries — system design, system of a down, systemctl. Where do those candidates even come from, and how do we find them fast?
Stand up a Suggest API: the box calls GET /suggest?q=sys on every keystroke and gets back a ranked list. Everything hard lives behind this one endpoint, which exists to do exactly one thing as fast as possible.
Read-only and hot: Typeahead is almost pure reads, hammered constantly. That shapes everything: we’ll trade write-time and storage for read speed at every turn, because the read path is sacred.
Step 2 · Find matches fast
The trie
Scanning every known query to find ones starting with sys is far too slow at millions of queries. A database LIKE 'sys%' index helps, but still does real work per request — multiplied by every keystroke of every user.
Design decision: Find every query starting with "sys" among millions — on every keystroke. How?
The call: A trie (prefix tree): walk the path s→y→s. — Each node is a character; following the prefix lands on the subtree of all completions. Finding candidates is O(prefix length), independent of how many queries exist.
Use a trie (prefix tree): each node is a character, and the path s→y→s leads to the subtree of all completions beginning with “sys”. Finding the candidate set becomes walking a few pointers — O(length of the prefix), independent of how many queries exist.
Trie = prefix tree: Shared prefixes share a path, so “system”, “systemd” and “systematic” all branch off one “system” node. Walk to a node and everything below it is a match — no scanning required.
Step 3 · The hottest prefixes
Cache the common case
Even an O(L) trie walk plus gathering and ranking the subtree adds up when it runs billions of times a day. And traffic is wildly skewed: a tiny set of short prefixes (a, fa, you) accounts for most requests.
Design decision: A tiny set of short prefixes ("a", "you") drives most traffic. How do you exploit that?
The call: Cache prefix → precomputed top-10 in Redis. — A small set of short prefixes drives most traffic, so a prefix-keyed cache turns the common case into a sub-ms memory lookup. Misses fall through to the trie and warm the cache.
Put a cache in front keyed by prefix → its precomputed top-10. A request for a hot prefix never touches the trie; it returns the cached list in under a millisecond. Misses fall through to the Trie Service, then warm the cache.
Skewed traffic loves caches: When a small fraction of inputs drives most requests, a cache turns the common case into a memory lookup. Short prefixes have the most traffic and the most matches — exactly what you want cached.
Step 4 · Which ten?
Rank the candidates
A prefix like a matches millions of queries. Returning them alphabetically is useless — the user wants the ones people actually search, with the best on top. We need an order, not just a set.
Design decision: The prefix "a" matches millions of queries. How do you return the best 10 in time?
The call: Precompute and store the top-k at each trie node. — Rank offline when the trie is built and cache each node’s best 10. At request time you read a ready-made list — O(1) ranking on the hot path.
Score candidates with a Ranker using Query Counts (popularity), plus recency and length. Crucially, store only the top-k at each trie node so the answer is precomputed — at request time you read a ready-made list, you don’t sort millions of things live.
Precompute top-k: The expensive ranking happens offline, once, when the trie is built. Each node caches its best 10 children. Requests just read that list — O(1) ranking on the hot path.
Step 5 · Stay current
Build it from what people search
Suggestions go stale. A query that trended yesterday should appear today; a dead one should fade. But you can’t mutate a giant shared trie on every search without wrecking read performance.
Design decision: Yesterday’s trending query should surface today — but you can’t mutate a giant shared trie live. How?
The call: Log searches; an offline builder rebuilds the trie and swaps it atomically. — Aggregate the query log into fresh counts, rebuild the trie with new top-k lists, and flip to it atomically. Readers always see a complete version N, then N+1 — never a partial tree.
Log every search to a Query Log (Kafka). A periodic Trie Builder aggregates those logs into fresh counts, rebuilds the trie with new top-k lists, and atomically swaps the new version in. Reads always hit a complete, immutable trie.
Build offline, swap atomically: Separating the write-heavy build from the read-heavy serve keeps each simple. Readers never see a half-updated tree — they use version N until version N+1 is fully ready, then flip.
Step 6 · Make it personal
Your suggestions, not everyone’s
Global popularity is a decent default, but doc should probably suggest the user’s documents or recent searches before the world’s most popular “doc”. One-size-fits-all ranking leaves relevance on the table.
Design decision: "doc" should suggest the user’s own docs before the world’s most popular "doc". How?
The call: Blend user history into ranking over the global top-k. — Two stages: the global precomputed top-k narrows millions to a handful, then a light per-user re-weight reorders just those few. Expensive work stays global; per-user work stays tiny.
Blend in User History: mix each person’s recent and frequent queries into the score at request time. The global top-k from the trie is the base; personalization re-weights it for the individual.
Two-stage ranking: A cheap global stage (the precomputed trie top-k) narrows millions to a handful; a light personalization stage reorders just those few per user. Expensive work stays global; per-user work stays tiny.
Step 7 · Scale & the sharp edges
A trie too big for one box
Multi-language, multi-region suggestions don’t fit in one machine’s memory. And firing a request on every keystroke can melt your backend if a user types fast.
Design decision: The multi-language trie won’t fit in one box, and fast typists fire a request per letter. Fix?
The call: Shard the trie by prefix + replicate; debounce keystrokes on the client. — The first character is a natural shard key — route a–f, g–m, … to different replicated servers. Debouncing (~50ms) and cancelling stale requests means only meaningful prefixes hit the backend.
Shard the trie by prefix (route a–f, g–m, … to different servers) behind a load balancer, and replicate each shard for read throughput. On the client, debounce keystrokes (~50ms) and cancel stale requests so only meaningful prefixes hit the server.
Shard the read fleet: The first character is a natural shard key. Each shard holds a slice of the trie in memory and is replicated for traffic. Debouncing on the client is the cheapest scaling trick of all — fewer requests.
You did it
You just designed typeahead.
- A single Suggest API on the hot path, called every keystroke.
- A trie turns “find completions of a prefix” into an O(L) walk.
- A prefix-keyed cache answers the skewed, common prefixes in <1ms.
- Precomputed top-k at each node — ranking happens offline, not live.
- A query log + offline builder keep suggestions fresh, swapped atomically.
- User history blended in for two-stage, personalized ranking.
- Shard the trie by prefix and debounce keystrokes to scale.