The whole design, in writing
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.
Why this piece earns its place
The thing worth pushing back on is treating this like any other read endpoint. Suggest has a property the main search API doesn’t: nobody asked for it. A search request that fails needs an error page; a suggest request that fails shows no dropdown and the user keeps typing. That asymmetry is an asset, so spend it. Give the endpoint its own fleet and its own deploy, so a slow rollout on search can’t eat a budget measured in tens of milliseconds. Give it a hard timeout well under the 100ms target that fails open to an empty list rather than retrying — a retry lands after the next keystroke, by which time its answer is for a prefix the user has already left. There is nothing worth waiting past the deadline for — late is indistinguishable from never — so the box cuts the request off instead of holding it open. Degrading the content of an on-time answer is a separate question, and one that only arrives once there is something optional left to drop.
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.
Why this piece earns its place
Be precise about what that O(L) actually buys, because it’s only half the request. Reaching the node for sys is a few pointer hops, but the node for a has millions of completions hanging beneath it, and reading them out costs the size of the subtree, not the length of the prefix. So the cheap part is finding the candidate set and the expensive part is everything after it — which is precisely the work step 4 deletes by storing the answer on the node instead of gathering it from below. Until that exists, the shortest and hottest prefixes are the slowest requests on the site, which is the opposite of what the traffic wants. The other quiet cost is memory: a node per character with a child pointer table is far bigger than the query text it indexes, and the overwhelming majority of those nodes have exactly one child. Collapsing single-child chains into one labelled edge — a radix tree — is what keeps millions of queries indexed as a structure you can hold in RAM instead of a diagram.
- 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.
Why this piece earns its place
The knob this adds isn’t cache size, it’s how an entry dies — and the default answer bites. These lists are already precomputed, so a long TTL looks free. Then the builder swaps in a new trie and the cache doesn’t know: it keeps handing out lists computed from the old one, and the fresher suggestions the entire log pipeline exists to produce sit invisible behind a hot key until it expires. With most traffic concentrated on a handful of prefixes, those are exactly the entries that never fall out on their own, so the freshest part of the system is hidden by the fastest part of it. Fix it structurally rather than by tuning: put the trie version in the cache key, so a swap orphans the whole previous generation and the hot prefixes refill on their first miss. The TTL then only has to bound drift within a version, and can be generous. Go the other way — a short TTL to stay fresh — and you pay twice, because the hit rate falls away from ~90% and every one of those extra misses is the most expensive possible trie walk.
- <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.
Why this piece earns its place
The uncomfortable property of precomputed popularity is that it’s a closed loop. What a node shows is what gets clicked, a click is a search, and searches are what the counts are rebuilt from — so today’s top-10 becomes tomorrow’s evidence for itself. A genuinely better completion that never made a list never gets typed, never accumulates count, and is never promoted; the ranking converges on whatever it already believed. Offline evaluation won’t catch it either, because the log you’d score against was produced by the model you’re scoring. Two cheap defenses. Lean on recency, not just raw volume, so a query climbing fast can beat one that has merely been popular for years — rank by velocity as well as height. And hold a slot or two in each node’s list for candidates that would otherwise never surface, then read the counts back on those slots specifically: an impression that earns searches has proven itself and stays, one that doesn’t drops out at the next build. Without that, the index is a very fast record of what was popular the day it was first assembled.
- 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.
Why this piece earns its place
Cadence is the knob, and what bounds it is the build: a full pass over the log, a re-rank of every node’s top-k, then shipping the serialized trie out and loading it on every serving box. The swap adds a price of its own, but a fixed one — version N keeps answering while N+1 loads, so each box must hold two tries at the instant of the flip, and that cost is identical whether you flip hourly or by the minute. It decides whether an in-process swap is affordable at all, not how often you get to do it. Between the two, the honest answer is a cadence of minutes to hours instead of something continuous. Run it too slowly and the freshness requirement is simply gone — this morning’s trending query appears tomorrow, and the query log becomes an expensive description of the past. The second property of an all-or-nothing build is worth saying out loud, because it only helps if you plan for it: one bad input window — a bot hammering a single query, a spike caused by an outage — bakes itself into every node’s top-k at once, and there is no per-entry patch for that. Keep version N−1 loadable on every box so the recovery is a flip backwards, taking seconds, rather than an emergency rebuild run while the wrong suggestions are on screen.
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.
Why this piece earns its place
Notice what this quietly reintroduces: per-request ranking work, on the one path the previous steps spent their whole time emptying out. It also collides with the cache, and that collision is the thing to design around. A cached entry is keyed by prefix alone, which is only sound while the answer is identical for everybody. The moment history is blended in before the cache, a shared entry either hands one person’s suggestions to the next or stops being shareable at all — and the hit rate carrying most of the traffic evaporates. So the ordering is load-bearing: the cache keeps storing the global top-10, and the re-weight happens after the read, on the ten candidates that came back. Personal signal never enters the cache or the trie, which is also the privacy answer. Then bound it. Give the history lookup a tight timeout and let it fail open to the global order, because a slow history store should cost relevance and not the dropdown, and cap how far it can reorder — otherwise someone who types the same query all day is shown nothing else ever again.
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.
Why this piece earns its place
Sharding on the first character is the natural key and also the unbalanced one, for exactly the reason the cache works: traffic is heavily skewed toward a few short prefixes. An a–f shard and an x–z shard do not see comparable load, and the single hottest first letter can’t be split any further under that rule — so you’ve bought capacity precisely where it wasn’t needed. Cut the ranges by measured volume instead, using the same counts the builder already computes, and let the boundaries move at each rebuild; replication then adds throughput where the traffic actually lands. The client has its own sharp edge. Once you debounce and cancel, responses can return out of order, and the reply for sy arriving after the reply for sys will happily paint the shorter, staler list over the better one — the box appears to type backwards. Every response has to carry the prefix it answered and be discarded unless that still matches the input. And the ~50ms wait is a real charge against the sub-100ms budget, spent before the request is even sent.
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.