// Heavy Systems + Your Rehearsal
Design search autocomplete
System Design track · 20 min
- Explain how a trie with a ready top-k list in every node answers each keystroke in microseconds.
- Design the offline pipeline that builds, filters and swaps in the suggestions.
- Choose how to shard the trie, and avoid the first-letter trap.
You type three letters and the search box already knows what you want. It does this for every keystroke of every user, hundreds of thousands of times per second, with about 100 ms before the suggestion feels late.
The trick is that almost nothing is calculated while you type. The answer was ready hours ago.
The requirement: given what the user typed so far (the prefix), return the top 5 suggestions by popularity, fast enough to show before the next keystroke.
The scale: a big search engine gets around 100,000 searches per second. Autocomplete fires on every keystroke, not every search, so expect several times that, say 300,000 to 500,000 requests per second at peak.
Three properties will do the design for you: it is read-only, it must be very fast, and it is fine if the data is a few hours old.
The core structure is a trie: a tree with one node per character, so “weather” lives under w, then we, then wea, then weat, and so on.
The naive way: walk down to the prefix node, then search its whole subtree for the five most popular queries. That cost grows with the size of the subtree, on every keystroke, and it dies at scale.
The key trick: store the top-k suggestions (the best k, here 5) inside every node, calculated in advance. Now a lookup means walking p characters and reading one ready list. That is a handful of steps, however big the trie is.
The price is memory. A popular query is copied into the list of every node along its path. With 20 million prefix nodes, 5 entries each and about 30 bytes per entry, you need around 3 GB of RAM. That is exactly why k is 5 and not 50.
Never from live traffic. Search logs flow into an offline pipeline: a daily or weekly batch job (MapReduce, Spark, whatever your team runs) that counts how often each query was searched, ranks them, and builds the top-k list for every prefix.
Before anything is ranked, it is filtered. Profanity, abuse, legal takedowns and known attack strings are removed inside the pipeline, so a banned phrase never reaches the trie, let alone a user's screen.
Why not update the trie with every search? Because then hundreds of thousands of writes per second would fight with readers who need answers in 100 ms. By moving the work offline, you simply avoid that fight.
When the trie no longer fits in one machine's memory, you shard it. The obvious split is by first letter: a to f on one server, g to l on another. It is badly uneven. Far more queries start with “s” than with “x”, so one server melts while another sits idle. Hashing the prefix spreads the load evenly, which is what you want, as you saw in the data-at-scale lesson.
Updates are just as careful. The pipeline builds the whole new trie offline and ships it to the servers. Each server switches from the old trie to the new one in a single step, by flipping a pointer. Readers never see a half-built trie, and if the new build is bad, you flip the pointer back.
Autocomplete is an answer prepared in advance and rebuilt on a schedule. The live system does one thing: read. Every hard part, ranking, filtering, freshness, moved to a batch job where minutes are cheap, so the live path stays a short walk through memory.
A common mistake is to “improve” freshness by writing every search into the trie as it happens. It looks smart on the whiteboard and it breaks the one thing that matters: fast reads. If you truly need trending queries within minutes (breaking news), add a small separate layer for recent trends and merge it at read time. Keep the main trie offline.
Why store a top-k list inside every trie node, and what do you pay for it?
Answer in your head first, then check.
A trie for the shape, a top-k list in every node for speed, an offline pipeline over the search logs for ranking, filtering before anything reaches the trie, hashed sharding when memory runs out, and a one-step swap so updates never show. Autocomplete is the clearest example you will meet of preparing the read path in advance.
Take your product's search logs, or a public query dataset, and design the pipeline on paper: how you would count frequencies, what you would filter out, and how often you would rebuild. Then size the trie: how many prefixes, which k, and does it fit in one machine's memory? Do the math. It is usually smaller than people fear.
- Explain how a trie with a ready top-k list in every node answers each keystroke in microseconds.
- Design the offline pipeline that builds, filters and swaps in the suggestions.
- Choose how to shard the trie, and avoid the first-letter trap.
Heavy Systems + Your Rehearsal