RETURN TO SYSTEM DESIGN VAULT (55)BLUEPRINT #08 // Hard
#08HardSearch, Autocomplete & Big Data
Design Typeahead Suggestion/Autocomplete
ASKED IN INTERVIEWS AT:MetaGoogleExpediaBloomberg
EXECUTIVE SUMMARY & PROBLEM STATEMENT
Build a real-time search autocomplete system that returns the top 5-10 query suggestions in under 30ms as the user types each keystroke.
SCALE ESTIMATION & TRAFFIC ENVELOPE
DAILY ACTIVE USERS / TPS5 Billion searches/day = ~25 Billion autocomplete keystroke queries/day
READ / WRITE TRAFFIC RATIORead-intensive (Keystrokes streamed live)
5-YEAR STORAGE CAPACITYTrie compressed in RAM ~ 50 GB per instance
FUNCTIONAL REQUIREMENTS
- [1]Provide top 5-10 relevant completions for user search prefix
- [2]Rank suggestions based on historical query frequency
NON-FUNCTIONAL REQUIREMENTS
- •Response latency < 30ms
- •High availability (99.99%)
- •Freshness: reflect trending searches within hours
CORE ARCHITECTURAL COMPONENTS
Keystroke Aggregator
In-Memory Trie Cluster
Offline Aggregation Pipeline (Spark/Flink)
ZooKeeper Cluster Coordinator
Browser Cache / Debouncer
DATA SCHEMA & PERSISTENCE
PrefixTrie in RAM: Node { children: Map, topSuggestions: List<{query, score}> }
DISTRIBUTED TRADE-OFFS & FAILURE MODES
- ⟡Pre-computing top suggestions at each node increases Trie memory by 4x but avoids runtime Trie tree traversal.