System Design · Design Question
Design Autocomplete
Typeahead suggestions: tries, ranking by popularity, low-latency serving, and personalization at the edge.
In simple words:
Map each typed prefix to a short ranked list in memory. Build popularity data offline so the live lookup stays fast.
Concrete example: Typing uni in Google may suggest "university", "unicode", and "unicorn" within ~50 ms because a trie stores top queries for each prefix, ranked by search logs.
1. Requirements
Functional
- As user types, show top K query suggestions (e.g. K=10).
- Latency budget: ~50–100ms end-to-end.
- Rank by popularity / relevance; optional personalization.
- Handle typos lightly (optional fuzzy); multi-language later.
Non-functional
- Keep end-to-end latency below about 100ms and remain available during rebuilds.
- Refresh popular queries without blocking the serving path.
Back-of-envelope
100M users × 20 search sessions × 10 keystrokes ≈ 20B raw key events/day.
Client debounce and a 2-character minimum can cut origin traffic by several times; size for ~100k peak QPS.
Prefix "uni" → university, unicode, unicorn, ...
Update popularity from search logs daily / nearline
2. API
GET /v1/suggest?q=uni&limit=10&lang=en
→ {
"suggestions": [
{ "text": "university", "score": 0.91 },
{ "text": "unicode", "score": 0.88 }
]
}
3. Data structures
Trie (prefix tree)
root
/ \
u ...
|
n
|
i → topK: [university, unicode, ...]
Each node can cache top-K completions for its prefix so serving does not walk the whole subtree. Memory-heavy at web scale — shard or use succinct structures / analytics DB.
Alternatives
- Sorted list + binary search on prefixes (simpler ops).
- Search engine completion suggester (Elasticsearch).
- n-gram indexes for mid-string match (heavier).
4. Ranking
score = f( frequency, recency, click-through, personal history )
Offline job aggregates query logs → popularity table
Personal: boost queries user issued before (small Redis profile)
5. High-level design
Client (debounce 30–50ms) → Edge / API → Suggest Service
|
in-memory trie shard OR Redis
|
Build pipeline:
Search logs → aggregate → publish new trie snapshot → reload workers
6. Deep dive — serving latency
- Debounce client keypresses; cancel in-flight requests.
- Keep trie in RAM per shard; hash prefix to shard.
- CDN/edge cache for popular prefixes (
q=a,q=how). - Limit minimum prefix length (e.g. 2+) to cut load.
7. Data model
query_stats(query, freq, last_seen) -- analytics store
trie_snapshots(version, blob_or_path) -- published artifacts
user_recent_queries(user_id, queries[]) -- personalization cache
8. Scaling
- Shard by first character(s) or hash(prefix).
- Rebuild snapshots asynchronously; atomic swap version.
- Hot prefixes cached at edge; protect origin.
- Abuse: rate limit suggest API per IP.
9. Edge cases
- Toxic / illegal suggestions → blocklist filter on publish and serve.
- Empty / whitespace query → return empty or trending.
- Sudden viral query → nearline bump into trie without full rebuild.
10. Offline vs online split
Offline (daily/hourly):
logs → aggregate counts → build trie snapshot → publish to object store
Online:
suggest servers mmap/load snapshot
optional delta stream for viral queries
personalization re-rank using small user profile
Keep online path CPU-light: dictionary lookup + tiny re-rank. Heavy ML belongs in offline candidate generation when possible.
11. Multilingual notes
- Separate tries or segments per language / locale.
- Normalize Unicode (NFKC) carefully so visually identical prefixes match.
- Do not mix scripts in one naive trie without tokenization rules.
12. Failure modes
- New snapshot is corrupt → keep serving the previous version and reject the swap.
- Personalization store is down → return global suggestions.
- A shard is slow → time out quickly and return cached or fewer suggestions.
Interview talking points
- Lead with: Keep serving in memory and move heavy ranking work offline.
- Prefix → top K; trie with cached top-K per node is the classic model.
- Popularity from search logs; rebuild snapshots offline.
- Serve from RAM; debounce client; cache hot prefixes.
- Personalization is a light re-rank on top of global results.
- Shard tries; atomic snapshot reload.
- Min prefix length + rate limits control cost.
- Filter unsafe suggestions in the pipeline.