Type one letter into a search box and a ranked list of likely queries appears in under a tenth of a second. This chapter builds the machine behind that magic — a trie with precomputed top-k lists, an offline pipeline that learns from billions of past searches, and a way to shard it all across servers.
Autocomplete feels like mind-reading, but it's really just very fast list-lookup. The user types a few characters — a prefix — and you must instantly produce the handful of complete queries that (a) start with those characters and (b) are the most popular.
That's the whole problem in one sentence, and almost everything interesting follows from one brutal constraint: it has to be fast. Every keystroke fires a new request, so "fast" means a full round trip and ranked answer in well under a tenth of a second, while the system as a whole is fielding millions of these per second.
We'll build it the way the chapter on scaling taught us — start with the obvious data structure, find where it's too slow, and peel that job off into something dedicated. The obvious structure is a trie; the thing it's too slow at is ranking; and the fix is to precompute the answers. Then we wrap that core in an offline learning pipeline, a fast serving layer, and a sharding scheme — and finish with the messy real-world extras: typos, trends, and personalization.
Before any boxes-and-arrows, pin down what the thing must do. Autocomplete has a surprisingly tight, surprisingly small spec — and naming it precisely is what keeps the design honest.
Notice what's not here: we don't need the suggestions to reflect the very latest search this second, and we don't need perfect ranking. "Good enough, instantly" beats "perfect, eventually." That trade — sacrificing freshness and exactness to buy speed — is the seed of every decision below.
Here's the natural way to store words so you can find everything starting with "di" instantly: build a tree where each node is one character, and the path from the root down to a node spells out a prefix. To find all words starting with "di", you walk root → "d" → "i" and everything in the subtree below is your answer set.
This tree of prefixes is called a trie (from retrieval, and yes, everyone pronounces it "try"). Shared prefixes are stored once: "disney", "discord", and "dictionary" all share the same "d" and "i" nodes near the top, then branch apart. At each node that completes a real query, we store how many times that query has been searched — its frequency. A node can be both a complete word and a stop along the way to longer ones ("disc" is a word and a prefix of "discord").
So a lookup is two phases: walk down to the prefix node (cheap — as many steps as there are characters typed), then explore the subtree to collect every completion and its frequency, sort by frequency, and take the top k. And that second phase is the problem.
For a hot prefix like "a" or "the", the subtree underneath holds an enormous number of words. Visiting all of them, gathering frequencies, and sorting — on every single keystroke — blows the millisecond budget instantly. The trie makes "find the prefix" fast, but leaves "rank the completions" slow. That's the gap the next section closes.
Trie(children: Map[Char, Trie], freq: Int). Insert and lookup are folds over the characters of a string. We'll write exactly that in the code section.The fix is almost insultingly simple, and it's the heart of the whole system: store the answer on the node itself. At each prefix node, keep a small list — the top k completions for that exact prefix, already ranked. The "d-i" node doesn't just point at a subtree; it carries a ready-made list ["disney", "discord", "disco"].
Now a query is trivial. Walk down to the prefix node (a handful of character steps) and read the list that's sitting right there. No subtree exploration, no sorting at query time. The whole lookup costs about O(length of the prefix) — and prefixes are short. That's how you hit single-digit milliseconds.
This is a classic space–time tradeoff. We spend extra memory (every node now stores k suggestions) to buy extra speed (no work at query time). The cost is real — millions of prefix nodes each holding a small list — but memory is cheap and latency is sacred, so it's a trade we happily make. It's the same instinct as the cache from Chapter 1: remember the answer instead of recomputing it.
The natural question: when does that precomputed list get built? Not at query time — that would defeat the point. It's built offline, in advance, by a separate pipeline. Which is exactly the next section.
Where do those frequencies come from? From watching what people actually search. Every query users type gets logged, and those logs are the raw material we turn into a ranked trie. The trick is to split the system cleanly into two halves that run at very different speeds.
The offline pipeline does the slow, heavy thinking. It takes the firehose of raw query logs, aggregates them (group identical queries, count how often each was searched over some window), filters out junk and offensive terms, and then rebuilds the trie from scratch with fresh frequencies and freshly precomputed top-k lists at every node. This runs on a schedule — say once a week, or nightly — far away from any user request.
"disney" → 1.2M this week). This is a big batch job — exactly the kind of work a data-warehouse / map-reduce style pipeline eats for breakfast.The online query service does the opposite job: nothing but lightning-fast reads against the trie the pipeline handed it. It never aggregates, never rebuilds, never sorts. This separation — expensive batch work offline, trivial reads online — is the single most important architectural decision in the whole design. It's why a keystroke can be answered in microseconds: all the hard work already happened, hours ago.
The online side has one job — turn a prefix into a top-k list as fast as physically possible — and a few well-worn tricks make it scream.
Together these mean the server fields fewer requests than you'd fear, and each one it does field is a near-instant in-memory read. The expensive parts of the system are kept rare; the frequent part is kept cheap.
A trie covering every query in every language, with top-k lists on every node, can grow far past what fits on one server. Same move as Chapter 1: chop it into pieces and put each piece on its own machine. The natural cut is by first letter — one shard owns all prefixes starting with "a", another owns "b", and so on. A query for "disney" goes straight to the "d" shard.
But splitting evenly by letter spreads letters evenly, not traffic. The letter "s" starts a colossal share of English queries; "x" and "z" start almost none. Give each its own shard and the "s" server melts while the "x" server idles — the hotspot problem again. The fix is load-aware splitting: keep heavy letters on their own (or split them further by the second letter — "sa", "sb", "sc"…), and bundle many light letters together onto one shard ("x", "y", "z", "q" can comfortably share).
Once shards no longer map one-to-one to letters, you need a small lookup layer that knows the current layout — a shard map that, given a prefix, names the shard holding it. The query path becomes: consult the shard map, route to that shard, read its in-memory top-k. When traffic shifts, you re-split the map and rebalance, and the routing layer just follows along.
The offline rebuild is what makes the system fast, but it's also what makes it stale: between rebuilds, the trie is frozen. Most of the time that's fine — popularity drifts slowly. The hard case is sudden news: a celebrity, an event, a product launch that everyone starts searching for in the same hour. A weekly rebuild won't show it for days. So freshness is a spectrum of choices, traded against cost and complexity.
Most production systems run a hybrid: a sturdy periodic rebuild for the long tail, plus a nimble trending layer for the head. The base trie gives you correct, comprehensive coverage; the trending layer gives you the same-day relevance the base can't.
The clean prefix trie is the skeleton. Real autocomplete grows several extra organs, each a small system of its own bolted onto the core.
None of these change the core idea. They're re-rank layers, filters, and variant-expansions wrapped around the same engine: a trie with precomputed top-k, fed by an offline pipeline, served from memory, sharded by prefix. Here's the whole machine as a checklist:
Section 2 promised the trie is "a node is a map from char to sub-trie, plus a frequency." Here it is, exactly that, in both languages. insert folds a word into the tree one character at a time, bumping the frequency at the terminal node. topK walks down to the prefix node, gathers every completion in its subtree with its frequency, sorts, and takes k — the live version, the one section 3 told us to precompute and cache. Watch how both versions are just folds over a Map.
Map of children — insert rebuilds one path, topK aggregates a subtree. In production you'd run a single pass that attaches the sorted top-k list to every node, so the query path never calls this collect at all. The precomputed cache is just this fold, memoized onto the structure.