Loading…
Loading…
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
A naive approach — scanning every stored query string to check if it starts with the user's typed prefix — is O(n * m) per keystroke (n = number of stored strings, m = average string length), and gets slower as the dataset grows, with no way to bound latency as query volume scales. A Trie makes prefix lookup O(m) — proportional only to the LENGTH of the typed prefix, completely independent of how many total strings are stored — because each character typed simply walks one level deeper into the tree structure, arriving at the relevant subtree directly rather than scanning anything. This is exactly why sub-100ms autocomplete latency at scale is achievable with a Trie and effectively impossible with naive substring scanning once the dataset is large.
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.
Q: Why precompute top suggestions per prefix instead of searching the trie at request time? A: Walking a large trie subtree and ranking all its completions on every keystroke is too slow at high query rates. Storing the top-k completions directly in each prefix node (or in a prefix → suggestions key-value store) makes each lookup O(prefix length) or a single key fetch. Rankings change slowly, so they can be rebuilt offline.
Q: How often should suggestion rankings be updated, and how? A: Aggregate query logs in batch jobs, hourly or daily, weighting recent queries more heavily, and rebuild the per-prefix top-k lists. For trending topics that need to appear within minutes, add a small streaming layer that counts recent queries and merges hot items into the served results. A full rebuild on every search would be too expensive, and too noisy.
Q: How do you keep latency low when the user types quickly? A: Several ways. Debounce requests on the client (wait roughly 100–150 ms after the last keystroke). Cancel outdated in-flight requests. Cache responses for popular prefixes at the edge and in the browser. Serve from in-memory stores replicated close to users. Short prefixes are the hottest, and nearly identical for everyone, so they cache extremely well.
Q: How do you personalize suggestions without losing the benefits of caching? A: Serve the global top-k from cache, then blend in a small number of user-specific candidates (recent searches, items related to their history) in a lightweight re-ranking step. That keeps the expensive, shared part cacheable, and makes only the small personal part per-user.
Q: How should offensive or unsafe suggestions be handled? A: Filter candidates against block lists and classifier scores during the offline build, and apply a fast final filter when serving, so newly blocked terms disappear immediately without waiting for the next rebuild. Suggestions are effectively published content, so they need a moderation path.
Q: How do you shard the suggestion data? A: Shard by prefix, for example by the first one or two characters. Uneven prefix popularity creates hot shards, though, so a better approach is hashing prefixes across shards and replicating the hottest short prefixes widely. Each shard can hold its data entirely in memory.