system-design

Design Typeahead / Autocomplete (Search Suggestions)

Difficulty: Tier 2 Asked at: Google, Meta, Amazon, Careem Time budget: 45 min

Every search box that suggests as you type is a typeahead system. The challenge is latency — a suggestion must appear within milliseconds of each keystroke, at enormous query volume — which forces a precomputed, in-memory prefix structure (a trie) rather than querying a database per keystroke. The signature data structure is the trie, and the signature tension is precompute-vs-freshness.

Prerequisites: Caching, Search Systems, Batch vs Stream

1. Requirements

Functional:

As the user types a prefix, return the top-K most relevant completions.
Suggestions ranked by popularity/frequency (and possibly personalization, recency).
Update suggestions as new queries trend.

Non-functional:

Ultra-low latency — < 100 ms per keystroke (ideally < 50 ms); it fires on every character.
Very high QPS — every keystroke of every searching user → far more requests than actual searches.
Scale to billions of possible queries.
Freshness — trending terms should appear, but not necessarily instantly.

Out of scope: the full search backend (separate), spell correction (mention).

2. Estimation

Google-scale: billions of searches/day; each search is ~20 keystrokes → tens of billions of typeahead requests/day ≈ hundreds of thousands to millions/sec. 🚨 The QPS is higher than search itself — every character typed is a request.
This QPS at < 50 ms means: serve from memory, precompute answers. A database lookup per keystroke is out of the question.

3. The core data structure: the trie

🚨 A trie (prefix tree) stores strings by shared prefix — each path from the root spells a prefix, and each node can hold the top-K completions for that prefix, precomputed.

        (root)
        /    \
       c      t
       |      |
       a      e
      /|      |
     r t      a  ...
   "car"   "tea"

Typing “ca” → navigate root→c→a → return that node’s precomputed top-K (car, cat, care…).
🚨 Precompute top-K at each node so a lookup is O(prefix length) — no ranking at query time. This is what hits the latency budget.

Memory: billions of queries make a naive trie huge; compress it (radix tree), store only popular prefixes, and shard by prefix.

4. High-level design

flowchart TB
    User -->|keystroke: prefix| API[Suggestion Service]
    API --> Cache[(In-memory trie<br/>top-K per node, sharded)]
    Cache -->|top-K completions| User

    Logs[(Search query logs)] --> Batch[Batch aggregation<br/>count frequencies]
    Batch --> Build[Build/update trie]
    Build --> Cache
    Stream[Trending stream] -.fast path.-> Cache

Serve path (hot): keystroke → suggestion service → navigate the in-memory trie → return top-K. Pure memory read, milliseconds.

Build path (cold, offline): aggregate search logs to count query frequencies (a batch job), rebuild the trie with fresh top-K rankings, and deploy it to the serving tier. 🚨 Separate the fast read path from the slow build path — the trie is built offline and served online.

5. Deep dives

5a. Why precompute top-K per node?

If you stored only frequencies and ranked at query time, each keystroke would gather all completions under a prefix and sort them — too slow at this QPS. Instead, precompute and store the top-K (e.g. top 10) directly at each node during the offline build. Query time becomes “walk to the node, return its list” — O(prefix length), no sorting. The cost is a heavier build and more storage, paid offline where it’s cheap.

5b. Building & updating the trie (freshness)

Suggestions come from aggregating real search frequencies. Do this in a batch pipeline: collect query logs, count/weight by recency, compute top-K per prefix, build the trie, and swap it into the serving tier periodically (e.g. hourly/daily). 🚨 The trade-off: precomputed = fast but slightly stale. For trending terms (breaking news), add a faster streaming path that nudges hot prefixes in near-real-time. Most of the trie updates slowly; a small trending overlay stays fresh. (Batch vs Stream)

5c. Scaling the serving tier

Replicate the trie across many servers (it’s read-only at serve time) → scale QPS horizontally, each replica serving from memory. Shard by first characters if the trie is too big for one machine (prefixes starting “a…” on one shard, etc.), routing by prefix. A CDN/edge cache can even serve very common prefixes.

5d. Ranking & personalization

Base ranking = query frequency (+ recency weighting so old-but-once-popular terms fade). Personalization (your history, location) and context can re-rank the precomputed candidates at query time cheaply — take the node’s top-K candidates and lightly reorder, rather than ranking from scratch.

