Chapter 5 · Hinglish · Sunne-wala Sabak
Consistent Hashing — Hash Ring ka Khel
Servers ke badalte hue set par keys ko spread karne ka tareeka, taaki node add ya remove hone par sirf thoda data shift ho. 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.
Mod-N kyun tootta hai Slide 2
Chapter paanch, consistent hashing. Pehle problem samjho. Keys ko servers par baantne ka sabse seedha tareeka hai, server barabar hash of key modulo N. Yaani key ka hash nikaalo, aur usko server count se modulo le lo. Yeh fast aur even hai, lekin sirf tab tak jab tak N nahi badalta. Jaise hi aap ek server add ya remove karte ho, modulo har key ke liye badal jaata hai, isliye lagbhag saari keys ek nayi bucket par chali jaati hain. Char servers se paanch par jaao to lagbhag assi percent cache ek saath invalid ho jaata hai. Cache ke liye yeh ek stampede hai, aur database ke liye yeh downtime hai.
Hash space ko ring banao Slide 3
Ab fix. Ek hash function lo jiska output space bahut bada ho, jaise ek sau atthais bit wale hash ka range. Us poore range ko end to end bichha do aur dono sire jod kar ek circle bana do. Ab har possible hash value ring par ek single point hai. Sabse important baat, servers aur keys dono isi ek ring par usi hash function se map hote hain. Ek server ki jagah sirf uske identifier par depend karti hai, kabhi node count par nahi. Isliye cluster resize karne se formula ko koi farak nahi padta.
Servers apni jagah claim karte hain Slide 4
Pehla step. Har node apne stable identifier ka hash leta hai, jaise uska IP, hostname, ya koi label. Hash of A, hash of B, aur aage bhi. Har output node ko ring par kahin rakh deta hai. Convention yeh hai ki ek server us arc ka maalik hota hai jo uski position par khatam hota hai, aur agla server clockwise uski seema banata hai. Zyadatar systems mein har node ke paas poori membership list ki copy hoti hai, isliye lookup bina kisi central coordinator ke locally answer ho jaata hai.
Key clockwise pehle server ki hoti hai Slide 5
Doosra step. Key ka hash lo, usko ring par rakho, aur clockwise chalo jab tak koi server na mile. Jo pehla server milta hai, key uski hoti hai. Yeh walk sirf conceptual hai, code mein yeh sorted node positions par ek binary search hai, isliye lookup order log N hai. Yahi ek rule reads, writes, aur replica placement, sab par chalta hai. Aur ring mein koi seam nahi hai. Agar koi key last server ke aage gir jaaye, to walk zero ke paar jaakar pehle server par pahunch jaata hai.
Node add ya remove, sirf ek arc badalta hai Slide 6
Ab elasticity. Maan lo ek naya server E, B aur C ke beech aata hai. Jo keys pehle E ko paar karke C tak jaati thi, ab woh E par hi ruk jaati hain, aur baaki kuch nahi hilta. Ring par kahin aur ki keys ka successor wahi rehta hai. Average mein, N nodes ke cluster mein join karne par sirf lagbhag ek upon N keys shift hoti hain, mod-N ki tarah saari nahi. Remove bilkul ulta hai. Agar koi server fail ho jaaye, to uski saari keys bas ek kadam aage chal kar agle surviving server clockwise par chali jaati hain. Koi doosra arc disturb nahi hota.
Chhota ring lumpy hota hai Slide 8
Lekin ek catch hai. Ek uniform hash keys ko sirf average mein even spread karta hai. Jab ek bade circle par sirf gine-chune random points hote hain, to kuch arcs doosron se kaafi zyada chaude ho jaate hain. Chaude arc ke clockwise end wala server keyspace ka, aur isliye traffic ka, bahut bada hissa own kar leta hai. Aur jab woh node fail hota hai, to uska poora arc ek hi neighbor par gir jaata hai, jiska load achanak double ho sakta hai aur woh bhi gir sakta hai. N char ya aath ho to yeh variance bahut saaf dikhta hai.
Virtual nodes load smooth karte hain Slide 9
Iska fix hai virtual nodes. Har server ko ek baar rakhne ke bajaay, usko dozen ya saikdon baar rakho. Har replica ek virtual node hai, jo A hash zero, A hash ek, A hash do, aise labels ka hash leke banta hai, lekin physical server hi har position ka maalik rehta hai. Ab law of large numbers humare favor mein kaam karta hai. Har physical server lagbhag barabar total arc length own karta hai, aur jab ek node marta hai to uske kayi chhote arcs kayi alag neighbors mein bant jaate hain, ek par cascade nahi hota. Ek bada machine ko zyada virtual nodes deke heterogeneous capacity bhi aasaani se set ho jaati hai. Cost sirf itna hai ki ring bada ho jaata hai aur thodi zyada memory leta hai.
Asli systems mein kahan milega Slide 10
Yeh pattern wahan dikhta hai jahan servers ke ek fleet ko yeh decide karna hota hai ki kaunsa server kaunsa data own karta hai, jabki niche churn chalta rehta hai. Teen families mukhya hain. Ek, distributed caches, jaise Memcached client libraries aur Ketama, jahan client request keys ko cache servers ke ring par hash karte hain. Do, partitioned databases, jaise Amazon Dynamo, Cassandra, aur Riak, jahan har row ki primary key ring par hash hoti hai aur owning node clockwise neighbors ko replicas bhejta hai. Teen, edge aur CDNs, jahan edge layer object ke URL ko hash karke decide karta hai ki kaunsa cache node usko serve karega.
Tradeoffs Slide 11
Consistent hashing ek problem solve karta hai aur kuch chhoti problems le aata hai. Ek, membership track karni padti hai, isliye zyadatar clusters ring ke upar ek gossip protocol lagate hain. Do, replica placement dhyaan se karna padta hai, kyunki agle clockwise nodes ek hi rack ya zone mein ho sakte hain, isliye rack aur region diversity ke liye kuch neighbors skip karne padte hain. Teen, virtual nodes ke baad bhi load statistical hai, isliye kuch shards garam chalte hain. Aur char, rebalance ke time keys kam shift hoti hain, lekin woh data physically copy karna padta hai, isliye transfer ko throttle karo taaki live reads aur writes bhukhe na rahein.
Chhah cheezein yaad rakho Slide 12
To chhah cheezein yaad rakho. Ek, hash space ek circle hai, list nahi. Do, har key agle server clockwise ki hoti hai. Teen, node ke join ya leave par sirf ek arc badalta hai, lagbhag ek upon N keys. Char, har server ke liye kayi virtual nodes use karo. Paanch, replicas ko sirf neighbors par nahi, alag failure domains par rakho. Aur chhah, rebalancing asal mein data movement hai, isliye usko pace karo.
Aage kya
Bas, yahi hai chapter paanch. Ek kaam karo, char cache servers banao, kuch keys mark karo, ek server ko maaro, aur trace karo ki har key kahan jaati hai, pehle mod-N mein aur phir ring par. Yeh contrast hi poora lesson ek picture mein dikha deta hai. Agle chapter mein hum apna pehla bada system design karenge, ek key-value store.