Chapter 13 · Hinglish · Sunne-wala Sabak
Search Autocomplete — Typing ke Saath Suggestions
Jab user type kar raha ho, tabhi likely query completions dikhana. Niche "Play all" dabaiye aur browser pura chapter padh kar sunayega. Kisi bhi section par "Suniye" se wahin se shuru karein.
▶ Companion slides kholiyeTip: jo voice sabse natural lage wahi chuniye — ek Hindi (hi-IN) ya Indian-English (en-IN) voice aam taur par best chalti hai.
Kya banana hai Slide 2
Chalo chapter terah shuru karte hain, search autocomplete system. Dikhne mein yeh ek simple lookup lagta hai, par actually mushkil hai. Wajah yeh hai ki yeh box user ke hot path par hai, aur har ek keystroke ek alag request hoti hai. Iska matlab reads writes se bahut zyada hote hain, aur latency sabse tough constraint ban jaati hai. Functional requirement chhoti hai, ek prefix do aur top K matching queries popularity ke hisaab se ranked wapas milen, aur jaise jaise user characters add ya delete kare list update hoti rahe. Non-functional requirements asli design decide karti hain. End to end latency lagbhag sau milliseconds se kam honi chahiye, ninety-ninth percentile par bhi. Freshness ghanton mein honi chahiye, dinon mein nahi. Aur throughput bahut zyada, kyunki har keystroke request banti hai, lagbhag das guna query rate. Ek chhota envelope, ek crore daily users, das queries per day, har query mein lagbhag chhah keystrokes, matlab lagbhag saath hazaar QPS peak par.
Trie — shared prefixes ka tree Slide 3
Yahan data structure hi asli design hai. Hum use karte hain ek trie, yaani prefix tree. Yeh strings ko ek ek character karke store karta hai, har edge par ek character. Isliye jitni bhi queries same prefix share karti hain, wo root se same path share karti hain. To jab hume nikalna ho ki swi se shuru hone wali saari queries kaunsi hain, to bas teen edges walk karo aur neeche wala subtree padho. Yeh cost hai order P, yaani prefix ki lambai. Yahi prefix sharing hi asli wajah hai ki autocomplete latency budget ke andar fit ho paata hai. Jo terminal node hai, matlab jahan ek poora word khatam hota hai, use hum alag mark karte hain.
Har terminal par frequency Slide 4
Trie sirf yeh batata hai ki kaunsi strings exist karti hain. Yeh nahi batata ki log kaunsi queries actually search karte hain. To rank karne ke liye hum har terminal node par ek frequency counter store karte hain. Yeh count batata hai ki wo exact query recent window mein kitni baar search hui, aksar ek sliding tees din ka count. Naye hits ko exponential decay se thoda zyada weight de sakte hain, taaki trends upar aa jaayen. Yeh count sirf terminal nodes par hota hai, beech wale nodes par nahi, kyunki wo poori query nahi hote. Aur yeh count offline aggregation job se banta hai, live request path par kabhi nahi. Sirf rank order maayne rakhta hai, absolute number nahi.
Naive lookup kyun fail hota hai Slide 5
Textbook algorithm ke chaar steps hain. Pehle prefix node tak utro, ek node per character. Yeh cost order P hai, sasta. Phir us subtree ka poora depth first search karo, har terminal collect karo, jo cost order N hai. Phir frequency ke hisaab se top K heap se nikalo. Problem yahan hai. Chhote aur popular prefix, jaise sirf s, ke neeche subtree mein millions of queries ho sakti hain. Har keystroke par, har user ke liye, itne saare nodes traverse karna latency budget ko orders of magnitude se cross kar deta hai. Prefix walk to free hai, asli killer hai subtree ka explosion.
Har node par top K cache karo Slide 6
Trick simple hai. Expensive read ko sasta banao, kaam pehle se kar ke rakh lo. Har prefix ke liye top K pehle se compute karke, us list ko usi node par store kar do. Ab lookup sirf itna hai, node tak walk karo aur uski cached list wapas kar do. Yeh total cost order P hai, matlab corpus ki size se independent, chahe neeche billions queries ho. Yeh wahi caching wali soch hai jo Key-Value Store chapter mein thi. Writes par compute karo, taaki reads bilkul trivial rahe. Query ab ek pointer chase ban jaati hai, jawaab wahin rakha hota hai jahan walk khatam hoti hai.
Speed ke badle memory — ab prune karo Slide 7
Kuch bhi free nahi hota. Har node par K strings store karne se memory lagbhag K guna badh jaati hai. Maan lo pachaas million nodes hain aur K das hai, to yeh lagbhag pachaas crore cached strings ho gaye. Yeh speed for memory ka trade hai. Achhi baat yeh hai ki memory ek knob hai, cliff nahi. Kuch pruning levers footprint wapas RAM ke andar le aate hain. Ek, minimum frequency cutoff, matlab jo queries bahut kam search hoti hain unhe drop kar do. Do, maximum prefix depth, lagbhag chhah depth ke baad precompute mat karo, kyunki deep prefixes ke candidates waise bhi kam hote hain, wahan quick DFS chalega. Teen, variable K, chhote hot prefixes ke liye zyada suggestions rakho, deep rare ke liye kam. Aur chaar, radix compression, single-child chains ko ek edge mein collapse kar do.
Trie offline banao query logs se Slide 8
Serving trie ek derived aur immutable artifact hai. Ek periodic batch job raw search logs padhta hai, unhe query se count mein aggregate karta hai, phir ek fresh trie banata hai jisme top K pehle se computed hoti hai, use ek blob mein serialize karta hai, aur serving fleet ko publish kar deta hai. Live request path kabhi state change nahi karta, wo sirf ek read-only structure padhta hai jo koi doosra pipeline banata hai. Jab naya blob ready ho, serving nodes atomic swap karte hain, purane se naye par, taaki koi reader kabhi aadha bana hua state na dekhe. Yeh pura kaam write side par hota hai, isliye read side par compute karne ko kuch bacha hi nahi.
Kitna fresh, kaafi fresh Slide 9
Batch rebuilds har kuch ghante mein naye trends de dete hain, jo zyadatar products ke liye kaafi hai, kyunki zyadatar queries minute minute par trend nahi karti. Path A hai delayed batch refresh. Har ek se chhah ghante mein trie rebuild karo aur atomic swap kar do. Simple, sasta, thoda stale, yahi sahi default hai. Path B hai streaming top-up, jab breaking news ya live event ko minute level freshness chahiye. Yahan query log ko Kafka ya Flink se real time tail karo, aur ek chhota mutable delta trie rakho jisme recently spike hui queries hon. Query time par base trie ki top K ko delta ki top K ke saath merge kar do. Yeh minutes mein fresh hota hai, par ab do systems ko sync rehna padta hai, aur delta har batch swap par wipe ho jaata hai. Isliye streaming ko default mat banao, sirf tab lo jab product ko sach mein chahiye.
Zyadatar keystrokes wahi kuch prefixes par Slide 10
Prefix popularity ek steep Zipf jaisi curve follow karti hai. Chhote prefixes ka ek chhota set hi zyadatar traffic le leta hai. Isliye ek cache cascade bahut effective hai. Sabse aage CDN edge un chhote, sabke liye common prefixes ko serve karta hai, lagbhag assi percent traffic, lagbhag paanch milliseconds mein. Jo miss ho jaaye wo regional Redis par jaata hai, longer aur per-locale variants, lagbhag pandrah percent traffic. Baaki sirf paanch percent long tail trie servers tak pahunchta hai. Invalidation lazy rakho, chhote TTL edge ko thoda stale rehne dete hain, aur har fresh trie deploy par ek version tag bump kar do taaki caches apne aap refill ho jaayen. Kabhi request ko cache ke intezaar mein block mat karo, jaldi fall through karo.
Trie shard karo jab ek box kam pade Slide 11
Pura trie ek single machine ki RAM se bada ho sakta hai. Do common partitioning schemes hain. Pehla, by first character. Ek shard a se c rakhta hai, doosra d se g, aur aise hi. Router pehle byte se shard chun leta hai. Routing to trivial hai, par load bahut skewed ho jaata hai, s wala shard bahut bada aur hot, z wala khali. Ise thoda theek karne ke liye hot ranges ko aur todo. Doosra, by hash of the prefix. Har prefix aur uski top K ko hash prefix modulo N par store karo. Load uniform ho jaata hai aur lookup ek hi hop, par ab trie structure shards ke beech share nahi hoti, to prefix slices duplicate ho jaati hain. Practically kai systems hash wala approach chunte hain, kyunki even load aur single hop lookup serving time par zyada maayne rakhte hain.
Yaad rakhne wale principles Slide 12
To chhah principles yaad rakho. Ek, data structure hi design hai, trie chunne se order P lookup aur prefix sharing mil jaate hain. Do, writes par precompute karo, reads par nahi, sabse sasta read wo hai jo bas ek pointer wapas kare. Teen, serving trie ko immutable maano, offline banao aur atomic swap karo. Chaar, freshness ko product se match karo, batch default, streaming sirf zaroorat par. Paanch, cache cascade traffic curve ko absorb kar leta hai. Aur chhah, memory ek knob hai, cutoff, depth cap, variable K, aur radix compression se tune karo.
Aage kya
Bas, yahi hai chapter terah. Ek line mein yaad rakho, autocomplete ka pura khel hai kaam ko read path se hata kar offline le jaana. Trie, precomputed top K, immutable build, aur cache cascade, yeh chaar milkar sau milliseconds ka budget bacha lete hain. Ek chhota exercise, socho ki agar ek query achanak viral ho jaaye, to use user tak dikhne mein kitna time lagega, batch swap se aur streaming delta se. Koi bhi part confuse kare to mujhse pooch lena. Agle chapter mein hum YouTube design karenge.