Chapter 6 · Hinglish · Sunne-wala Sabak
Key-Value Store — Ek Distributed Design
Ek hash map se shuru karke ek poore ring of replicas tak — replication, quorum, CAP, vector clock, Merkle tree aur LSM storage. Niche "Play all" dabaiye aur browser pura chapter padh kar sunayega. Kisi bhi section par "Suniye" se wahin se shuru karein.
▶ Companion slides kholेंTip: jo voice sabse natural lage wahi chuniye — ek Hindi (hi-IN) ya Indian-English (en-IN) voice aam taur par best chalti hai.
Hum kya bana rahe hain Slide 2
Chapter chha, ek distributed key-value store. API bahut chhoti hai, sirf do methods. put, jo ek key ke neeche value store karta hai. Aur get, jo us key ki sabse recent value wapas deta hai. Asli mushkil non-functional cheezon mein hai. Bahut saari keys, bahut zyada read aur write traffic, aur hundreds se thousands commodity nodes, kayi data centres mein faile hue. Do goals aapas mein tension mein rehte hain. Ek, availability, yaani store hamesha writable rahe, chahe koi replica, ek rack, ya poora zone down ho. Aur do, consistency, jo har operation ke liye tunable ho, par system khud chupke se decide na kare.
Single node, ek hash map Slide 3
Ek machine par key-value store banana bahut aasan hai. Ek in-memory hash map se put aur get constant time mein ho jaate hain, aur durability ke liye har write ko ek append-only commit log mein likh do ack dene se pehle. Lekin yeh reality mein survive nahi karta. Working set ko RAM mein fit hona padta hai, jo aapko jaldi rok deta hai. Ek kharab disk, ek kernel panic, ya ek cable nikal jaaye to saara data chala jaata hai. Aur vertical scaling sirf time khareedta hai, solution nahi. Yahi reason hai ki aage ka har section zaroori hai.
Keys ko ring par baanto Slide 4
Ek box se aage badhne ke liye keyspace ko consistent hashing se baanto. Key ko hash karo, ek circle par rakho, aur clockwise chal kar pehle node tak jaao. Iska fayda yeh hai ki simple key modulo N ke mukable, ek naya node add karne par ya purana node hatane par sirf lagbhag ek bata N keys move hoti hain, poora keyspace nahi. Virtual nodes ek hi physical machine ko kayi chhote arcs dete hain, jisse load even rehta hai aur powerful hardware ko zyada tokens diye ja sakte hain.
Replication, kabhi sirf ek copy nahi Slide 5
Ek replication factor N chuno, aam taur par teen. Jis node par ring point karta hai woh coordinator hai, aur uske aage clockwise N minus one nodes bhi value store karte hain. In sabko mila kar key ki preference list banti hai. Sabse important baat, aap aise replicas ko skip karte ho jo us rack ya zone mein hain jo pehle se list mein hai. Isse har key ki copies kam se kam do alag failure domains mein hoti hain. Warna ek hi rack down hone par teeno copies ek saath chali jaayengi.
CAP ka corner Slide 6
Jab data kayi machines par replicate hota hai, to network unke beech split ho sakta hai. Jab aisa partition hota hai, to aap ek saath strong consistency aur poori availability dono nahi de sakte. Aapko choose karna padega. CAP sirf partition ke dauraan bites karta hai, partition ke bahar aapke paas teeno ho sakte hain. CP system minority side par writes reject kar deta hai jab tak partition theek na ho, taaki koi stale ya conflicting state na dekhe, par kuch users ko error milte hain. AP system dono sides par writes accept karta rehta hai aur baad mein versions ko reconcile karta hai, par app ko purani ya conflicting value mil sakti hai. Shopping cart aur session ke liye banaya gaya store lagbhag hamesha AP hota hai.
N, W, R aur overlap rule Slide 7
AP ka matlab yeh nahi ki consistency hai hi nahi, matlab hai ki consistency ek dial hai. Teen knobs ise set karte hain. N, yaani har key ke replicas. W, yaani write success hone se pehle kitne acks chahiye. Aur R, yaani read return hone se pehle kitne responses chahiye. Sabse important rule yeh hai. Agar W plus R, N se bada ho, to har read set har write set se kam se kam ek replica par overlap karta hai. Wahi ek replica latest write rakhta hai, isliye read use dekh sakta hai. Jaise N teen ho, W do ho aur R do ho. Do plus do, teen se bada hai, isliye sets zaroor overlap karte hain. In knobs ko tune karke ek hi cluster fast writes aur strong reads dono de sakta hai.
Consistency ka asli matlab Slide 8
Quorum settings mechanism hain. Consistency models woh contract hain jo yeh mechanism application ko dete hain. Strong consistency mein har read sabse recent complete write deta hai, jaise ek hi global timeline ho, par ek slow ya partitioned replica operation ko block kar deta hai. Eventual consistency mein, agar writes ruk jaayein to sab replicas akhir mein same value par aa jaate hain, par beech mein reader ko purani value dikh sakti hai. Read your writes mein ek client kabhi apni hi writes ko peeche jaate nahi dekhta, jo user facing features ke liye ek practical middle ground hai. Iske alawa monotonic reads, causal consistency aur bounded staleness jaise flavours bhi hain, aur real systems inko mila kar use karte hain.
Vector clocks, kisne last likha Slide 9
Ek AP design mein, partition ke dauraan do clients ek hi key ko alag alag replicas par likh sakte hain. Store ko yeh detect karna padta hai aur ya to ek winner deterministic tareeke se chunna padta hai, ya dono versions application ko wapas dene padte hain. Ek vector clock har write par per replica counter lagaata hai, aur likhne wala replica apna counter badha deta hai. Agar ek version ke counters doosre se component wise chhote ya barabar hain, to woh causally ordered hain, naya rakho. Agar koi dominate nahi karta, to woh concurrent hain, dono ko siblings ke roop mein wapas do aur caller unhe merge kare, jaise cart items ko union karta hai. Last write wins simpler hai, par jab clocks disagree karein to woh chupke se ek write drop kar deta hai, isliye use sirf wahan use karo jahan ek write khona acceptable ho.
Replicas gayab ho jaayein to Slide 10
Hosts reboot hote hain, switches flap karte hain, garbage collectors ruk jaate hain. Ek AP store short lived failure ko ek routing problem maanta hai, data loss nahi. Sloppy quorum mein, agar preference list ka koi replica unreachable hai, to coordinator agle healthy node ko clockwise likh deta hai, aur W acks phir bhi aate hain. Hinted handoff mein, woh stand in node write par ek hint lagaata hai, jaise yeh asal mein node chhah ke liye hai. Jab node chhah wapas aata hai, to peers buffered hints replay kar dete hain aur data sahi jagah pahunch jaata hai. Aur failure detection ke liye ek gossip protocol heartbeats faila deta hai, taaki har node ko pata rahe kaun zinda hai, bina kisi central master ke.
Merkle tree se anti-entropy Slide 11
Hints sirf kuch minute cover karte hain. Jab ek replica itni der gayab rahe ki hints expire ho jaayein, to do replicas ko apne poore keyspaces compare karne padte hain aur jo missing hai woh copy karna padta hai. Par poora scan bahut mehnga hota hai. Ek Merkle tree har keyspace range ko ek leaf mein hash karta hai, phir children ko upar ek single root fingerprint tak hash karta hai. Do replicas pehle sirf root exchange karte hain. Agar barabar hai, to woh already in sync hain. Agar nahi, to woh sirf un subtrees mein descend karte hain jinke hashes alag hain, aur thode comparisons mein exact divergent ranges dhoond lete hain. Yeh ek periodic background repair ke roop mein bhi chalta hai aur silent disk corruption bhi pakad leta hai.
Write path, commit log se SSTable Slide 12
Har node ka storage engine ek LSM tree hai. Yeh writes ko sasta banaata hai random updates ko sequential appends mein badal kar. Ek write pehle ek durable commit log mein append hota hai aur fsync kiya jaata hai, phir ek in memory sorted memtable mein insert hota hai. Jab memtable bhar jaata hai, to use freeze karke disk par ek immutable sorted SSTable ke roop mein flush kar diya jaata hai. Baad mein background compaction in SSTables ko merge karta hai, purane versions aur tombstones ko drop karta hai, aur disk debt ko chupke se chukaata rehta hai.
Read path, bloom filter ke saath Slide 13
Kyunki kisi key ka newest version memtable mein ho sakta hai ya kayi SSTables mein, ek read kayi files ko touch kar sakta hai. Yahi LSM design ka read amplification cost hai. Bloom filter ise sane rakhta hai. Yeh ek chhota probabilistic structure hai har SSTable ke liye, jo kehta hai definitely not here, ya possibly here, jisse engine zyaadatar files ko bina disk seek ke skip kar deta hai. Pehle memtable check karo, ek hit microseconds mein wapas aata hai. Phir har SSTable ka bloom filter poocho. Phir candidate file ke liye block index ek block par point karta hai aur wahi ek block padha jaata hai. Aur agar key kayi jagah mile, to highest sequence number ya timestamp wala version rakho.
Chha cheezein yaad rakho Slide 14
To chha cheezein yaad rakho. Ek, hash karo, modulo nahi, taaki node join ya leave ka cost ek bata N rahe. Do, alag alag failure domains mein replicate karo, teen copies teen racks mein. Teen, consistency ko ek knob banao, N, W aur R per request expose karo. Chaar, divergence ke liye plan karo, aise data types banao jo gracefully merge hon, counters jo sum karein, sets jo union karein. Paanch, sirf retry nahi, repair bhi karo, hinted handoff minutes ke liye aur Merkle tree anti-entropy hours aur days ke liye. Aur chha, random writes ko sequential banao, commit log plus memtable plus SSTable se sasti durable writes milti hain.
Aage kya
Bas, yahi hai chapter chha. Ek distributed key-value store koi ek badi idea nahi hai, balki chhote chhote sahi mechanisms ki ek careful stack hai. Ek kaam karo, ek shopping cart ke liye W aur R chuno jo kabhi koi write na khoye, aur use loud defend karo. Agle chapter mein hum ek distributed unique ID generator design karenge.