Design search autocomplete / typeahead

Expected question

"Design a search autocomplete system. How do you serve prefix suggestions with low latency at high QPS, keep them fresh, and personalize without leaking private queries?"

Variant forms

Same design, different framing:

"Design Google-style search suggestions as the user types."
"How do you rank autocomplete when two prefixes share millions of queries?"
"Design typeahead for an e-commerce catalog with product + query suggestions."
"Our suggestions show another user's private search — architect isolation."
"Scale autocomplete to 100k QPS with P99 under 50ms."
"How do you handle typos and fuzzy prefix match?"
"Design personalization (recent searches) vs global popularity."
"How fast do new trending queries appear in suggestions?"

Where this actually gets asked

Canonical high-frequency classic system-design prompt (Google/Amazon/Meta/Microsoft screening and mid rounds). Often paired with rate limiter or feed questions. Staff+ depth: trie/segment trees vs inverted indexes, offline aggregation vs online personalization, privacy, and freshness.

Executive summary

30-second thesis

I'd serve top-k from a sharded in-memory prefix index built offline from anonymized aggregates, edge-cache the global lists, and keep personal recents in a private store — never in shared CDN keys.

2-minute answer

Clarify QPS, p99 budget (~30–50ms H), locales, and personalization. Client debounces; server still must be cheap. Default: nearline aggregators turn query logs into capped top-k lists per prefix; atomic swap into trie/prefix shards; trending overlay for minutes-level freshness. Global suggestions only above min distinct-user thresholds. Personal blend only for authenticated prefix matches from per-user storage. Suppress unsafe strings via ops API. Under load: smaller k, drop personalization, serve slightly stale global. Don't hit OLTP with LIKE per keystroke.

Quantitative trade-offs

Decision	Trade-off and reversal evidence	Evidence class
In-memory trie vs DB prefix scan	Trie hits latency SLO; reverse only for tiny catalogs.	H
Fast trending overlay vs hourly full rebuild	Overlay for virality; reverse weight if noisy/spammy trends hurt trust.	H
Personalization on vs privacy-safe global only	Personal helps UX; reverse/disable when cache keying or ACL risk can't be proven safe.	H

What I'd ask them

Hard p99 latency and peak QPS?
Personalization required, or global-only v1?
Fuzzy/typo tolerance in scope for this round?

Requirements

Functional

Given a prefix, return top-k suggestions (queries and/or entities).
Optional: personal recent searches, trending boosts, locale.
Suppress unsafe / banned suggestions.

Non-functional

Extremely low latency: P99 often <30–50ms (H) including network to edge.
Very high read QPS; write path is aggregated, not per-keystroke DB writes.
Privacy: never suggest another user's private or authenticated-only queries.
Freshness: new viral queries appear in minutes–hours, not weeks.

Core entities

Suggestion: text, type (query|product|user), score components, locale.
Prefix entry: prefix → ranked posting list (capped).
Query aggregate: query string, frequency windows (1h/1d/7d), filtered flags.
Personal store: per-user recent searches (small, private).

API / interface

GET /v1/autocomplete?q=ama&locale=en-US&limit=8
Authorization: optional Bearer (personalization)
→ 200 { "suggestions":[{"text":"amazon","score":0.92},{"text":"amazon prime","score":0.88}] }

POST /v1/autocomplete/admin/suppress
{ "text":"...", "reason":"unsafe" }
→ 204

Staff+ callout: client debounces; server still needs cache + cheap prefix structures — do not hit OLTP per keystroke.

Data Flow

Keystroke → edge cache → prefix index → blend global + personal → filter → respond; offline/nearline jobs aggregate query logs into prefix lists.

Rendering architecture diagram…

High-level design

Rendering architecture diagram…

Deep dive 1: data structure choice

In-memory tries (or compressed prefix maps) per shard hold top-k per prefix — optimal for strict prefix. For huge alphabets / fuzzy, use n-gram or AQ (approximate) indexes with higher latency. Cap posting lists (e.g., top 50) at build time so reads are O(k). Shard by prefix hash or first character ranges; hot prefixes ("a", "how") need replication.

Deep dive 2: ranking and freshness

Score = f(frequency windows, CTR on suggestion, personal match, freshness boost). Use time-decayed counts so yesterday's spike fades. Trending pipeline (minutes) updates a small overlay index; full rebuild hourly/daily. Personalization: blend 1–2 personal hits at the top only if prefix matches — never show another user's history.

Deep dive 3: privacy and abuse

Authenticated recent-search is per-principal storage with strict ACL. Global index only includes queries above anonymity thresholds (min distinct users). Suppress porn/illegal/PII-like patterns. Rate-limit suggestion analytics writes. Cache keys must not embed raw user ids in shared CDN entries for personalized responses (cache global separately from personal).

Deep dive 4: failure and 45-min focus

If aggregator lags, serve stale global index + personal — still better than empty. Under overload, reduce k and disable personalization. In 45 minutes: prefix index + top-k cap + aggregation pipeline

privacy threshold — not ML query rewriting unless asked.

What's expected at each level

Mid-level: SQL LIKE 'ama%' or simple cache.
Senior: trie / prefix index + top-k by frequency + client debounce.
Staff+: sharded in-memory index, nearline aggregation, anonymity thresholds, personal vs global cache split, P99 budget.
Principal: trending overlay, abuse/suppression ops, multi-locale sharding, and CTR feedback without privacy leaks.

Follow-up questions to expect

"Typos?" — Fuzzy layer or spell-correct before prefix lookup — watch the latency budget.
"How do you update top-k?" — Recompute offline; atomic swap of prefix lists. Don't mutate lists in place under read traffic.
"Ajax storm?" — Client debounce ~20–50ms (H); server coalesce identical in-flight prefixes.