Typeahead System Design: Why Google Autocomplete Is a Favorite Interview Question
You type "how to" into Google, and before your finger leaves the keyboard, ten suggestions appear. That feature is called typeahead (or autocomplete), and "Design Google Typeahead" is one of the most common system design interview questions. It looks simple, but it forces you to combine a classic data structure, an offline pipeline, sharding, and aggressive caching into one coherent design.
What Makes Typeahead So Hard? The 100ms Budget
Here is the constraint that shapes the entire design: every single keystroke is a request. If a user types "cricket score", that is thirteen requests, one per character.
An average user types a character every 200 to 300 milliseconds, and your suggestion must appear before the next keystroke lands, or it is useless. Subtract network travel time, and the server has a latency budget of under 100 milliseconds, often closer to 20 or 30 milliseconds of actual computation.
Compare that with a normal search: users will tolerate a full second for results, but not suggestions that lag behind their typing. If you are new to thinking in milliseconds, start with my guide on latency and how it is measured. And since each search generates 10 to 15 keystroke requests, typeahead receives far more traffic than search itself. Huge traffic plus a tiny budget. That is the problem.
The Chai Stall Analogy: Precompute, Don't Compute
Near my old office there was a chai stall. The owner knew his regulars: the moment he saw me park my bike, he started making my usual order. By the time I reached the counter, the chai was ready. He predicted the order and prepared it in advance.
That is the core insight of typeahead system design. With 30 milliseconds of budget, you cannot rank millions of matching phrases at request time. The winning move is the chai stall move: do the expensive work ahead of time, and at request time just hand over what is already prepared. The trie, the top-k lists, and the offline pipeline are all this one idea applied carefully.
How Does a Trie Power Prefix Matching?
The natural data structure for autocomplete is the trie (prefix tree). A trie stores strings character by character: the root is empty, each edge adds one character, and every path from the root spells a prefix. Why not a database with a LIKE 'cri%' query? Because scanning millions of rows per keystroke blows the budget instantly. A trie reaches all phrases sharing a prefix by walking one short path.
Step-by-Step: Serving the Prefix "cri"
- The user has typed "cri". The request arrives at the suggestion service.
- Start at the root of the trie and follow the edge for c, then r, then i: exactly three hops, one per character.
- You are now at the node for "cri". Every phrase in the subtree below it ("cricket", "cricket score", "crime news") is a valid completion.
- Return the best few phrases from that subtree to the user.
Reaching the node costs O(L), where L is the length of the prefix, and L is tiny. The trap is step 4. If the subtree under "cri" holds 500,000 phrases, you cannot rank them per request. This is where precomputation enters.
Precomputing Top-K Suggestions vs Computing on the Fly
Option 1: Compute on the Fly
Walk to the prefix node, traverse the whole subtree, look up each phrase's popularity, sort, and return the top 10. Correct and always fresh, but for short prefixes like "a" or "th" the subtree is enormous. Traversal alone can take hundreds of milliseconds. The budget is gone.
Option 2: Precompute Top-K at Every Node
Instead, store the answer directly on the node. Each trie node keeps its own top-k list (usually k = 5 or 10): the k most popular full phrases starting with that prefix, already ranked. Now a request is: walk L characters, read a stored list, return it. A few memory lookups. Single-digit milliseconds.
State the trade-offs explicitly in an interview:
- Storage cost: every node duplicates up to k phrases (or pointers). You pay memory to buy speed, and for typeahead that trade is obviously worth it.
- Update cost: when a phrase gains popularity, the top-k lists of all its prefix nodes need updating. So you never update the trie on the hot path, which leads to the offline pipeline.
Where Do Suggestions Come From? The Offline Aggregation Pipeline
The trie has to be built from something. The source is the query log: a record of what people actually search for.
Sampling: You Do Not Need Every Log Entry
At Google scale, processing every query is expensive and unnecessary. If "cricket score" is searched millions of times a day, recording one out of every thousand occurrences still measures its popularity accurately, because popular queries stay popular in a sample. Sampling cuts processing cost by orders of magnitude at almost no accuracy loss.
The Pipeline, End to End
- Collect: search services write sampled queries to a log store.
- Aggregate: a periodic batch job (MapReduce or Spark style) groups identical queries and counts frequencies over a window, say the last 7 days.
- Rank and filter: compute a popularity score per phrase; drop spam, offensive phrases, and one-off junk.
- Build: construct a fresh trie with top-k lists baked into every node.
- Ship: push the new trie to the serving fleet and atomically swap it in.
Notice the clean separation: the serving path is read-only and blazing fast, while all writes happen offline where latency does not matter. Suggestions are only as fresh as the last pipeline run, and for typeahead that staleness is acceptable; trending topics get a separate fast path, covered below.
How Do You Shard the Prefix Space?
A trie for billions of phrases will not fit on one machine, and one machine cannot serve the traffic anyway. So you shard by prefix: different servers own different regions of the prefix space.
The naive scheme, one shard per starting letter, fails because the alphabet is not uniform. Vastly more queries start with "s" or "t" than with "x" or "z". The "s" server melts while the "x" server sleeps.
The better scheme is to shard by load, not by letter. Analyze historical traffic and cut the prefix space into ranges with roughly equal query volume: a hot range like "s" through "sm" might be a shard by itself, while "u" through "z" together form another. A small lookup service maps an incoming prefix to the shard that owns it. Because the data is read-only between pipeline runs, each shard is also replicated: replicas multiply a hot shard's throughput and give you fault tolerance for free.
Caching at Every Layer: Browser, CDN, Server
Typeahead traffic has a beautiful property: it is extremely repetitive. Millions of people type the same popular prefixes every hour, and the answers barely change between pipeline runs. That makes it a dream workload for caching.
- Browser cache: if the user types "cric", deletes a character, and retypes it, the browser reuses the earlier response. A short TTL on suggestion responses kills a chunk of traffic before it leaves the device.
- CDN / edge cache: the few thousand hottest prefixes cover a huge share of all requests, so a small cache at edge servers close to users absorbs enormous load.
- Server-side cache: an in-memory cache (Redis style) in front of the trie shards holds recently requested prefix results, shielding the shards from repeated work.
Each layer cuts both latency and backend load. If this layering is new to you, my post on caching strategies walks through the patterns in detail. One extra client-side trick: debouncing, where the client waits 30 to 50 milliseconds after a keystroke before firing, so prefixes a fast typist blows past never generate traffic at all.
Want to master this with video lessons and real case studies? This topic is covered in depth in my Udemy course System Design Fundamentals for Interviews — 5.5 hours, rated 4.8★, built from real interview questions.
Filtering the Results: Personalization and Trending
A single global top-k list is a good baseline, but real systems layer two refinements on top.
Personalization
Two users typing "j" should not see identical suggestions: a cricket fan might see "jasprit bumrah" while a developer sees "java download". The serving layer fetches the global top-k from the trie, then re-ranks that small candidate set using the user's search history, language, and location. Re-ranking 10 to 20 candidates is cheap, and it is the same "generate candidates, then rank" pattern used in the Facebook News Feed design.
Trending Queries
The offline pipeline is hours behind reality, but when news breaks, people expect the suggestion within minutes. So a small real-time stream runs alongside the batch pipeline, watching for sudden spikes and keeping a short list of trending phrases with time-decayed scores, which the server merges into the trie's results at request time.
Safety Filtering
Finally, a filter removes offensive or harmful phrases. Suggesting a harmful query is far worse than suggesting nothing, so this runs both offline during the trie build and online on the merged results.
How to Talk About Typeahead in an Interview
Here is a 30-second answer you can memorize and adapt:
"Typeahead is latency-critical: every keystroke is a request, and the answer must arrive in under 100 milliseconds, so nothing expensive can happen at request time. I'd build a trie over popular queries, and precompute the top 10 suggestions at every node so a request is just walking the prefix and reading a stored list. The trie is built offline by a batch pipeline that samples query logs, aggregates frequencies, and ships a fresh trie periodically. I'd shard the trie by prefix ranges balanced on load, replicate shards for read throughput, and cache aggressively at the browser, CDN, and server. On top of that, a lightweight layer re-ranks results for personalization and merges in trending queries from a real-time stream."
Then let the interviewer pick a thread. Common follow-ups, with one-line answers:
- "Why not query a database per keystroke?" Latency: scan-and-rank per keystroke cannot meet a sub-100ms budget at this volume.
- "What if a shard gets hot?" Split its prefix range, add replicas, let the edge cache absorb the head of the distribution.
- "How do trending queries show up quickly?" A real-time spike detector on the query stream, merged with trie results at serve time.
Key Takeaways
- Every keystroke is a request, so typeahead needs a sub-100ms budget and gets more traffic than search itself.
- A trie with precomputed top-k lists per node turns each request into a short walk plus one read. Precompute, don't compute.
- An offline pipeline samples query logs, aggregates frequencies, and periodically rebuilds and ships the trie, keeping the serving path read-only.
- Shard the prefix space by load, not alphabetically, and replicate shards for throughput.
- Cache at browser, CDN, and server layers, then layer personalization, trending, and safety filtering on top of the global results.
Next Steps
Typeahead pulls together almost everything in this series: latency budgets, precomputation, batch pipelines, sharding, and caching. If any of those felt shaky, browse the full System Design Tutorial series, and make sure you are solid on consistent hashing, because balanced partitioning shows up in nearly every design question you will face next.