Course Content
System Design Interview
31 sections · 71 lessons
Search Autocomplete: scope, scale and the top-k trie
The prompt: "Design search autocomplete." The drop-down of suggestions that appears as a user types into a search box.
Attempt it for 45 minutes first. In particular, before reading on, work out how many requests per second your design has to serve — that number is the surprise in this problem, and meeting it yourself is worth more than reading it here.
This lesson scopes the problem, finds that surprising request rate, and then builds the data structure at the centre of the design: a trie that answers "top five completions" without searching.
What makes this problem interesting
The functionality is small: given a prefix, return the five most popular completions. There is no fan-out, no distributed transaction, and no interesting failure mode. What makes it a real design question is the latency budget and the request multiplier. A suggestion that arrives after the user has typed the next character is worthless, and the user types a lot of characters.
The five questions
1. Prefix matching only, or fuzzy? "Does the query have to start with what was typed, or should resturant return restaurant?" Prefix-only is a trie. Fuzzy is a different and much larger system. Scope to prefix matching, and handle typos as a follow-up in Follow-ups.
2. How many suggestions? Five is the usual answer, and the number matters because the trie design later in this lesson caches exactly k results at every node. A change from 5 to 50 multiplies the index memory by ten.
3. How fresh must new queries be? If a term that started trending an hour ago must appear, an hourly rebuild works. If it must appear in seconds, you need a second, real-time path alongside the batch one. Ask, because it decides whether the design has one pipeline or two.
4. Is personalisation in scope? Global popularity means one shared index that every user reads. Per-user history means a per-user data structure and a merge at request time. Scope personalisation out for the main design and discuss it in Follow-ups — it changes the caching story completely.
5. What is the latency target? Push for a number. The answer is usually around 100 ms end to end, and it is a hard constraint rather than an aspiration: if the round trip exceeds the interval between keystrokes, suggestions arrive for prefixes the user has already left behind.
Scope
In: prefix suggestions ranked by popularity, the pipeline that builds the ranking, and serving at scale. Out: the search results themselves (a different system), spelling correction as a product feature, and query understanding.
Requirements and scale
Functional: given a prefix, return the top k completions ranked by popularity; reflect newly popular queries within the agreed freshness window; filter unsafe suggestions.
Non-functional: 99th-percentile server-side latency under 50 ms; high availability — a failed autocomplete degrades to no suggestions and must never block the search box; suggestions may be slightly stale, so eventual consistency is fine (Consistency models).
The multiplier that catches people out
Invented figures for a mid-size search product. A day is 100,000 seconds (Rounding aggressively and staying fast).
| Quantity | Assumption |
|---|---|
| Daily active users | 10 million |
| Searches per user per day | 10 |
| Total searches per day | 100 million |
| Average query length | 20 characters |
If the client requested suggestions on every keystroke:
100M searches × 20 characters = 2 billion autocomplete requests per day
2,000,000,000 ÷ 100,000 s = 20,000 requests/s average, 100,000/s at a 5× peak
That is the number. The search backend handles 100 million queries a day, comfortably 1,000 per second. The autocomplete service in front of it handles twenty times that, because every search is preceded by twenty of them.
Debouncing, and what it recovers
The client does not have to fire on every keystroke. Waiting until the user pauses — a debounce of around 50 ms — collapses fast typing into far fewer requests. A realistic assumption is 4 to 6 requests per query instead of 20.
100M × 5 = 500 million requests/day → 5,000/s average, 25,000/s peak
A 4× reduction, obtained entirely on the client, for a few lines of code. Say this out loud in the interview: the cheapest optimisation in this design is not in the datacentre.
Data volume
Assume 20% of daily searches are unique query strings: 20 million distinct queries a day, of which most are seen once and never again. Over a rebuild window of, say, a week, the queries worth indexing — those seen more than a handful of times — might number in the low tens of millions.
Aggregated, that is a small dataset. At an average 25 bytes per query string plus a count, 20 million queries is around 600 MB of raw terms. The trie built over it is larger (the next part computes that), but the headline is important: this index fits in memory on one machine before sharding, which is why the design can meet a millisecond lookup budget at all.
The trie, and why the naive trie is not enough
This is the deep dive and the one new idea this section owns: caching the top-k result at every node so a lookup is a traversal with no subtree scan, combined with the offline rebuild in The data-gathering pipeline.
The data structure
Store the popularity count on nodes that terminate a complete query. The trie for cat (30), car (25), card (10) has a path c → a → t, with a branch at a to r, and counts sitting on the terminal nodes.
Why the naive version misses the latency budget
Finding the node for a prefix is fast. Answering the question is not, because the answer requires the most popular completions, and those are scattered through the subtree below the node.
The naive algorithm: walk to the prefix node, then traverse the entire subtree collecting every terminal node, sort by count, take the top five.
Cost the worst case. The prefix is a single letter — a — and the subtree beneath it contains, say, 2 million queries. Traversing 2 million nodes and sorting the results is on the order of hundreds of milliseconds. The budget was a few milliseconds.
And the worst case is not rare. Short prefixes are the most common requests, because every query passes through its first character on the way to being typed. The naive trie is slowest exactly where traffic is heaviest.
The fix: cache the top-k at every node
Store, at each node, the k best completions of that node's prefix, precomputed.
A lookup becomes: walk p hops to the node, read the stored list, return it. For k = 5 and a prefix of 6 characters, that is 6 pointer hops and one array read — comfortably under a millisecond. Query cost no longer depends on subtree size at all.
The trade-offs, both real:
Memory. Suppose the trie has 30 million nodes over 20 million indexed queries. Storing 5 entries per node, each a 4-byte reference into a string table plus a 4-byte score, adds 40 bytes per node:
30M nodes × 40 bytes = 1.2 GB of cached results
on top of the trie structure itself. Roughly a 2–3× increase in index size, in exchange for a 100× improvement in worst-case lookup. That is a good trade, and being able to state both halves is the point.
Update cost. Incrementing one query's count can change the cached list at every node along its path, and a query of 20 characters has 20 ancestors. Worse, a change deep in the tree can propagate upward only if the new score beats the fifth-best entry at each level. Doing this under live traffic means locking parts of a shared structure on the read path. The answer in The data-gathering pipeline is not to do it at all.