Architecture & Data Structure Design:
- Goal: Provide top-5 query suggestions as users type in a search box with <30ms latency at 50,000 queries/sec.
1. Core Data Structure: Trie with Pre-computed Top Suggestions:
- Standard Trie traversal at runtime is too slow for high throughput.
- Optimized Trie: At every prefix node, pre-store the top 5-10 highest-frequency completions. Searching a prefix becomes an O(1) lookup returning pre-ranked results instantly.
2. Storage & Sharding:
- In-Memory Trie Cluster: Distribute the Trie in memory across nodes, sharding by prefix character (e.g., node 1 holds 'a-c', node 2 holds 'd-f') or by consistent hashing on prefix strings.
- Cache Layer: Edge CDN and client-side browser caching (Cache-Control: private, max-age=3600) for top search queries.
3. Offline Data Pipeline (Updating Frequencies):
- Real-time queries stream to Kafka -> Aggregated by Apache Flink or Spark Streaming every hour to compute frequency counts.
- Offline worker builds a new Trie snapshot weekly and deploys it to read-only memory replicas via blue/green rolling swaps.
4. Client Optimization:
- Frontend debounces keystrokes by 200ms to reduce unneeded network requests.