Search Autocomplete System
Data structure TRIE hai — prefix ke saath tree traverse karke aage ke suggestions milte hain. Par har node par top-K suggestions PRECOMPUTED honi chahiye, warna har query par poora subtree scan karna padega. Trie memory mein rehta hai aur read-only serve hota hai.
Update path bilkul alag hai. Trie real-time update NAHI hota — search logs Kafka mein jaate hain, ek batch job (har ghante ya din) frequencies aggregate karta hai aur naya trie build karke atomically swap kar deta hai. Ye batana ki "read path aur write path alag hain" is problem ka core insight hai.
// Read path — 100ms budget, sab memory mein
Keystroke → CDN/edge cache → Trie service (in-memory)
→ node par precomputed top-5 → return
// Write path — offline, batch
Search logs → Kafka → aggregation job (hourly)
→ naya trie build → atomic swap- Trie with precomputed top-K per node — runtime scan nahi
- Read path in-memory, update path offline batch + atomic swap
- Debounce aur edge caching se traffic bahut ghat jaata hai
Global top-K sabke liye same suggestions deta hai. Personalization ke liye user ke apne search history se suggestions merge kiye jaate hain — ye chhota per-user data hai jo alag store se aata hai aur global results ke saath blend hota hai.
Freshness ka alag problem hai — trending topic (breaking news) global trie mein aane mein ghante lag sakte hain. Iske liye ek chhota REAL-TIME layer rakha jaata hai jo last few minutes ke trending terms rakhta hai aur trie results ke upar merge hota hai.
suggestions =
merge(
trie.topK(prefix), // global, hourly batch
trending.topK(prefix), // real-time, last 15 min
userHistory.match(prefix) // personal
).rank().take(5)Poora trie ek machine ki memory mein na aaye to shard karna padta hai — aksar pehle character ya pehle do characters par. "a" se shuru hone wale queries ek shard par, "b" doosre par.
Load uneven hota hai (kuch letters zyada common hain), isliye shards ko usage ke hisaab se balance karna padta hai. Har shard replicated hota hai availability aur read throughput dono ke liye.