Design a real-time search autocomplete feature like Google's search bar. As the user types, show the top 5 matching suggestions within 100ms. Suggestions should be ranked by query popularity.
[User types in search box]
↓ (every keystroke, debounced 100ms)
[Autocomplete API]
│
├── Redis Cache ──→ HIT: return cached top-5
│
└── MISS: query Trie Service
│
[Trie Service] → in-memory Trie
│
top-5 → cache in Redis (TTL: 1 hour)
│
return to client
[Background]
[Query Logger] → Kafka → [Frequency Aggregator]
│
hourly batch → update Trie weights
GET /autocomplete?q=java&limit=5&userId=optional
Response:
{
"suggestions": [
{ "text": "java interview questions", "frequency": 1500000 },
{ "text": "java stream api", "frequency": 980000 },
{ "text": "java 21 features", "frequency": 750000 },
{ "text": "java concurrency", "frequency": 680000 },
{ "text": "java spring boot", "frequency": 590000 }
]
}
Root
└── 'j'
└── 'a'
└── 'v'
└── 'a' ← TrieNode { topSuggestions: ["java interview...", "java stream api", ...] }
├── ' ' → 'i' → 'n' → ...
└── 's' → 'c' → ...
Optimisation: store top-K suggestions at each node to avoid traversal on read:
class TrieNode {
Map<Character, TrieNode> children;
List<Suggestion> topK; // pre-computed top-5 at this node
}
This makes read O(P) where P = prefix length (not O(subtree size)).
Storage: Serialize trie to disk (protobuf). Load into memory on service start.
We cannot lock and rebuild the trie on every query. Strategy:
Top-K prefixes by request volume are cached in Redis with a 1-hour TTL. The top 1000 prefixes serve 80% of traffic — these fit in <10 MB of Redis.
If trie is too large for one node: partition by first character (26 shards, or by first 2 characters for 676 shards). Route prefix to correct shard.