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.

Rahul Bisht

Founder, CrawlPilot

·
Dec 11, 2026
·
Verified Nov 15, 2026
·System Design·
13 min read
·
Design Search Autocomplete: A 100 ms Budget, Every Keystroke
Key takeaway
Autocomplete is a read-only lookup with a brutal latency budget and a request multiplier built in: every search is several suggestion requests. So you precompute. An offline pipeline turns query logs into a table of top suggestions for every prefix, a streaming lane adds what's trending now, and serving is one key lookup plus a small merge. Most of the hard work is on the client (fewer requests) and in the pipeline (safe, fresh, local suggestions), not in the lookup.

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:

In-memory trie, top-k at each node
  • 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
Prefix table, prefix → 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.

Two ways to serve top-k suggestions for a prefix

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.

From query logs to a suggestion table
1234staged rollout5Query logsquery, locale, timeAggregatedecayed countsFilterpolicy + privacyBuild top-kper prefix, per localeTable shardsversioned filesServing fleetswap atomically
  1. Search logs record each query with its language, region and time. Normalise first: lower-case, collapse whitespace, strip tracking junk.
  2. 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.
  3. 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.
  4. Expand every surviving query into its prefixes and keep the top 10 scored completions for each prefix and locale.
  5. 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.

Query logs are aggregated with time decay, filtered for policy and privacy, expanded into prefixes with top-k per prefix, then sharded and swapped into serving.

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:

  1. 01
    Distinct-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.
  2. 02
    Pattern filters. Drop strings that look like emails, phone numbers, card numbers or IDs, regardless of count.
  3. 03
    Policy 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.

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

One keystroke, end to end
GET /suggest?q=weat1cache miss2one key lookup3trending candidates4merged top 105Search boxdebounce + local cacheEdge cacheshort prefixesSuggest APIhash(locale, prefix)Table shardprefix → top-kTrending tablein memory
  1. 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.
  2. 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.
  3. Everything else is routed by hashing locale and prefix to a shard, and answered with a single key lookup. No scans, no sorting.
  4. The same server checks the in-memory trending table for the prefix and pulls in any fresh candidates.
  5. 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.

The client debounces and checks its cache; a request goes to the nearest edge; short prefixes are answered from the edge cache; others hit a serving shard that merges main, trending and locale candidates.

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:

text
score(query | prefix, locale) = decayed_count(query, locale) × freshness_boost(query) # trending lane signal × locale_match(query, locale) # same language and region first

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

Check yourself

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?

Cheat sheet
Search autocomplete

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