Back to System design
Design Typeahead / Search Autocomplete
mediumTypeahead is the list of suggestions that appears while you type in a search box. It has to appear before you finish typing, which means answering in well under a tenth of a second.
Scale<100 ms p99; 1M QPS at search scale
StorageTrie ~10-100 GB sharded; per-shard fits in RAM
Key Concepts
1
That single requirement decides everything else.
2
Work out the time budget first. From a phone in Bengaluru to a server in the same region, the network
round trip alone is 30 to 60 milliseconds. Setting up the secure connection and drawing the dropdown take
another 10 to 20.
Work out the time budget first.
3
If the whole thing must feel instant at around 100 milliseconds, your server has 20 to 40 milliseconds
to do its work.
20 to 40 milliseconds
4
That is not enough time to search anything. So you cannot rank suggestions when the request arrives — the
ranking has to be done already, and the request must be a simple lookup.
5
Pre-compute the answers. Take the log of what people actually searched for, count how often each
phrase appears, and for every prefix store the top few completions.
Pre-compute the answers.
6
"fa" -> facebook, fastrack, fan
"fac" -> facebook, facewash, factory
"face" -> facebook, facewash, facetime
7
Now answering is one lookup: take what the user typed, find that entry, return the stored list.
8
How big is that? Say 500 million different searches a month, and you keep only those searched at least
five times — that leaves about 50 million. Storing five suggestions per prefix at roughly 30 bytes each
gives about 150 bytes per entry, and around 200 million entries once prefixes are shared.
How big is that?
9
200,000,000 x 150 bytes = about 30 GB
10
Too much for one machine, fine across eight to sixteen. Now you have justified splitting it up with a
number rather than a hunch.
11
Split by the first two letters, then fix the hot spots. Lookups stay on one machine. But traffic is not
even — far more searches start with "th" than "qz" — so splitting by alphabet leaves some machines idle and
others overloaded.
Split by the first two letters, then fix the hot spots.
12
Split by measured traffic share instead. If you do not, the interviewer will ask what happens to your
slowest responses when one machine is hot.
13
Fresh results need a second path. If something happens in the news, people search for phrases your
nightly job has never seen. So run a second job that looks at the last few minutes of searches and pushes
updates in continuously.
Fresh results need a second path.
14
The hard part is stopping a brief spike from pushing out the reliable suggestions. Add trending terms as a
bonus that fades, rather than replacing what the batch job computed.
15
Typos, cheaply. Comparing what someone typed against every possible phrase is far too slow for this
budget. Instead, mine the corrections from your own logs: people who typed
youtub overwhelmingly went on
to accept youtube. That gives you a lookup table. One extra lookup, no searching.Typos, cheaply.youtubyoutube
16
Personalise at the end, not the start. Fetching someone's history during the request would blow the
budget. Return the globally best suggestions, then re-order that short list using what you already know
about the user, close to them.
Personalise at the end, not the start.
17
What the interviewer is probing.
What the interviewer is probing.
18
1. "Suggestions as the user types." Probing: whether you find the budget. Stalls: "Query the
database with a LIKE." Moves up: splitting 100 milliseconds across network, connection and drawing, and
concluding that ranking must already be done.
1. "Suggestions as the user types."
19
2. "How big is the index?" Probing: whether you can produce a number. Stalls: "It depends." *Moves
up:* state the assumptions and compute: searches, pruning, bytes per entry, total, then machines.
2. "How big is the index?"
20
3. "Something appears in the news." Probing: freshness. Stalls: "Rebuild more often." Moves up:
a second streaming path beside the nightly one, and protecting the stable suggestions from a spike.
3. "Something appears in the news."
21
4. "One machine is much busier than the others." Probing: how you split the data. Stalls: "Add
replicas." That helps reads, not a skewed split. Moves up: split by measured traffic, not by alphabet.
4. "One machine is much busier than the others."
22
5. "People make typos." Probing: whether you reach for the expensive algorithm. Stalls: "Compute
edit distance." Moves up: a correction table mined from the logs, which is one lookup.
5. "People make typos."
High-level design
Offline batch: query logs → Spark aggregator → top-K per prefix → trie builder → trie store.
Streaming: query logs → Flink → delta updates → push to trie (every few minutes).
Serving: user prefix → trie lookup → top-K candidates → edge rerank for personalization → response.
Misspelling: separate lookup; replace prefix with corrected form before trie walk.
Components
- Query log aggregator (Kafka + Spark).
- Trie builder (batch + incremental).
- Serving fleet (in-memory trie shards, sharded by first 1-2 chars).
- Edge cache (CDN) for short prefixes (huge hit rate).
- Personalization service (per-user history, session context).
- Streaming pipeline for trending detection.
- Misspelling correction service.
- Feedback logging — which suggestion the user picked, for ranking refinement.
Latency budget (worked)
Worked latency budget -- 100 ms, mobile user, same-region server.
Network round trip (4G, in-region) 30-60 ms TLS resumption + request parsing 5-10 ms Client render of the dropdown 5-10 ms ------------------------------------------------ Remaining for your server 20-40 ms
Inside that remainder:
Shard lookup (in-memory trie walk) < 1 ms Top-K read from the node < 1 ms Edge re-rank over 10 candidates 1-2 ms Everything else is headroom for p99 spikes.
Two consequences worth stating in the room:
- A cross-region hop (150 ms+) blows the budget on its own, so the serving
tier has to sit near the user. This is the argument for edge placement,
and it is stronger than "edge is faster".
- Anything that touches disk or a second service inside the request is out.
That includes fetching a user profile, which is why personalisation
re-ranks what the shard already returned.
Index sizing (worked)
Index sizing -- redo this with your own assumptions.
Distinct queries per month 500,000,000 Kept after pruning (seen >= 5 times) 50,000,000 Prefix nodes after sharing (len 1-20) ~200,000,000 Top-K stored per node 5 Bytes per completion (string + score) 30 Payload per node 5 x 30 = 150 bytes ------------------------------------------------------------ Index size 200M x 150 B = ~30 GB
Per shard, at 16 shards ~2 GB
With 3 replicas 48 machines' worth of RAM,
though a 2 GB shard shares
a host comfortably.Change one assumption and the shape changes:
- Pruning at >= 50 occurrences instead of 5 cuts the index by roughly an
order of magnitude, at the cost of long-tail coverage.
- Storing top 10 instead of top 5 doubles payload for a ranking gain most
users never see, since the dropdown shows 5-8 rows.
Failure modes in production
Failure modes that come up once this is running.
Hot shard on a common prefix
Symptom: p99 climbs on a subset of traffic while p50 looks fine.
Cause: shard boundaries drawn on the alphabet, not on traffic.
Fix: rebalance by measured share; keep the map versioned so serving nodes
can reload without a deploy. Trending term swamps the index
Symptom: durable completions disappear during a spike, return later.
Cause: streaming deltas overwrite rather than add.
Fix: additive boost with decay, and a floor on the batch-computed entries. Stale index after a failed batch
Symptom: suggestions quietly age; nobody notices for days.
Cause: no freshness signal on the serving tier.
Fix: serve the build timestamp with the response and alert on its age --
the cheapest observability in the whole design. Empty results for a valid prefix
Symptom: a real query returns nothing as the user passes a certain length.
Cause: pruning removed the tail, and there is no fallback.
Fix: fall back to the longest prefix that does have completions, rather
than returning an empty list.