System Design Problems
Design Search Autocomplete
Search autocomplete (typeahead) suggests search queries in real-time as users type. Google processes billions of autocomplete queries daily with < 100ms latency, using a trie-based data structure ranked by query popularity.
- Real-time Suggestions â Results returned within 50ms of each keystroke
- Popularity-ranked â Most popular queries appear first
- Context-aware â Suggestions personalized by user location and history
The challenge is balancing freshness (trending queries), relevance (popular queries), and latency (sub-50ms response times) across billions of possible prefixes.
Requirements
Functional Requirements
- As user types, show top 5-10 search suggestions
- Suggestions ranked by popularity (frequency)
- Support for multiple languages
- Suggestions update in near real-time as trends change
- Personalized suggestions based on user history
Non-Functional Requirements
- Latency: Response in < 50ms (p99)
- Throughput: 100K QPS per region
- Freshness: Trending queries visible within 1 hour
- Availability: 99.99% uptime (autocomplete is critical for UX)
Back-of-the-Envelope Estimation
API Design
GET /api/v1/autocomplete?q=how+to+ma&limit=5
Response: {
"suggestions": [
"how to make pasta",
"how to make money",
"how to make friends",
"how to make candles",
"how to make soap"
],
"latency_ms": 12
}
High-Level Architecture
Detailed Design
Trie Data Structure
Aggregation and Ranking
Aggregate query frequencies and rank by popularity:
Two-Layer Architecture
Use a two-layer approach for efficiency:
- Offline Aggregation Layer: Collects search logs, aggregates frequencies, builds trie
- Online Serving Layer: Serves trie from memory, returns top-K suggestions
CDN Caching
Popular prefixes can be cached at CDN edge locations:
- Cache prefix "how to" at all edge locations
- Cache prefix "best rest" at regional edges
- Cache invalidation: TTL-based (1 hour) or explicit purge
Practice Exercises
-
Design: How would you handle multi-language autocomplete? What changes are needed for languages with different character sets (Chinese, Arabic)?
-
Algorithm: Implement a trie that supports top-K retrieval for a prefix. What is the time and space complexity?
-
Scale: If the system needs to handle 100K QPS with < 10ms latency, estimate the memory needed for a trie with 1 billion unique prefixes at 50 bytes per node.
-
Freshness: Design a system to update trending autocomplete suggestions in real-time without rebuilding the entire trie.
What to Learn Next
-> Design Search Engine Full-text indexing, inverted indices, and relevance ranking.
-> CDNs Edge caching and global content distribution.
-> Design Typesense Autocomplete Typo-tolerant fuzzy search with instant results.
-> Database Indexing B-tree, LSM-tree, and index structures for fast lookups.
-> Caching Strategies CDN caching, application caching, and cache invalidation.
-> Rate Limiting Protecting autocomplete from abuse and excessive load.