Back to System Design
System Design
Search autocomplete
Senior level · full staged walkthrough
Senior
Architecture
SeniorClientEdgeDataAsyncService
Solution, step by step
- 1
Functional requirements
- Suggest completions as the user types
- Rank by popularity/personalization
- Support typo tolerance (optional)
- 2
Non-functional requirements
- Latency < 100ms p99
- Read-heavy; refresh ranking periodically
- High availability
- Graceful degradation on cache miss
- 3
Capacity & estimation
- Hundreds of millions of queries/day → tens of K QPS
- Top-k (≈10) completions per prefix
- Prefix index of millions of terms → fits in memory per shard
- Query logs: TBs/day for ranking refresh
- 4
Preliminary design
- Trie / FST of top prefixes
- Precompute top-k completions per prefix
- Serve from an in-memory cache
- 5
Final architecture
- In-memory suggestion service sharded by prefix range
- Offline pipeline aggregates query logs → builds ranked trie/FST
- Top-k precomputed and stored at each trie node
- Periodic index swap (blue/green) for fresh rankings
- Optional personalization layer re-ranks the precomputed list
Interview Q&A (8)
A trie or FST of prefixes with the top-k completions precomputed and stored at each node, held in memory for sub-100ms lookups.
Key components
- Suggestion service
- Trie/index builder
- Query-log pipeline
- Cache
Bottlenecks & how to address them
- Per-keystroke QPS → aggressive caching + debounce
- Index rebuild cost → incremental updates
- Long-tail prefixes → fallback search
Tradeoffs to articulate
- Precompute vs query-time ranking
- Memory footprint vs coverage
- Freshness vs cost
Where this content comes from
For full transparency, this content is curated and verified from these sources:
Published architecture case studiesCompany engineering blogsOppZen design rubric library