Type "sys" into a search box and ten suggestions appear before your finger reaches the next key. "Design typeahead" tests whether you notice that this is two systems in one. The online part must answer a prefix in a few milliseconds, tens of thousands of times a second, so it can't compute anything. The offline part decides what the right ten suggestions are, from billions of past searches, and hands the online part a ready-made answer for every prefix.
Design the autocomplete for a large search product. As the user types, show up to ten suggested queries ranked by popularity, with trending searches surfacing quickly and offensive suggestions never shown.
In scope
- Query suggestions for prefixes (not full search results)
- Ranking by popularity and recency
- Freshness, filtering, scale
Typeahead returns the ten best completions for a prefix within a keystroke, about 70,000 requests a second at an assumed 100M daily users, leaving the server 10 to 20 ms. About 100M prefixes with their top 10 fit in roughly 10 GB, so every suggest server holds the whole dataset in memory, behind a debounced client and a CDN that caches the ~18,000 short prefixes. Offline, search logs flow through Kafka into daily counts with time decay and last-hour trending counts; a builder ranks, filters the blocklist and publishes S3 snapshots that servers swap in atomically. The deep dives store a top-10 list at every trie node, shard by measured prefix ranges when needed, count distinct users and personalise on the client; failures cover bad snapshots, server loss, CDN staleness and typos.
Phase 1: Requirements (3 minutes)#
"Suggestions for the query being typed, not documents? Ranked by popularity? Personalised? Do we need typo tolerance? How fresh?"
"Query suggestions ranked by popularity. Light personalisation is a bonus. Prefix matching only to start. Trending queries should appear within an hour."
Functional requirements#
suggest(prefix, locale)returns up to 10 completions, best first- Ranking by how often a query is searched, favouring recent searches
- Trending queries appear within about an hour
- A blocklist removes offensive, dangerous or legally problematic suggestions
- Optional: the user's own recent searches mixed in
Non-functional requirements#
- Very low latency: under 100 ms from keystroke to render, so the server gets roughly 10–20 ms
- High throughput: every keystroke is a request
- Highly available: if suggestions fail, the search box still works, but the product feels broken
- Eventually consistent: suggestions can be minutes to hours behind real searches
Phase 2: Estimation (3 minutes)#
- Requests: assume 100M DAU × 10 searches a day × ~6 suggestion requests per search (after the client skips some keystrokes) = 6B a day ≈ ~70,000/s, ~140,000/s at peak
- Data: assume the logs boil down to 10M distinct popular queries averaging 20 characters. Their prefixes, deduplicated and capped at 20 characters, come to roughly 100M prefixes
- Per prefix: the prefix (~20 B) plus 10 query IDs (40 B) plus overhead, assume ~100 B: 100M × 100 B ≈ ~10 GB, which fits in memory on one server
- Servers: if one in-memory server answers ~20,000 requests/s, peak needs at least 7; run about 10 per region for headroom
- Short prefixes dominate: there are only 26 + 26² + 26³ ≈ 18,000 prefixes of one to three letters (Latin alphabet), and they get a large share of requests, so they cache extremely well
"10 GB fits in RAM, so I'd replicate the whole dataset to every suggestion server rather than shard it. That keeps every request to one in-memory lookup."
Phase 3: API (2 minutes)#
GET /v1/suggest?q=sys&locale=en-IN&limit=10
→ 200
Cache-Control: public, max-age=300
{ "q": "sys", "suggestions": ["system design", "system design interview", "sysadmin", ...] }On the client:
- Debounce: send a request when typing pauses for about 100 ms, not on every key.
- Cancel stale requests: if "sys" is answered after "syst", drop the "sys" answer.
- Cache locally: answers for "s", "sy", "sys" are reused when the user deletes back.
Phase 4: High-level design (4 minutes)#
%% title: Typeahead: online lookups, offline building
flowchart TD
U@{ icon: "sd:browser", label: "Search box<br/>debounce, local cache" } --> CDN@{ icon: "sd:cdn", label: "CDN edge<br/>short prefixes, 5 min TTL" }
CDN --> LB@{ icon: "sd:load-balancer", label: "Load balancer" }
LB --> SS["Suggest servers<br/>in-memory prefix → top 10"]:::hot
U -.->|"searches run"| LOG@{ icon: "sd:log", label: "Search logs" }
LOG --> K@{ icon: "tech:kafka", label: "Kafka · queries" }
K --> BATCH@{ icon: "tech:spark", label: "Spark · daily counts<br/>with time decay" }
K --> STREAM@{ icon: "tech:flink", label: "Flink · last-hour counts<br/>(trending)" }
BATCH --> BUILD["Builder<br/>rank, filter blocklist,<br/>top 10 per prefix"]:::core
STREAM --> BUILD
BUILD --> S3@{ icon: "tech:s3", label: "S3 · versioned snapshots" }
S3 -.->|"load, then swap atomically"| SS
class U client
class CDN,LB edge
class LOG,S3 store
class K queue
class BATCH,STREAM service- Online path: the search box asks for the prefix; short prefixes are usually answered by the CDN; everything else reaches a suggest server, which does a single in-memory lookup and returns.
- Offline path: every search is logged to Kafka. A batch job computes long-term popularity with time decay; a stream job counts the last hour for trending terms. The builder merges both, removes blocklisted terms, and writes a new snapshot of "prefix → top 10".
- Snapshots: suggest servers load each new snapshot in the background and swap a pointer when it's fully loaded, so a request never sees half of an old and half of a new dataset.
Phase 5: Deep dives (5 minutes)#
Deep dive 1: The data structure#
"You said trie. Walk me through a lookup for 'sys'."
"A plain trie finds the node for 's' → 'y' → 's' in three steps. Finding the top 10 under it would mean walking the whole subtree, which for a short prefix is millions of nodes. So I precompute: every node stores its own top-10 list."
- Build offline: insert each popular query with its score. For every node, keep the 10 highest-scoring queries in its subtree.
- Look up online: walk one node per character of the prefix and return that node's list. Cost grows with the prefix length (at most 20 here), not with the number of queries.
- Or flatten it: since the whole structure is rebuilt offline anyway, a hash map from prefix string to top-10 IDs gives the same answer with one lookup, and serialises into a snapshot easily.
- Store IDs, not strings, in the lists: a query string is stored once in a table; each list holds 10 small IDs. That is what keeps the estimate near 10 GB.
More languages and markets can grow the data past one machine. Then shard by prefix, but not by first letter: far more English queries start with "s" than with "x", so letter-based shards are badly skewed. Split prefix ranges by measured traffic (for example "sa–sh" might be its own shard), and keep a small routing table the load balancer consults.
Deep dive 2: Ranking and freshness#
"A celebrity's name starts trending at 9 AM. When does it show up for 'cel'?"
- Long-term popularity (batch, daily): count each query's searches with time decay, for example a half-life of 7 days, so last week counts more than last year. Count distinct users, not raw searches, so one bot repeating a query can't promote it.
- Trending (stream, hourly or faster): count the last hour per query and compare with its usual rate. A query far above its normal level gets a boost.
- Merge and filter: score = long-term score + trending boost. Drop anything on the blocklist, and anything searched by fewer than a minimum number of distinct users (rare queries can contain private information).
- Publish: the builder writes a small "trending delta" snapshot every hour and a full one daily. Servers apply both. The 9 AM term appears in suggestions within the hour.
Keep the global suggestions global (they cache well) and mix in the user's own recent searches on the client, which already has them. Server-side personalisation per user would make every response uncacheable.
Structure and freshness
Q1/2 Why does each trie node store its own top-10 list?
Answer & explanation
Answer: B
Finding the best 10 under "s" by walking the subtree would touch millions of nodes. Precomputing the list per node makes a lookup one step per character.
Q2/2 A bot searches the same made-up phrase 100,000 times. What keeps it out of suggestions?
Answer & explanation
Answer: C
One user repeating a query counts once. A minimum distinct-user threshold also keeps rare, possibly private queries from being suggested.
Phase 6: Trade-offs and failure modes (2 minutes)#
A bad snapshot
A builder bug could publish empty or offensive suggestions everywhere at once. Validate each snapshot before publishing (size, sample lookups, blocklist check), roll it out to a few servers first, and keep the previous version to roll back to.
A suggest server dies
Every server holds the full dataset, so the load balancer simply stops sending it traffic. A new server loads the latest snapshot from S3 before taking requests.
Freshness versus cost
Hourly trending deltas plus daily full builds are a middle ground. Real-time updates per search would need writes on the read path of every server; rarely worth it for suggestions.
CDN staleness
Short prefixes cached at the edge for 5 minutes can lag a trending term by those 5 minutes. Purge the affected prefixes when a trending delta lands, or accept the delay.
Typos
Prefix matching misses "sytem design". Fuzzy matching is far more expensive per request; a common compromise is adding known misspellings as extra keys pointing at the correct suggestions.
Phase 7: Go deeper in the course#
- Autocomplete inside a search engine (edge n-grams, completion): Week 7 · Day 4: Advanced Search Features
- Search architecture and the vocabulary: Week 7 · Day 1: Search Fundamentals
- Client, CDN and server caches together: Week 4 · Day 5: Multi-Tier Caching
- Collecting every search as an event: Week 8 · Day 1: Event Ingestion at Scale
- Daily batch counts plus hourly trending: Week 8 · Day 2: Streaming vs Batch
- Skewed prefixes and range splitting: Week 1 · Day 1: Partitioning Deep-Dive and Week 1 · Day 4: Hot Keys and Skew
- Rolling out a new snapshot safely: Week 10 · Day 3: Deployment Strategies
- Search at web scale: Side quest: Google Search
Final check#
Final check · Typeahead
Q1/3 100M users × 10 searches a day × 6 requests per search. About how many suggestion requests a second is that?
Answer & explanation
Answer: B
6B requests a day ÷ 86,400 s ≈ 69,000 a second on average, about 140,000 at peak.
Q2/3 The prefix data is about 10 GB. Why replicate it to every suggest server instead of sharding it?
Answer & explanation
Answer: A
Replicating a dataset that fits in RAM avoids routing and cross-shard requests. Shard by measured prefix ranges only when it stops fitting.
Q3/3 Why mix the user's own recent searches in on the client rather than on the server?
Answer & explanation
Answer: C
Per-user responses can't be shared from a cache. The client already knows its recent searches and can merge them locally.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.