5e. Handling typos & partial matches

Real systems tolerate typos (fuzzy matching) via edit-distance-tolerant structures or a secondary correction step. Mention it as an extension; the core trie handles exact prefixes.

6. Bottlenecks & scaling further

Query latency → in-memory trie with precomputed top-K per node.
QPS → replicate the read-only trie across many servers; edge-cache common prefixes.
Trie size → radix compression, prune rare queries, shard by prefix.
Freshness → periodic batch rebuild + a streaming overlay for trending.
Build cost → offline batch pipeline, decoupled from serving.

7. Trade-off summary

Decision	Chosen	Alternative	Why
Data structure	Trie with precomputed top-K	DB LIKE query per keystroke	O(prefix) memory read hits the latency budget
Ranking	Precompute offline	Rank at query time	Query-time sorting too slow at this QPS
Freshness	Batch rebuild + trending overlay	Real-time updates everywhere	Most terms change slowly; overlay covers trends
Serving	Replicated read-only in-memory	Shared database	Scales QPS; memory-speed reads

8. Follow-up questions

Why a trie instead of a database query per keystroke?

Because the latency and QPS budgets make a per-keystroke database query impossible. Typeahead fires on every character of every searching user, so it sees more requests than search itself — hundreds of thousands to millions per second — and each must respond in tens of milliseconds so suggestions feel instant. A database LIKE 'prefix%' query, even indexed, involves network round trips and query planning and can't reliably hit that latency at that volume, and ranking the matches would add sorting cost. A trie keeps all prefixes in memory as a tree where walking to a prefix is O(prefix length) and the top-K completions are precomputed and stored right at each node, so a lookup is a short in-memory walk returning a ready-made list — no query, no sort, no disk. That's what meets the budget.

How do suggestions stay fresh if the trie is precomputed offline?

Through a two-speed design. The bulk of the trie is rebuilt periodically (say hourly or daily) by a batch pipeline that aggregates recent search logs, weights queries by frequency and recency, recomputes the top-K per prefix, and swaps the fresh trie into the serving tier — which is fine because most query popularity changes slowly. For genuinely trending terms (a breaking-news query spiking in minutes), a faster streaming path detects the surge and nudges the affected prefixes' suggestions in near-real-time as a small overlay on top of the batch-built trie. So you get the speed and simplicity of precomputation for the vast majority of prefixes, plus a lightweight fast path for the small set of things that are changing right now — accepting mild staleness everywhere else as a good trade for the latency and simplicity gains.

How do you scale to millions of QPS?

Exploit that the serving trie is read-only. Once built, it can be replicated across a large fleet of servers, each holding the trie in memory and serving lookups independently, so QPS scales horizontally just by adding replicas. If the trie is too large for one machine, shard it by prefix (e.g. by first character or two) and route each request to the shard owning its prefix. Extremely common short prefixes can even be cached at the edge/CDN. Because every lookup is an in-memory read with no shared mutable state during serving, there's no contention bottleneck — the design is embarrassingly parallel on the read side, which is exactly what the huge QPS demands.

How would you personalize suggestions without blowing the latency budget?

Keep personalization as a cheap re-rank of the already-precomputed candidates rather than a from-scratch computation. The trie node gives you the top-K globally-popular completions for the prefix in one fast read; then you lightly reorder or blend that small candidate list using per-user signals (search history, location, current context), which is a quick operation over ~10 items, not a ranking over the whole corpus. You can precompute per-user or per-segment signals offline so the query-time step is just a small weighted reshuffle. This preserves the millisecond budget because the expensive part (finding and globally ranking candidates) stays precomputed, and only a tiny, bounded personalization pass happens per request.

9. What junior / mid / senior answers look like

Junior: proposes a DB query with LIKE ‘prefix%’ on each keystroke. Correct results, but can’t meet the latency or QPS — misses the need for an in-memory precomputed structure.
Mid: uses a trie with precomputed top-K per node, serves from memory, rebuilds from query logs, ranks by frequency.
Senior: cleanly separates the offline build path from the online serve path, precomputes top-K to kill query-time sorting, replicates/shards the read-only trie for QPS, adds a batch+streaming two-speed freshness model with a trending overlay, and treats personalization as a bounded re-rank — articulating the precompute-vs-freshness trade-off throughout.