12. Consistent Hashing with Virtual Nodes (Solving Cache Clustering & Dynamic Scaling) • High-Level System Design (HLD): Distributed Systems at Scale • Rishabh Ki Kaksha

Agar hum standard hashing use karein: $\text{Server} = \text{hash}(\text{key}) \pmod N$
*   Agar cluster me 4 servers se badhakar **5 servers ($N=5$)** kar diye jayein:
*   **99% keys ka mapped server badal jayega!** Natija: **Massive Cache Wipeout & Database Crash!**

---

### 2. Consistent Hashing Ring ($2^{32} - 1$ Ring Architecture 💍)

Keys aur Servers dono ko ek continuous Circular Ring $[0, 2^{32}-1]$ par hash kiya jata hai.  
Kisi key ko locate karne ke liye ring par **Clockwise search karke pehla server pick kiya jata hai!**

```
                  [ Server A (Hash: 100) ]
                       /           \
         [ Key 1 ] ➔ Clockwise ➔ [ Server B (Hash: 5000) ]
                       \           /
                  [ Server C (Hash: 15000) ]
```
*When adding Server D:* Sirf Server D aur uske piche wale server ke beech ki **$\frac{K}{N}$ keys migrate hoti hain** (99% baki keys un-affected rehti hain!).

---

### 3. Virtual Nodes (Eliminating Non-Uniform Hotspots 👑)

Agar 3 physical servers ring par paas-paas hash ho jayein, toh Server A par 80% traffic gir sakta hai (Hotspot!).  
**Virtual Nodes:** Har physical server ke **100 se 200 virtual replicas** (`ServerA#1`, `ServerA#2`, `ServerA#3`) ring par uniformly scatter kiye jaate hain!

---

### 4. Master Comparison Matrix

| Hashing Scheme | Keys Migrated on Server Add/Remove | Load Distribution |
| :--- | :--- | :--- |
| **Traditional Modulo (`hash % N`)**| 💥 **~100% Cache Miss (Disaster!)** | High variance |
| **Consistent Hashing** | ⚡ **Only $\frac{1}{N}$ keys migrated** | Non-uniform without virtual nodes |
| **Consistent Hashing + V-Nodes**| ⚡ **Only $\frac{1}{N}$ keys migrated** | 🛡️ **Near-Perfect Uniform Distribution** |

---

### 5. Interview Ke 3 Sawal Is Topic Se

1. **Amazon DynamoDB aur Apache Cassandra me Consistent Hashing kaise use hoti hai?** -> Data partitioning aur replica placement ring par clockwise adjacent $N$ physical nodes par replicate karne ke liye.
2. **Consistent hashing me key lookup $O(\log S)$ time me kaise hota hai?** -> Sorted array of virtual node hashes par Binary Search (`std::lower_bound` / `bisect_left`) run karke.
3. **Weight-based consistent hashing kaise implement hoti hai?** -> Powerful bare-metal server (64 Cores) ko 500 virtual nodes assign karna aur chhote server (8 Cores) ko 50 virtual nodes assign karna.

---
**Next Topic:** 13. Content Delivery Networks (CDN): Edge Caching, Dynamic Site Acceleration & Origin Shielding

Loading lesson content...

Python 3.12

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track