Search Autocomplete
Suggestions in under 100 ms — the trie, precomputing the top results at every prefix, and updating without rebuilding
Autocomplete is a latency problem disguised as a search problem. The suggestions must appear between keystrokes, which leaves almost no budget.
1. Clarify and Scope
| Question | Assumption taken here |
|---|---|
| How many suggestions? | Top 5 |
| Ranked by what? | Historical search frequency |
| Personalised? | No — a single global ranking |
| How fresh? | New trends may take an hour to appear |
| Spelling correction? | Out of scope |
2. Put Numbers On It
100 million searches/day
Average query: 20 characters, so ~20 autocomplete requests per search
REQUESTS
100M × 20 = 2B autocomplete requests/day
÷ 100,000 sec ≈ 20,000 req/sec
× 3 peak ≈ 60,000 req/sec ← 20× the search rate
LATENCY BUDGET
target < 100 ms end to end
network round trip ≈ 40 ms
remaining for us ≈ 60 ms ← very tight
DATA
~10 million distinct queries worth suggesting
20 bytes each ≈ 200 MB rawTwo findings decide the whole design
Autocomplete traffic is 20× search traffic. Every keystroke is a request. This must be far cheaper per request than search itself.
60 ms leaves no room for a database query, ranking and sorting. Anything computed at request time is too slow. The answers must already exist.
Conclusion: precompute everything, serve from memory.
3. Define the Interface
PUBLIC — one operation, and that is the whole surface
GET /suggest?q=algo → ["algorithms", "algorithm design", "algo trading",
"algorithmic", "algorithms book"] (top 5)
INTERNAL — never called by a browser
ingest(query_string) → fed from the search log, in batchesThe read path and the write path are different systems
Nothing a user types goes straight into the suggestions. Typing is logged; the log is processed later; the serving structure is rebuilt and swapped in.
That separation is what makes 60 ms possible. The structure being read is never being written to, so it needs no locks, and it can be laid out purely for read speed.
The cost is stated in the scope table: a new trend takes about an hour to appear. Section 6 is about that choice.
Why the reply is a bare list and not objects
Every keystroke fires a request. At 60,000 requests per second, wrapping five strings in { "text": ..., "score": ..., "type": ... } multiplies the bytes on the wire for data the UI does not draw.
When an endpoint is called this often, the shape of the response is a capacity decision, not a style preference.
4. The Trie
A trie stores strings by shared prefix. Each node is one character; walking down from the root spells a prefix.
(root)
/ \
c d
| |
a o
/ \ |
t r g
| | |
[cat][car] [dog]cat and car share the path c → a, stored once. Finding everything starting with ca means walking two nodes, then collecting what is below.
| Operation | Cost |
|---|---|
| Walk to a prefix | O(length of prefix) |
| Collect all completions | O(number of completions) |
A plain trie is still too slow
Walking to the prefix a is instant. Collecting everything beneath it is not — millions of queries start with a, and you would gather them all, sort by frequency, and return five.
That is O(n log n) over millions of entries, per keystroke, at 60,000 requests/sec. Nowhere near 60 ms.
Store the answer at every node
The fix: at each node, precompute and store the top 5 completions of that prefix.
node "ca" → top5: ["cat", "car", "camera", "candle", "call"]
node "c" → top5: ["can", "cat", "car", "cheap", "chat"]Now a request is: walk the prefix, read a list, return it. No collecting, no sorting.
| Compute on read | Precomputed top-k | |
|---|---|---|
| Read cost | O(subtree × log) | O(prefix length) |
| Memory | Small | 5 strings per node |
| Update cost | Free | Must propagate upward |
This is the trade the design turns on
Memory rises — five strings at every node, so roughly 5–10× the raw data, or a few GB. That fits in memory on one machine.
In exchange, a read becomes about 20 pointer hops and one array read. Well inside 60 ms, and cheap enough for 60,000 requests/sec.
Spending memory to buy latency is the same trade as caching, applied inside a data structure.
5. The Architecture
Rebuild rather than update in place
Updating a live trie means changing the top-5 list at a node, then possibly at its parent, and its parent's parent — while reads are happening. That needs locking, and locking on a structure serving 60,000 requests/sec is a problem.
Building a fresh immutable trie and swapping a pointer avoids all of it. Reads are lock-free; the swap is one atomic assignment. The cost is that updates arrive on a schedule rather than instantly.
6. Scaling and Freshness
Sharding the trie
At a few GB the trie fits on one machine, so start by replicating it — every server holds the whole thing, and reads scale by adding servers.
If it outgrows memory, shard by first character or first two characters: prefixes starting a–f on one group, g–m on another. Every query has a prefix, so routing is trivial and there are no cross-shard reads.
Making trends appear faster
An hourly rebuild is fine for stable rankings and too slow for breaking news.
A small hot layer beside the big cold one
Keep the large hourly-rebuilt trie for the long tail, and a small, frequently-updated structure holding just the last few minutes of surging queries.
Merge the two at read time — check the hot layer first, fill from the main trie. The hot layer is tiny, so rebuilding it every minute is cheap.
This is a general pattern: split by rate of change, not by size.
7. What Was Traded Away
| Decision | Gained | Cost |
|---|---|---|
| Precomputed top-5 per node | Reads are O(prefix length) | 5–10× memory; updates propagate |
| Offline hourly rebuild | Lock-free reads, no write path | Rankings lag by up to an hour |
| Immutable snapshot + swap | No locking, safe deploys | Whole trie rebuilt each time |
| CDN in front | Popular prefixes never reach us | Stale for the CDN TTL |
| Global, not personalised | One trie serves everyone | Suggestions ignore the individual |
Follow-on Questions
Related Reading
- Caching — the CDN layer, and precomputation as caching
- Numbers Every Design Needs — where the 60 ms budget comes from
- Databases — why an index is not enough here
- Trees — a trie is a tree keyed by character