Lesson 6.7 · 25 min
Search autocomplete
Type into a live trie and watch a cached top-5 cut a lookup from 127 nodes to 3, shard prefixes by real traffic, and see a weekly rebuild miss a trending eclipse entirely.
The idea in plain words
Autocomplete guesses what you are typing and offers the most popular matches after every keystroke. To answer that fast, the answers are worked out ahead of time, not when you type.
The problem it solves
Suggestions must appear within a few tens of milliseconds of every keystroke, for millions of people typing at once. Searching all past queries on each keystroke is far too slow.
How it works
- Count how often each search has been made, from logs.
- Build a tree of prefixes (a trie): each step down adds one letter.
- At each node, store the top few completions for that prefix, worked out in advance.
- A lookup just walks down the typed letters and returns the stored list.
- Rebuild the counts regularly, and boost recent searches so trends appear quickly.
Example
Typing “sys” walks s → y → s and returns the stored top 5: “system design”, “system32”, “systemctl”, “sysco”, “system of a down”. No counting happens while the user types; that was done when the trie was built.
Key terms
- Prefix
- The letters typed so far, such as “syst”.
- Trie
- A tree where each step down adds one letter, so all words with a prefix sit under one node.
- Top-k
- The k most popular completions, such as the top 5.
- Debounce
- Waiting a few milliseconds after a keystroke before sending a request.
- Decay
- Making older searches count less, so trends rise quickly.
In this lesson you'll learn
- How keystrokes turn into request rates, and how debounce and caching cut them.
- How a trie with top-k cached at every node makes each lookup a short walk, and what that costs in memory.
- How to shard by real traffic, keep suggestions fresh for trends, and defend the design.
Sections
- Requirements and numbers
- API and data
- Architecture
- Deep dive: the trie
- Deep dive: scale and freshness
- Design review
Cheat sheet
| Lookup | walk prefix, read cached top-k |
|---|---|
| Updates | offline build + snapshot swap |
| Trends | streaming counts with decay |
| Sharding | ranges balanced by traffic |
| Client | debounce + CDN for short prefixes |
The interactive simulations and the scored design review load with JavaScript.