Design search autocomplete
Design typeahead with a sub-100ms budget: a trie of prefixes, precomputed top-k completions per node, an offline aggregation pipeline that ranks queries by frequency, edge caching, and why suggestions are served from precomputed structures, never queried live per keystroke.
A team built search autocomplete the obvious way: on each keystroke, fire a query that scanned the search log for the top matching past queries and returned them. In a demo with a small dataset it was snappy. In production it was a disaster — every character a user typed launched a fresh aggregation over billions of log rows, so “restaurant” was ten separate heavy queries, the search cluster buckled under the keystroke storm, and suggestions arrived 600 ms late, well after the user had finished typing and hit enter. The feature that was supposed to feel telepathic instead felt broken. The lesson they missed: autocomplete has a brutal latency budget (suggestions must beat the user’s next keystroke, under ~100 ms) and enormous read volume, so you can never compute suggestions live — you serve them from a structure precomputed offline. This lesson designs that structure and the pipeline that feeds it.
Requirements
The requirements here are almost entirely driven by one brutal number: the latency budget. When you understand why 100 ms is the ceiling, every other design choice falls out naturally.
Functional: as a user types a prefix, return the top few (say 5–10) most relevant complete queries that start with that prefix, ranked by popularity (and possibly personalization/recency). Update suggestions to reflect trending queries over time. Handle typos loosely (often a stretch goal) and filter unsafe/banned suggestions.
Non-functional: the latency budget is the headline constraint — a suggestion must appear faster than the user types the next character, so the end-to-end budget is roughly 100 ms, and since that includes a network round trip, the server has only tens of milliseconds. Read volume is huge: every keystroke of every search is a request, so requests vastly outnumber actual searches (typing “weather” is 7 requests for 1 search). Freshness is eventually consistent — suggestions reflecting yesterday’s trends, or lagging a new viral term by minutes, is acceptable; nothing is wrong if a brand-new query is not yet suggestable.
The defining tension is the latency budget against the data size: you are ranking the top completions out of billions of historical queries, in under 100 ms, on every keystroke. That is only possible if the ranking is already done — precomputed — before the request arrives.
Estimation
Take 5 billion searches/day. Each search is ~6 characters typed, and each character (after a tiny debounce) is a request, so request volume is several-x the search volume: on the order of 10^10+ autocomplete requests/day, roughly hundreds of thousands of requests/second, peaking higher. That read volume alone says: precompute and cache aggressively; nothing per-request can touch the raw logs.
Data: the distinct query vocabulary is large but the trie of prefixes worth suggesting is bounded — you only store the popular queries (the long tail of one-off queries is never suggested), so the trie holds millions of nodes, not billions. With top-k completions cached at each node, the whole serving structure fits in memory (single-digit to tens of GB), which is what makes tens-of-milliseconds serving possible. The napkin’s verdict: serving = in-memory precomputed top-k; ranking = a separate offline batch job over the logs.
High-level design
Two decoupled paths: an offline pipeline that builds the ranked trie, and an online path that serves from it.
- Offline pipeline: ingest search logs, aggregate query frequencies over a window, rank, and build a trie where each prefix node carries its top-k completions. Publish the new trie as an immutable snapshot.
- Served trie: the published snapshot, held in memory and replicated across serving nodes for read throughput.
- Typeahead service: on a request, walk the trie to the prefix node and return its cached top-k. No ranking, no log access — just a lookup.
- Edge cache/CDN: popular prefixes (“a”, “th”, “wea”) are cached at the edge so the most common requests are served without touching the service at all.
Deep dive
The trie and top-k per prefix
A trie (prefix tree) stores strings by their characters along a path from the root: the prefix “te” is the node reached by following the edge t then e, and all completions starting with “te” live in the subtree below it. The naive use of a trie is “walk to the prefix node, then traverse the whole subtree to find the best completions” — but that subtree can be enormous, and traversing it per keystroke blows the latency budget. The senior move is to precompute and store the top-k completions at every node: the “te” node directly holds ["tesla", "tennis", "temperature", ...] already ranked. Now serving is O(length of prefix) to walk down plus O(1) to read the cached list — no subtree traversal at all.
This precomputation is the entire trick. It trades build-time work and some memory (k strings per node) for constant-time serving, which is exactly the right trade when reads outnumber writes by orders of magnitude and the latency budget is tiny. The k completions per node are typically stored as a small ranked list (or a Redis sorted set per prefix), so a lookup is a single fast read.
▸Why this works
Why store top-k at every node instead of just walking the subtree on demand, or storing the full ranked list once at the root? Because of the asymmetry between reads and the budget. A subtree under a short prefix like “a” can contain millions of queries; traversing and ranking them in under tens of milliseconds, hundreds of thousands of times per second, is impossible. Storing top-k at the node makes the read O(1) regardless of how huge the subtree is — the expensive ranking already happened offline. The memory cost is bounded: k is small (5–10), and you only keep nodes for prefixes of popular queries, so it is k strings times millions of nodes, not billions. This is the same precompute-on-write-to-make-reads-cheap pattern as the news feed’s fan-out-on-write — pay once at build time, serve cheaply on the flood of reads. The trie just makes the “which precomputed answer” lookup itself O(prefix length).
The data collection and aggregation pipeline
Suggestions are only as good as the ranking, and the ranking comes from an offline aggregation pipeline, fully separate from serving. It reads the raw search logs, counts how often each query was issued over a rolling window (e.g. the last day/week, often time-decayed so recent searches weigh more), filters out rare/one-off queries and banned terms, and emits a ranked list of query, score. The trie builder then inserts those queries and, for each node, records the top-k of its subtree.
Critically, this runs on a schedule (continuously or every few minutes/hours), not on the request path. The output is published as a new immutable snapshot that serving nodes load atomically — you never mutate the live trie in place under read traffic (that risks inconsistency and locking). Because building over billions of rows is heavy, it is a batch/streaming job (MapReduce-style aggregation or a stream processor with windowed counts), and its cadence sets the freshness: a tighter cadence surfaces trends faster at higher compute cost. This is why autocomplete can be eventually consistent — the snapshot is minutes-stale by design, and that is fine.
▸Common mistake
The defining mistake is the hook’s: computing suggestions live per keystroke by querying the logs or the database on each request. It seems natural (“just search for matching queries”), but it fails on two axes at once. First, latency: aggregating or scanning to rank, per request, cannot fit a tens-of-milliseconds server budget over a large dataset. Second, load: every keystroke is a request, so a single user typing one word fires a half-dozen heavy queries, and at scale that is a keystroke storm that melts the search cluster. The fix is the architectural split: ranking is offline and periodic, serving is an O(1) read of a precomputed structure. A related, subtler mistake is mutating the served trie in place as new data arrives — instead, build a fresh immutable snapshot offline and swap it in atomically, so reads never contend with writes and a half-built index is never served. If you find yourself touching the logs on the read path, you have already lost the latency budget.
Latency budget and edge caching
The ~100 ms end-to-end budget is the spec, and it is spent deliberately. The client debounces keystrokes (waits a few tens of ms for typing to pause) so it does not fire a request per character at machine speed, and it can prefetch/cache locally. The network round trip eats a big chunk, leaving the server only tens of ms — which the precomputed trie lookup easily meets. To shrink the network and server cost further, popular prefixes are served from an edge cache/CDN: the suggestions for “a”, “th”, “new” are identical for most users and change slowly, so caching them at the edge (with a short TTL matching the snapshot cadence) serves the highest-volume requests close to the user without a round trip to the origin, and shields the service from the bulk of read traffic. Personalized suggestions (mixing a user’s own history) are the exception that bypasses the shared edge cache, layered on top of the popular base — and kept cheap because per-user history is small.
The budget logic is the through-line: every design choice (precompute, cache top-k at nodes, immutable snapshots, edge caching, debounce) exists to keep the read path far under 100 ms while absorbing a flood of requests, by ensuring no request ever does real ranking work.
Your autocomplete queries the search logs on each keystroke to rank matching queries. It is 600 ms slow and the search cluster is overloaded. What is the architectural fix?
In your trie, each lookup walks to the prefix node and then traverses the entire subtree to rank completions on the fly. Short prefixes like 'a' time out. What is the fix?
To serve suggestions within the ~100 ms budget, the top-k completions are stored at every node of the trie ahead of time by an offline pipeline, so a request is just a walk to the prefix plus a constant-time read — the ranking is _______, never computed live on the read path per keystroke.
Bottlenecks & tradeoffs
The binding constraint is the latency budget under enormous read volume, and every choice serves it. Key tradeoffs:
- Precompute vs compute-live. Precomputing top-k per node trades build-time compute and memory for O(1) reads — mandatory at this read:write ratio and budget. Computing live (the hook) is simpler to build but cannot meet the budget or the load.
- Freshness vs cost. A tighter snapshot cadence surfaces trends faster but costs more compute; autocomplete tolerates minutes of staleness (eventual consistency), so you pick a cadence, not real-time.
- Memory vs answer quality. Storing top-k at every node and keeping the trie in memory costs RAM; you bound it by only indexing popular queries (dropping the never-suggested long tail) and keeping k small.
- Shared edge cache vs personalization. Popular-prefix suggestions are identical across users and cache beautifully at the edge; personalization bypasses that shared cache, so you layer a small personalized set on top of the cached popular base rather than personalizing everything.
- Immutable snapshot vs in-place update. Publishing an immutable snapshot avoids read/write contention and never serves a half-built index, at the cost of full rebuilds; this is why the live trie is swapped, not mutated.
The deepest principle is the same as the feed: do the expensive work once, offline, on the write/build side, so the read path is a trivial lookup. Autocomplete is a read-optimized system whose entire architecture is organized around never doing ranking work while a user is waiting.
- 01Why can autocomplete never compute suggestions live per keystroke, and what is the architectural split?
- 02How does a trie with precomputed top-k per node serve suggestions in constant time?
- 03What does the offline aggregation pipeline do, and why publish an immutable snapshot?
- 04How is the ~100 ms budget spent, and what does edge caching add?
Search autocomplete is a read-optimized system defined by a brutal latency budget (~100 ms end-to-end, tens of ms for the server) under enormous read volume (every keystroke is a request). That makes the hook’s approach — computing suggestions live per keystroke by scanning the logs — fatal on both latency and load. The architecture splits the two concerns: an offline aggregation pipeline reads the search logs, counts and ranks queries over a rolling (often time-decayed) window, filters rare and banned terms, and a trie builder stores the top-k completions precomputed at every prefix node, published as an immutable snapshot that serving nodes swap in atomically. Serving is then trivial: walk the trie to the typed prefix (O(prefix length)) and return its cached top-k (O(1)) — no subtree traversal, no log access. An edge cache/CDN fronts the highest-volume popular prefixes so most requests never reach the service, and the client debounces keystrokes; personalization layers a small per-user set over the cached popular base. Freshness is eventually consistent by design — the snapshot is minutes-stale, which is fine. The unifying principle, shared with the news feed, is do the expensive ranking once, offline, on the build side, so the read path is a constant-time lookup — never make a user wait while you rank billions of rows. Now when you see an autocomplete feature that gets slow under load or blows its latency budget, you’ll know the first thing to check: is ranking happening on the request path, or is the system serving precomputed top-k from a trie?
Practice
Start at the top. Tasks go easiest → hardest: recall a fact, apply it to a case, then a senior-level stretch. Open one, attempt it, then reveal.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.