Design Typeahead / Autocomplete
Search suggestions as you type — prefix indexes, trie, Elasticsearch, and ranking at <100ms p99.
Interview tip Target <100ms p99. Precompute top queries offline. Trie or ES completion suggester. Cache hot prefixes in Redis. Debounce client requests (200ms).
① Functional requirements
- Return top 10 suggestions for a given prefix (min 1 char)
- Rank by popularity (query frequency) + recency
- Optional personalization based on user search history
- Debounce-friendly: fast response for partial prefixes
- Filter blocked terms (NSFW, policy violations)
- Support multiple languages/locales
- Refresh suggestion corpus daily from query logs
Out of scope (state in interview)
- Full search results page
- Spell correction (mention as extension)
- Voice input
- Real-time trending (sub-minute updates)
② Non-functional requirements
- Latency p99 < 100ms end-to-end
- Support 5B searches/day → ~58K typeahead requests/sec (5× per search)
- Highly available (99.9%) — degrade gracefully if index slow
- Corpus of 100M unique queries with prefix index
- Consistent suggestions within a daily batch window
③ Back-of-the-envelope scale
Assumptions
- 5B searches/day × 5 keystrokes = 25B typeahead requests/day → ~290K RPS
- Corpus: 100M unique queries; avg 20 chars → trie ~2GB in memory
- Top 10 suggestions per prefix; avg prefix depth 3 chars → ~50K active prefixes hot
- Cache: 50K hot prefixes × 10 suggestions × 50B ≈ 25 MB Redis
- Offline job: process 5B query logs/day → aggregate top 10M queries → build trie in ~2 hours
- Read:write ratio ∞ — entirely read-optimized
Precompute everything offline. Online path is pure lookup + optional personalization overlay. Redis caches top 50K prefixes (covers 90% of traffic). Trie kept in memory on each API server (2GB replicated).
④ High-level architecture
Typeahead System
Search Clients
Typeahead API (stateless)
Redis Cache (hot prefixes)
In-Memory Trie (per server)
Personalization Service (optional)
Offline: Query Log Aggregator
Trie Builder (daily batch)
Query Log Store (S3/HDFS)
Prefix "app"→Redis cache hit?→Trie lookup→Top 10 ranked
Client debounces 200ms before sending request. API normalizes prefix (lowercase, trim). Cache key = locale + prefix. On cache miss, trie lookup O(k) where k = prefix length. Personalization reorders top 10 if user history available.
⑤ Data flow & execution path
End-to-end execution flow
① Client→② API / LB→③ Core services→④ Cache + DB→⑤ Message queue→⑥ Async workers
Sync path: validate → authorize → read/write primary store
Async path: publish domain events → consumers (email, analytics, search index)
Read-heavy path: CDN / edge cache → regional cache → DB replica
Failure path: retry with backoff, DLQ, idempotent handlers
In interviews, trace one user action through this diagram. State what is synchronous (user waits) vs asynchronous (background), and where you enforce idempotency.
⑥ API & interfaces
| Endpoint / flow | Purpose | Notes |
|---|---|---|
| GET /v1/suggest?q={prefix}&limit=10&locale=en | Get suggestions | Returns [{text, score, type}] in <100ms |
| Internal: rebuild_index() | Daily batch job | Reads aggregated queries; builds trie; rolling deploy to API servers |
| GET /v1/admin/corpus/stats | Ops | Corpus size, last rebuild time, cache hit rate |
| POST /v1/admin/blocklist | Block term | Adds term to filter; applies on next rebuild |
⑦ Data model & storage
query_corpus (offline):
trie_node (in-memory):
blocklist:
query_text, count, last_seen, locale — top 10M by counttrie_node (in-memory):
char, children{}, top_queries[] (heap of top 10 by count at this prefix)blocklist:
term, reason — filtered during trie build| Store | What | Why |
|---|---|---|
| In-memory Trie (per API pod) | Prefix index | 2GB RAM; rebuilt daily; blue-green deploy |
| Redis | Hot prefix cache | TTL 1h; 50K keys; 90%+ hit rate |
| S3 / HDFS | Raw query logs | Daily batch input for corpus aggregation |
| PostgreSQL | Blocklist + corpus metadata | Admin operations; corpus version tracking |
⑧ Deep dive — core components
Trie with top-K at each node
Build trie from corpus: for each query, walk trie inserting chars; at each node maintain min-heap of top 10 queries by count seen through this prefix. Lookup: walk trie for prefix → return node's top 10 heap. O(k) lookup, k = prefix length. Space: ~2GB for 100M queries.
Alternative: Elasticsearch completion suggester with edge n-grams — easier to operate but 50–100ms vs 5ms trie. Use ES if corpus > 500M or need fuzzy matching.
Offline aggregation pipeline
Daily Spark job: read 5B query logs from S3 → normalize (lowercase, trim, dedupe session repeats) → count frequency → filter blocklist → keep top 10M → serialize trie → push to API servers via rolling update (blue-green, zero downtime).
Incremental updates (hourly) possible for trending terms: merge delta into trie or overlay trending layer in Redis with 1h TTL.
Caching and latency budget
Latency budget: network 20ms + API 5ms + cache/trie 5ms + serialization 5ms = 35ms p50. Redis hit (90%): <10ms. Trie miss on long tail prefix: <20ms. Personalization adds 15ms — only for logged-in users, async overlay.
CDN edge caching for anonymous users with common prefixes ("a", "th") — cache 60s at edge.
Personalization without killing cache
Base suggestions from global trie (cacheable). Personalization: fetch user's top 20 historical queries from user profile service; if any match current prefix, boost in re-ranking. Personalization layer is per-user (not cacheable) but only reorders 10 items — cheap.
⑨ Trade-offs & alternatives
| Decision | Option A | Option B | Pick when |
|---|---|---|---|
| Index | In-memory trie | Elasticsearch | Trie for speed; ES for scale/fuzzy |
| Update freq | Daily batch | Real-time stream | Daily sufficient; stream for trending |
| Personalization | Re-rank overlay | Separate index per user | Overlay preserves cache; per-user index impossible |
| Prefix min length | 1 char | 3 chars | 1 char better UX; 3 chars reduces load 100× |
| Fuzzy match | No (exact prefix) | Yes (edit distance) | Exact for speed; fuzzy for typo tolerance |
⑩ 45-minute interview script
- 0–5 min: Clarify suggestion count, ranking, personalization, latency SLA
- 5–10 min: Scale — 290K RPS, corpus size, read-heavy
- 10–20 min: Offline pipeline — log aggregation → trie build
- 20–28 min: Online path — cache → trie lookup → rank
- 28–35 min: Trie data structure with top-K heaps
- 35–40 min: Personalization overlay approach
- 40–45 min: Daily rebuild zero-downtime deploy
⑪ Likely follow-up questions
| Question | Short answer |
|---|---|
| User types single char "a"? | Trie root children return top 10 global queries starting with "a"; heavily cached |
| Trie too big for memory? | Shard trie by first 2 chars across servers; or use ES completion |
| NSFW term in suggestions? | Blocklist filtered at build time; human review queue for flagged terms |
| Stale suggestions (old news)? | Recency decay in ranking score; boost queries from last 7 days |
| Multi-language? | Separate trie per locale; route by Accept-Language header |
| How to A/B test ranking? | Shadow traffic to variant trie; compare CTR offline |
⑫ Revision checklist
- Offline batch aggregation from query logs
- Trie with top-K heap at each node
- p99 < 100ms latency budget
- Redis cache for hot prefixes
- Client debounce mentioned
- 290K RPS scale math
- Daily corpus rebuild strategy
- Blocklist filtering
- Personalization as re-rank overlay
- Blue-green trie deployment