Design an Autocomplete System

Type n-e-t into a search box and four suggestions appear before your finger leaves the t key. That is autocomplete, and the reason it feels instant is that the hard work happened long before you started typing. The system never searches at query time — it looks up an answer it precomputed.

The design question is deceptively small: given a prefix, return the best few completions. What makes it a real system-design problem is scale and freshness. A large search engine serves this on every keystroke, for hundreds of millions of terms, in under 50 milliseconds, while breaking-news queries need to surface within minutes of trending. Every decision below trades one of those against another.

What autocomplete actually has to do#

Strip the feature down to its promises. Given a prefix string, the service returns an ordered list of the top K completions — typically K is 5 to 10 — ranked by how likely the user is to want each one. It fires on every meaningful keystroke, so it is overwhelmingly a read workload. Writes (new terms, updated popularity) arrive on a slower, separate path.

The non-functional requirements are where the design lives:

• Latency: p99 under ~50ms end to end, because the suggestions must appear faster than the next keystroke.
• Read-heavy: reads outnumber writes by many orders of magnitude, so the index can be optimized purely for lookup.
• Freshness: popularity shifts hourly; a term that trends at 9am should appear by 9:05am, not tomorrow.
• Relevance: "starts with the prefix" is table stakes; the ranking is the product.

The core data structure: a trie with cached answers#

The natural fit for prefix lookup is a trie (prefix tree). Each edge is a character, each path from the root spells a prefix, and every node marks whether a complete term ends there. Walking a prefix of length p costs O(p) — independent of how many terms exist. That is the whole appeal: lookup time depends on the query, not the corpus.

But a plain trie has a problem. Once you reach the node for net, you still have to walk the entire subtree beneath it to find every completion — netflix, network, netherlands, thousands of them — then sort by score. For a hot prefix like a, that subtree is enormous.

The fix is to precompute the top K at each node. Every trie node stores a small sorted list of the best K completions in its subtree, ranked by score. A query walks down p nodes and returns that cached list directly:

Now query latency is O(p) plus a constant read of K entries — independent of subtree size. The a prefix costs the same as azerbaijan.

An n-gram index — mapping every length-n substring to the terms containing it — earns its place when users expect infix or "contains" matching, like symbol search in an IDE (Btn should find PrimaryButton). It costs far more memory and is slower for plain prefixes, so for a search box the augmented trie wins. Pick n-grams only when the product genuinely needs substring match.

Why writes are the hard part#

Caching the top K per node makes reads trivial and makes writes expensive. Increment the frequency of one leaf term and its new score may have to bubble all the way up to the root, rewriting the top-K list at every ancestor node. Doing that per keystroke would collapse under its own write amplification.

So you decouple the two. Popularity counts are aggregated offline and the trie's top-K lists are rebuilt in batches — a nightly full rebuild from the complete query log keeps the base index correct. Between rebuilds, the read path stays frozen and fast. This batch/serving split is the single most important structural decision in the design.

Ranking: frequency is only the start#

Ordering by raw global frequency is a weak baseline. Real ranking blends several signals into the score that decides each node's top-K list:

• Time-decayed frequency — last week's counts weigh more than last year's, so stale popularity fades.
• Personalization — the user's own history and language; at query time you merge the global top-K with a short user-specific list.
• Location and recency — regional terms and freshly trending queries get a boost.
• Click-through rate — suggestions users actually click get promoted, closing the feedback loop.

A linear model or gradient-boosted trees (GBDT) combines these features into one score per term, which is what gets cached. Personalization is the exception to pure precomputation: because per-user lists cannot be baked into a shared trie, you keep a small personal history client- or server-side and merge it into the global result at request time.

Capacity: the numbers interviewers push on#

Concrete estimates separate a real answer from hand-waving. Assume a large search engine: 5 billion queries per day, and because suggestions fire per keystroke, roughly 20 keystrokes per final query.

Keystrokes are what actually hit the service:

That is an extreme read load, and it is the reason client-side debouncing is not optional — firing every 2-3 keystrokes instead of every one cuts this dramatically.

Memory, with ~500M unique terms:

That 200 GB lives in memory — autocomplete on disk would blow the latency budget — sharded across roughly 20-50 machines, each replicated ~3x for read throughput and failover.

Sharding: keep each query on one machine#

Two hundred gigabytes does not fit on one box, so the trie is partitioned. The goal is that any single prefix query hits exactly one shard — fanning out to every shard would multiply tail latency.

The clean approach is sharding by the first one or two characters of the prefix. A router table maps a character prefix to a shard id, so the client or router sends net... straight to the shard owning n (or ne). Every query is single-shard.

The catch is skew: prefixes starting a, s, t are far hotter than x, z, q. You rebalance by splitting hot prefixes — spread a across several shards as aa, ab, ... az — and coalescing cold ones onto a shared shard. Combined with 3x replication, this keeps any one machine from becoming a bottleneck.

