Design Search Autocomplete: A 100 ms Budget, Every Keystroke
A system design walkthrough for typeahead suggestions at search-engine scale: the keystroke multiplier, why a trie isn't the serving format, precomputed top-k per prefix, an offline pipeline plus a trending fast lane, client debounce and caching, sharding, ranking by locale and freshness, and the filters that keep predictions safe.
Type weather in pune into a search box. That's 15 characters. A naive client sends a suggestion request on every keystroke: 15 requests for one search. A careful client that waits for a short pause in typing and drops stale requests might send five or six. Either way, the suggestion service sees several times the traffic of the search service it sits in front of, and each request has to come back in well under the time it takes to type the next letter.
That ratio, call it the keystroke multiplier, is the number that shapes this whole design. With illustrative numbers: a billion searches a day at a multiplier of six is six billion suggestion requests, about 70,000 a second on average and several times that at peak. Each one needs to render suggestions within about 100 ms of the keystroke to feel instant, and the network takes a good part of that.
The Requirements
Typeahead for a large consumer search box. Working requirements (illustrative):
- Top 10 suggestions for the current prefix, in the user's language and region.
- End-to-end under 100 ms at p99 from keystroke to rendered list, which leaves the server under 10 ms.
- Fresh enough: a breaking news query should start appearing within about 15 minutes.
- Safe: no suggestions that violate policy, and nothing that reveals what an individual searched.
- Read-heavy, write-never at request time. Nobody's keystroke changes the suggestions directly; logs do, later.
That last point is the design's big simplification. Suggestions are derived data. You can compute them however slowly you like, as long as you can serve them fast.
Why the Obvious Designs Don't Serve
The first idea is a database query: SELECT query FROM searches WHERE query LIKE 'weat%' ORDER BY count DESC LIMIT 10. Even with an index on the prefix, this scans every query starting with w for a one-letter prefix and sorts them. Short prefixes, which are the most common requests, are the slowest. It won't meet 10 ms at 70,000 requests a second.
The second idea, and the textbook one, is a trie: one node per character, walk down the prefix, collect the most popular completions below. Storing the top-k completions at each node makes lookup fast. It's a good build-time structure, but as a serving format it has problems:
- Compact for shared prefixes
- Natural to build from logs
- One big pointer-heavy structure per server; hard to shard by key
- Updating counts means locking or rebuilding paths
- Every replica needs the whole thing
- Walk the prefix, read the node's top-k
- Shards by hashing the prefix
- Fits any key-value store or a memory-mapped file
- Rebuilt offline and swapped atomically
- Stores every prefix explicitly (more bytes)
- Freshness depends on rebuild frequency
- Precompute top-k for every prefix up to a length limit
- Serve with one key lookup
Verdict: Use the trie, or a sort, to build the table offline. Serve the table.
The table sounds wasteful until you size it. Only prefixes that real users typed, and that have enough distinct users behind them, get an entry. Cap prefixes at around 20 characters (beyond that, suggestions rarely help) and store each suggestion as an ID into a dictionary of query strings rather than repeating the text. For a big search engine that's still large, but it's hundreds of gigabytes, not petabytes, and it shards.
The Build Pipeline
Suggestions come from what people actually search. Google says as much: autocomplete predictions reflect real searches that have been done on Google, weighed by factors including trending interest, language, location and freshness. The pipeline that produces the table runs every hour or so.
- Search logs record each query with its language, region and time. Normalise first: lower-case, collapse whitespace, strip tracking junk.
- Count queries per locale with time decay, so last week matters more than last year. A raw all-time count would suggest what was popular in 2019.
- Drop anything that violates policy, and anything typed by fewer than a threshold of distinct users. A query searched by one person must never become a suggestion; that's how private data leaks.
- Expand every surviving query into its prefixes and keep the top 10 scored completions for each prefix and locale.
- Write the table as versioned shard files and roll them out in stages, like any other config. A bad build that suggests garbage should hit a canary, not every user.
5 steps. Press Play to walk through them, or click any part of the diagram.
That last step connects to something I'd underline. A suggestion table is a big generated file pushed to a large fleet, exactly the shape of change that took down Cloudflare in November 2025. Validate the build (row counts, size and diff against the last version, a sample of top prefixes) and roll it out in waves. The config rollout design applies unchanged.
The privacy threshold
The filter step deserves more than a bullet. Query logs contain names, addresses, order numbers and things people would never say out loud. Three rules:
- 01Distinct-user threshold. Only suggest a query if at least N different users searched it in the window. N is a policy decision; the point is that it's more than one.
- 02Pattern filters. Drop strings that look like emails, phone numbers, card numbers or IDs, regardless of count.
- 03Policy filters. Google's policies, for instance, bar predictions that are sexually explicit (outside medical or educational topics), hateful, violent or dangerous, among others. Your list will differ; the pipeline needs one, and a fast path to remove a suggestion that slips through.
The Trending Fast Lane
An hourly rebuild over days of decayed counts is stable, and it's slow to react. When news breaks, people search for it within minutes. A second, streaming lane handles that:
- A stream processor reads the same query logs live and counts queries per locale over short windows (the last 5 and 15 minutes).
- It compares each window to the query's normal rate and keeps queries whose count jumped well above baseline, after the same privacy and policy filters.
- It writes a small trending table, prefix to a few trending candidates, refreshed every minute or so.
At request time the serving layer merges the two. The trending table is tiny compared with the main one, so it can live in memory on every server. The ad click aggregator design covers this kind of windowed streaming count in depth.
Serving a Keystroke
- The client waits for a short pause in typing before sending, cancels any in-flight request for an older prefix, and first checks its own cache: suggestions for 'weat' often answer 'weath' too.
- One- and two-character prefixes are few and extremely hot. They're answered from an edge cache for a short TTL, so the busiest requests never reach the origin.
- Everything else is routed by hashing locale and prefix to a shard, and answered with a single key lookup. No scans, no sorting.
- The same server checks the in-memory trending table for the prefix and pulls in any fresh candidates.
- It merges, re-ranks lightly (locale, freshness, any on-device history the client sent), removes anything on the live block list, and returns ten suggestions.
5 steps. Press Play to walk through them, or click any part of the diagram.
A few details from that picture:
Most of the latency budget is on the client and the network. The server's lookup is microseconds. The keystroke-to-render time is dominated by debounce delay, round-trip time and rendering, which is why the edge cache and the client cache matter more than how fast your key-value store is.
Hash sharding works here. Range sharding by prefix creates hot spots (everything starting with s), but every request is an exact-key lookup, so hashing (locale, prefix) spreads load evenly. Replicate each shard several times; it's read-only between builds.
Personal history doesn't need the server. A user's own recent searches can be stored on the device and merged in the client, which is faster and keeps personal data off the suggestion fleet.
Typos are a separate system. Suggestions keyed on exact prefixes miss wether. A spelling-correction service, or a small table of common misspellings mapped to their corrections, can rewrite the prefix before lookup. Keep it out of the main table so it doesn't bloat every prefix.
Ranking, Briefly
Ranking in the table is simple on purpose, because it's precomputed:
What you leave out matters as much. Google notes that its predictions differ by location and language, down to spelling "centre" correctly for Canadians. One global ranking would suggest American spellings to everyone and local news to no one. Build the table per locale, and fall back to a broader locale when a prefix has too few local results.
Heavier personalisation (results shaped by a user's interests) belongs downstream, in search ranking, not in a precomputed table. If you need it in suggestions, do a light re-rank of the ten candidates at serve time, as in the feed ranking design.
Signals Worth Graphing
- Keystroke-to-render latency at p50 and p99, measured on real clients. Server latency alone will look great and tell you nothing.
- Requests per search (the keystroke multiplier). If it creeps up, a client release broke debouncing.
- Suggestion acceptance rate: how often users pick a suggestion, and at what position. A drop after a table build is a bad build.
- Edge cache hit rate for short prefixes.
- Freshness: the delay between a query starting to trend and its first appearance in suggestions.
Quick Check
Q1Why serve from a precomputed prefix → top-k table rather than an in-memory trie?
Q2Which requests are best served from an edge cache?
Q3Why apply a distinct-user threshold before a query can become a suggestion?
Sizing
- Requests = searches × keystroke multiplier (several per search).
- Server budget is a few ms; the rest is client, network, render.
Build
- Logs → decayed counts → filters → top-k per prefix and locale.
- Distinct-user threshold, PII patterns and policy filters before ranking.
- Validate and roll out the table in stages like config.
Serve
- One key lookup, sharded by hash(locale, prefix), replicated.
- Edge cache for short prefixes; client debounce, cancel and cache.
- Merge an in-memory trending table; on-device history on the client.
Measure
- Keystroke-to-render p99 on real clients.
- Requests per search, acceptance rate, freshness delay.
Sources
Related posts
More in System Design →Design a Price Monitoring System: Spending a Freshness Budget, Not Crawling Everything
Dec 16, 2026
Design a Payment System: Idempotency Keys, a Double-Entry Ledger and the Timeout You Can't Trust
Dec 8, 2026
Design a Distributed Job Scheduler: Leases, Fencing Tokens and the Missed Tick
Nov 30, 2026
Design a Config Rollout System That Can't Take Down Your Whole Fleet
Nov 21, 2026
