The whole design, in writing
Learn system design by building a search typeahead / autocomplete step by step. An interactive guide covering prefix tries, top-k ranking, caching hot prefixes, building suggestions from query logs, personalization, and sharding.
Every step of the build above, written out: the problem each piece solves, the option that was taken and the ones that were not, the numbers, and how it fails in production.
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.
What the new pieces do
- Userclient
- Someone in a search box. After each keystroke they expect a fresh list of completions in well under 100ms — faster than they can think.
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.
What the new pieces do
- Suggest APIbackend
- Takes a prefix and returns the best handful of completions. The hot path: it runs on every keystroke for every user, so it must be brutally fast.
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.
Find every query starting with "sys" among millions — on every keystroke. How?
An index helps, but it still does real per-request work and degrades for the short, high-traffic prefixes — multiplied by every keystroke of every user. Fine for a form, not for typeahead scale.
A search engine ranks documents; it’s heavyweight for "walk to a prefix and read its subtree" under 50ms per letter. Wrong tool for the hot path.
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.
- O(L)lookup by prefix
- millionsqueries indexed
- 1shared path / prefix
What the new pieces do
- Trie Serviceservice
- Walks a prefix tree where each node is a letter. Following the path for “sys” lands on the subtree of every completion that starts that way.
- Trie Storestore
- Durable storage of the serialized trie. Loaded into memory by the Trie Service; rebuilt offline as query popularity shifts.
Back of the envelope
- lookup = O(prefix length)
- independent of how many queries exist
- "system", "systemd", "systematic"
- share one "system" path — zero duplication
- walk to node ⇒ subtree = matches
- finding candidates is pointer-following, not scanning
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.
A tiny set of short prefixes ("a", "you") drives most traffic. How do you exploit that?
Replicas add throughput but every hot request still redoes the same walk + rank. When the same few prefixes repeat constantly, recomputing the identical answer is wasted work.
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.
Per-session caching has terrible hit rates — the value is in prefixes shared across millions of users, not one person’s history. Cache by prefix, the thing everyone collides on.
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.
- <1mscache hit
- ~90%hit rate
- top-10per prefix
What the new pieces do
- Suggestion Cachecache
- Redis holding precomputed top-k lists for hot prefixes. Most traffic is short, common prefixes, so a cache hit answers in under a millisecond.
Back of the envelope
- short prefixes ≈ most traffic
- a handful of prefixes drives the bulk of requests
- ~90% hit ⇒ <1ms answer
- the common case is a memory lookup, never the trie
- miss ⇒ trie walk, then warm
- the long tail still resolves correctly
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.
The prefix "a" matches millions of queries. How do you return the best 10 in time?
Alphabetical ignores what people actually search — "aardvark" over "amazon". Order must come from real signal, not the dictionary.
Sorting millions of matches on every keystroke is exactly the live work typeahead can’t afford. The ranking must already be done before the request arrives.
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.
- top-10stored / node
- popularityprimary signal
- offlineranking cost
What the new pieces do
- Rankerservice
- Of the thousands of matches under a prefix, keeps only the best ~10 — scored by popularity, recency and personalization — so the list is useful, not exhaustive.
- Query Countsstore
- How often each query has been searched. The raw signal the Ranker uses to decide which completions are worth showing.
Back of the envelope
- rank offline at build time
- the expensive sort happens once, not per request
- store top-10 per trie node
- each node caches its best children
- request = read ready-made 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.
Yesterday’s trending query should surface today — but you can’t mutate a giant shared trie live. How?
Writing to the shared trie on every read wrecks read performance and risks serving a half-updated tree. The serve path must stay immutable and fast.
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.
Rebuilding per request is absurdly expensive and defeats precomputation entirely. Build is heavy and rare; serve is light and constant — keep them apart.
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.
What the new pieces do
- Query Logbus
- A stream of everything users actually search. The fuel for keeping suggestions current — what was trendy yesterday should surface today.
- Trie Builderworker
- A batch job that folds the query log into fresh counts and rebuilds the trie with updated top-k lists, then swaps it in atomically.
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.
"doc" should suggest the user’s own docs before the world’s most popular "doc". How?
A full trie per user is enormous and impossible to keep fresh for hundreds of millions of people. Personalization should re-weight a small candidate set, not duplicate the index.
Pure personal history is too sparse — most prefixes a user types they’ve never typed before. You need the global base for coverage and personal signal for relevance.
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.
What the new pieces do
- User Historystore
- A user’s own recent searches. Blended into ranking so “doc” suggests their docs, not just the globally popular ones.
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.
The multi-language trie won’t fit in one box, and fast typists fire a request per letter. Fix?
No single machine holds a multi-language trie in memory, and caching doesn’t solve the per-keystroke request storm. You need to split the index and cut the request rate.
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.
Shipping a multi-gigabyte, constantly-changing index to every browser is impossible. The trie stays server-side and sharded; the client only debounces and renders.
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.
You did it
You just designed typeahead.
Everything you assembled, in order
- 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.