Books Deep-Read · System Design Interview Vol 1 · Ch 13
System Design Interview Vol 1 · Ch 13 · Alex Xu · 2020
You type two letters into a search box and a list of suggestions drops down; you tap one and you're gone. That's search autocomplete. Chapter 13 of System Design Interview asks you to build it from scratch. It looks like the most modest problem in the book, and it has the most lopsided ratio between reading and writing of any chapter in it.
You probably assume autocomplete is "searching for you while you type." It's the opposite — it never searches. If it actually ran a search, you'd have finished typing the word first. What it does is look up a table that was sorted long ago: every letter you press just collects an answer that was written down in advance.
The difficulty is volume. Ten million people searching ten times a day is a hundred million searches; but one search takes about twenty keystrokes, and every keystroke is its own request — so the backend absorbs two billion requests a day, twenty thousand-odd per second, double that at peak. And each one has to come back in the blink of an eye; any slower and the dropdown visibly stutters. Asking a database to sift billions of past searches for "the five most popular ones starting with tr" is too slow even once, let alone twenty thousand times a second.
Two moves.
First, arrange every past search into a tree of forks, letter by letter: press t and you take one fork, press r and it forks again — every junction in the tree stands for one beginning. Reaching the "tr" junction then depends only on how many letters you typed, and not at all on whether the store holds a hundred million rows or ten billion.
The second move is the real trick: plant a signpost at every junction ahead of time, reading "from here on down, the five most popular are these." Now the query never has to walk any further — arrive at the junction, copy the sign, done. What gets written on the signs is recomputed overnight, once a week, from the previous week's search logs, and never crosses paths with the daytime queries at all.
The price is plain: the sign was planted last week, so a phrase that caught fire yesterday won't be suggested today — getting breaking terms in within minutes means building a second, real-time pipeline, and complexity and cost go up together. Most products don't need it.
Autocomplete isn't search, it's a lookup: arrange popular searches into a tree that forks letter by letter, and write "the top five" into every junction ahead of time. Daytime just fetches signs; rewriting them is an offline job that runs once a week.
Want the mechanisms, the numbers and the diagrams? → Switch to the deep read
This chapter teaches you to take a feature that looks like real-time search and turn it entirely into a precomputed lookup. Three steps: use a trie to decouple "locate by prefix" from the size of the corpus; precompute top-k at every node so a query collapses from "walk the subtree, then sort" into an O(1) fetch; then split the system into an offline rebuild path and an online read-only path that never touch each other. Those three steps are the general recipe for a whole class of problems: extreme read-heaviness under a latency budget of tens of milliseconds.
This is in Part II ("system case studies") of Volume 1, right after Chapter 12's chat system. It pushes the read/write ratio to an extreme: the write path may run offline on a weekly cadence, while the read path must absorb tens of thousands of requests per second and answer each in under a hundred milliseconds. Its real-world counterpart is every search box you use, and it leads directly into the skeleton Chapters 14 and 15 share — compute in bulk offline, serve read-only online.
Get the magnitudes straight first, or the discussion is hollow. On the book's assumptions — 10 million DAU, 10 searches per person per day — that's 100 million searches a day; a query averages 20 characters, and each character fires its own autocomplete request, so request volume is multiplied by 20: roughly 2 billion/day ≈ 24,000 QPS, with peak estimated at 2× ≈ 48,000 QPS. The book also cites Facebook's published figure for typeahead: latency has to stay around 100 ms, or the dropdown stutters visibly.
Put those numbers side by side and the shape of the problem appears: a "write" — somebody searched a new phrase — can take hours or days to become visible without anyone caring; a "read" has to pick the five most popular prefix matches out of billions of historical queries, tens of thousands of times a second, in tens of milliseconds.
What happens if you don't solve it? The obvious approach is a frequency(query, frequency) table and SELECT ... WHERE query LIKE 'tr%' ORDER BY frequency DESC LIMIT 5. That's fine over tens of thousands of rows; over billions, the prefix LIKE scans a large slice of the index and then sorts the whole result set — hundreds of milliseconds per call. Multiply by 24,000 QPS and the database is flat on its back. So the real proposition here isn't "how do we query faster" but "how do we make the query unnecessary."
A trie stores every historical query by branching one character per level: the path from the root to a node spells a prefix, and the node carries the queries under it along with their frequencies. In a lowercase-English setting each node has at most 26 children.
The first payoff is that reaching the prefix node costs only as much as you typed: p characters, p steps — O(p) — whether the store holds a million rows or ten billion. Add one engineering constraint (users essentially never type more than about 50 characters, so cap the maximum prefix length) and O(p) is a constant in practice.
But the trie alone doesn't save you. Having found the tr node, what you actually want is "the five most popular queries starting with tr" — which means walking its entire subtree to collect candidates and then sorting them by frequency. If the subtree holds c queries, that's O(c + c log c), and the shorter the prefix, the larger c gets. The instant a user presses the first letter t, c may be in the tens of millions. The query that most needs to be fast is exactly the slowest one.
Here's the turn: since "the five most popular queries starting with tr" cannot change between two offline rebuilds, why compute it in front of the user at all? So store a top-5 list directly on every node. The query collapses to two steps — walk the prefix to the node (constant), return the stored list (one step) — for O(1) overall, wholly independent of corpus size.
Two costs, stated plainly. Space: every node carries five extra references, so memory rises noticeably — which is precisely why sharding becomes necessary later. And write amplification: change one query's frequency and the top-5 on every ancestor along its path to the root may need re-ranking — one update touches p nodes on the way up. That bill is unpayable online, which forces the next step.
Updates are expensive and the candidate lists don't need to be fresh by the second — so don't update the trie online at all. The system splits into two halves that never interfere:
The offline data path — query logs land continuously; an aggregator compresses a week of them into a (query, frequency) table; build workers use it to construct a brand-new trie from scratch and swap it in wholesale. Old and new snapshots coexist across the switch, so rebuilding never disturbs live queries.
The online query path — keystroke → load balancer → API server → an in-memory trie cache that returns five candidates directly. Only on a miss (fresh capacity, a restart) does it fall back to the persisted Trie DB.
The Trie DB usually lands one of two ways: a document store (say MongoDB) holding the whole trie serialized into one document, replaced wholesale on rebuild; or a key-value store — flatten the trie into a hash table whose key is the prefix and whose value is that top-5. The second is worth dwelling on: once every node's answer is precomputed, the tree shape is useless on the read path; all that remains is a prefix → five candidates map. The trie is build-time scaffolding, not a serving-time necessity.
None of these change the architecture, and all of them move the bill.
Browser caching. Suggestions barely change within an hour, so let the browser hold them. The book's concrete evidence is that Google's autocomplete response carries cache-control: private, max-age=3600 — private, cache for an hour: the same user retyping the same prefix within the hour never leaves the browser.
AJAX requests. Fire asynchronously and repaint only the dropdown, never the page — this is the precondition for "one request per keystroke" being tolerable at all.
Log sampling. Frequency counts exist only to rank, so there's no need to record every request: keep 1 in every N. Log volume drops to a fraction while the relative ordering of popular queries is essentially unaffected — the classic trade of statistical precision for storage and bandwidth.
"Find the most popular entries with this prefix" has four typical answers, and their costs differ wildly:
Table 1 · Four ways to answer a prefix query
| Approach | Cost per query | Fits | What it costs you |
|---|---|---|---|
| SQL table + LIKE 'p%' | Index prefix scan + full sort, hundreds of ms | Tens of thousands of rows / internal tools | Any real QPS flattens the database |
| Inverted index / full-text search | Tens of ms, but it's built to search documents | When you genuinely need infix or fuzzy matching | Heavy; still expensive at one query per keystroke |
| Plain trie (no precompute) | O(p + c + c log c), slower the shorter the prefix | Demos / small vocabularies | The short prefixes that most need speed are slowest |
| Trie + per-node top-k | O(1) | Billion-row vocabularies, tens of thousands of QPS | Memory rises sharply; updates must go offline |
Once the approach is settled, three choices remain that an interviewer will press on:
Table 2 · Three decision points, and how to call them
| Decision | Option A | Option B | How to choose |
|---|---|---|---|
| Update cadence | Weekly offline rebuild: simple, stable, zero write pressure online | Near-real-time streaming: breaking terms visible within minutes | A by default. Go to B only when trending terms are the product value (news, flash sales), and accept a whole stream-processing pipeline as the price |
| Trie DB shape | Document store, serialized whole: matches the tree, rebuild replaces it wholesale | Flattened KV as prefix → top-5: simplest read path, easiest to scale out | Pure prefix autocomplete: B. If you still need subtree-level computation, keep the tree and take A |
| Sharding rule | 26 shards by first letter: simplest to implement | Shard map manager, split by historical distribution | Always B — letter frequency is wildly skewed, so an even split guarantees hot shards |
Sharding is where this question is most often answered wrong. Once one machine can't hold the whole trie, the reflex is 26 shards by first letter, then 676 by the first two; but letter frequency is inherently skewed, so an even split leaves one shard to blow up first. The right move is a shard map manager — a map of "prefix range → shard" derived from the historical distribution. The map itself is tiny and can be cached on every API server.
The value of this chapter isn't "how to code a trie" — it's that it pins down the solution to a class of problems: when reads vastly outnumber writes and the answer can't change between updates, precompute the answer and split the system into an offline rebuild path and an online read-only path. You'll keep running into that skeleton — Chapter 11's fan-out-on-write feed, Chapter 14's pre-generated video transcodes; same move underneath.
The book adds two extensions: different countries have different popular queries, so you can build a trie per country and push it to a CDN; multi-language support means widening nodes from 26 letters to Unicode characters.
The scoring points in an interview are equally concentrated: can you derive the 20× amplification from "one request per keystroke," can you point out unprompted that a plain trie is slowest on short prefixes, and do you avoid the "just split into 26 even shards" trap.
LIKE prefix query — the right mental model for autocomplete is a lookup.1 · The shape of the problem: 10M DAU × 10 searches/day × 20 characters, and one request per keystroke multiplies it 20× — about 24,000 QPS, ~48,000 at peak, each answered inside 100 ms.
2 · The proposition isn't "query faster," it's make the query unnecessary — autocomplete is a lookup, not a search.
3 · A trie brings "locate by prefix" down to O(p), independent of corpus size; cap the maximum prefix length and it's effectively constant.
4 · But a plain trie is slowest on short prefixes (walk the whole subtree, then sort) — precisely the query that most needs to be fast.
5 · The key move: precompute top-5 at every node, making the query O(1); you pay in memory and in write amplification (one update rewrites a whole ancestor path).
6 · Hence two paths: weekly offline rebuild with a wholesale snapshot swap, and an online read-only memory cache. Once precomputed, the read path can even flatten to a prefix → top-5 hash table — the trie is only build-time scaffolding.
7 · Three cheap wins: browser caching (Google uses max-age=3600), AJAX partial updates, and log sampling.
8 · Don't shard evenly by first letter: the distribution is skewed, so use a shard map manager keyed on historical data. Known limits: real-time trends, spell correction and personalization are all outside this design.