05 Β· Consistent Hashing Design karo¶
TL;DR
server = hash(key) % Nkeys ko barabar baant-ta hai β jab tak N na badle. Badla toh lagbhag har key alag server pe chali jaati hai β cache-miss ka toofan / bahut saara data move.- Consistent hashing servers aur keys dono ko ek ring pe rakhta hai (hash space ko gol mod diya). Key ka maalik hai clockwise chalte hue pehla server.
- Server add/remove karne pe sirf ring ke ek arc ki keys move hoti hain β average k/n keys (k keys, n servers), lagbhag saari nahi.
- Plain ring mein arcs uneven hote hain. Fix: virtual nodes β har server ring pe 100β200 jagah aata hai, toh load barabar ho jaata hai (std-dev ~5β10%).
- Sorted map (
TreeMap.ceilingEntry) se implement karo β O(log V) lookup. Dynamo, Cassandra, Riak, Discord, Akamai, Envoy/Maglev-style LBs use karte hain.
Intuition: students ko exam halls mein bhejna¶
College students ko halls mein roll_number % halls_ki_ginti se bhejta hai. Mast chalta hai β jab tak exam ki subah ek hall
ka AC kharab na ho jaaye. Ab % 4 ki jagah % 3, aur lagbhag har student alag hall mein bheja jaata hai, sirf kharab hall
waale nahi. Har darwaze pe hungama.
Smart rule: halls ko ek gol corridor mein lagao; har student apne "seat number" waali jagah se clockwise chale aur pehle khule hall mein ghus jaaye. Ek hall band hua toh sirf uske students thoda aage agle hall tak chalte hain. Baaki sab pe koi asar nahi. Yahi consistent hashing hai.
Rehashing problem¶
N cache servers hon toh server chunne ka seedha tareeka:
4 servers aur 8 keys lete hain. (Maan lo hash() yeh chhote numbers deta hai taaki hisaab aasaan rahe.)
| Key | hash | hash % 4 | Server (N = 4) |
|---|---|---|---|
| user:alpha | 10 | 2 | S2 |
| user:bravo | 21 | 1 | S1 |
| user:charlie | 32 | 0 | S0 |
| user:delta | 43 | 3 | S3 |
| user:echo | 54 | 2 | S2 |
| user:foxtrot | 65 | 1 | S1 |
| user:golf | 76 | 0 | S0 |
| user:hotel | 87 | 3 | S3 |
Har server pe exactly 2 keys β khoobsurat. Ab S1 crash ho gaya. Pool [S0, S2, S3] hai, toh % 3:
| Key | hash % 3 | Naya server | Move hui? |
|---|---|---|---|
| user:alpha | 1 | S2 | β wahin |
| user:bravo | 0 | S0 | β (zaroori tha β S1 mar gaya) |
| user:charlie | 2 | S3 | β bina wajah move |
| user:delta | 1 | S2 | β bina wajah move |
| user:echo | 0 | S0 | β bina wajah move |
| user:foxtrot | 2 | S3 | β (zaroori tha β S1 mar gaya) |
| user:golf | 1 | S2 | β bina wajah move |
| user:hotel | 0 | S0 | β bina wajah move |
8 mein se 7 keys move hui, jabki dead server pe sirf 2 thi. Cache ke liye iska matlab hai achanak cache misses ka toofan jo database ko pit deta hai. Sharded database ke liye matlab zyada tar data move karna. General rule: N se NΒ±1 servers pe jaane se lagbhag N/(N+1) keys relocate hoti hain β almost sab kuch.
Consistent hashing¶
Consistent hashing aisi hashing scheme hai jisme slots ki ginti badalne pe average sirf k/n keys move karni padti hain (k = keys, n = slots), lagbhag saari nahi.
Step 1 Β· Hash space ring ban jaata hai¶
Badi output range waala hash function lo β jaise SHA-1 ka output 0 β¦ 2ΒΉβΆβ° β 1 (practice mein systems MurmurHash ya xxHash jaise tez non-cryptographic hashes 32/64-bit range ke saath use karte hain). Is range ko gol mod do, taaki sabse bade value ke baad 0 aaye. Yahi hai hash ring.
Step 2 Β· Servers ko ring pe rakho¶
Har server ke naam ya IP ko same hash function se hash karo, aur us point pe ring pe rakh do.
Step 3 Β· Keys ko ring pe rakho¶
Har key ko same ring pe hash karo. Dhyaan do: ab % N nahi hai.
Step 4 Β· Lookup β clockwise chalo¶
Key us server pe store hoti hai jo key ki position se clockwise chalte hue pehla milta hai.
Server add karna¶
S4 ko ring pe k0 aur S0 ke beech add karo. k0 se clockwise chalne pe ab pehla server S4 hai, toh sirf k0 move hoti hai (S0 se S4 pe). k1, k2 aur k3 bilkul nahi hilti.
Kaunsi keys move hoti hain? Exactly woh jo S4 aur anticlockwise pichle server (S3) ke beech ke arc mein hain. Pehle woh S0 ki thi; ab S4 le leta hai.
Server hatana¶
S1 hatao. Sirf S0 (anticlockwise padosi) aur S1 ke beech ke arc ki keys β yahan k1 β move hoti hain, aur agle clockwise server (S2) pe jaati hain. Baaki sab wahin rehte hain.
flowchart LR
subgraph B1["Pehle"]
direction LR
a1["S0 arc"] --- b1["S1 arc Β· k1 yahan"] --- c1["S2 arc"]
end
subgraph A1["S1 hatne ke baad"]
direction LR
a2["S0 arc"] --- c2["S2 arc Β· ab k1 bhi yahin"]
end
B1 -->|"sirf S1 ke arc ka maalik badla"| A1
Khud try karo β servers add/remove karo, aur dekho hash % N ke muqable kitni keys move hoti hain:
Widget mein kya notice karna hai
Har server ka 1 virtual node ho toh load bars bahut uneven hain aur "max/avg" aksar 2Γ ya usse bura. Virtual nodes ko 50+
tak le jao aur dekho spread 1.1Γ ki taraf simat jaata hai. Phir server add karo: consistent hashing lagbhag 1/(N+1) keys move
karta hai; hash % N zyada tar keys hila deta hai.
Basic ring ki do problems¶
- Uneven partitions. Servers random points pe girte hain, toh unke beech ke arcs random size ke hote hain. Ek server ring ka 40% own kar sakta hai aur doosra 5%. Aur server hatne pe uska poora arc ek hi padosi ko milta hai, jis pe achanak double load aa jaata hai.
- Non-uniform key distribution. Arcs barabar hon tab bhi asli keys cluster ho sakti hain (hot ranges), aur ek server pe dher lag jaata hai.
Virtual nodes (vnodes)¶
Har physical server ko ek baar rakhne ki jagah kai baar rakho β jaise S0#0, S0#1, β¦ S0#199 β har ek ek virtual node
jo wapas physical server S0 pe map hota hai.
flowchart LR
subgraph Ring["Ring positions (clockwise)"]
direction LR
a["S0 Β· v3"] --> b["S2 Β· v7"] --> c["S1 Β· v0"] --> d["S0 Β· v9"] --> e["S2 Β· v1"] --> f["S1 Β· v5"] --> g["S0 Β· v4"] --> h["S1 Β· v2"] --> i["S2 Β· v4"]
end
Yeh kaam kyun karta hai:
- Har server ab ring pe bikhre kai chhote arcs own karta hai, toh uska total share average ho jaata hai. Har server ke ~100 vnodes ke saath load ka standard deviation mean ka lagbhag 10%; ~200 ke saath lagbhag 5%.
- Server jaane pe uske kai chhote arcs kai alag padosi sokh lete hain β load ek server pe girne ki jagah phail jaata hai.
- Alag-alag hardware: bade server ko 300 vnodes do aur chhote ko 100 β bade ko ~3Γ keys milengi.
Keemat: ring ki zyada entries store karni (metadata) aur membership badalne pe thoda zyada kaam. Sorted structure ke saath yeh kuch bhi nahi β 100 servers Γ 200 vnodes = 20,000 entries.
Java mein implementation¶
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.*;
public final class ConsistentHashRing<N> {
private final NavigableMap<Long, N> ring = new TreeMap<>();
private final int virtualNodes;
public ConsistentHashRing(int virtualNodes) { this.virtualNodes = virtualNodes; }
public synchronized void addNode(N node) {
for (int i = 0; i < virtualNodes; i++) ring.put(hash(node + "#" + i), node);
}
public synchronized void removeNode(N node) {
for (int i = 0; i < virtualNodes; i++) ring.remove(hash(node + "#" + i));
}
/** Key ki position se clockwise pehla node (end pe wrap around). */
public synchronized N nodeFor(String key) {
if (ring.isEmpty()) throw new IllegalStateException("no nodes");
Map.Entry<Long, N> e = ring.ceilingEntry(hash(key));
return (e != null ? e : ring.firstEntry()).getValue();
}
/** Clockwise N alag physical nodes β replica "preference list" (Chapter 6). */
public synchronized List<N> nodesFor(String key, int replicas) {
LinkedHashSet<N> out = new LinkedHashSet<>();
for (N n : ring.tailMap(hash(key), true).values()) { out.add(n); if (out.size() == replicas) return new ArrayList<>(out); }
for (N n : ring.values()) { out.add(n); if (out.size() == replicas) break; }
return new ArrayList<>(out);
}
private static long hash(String s) {
try {
byte[] d = MessageDigest.getInstance("MD5").digest(s.getBytes(StandardCharsets.UTF_8));
long h = 0;
for (int i = 0; i < 8; i++) h = (h << 8) | (d[i] & 0xff); // pehle 64 bits
return h;
} catch (Exception e) { throw new RuntimeException(e); }
}
}
- Lookup red-black tree pe
ceilingEntryhai β O(log V), jahan V = total virtual nodes. - MD5 yahan sirf isliye kyunki JDK mein hai; production systems MurmurHash3 / xxHash use karte hain (bahut tez, non-cryptographic).
- Har client (ya router) ko same ring dikhni chahiye. Membership aam taur pe gossip se phailti hai ya ZooKeeper/etcd jaisi coordination service mein rehti hai (Chapter 6).
Thoda gehraai mein: alternatives jo bata sakte ho¶
| Technique | Idea | Kyun/kab |
|---|---|---|
| Rendezvous (HRW) hashing | Har key ke liye har server ka score = hash(key, server) nikalo; sabse bada wala chuno |
Na ring, na vnodes; perfectly even; har lookup O(N) β das-bees servers ke liye theek |
| Jump consistent hash (Google) | Ek chhota arithmetic function key β bucket 0..Nβ1 map karta hai, minimal movement ke saath | O(ln N), memory nahi β par buckets sirf end pe add/remove ho sakte hain (numbered shards ke liye mast, random node failures ke liye bura) |
| Maglev hashing (Google LB) | Fixed-size lookup table banata hai, lagbhag perfect balance | Load balancers ke liye bahut tez lookups; changes pe chhota disruption |
| Bounded loads ke saath consistent hashing | Har server ko average ke (1+Ξ΅) Γ pe cap karo; overflow agle server pe | Hotspots rokta hai β kuch proxies/caches use karte hain (jaise HAProxy option, Vimeo) |
Asli duniya mein kahan use hota hai¶
- Dynamo-style databases mein partitioning β Amazon Dynamo, Apache Cassandra, Riak (Chapter 6 isi pe banta hai).
- Discord β kisi guild/channel ka chat traffic sahi server pe route karna.
- Akamai β 1997 ka original paper CDN servers pe web caches baantne ke baare mein tha.
- Load balancers / proxies β Envoy ki ring-hash aur Maglev load-balancing policies, NGINX
hash β¦ consistent. - Distributed caches β Memcached client libraries (ketama), Redis client-side sharding.
Interviewer follow-ups¶
Server add karne pe exactly kaunsi keys move hoti hain?
Sirf woh keys jinki position naye server aur anticlockwise pichle server ke beech ke arc mein hai. Woh naye server ke clockwise successor se naye server pe aati hain. Vnodes ke saath yeh kai chhote arcs hain β har naye vnode ka ek β aur har ek alag successor se keys leta hai, toh load existing servers se barabar khinchta hai.
Kitne virtual nodes use karein?
Itne ki load imbalance tumhari tolerance ke andar aa jaaye β aam taur pe har server ke 100β256. Zyada vnodes = better balance par zyada metadata aur membership change pe zyada ring entries update. Cassandra ka purana default har node pe 256 tokens tha, baad mein smarter token-allocation algorithm ke saath kam (jaise 16) recommend kiye.
Consistent hashing keys barabar baant-ta hai β kya isse load barabar ki guarantee hai?
Nahi. Yeh key count balance karta hai, traffic nahi. Ek hot key (celebrity profile, viral video) phir bhi ek server pe hi
girti hai. Mitigations: hot keys ko aage cache karo, hot keys ko kai servers pe replicate karke reads baanto, key ko tod do
(key#1..#n), ya bounded-load consistent hashing use karo.
Clients ko current ring kaise pata chalti hai?
Ya toh (1) ek router/proxy tier ring own karta hai aur clients usse baat karte hain; ya (2) har node ke paas ring hai aur membership changes gossip se phailte hain; ya (3) coordination service (ZooKeeper/etcd) membership store karti hai aur clients use watch karte hain. Changes ke dauraan thodi der ki asehmati tolerate hoti hai β jis node pe galat key aaye woh forward kar deta hai.
hash % N use karke offline re-shard kyun nahi kar lete?
Cache ke liye re-sharding matlab miss storm jo database gira sakta hai. Database ke liye matlab ~100% data move karna, jiske dauraan double-reads ya downtime chahiye. Consistent hashing membership changes ko sasta aur incremental banata hai, jo scale pe zaroori hai jahan nodes roz fail hote hain.
Practice¶
Practice 1 β Kitna hissa move hoga
Consistent hashing (bahut vnodes) ke saath 9 cache servers aur 9 crore keys hain. 10th server add karte ho. Roughly kitni keys
move hongi? Agar hash % N use karte toh?
Solution. Consistent hashing: naya server ring ka ~1/10 leta hai β ~90 lakh keys move.
hash % N: key tabhi wahin rehti hai jab h % 9 == h % 10, jo ~1/10 keys ke liye hota hai β ~8.1 crore keys move (90%).
Practice 2 β Weighted servers
Teen servers hain jinki RAM 64 GB, 64 GB aur 128 GB hai. 128 GB waale ko double keys kaise do?
Solution. Use double virtual nodes do (jaise 200, 200, 400). Uska ring share β 400/800 = 50%, baaki dono 25% each.
Practice 3 β Lookup trace karo
Ring positions (0β99): S_A 15 pe, S_B 40 pe, S_C 72 pe. Keys ke hash 5, 16, 40, 41, 80, 99 hain. Har ek ka maalik kaun? Phir S_B hata diya β ab kaun?
Solution. Clockwise pehla server β₯ key (wrap ke saath): 5βS_A, 16βS_B, 40βS_B (barabar ho toh wahi maalik), 41βS_C, 80βS_A (wrap), 99βS_A. S_B hatne ke baad: 16βS_C, 40βS_C; baaki sab same. Sirf S_B ki 2 keys move hui.
Revision checklist¶
- Numbers se dikha sakta hoon ki N badalne pe
hash % Nzyada tar keys kyun relocate karta hai. - Ring, clockwise lookup, aur add/remove pe exactly kaunsi keys move hoti hain β samjha sakta hoon.
- Basic ring ki do problems aur virtual nodes unhe kaise fix karte hain (weighting ke saath) β samjha sakta hoon.
-
TreeMapse ring implement kar sakta hoon aur usse N replicas nikaal sakta hoon. - Pata hai ki keys ka barabar spread β barabar traffic, aur hot keys kaise handle karein.
- Ise use karne waale real systems aur kam se kam do alternatives (rendezvous, jump hash) bata sakta hoon.