Fresh trends and fuzzy matching#

Trending terms. A nightly rebuild cannot surface a breaking-news query that started an hour ago. Layer a streaming pipeline on top: Kafka feeds Flink or Spark Structured Streaming, which aggregates query counts in short 1-5 minute windows and emits deltas to a small "recent trends" index. At query time the service merges the static trie's top-K with this trending layer, boosting any term whose short-window velocity crosses a threshold. The nightly batch job folds those trends into the base trie so nothing drifts permanently.

Typos. Users misspell, and full Levenshtein distance is too slow to run per request. The Symmetric Delete (SymSpell) trick precomputes, for every term, a small set of deletion-variants — the word with one character removed — stored in a hash map pointing back to the original. At query time you generate the input's deletions and do hash lookups, which surfaces edit-distance-1 candidates in sub-millisecond time with no scan. For edit-distance-2 you repeat the deletions, or fall back to a BK-tree over the smaller candidate set the prefix lookup already returned.

What the client does#

A surprising amount of the latency budget is won in the browser. The client debounces input by ~50-100ms so a burst of keystrokes collapses into one request. It cancels in-flight requests with an AbortController the moment a newer keystroke lands, so stale responses never overwrite fresh ones. And it keeps a small per-prefix LRU cache in memory, which makes backspacing completely free and lets the first few characters of a known query render with zero round trips.

How this shows up in interviews#

Autocomplete is a favorite because it rewards structure. Interviewers watch for a specific arc: identify the read-heavy nature early, reach for the trie, then — critically — realize a plain trie is too slow for hot prefixes and introduce top-K caching at each node. That single insight is the pivot the whole discussion turns on.

From there, the strong candidates go straight to the write/read split (batch rebuilds, streaming trends), do the QPS math out loud to justify sharding, and name the sharding key with its skew problem and mitigation. Weaker answers stall at "use a trie" without solving the subtree-walk cost, or forget that per-keystroke QPS is ~20x the query rate. Ranking beyond raw frequency and client-side debouncing are the details that signal you have actually shipped this, not just read about it.

Further learning#

• Design Autocomplete or Typeahead Suggestions — Tushar Roy walks the trie, top-K, and sharding decisions end to end.
• Practice this topic on YeetCode — the interactive roadmap item for this design.

Related core designs that share the same batch-serving, sharding, and top-K ideas:

• Design a Unique ID Generator
• Design a Task Scheduler
• Design a Leaderboard
• Design a URL Shortener

FAQ#

Why use a trie instead of a SQL LIKE 'prefix%' query?#

A database index can answer a prefix query, but it re-runs the search on every keystroke and still has to sort matching rows by score at request time — unpredictable latency that worsens for popular prefixes with millions of matches. A trie with top-K cached per node turns the query into an O(p) walk plus a constant read of a precomputed list, so latency depends only on the prefix length, not the corpus size. At millions of QPS with a p99 under 50ms, that predictability is the whole point.

How do you return the top K suggestions without walking the entire subtree?#

Precompute the answer. At each trie node, store a sorted list of the top K completions in its subtree, ranked by score, and update it offline whenever aggregate counts change. A query walks down to the prefix's terminal node and returns that cached list directly, so the response time is independent of how many terms live beneath the prefix. The cost is on the write side: a single count change can propagate up to the root, which is why updates are batched into periodic rebuilds rather than applied per keystroke.

How does autocomplete surface trending queries quickly?#

The nightly base-trie rebuild handles long-term popularity but is far too slow for a term that starts trending in the last hour. A streaming pipeline — Kafka into Flink or Spark Structured Streaming — aggregates counts in short 1-5 minute windows and writes deltas to a small "recent trends" index layered on top of the static trie. The service merges both at query time and boosts any term whose short-window velocity exceeds a threshold, so breaking-news queries appear within minutes while the base index stays authoritative.

How do you shard the trie so one query hits one machine?#

Shard by the first one or two characters of the prefix and keep a router table mapping character-prefix to shard id, so the client routes each request to exactly the shard that owns it — no fan-out. Because letters are unevenly distributed, hot prefixes like a, s, and t are split across several shards (aa..az) while cold ones like x and z are coalesced onto a shared shard. Every shard is replicated about three times for read throughput and failover.

How is fuzzy matching handled without wrecking latency?#

Full Levenshtein distance is too expensive to compute per request, so the system precomputes edit variants instead. Using the Symmetric Delete (SymSpell) approach, each term generates a small set of one-character-deletion variants stored in a hash map back to the original term. At query time you generate the input's deletions and do hash lookups, returning edit-distance-1 candidates in sub-millisecond time. For edit-distance-2 you either repeat the deletions or run a BK-tree over the small candidate set the prefix lookup already produced.