Deep Dive 01 — Consistent Hashing
Deep Dive 01 — Consistent Hashing
Hey everyone! Welcome to the Deep Dives — where we open the black boxes! 🙏
Back in Chapter 08 (Sharding) we hit a nasty wall: with hash(key) % N, adding one server reshuffles almost all your data. That's a catastrophe at scale. Consistent hashing is the beautiful idea that fixes it — and it powers Cassandra, DynamoDB, and load balancers everywhere. Let's truly understand it.
What we will cover:
- Why
mod Nis a disaster when N changes - The hash ring — the core idea
- How keys map to nodes on the ring
- Adding/removing a node moves only a few keys
- Virtual nodes — fixing uneven distribution
- Interview Questions
1. The Problem: mod N Reshuffles Everything
3 servers, key placement = hash(key) % 3: key "apple" → hash 100 → 100 % 3 = 1 → Server 1 key "mango" → hash 101 → 101 % 3 = 2 → Server 2 key "grape" → hash 102 → 102 % 3 = 0 → Server 0 Now add a 4th server → hash(key) % 4: key "apple" → 100 % 4 = 0 → Server 0 (MOVED!) key "mango" → 101 % 4 = 1 → Server 1 (MOVED!) key "grape" → 102 % 4 = 2 → Server 2 (MOVED!) Almost EVERY key moved. For a cache, that means a near-total MISS storm; for a DB, a massive migration. 😭
We need a scheme where adding/removing a node moves only a small fraction of keys. Enter the ring.
2. The Hash Ring
Imagine a clock face — a circle of hash values from 0 to a huge number, wrapping around. We place both servers and keys on this same ring by hashing them.
0 / MAX
│
S3 ◀─────┼─────▶ S1
/ │ \
/ │ \
270° ●ring 90°
\ (0..2^32) /
\ │ /
S2 ◀──────┼──────▶ ...
│
180°
Servers S1, S2, S3 are hashed onto points around the ring.
3. How Keys Find Their Server
RULE: to place a key, hash it onto the ring, then walk
CLOCKWISE until you hit the first server. That server owns it.
S1
/ \
key "x"● \ "x" walks clockwise → first server
/ \ it meets is S1 → S1 owns "x".
S2──────S3
Each server owns the arc of the ring BEFORE it (up to the
previous server). Keys are spread around the circle.
4. The Magic: Adding/Removing a Node
Here's the payoff. When you add a server, only the keys in one arc move — everything else stays put.
BEFORE: S1, S2, S3 on the ring.
ADD S4 between S2 and S3:
S1
/ \
S2 S3
\ /
S4 ← new
ONLY the keys that fall between S2 and S4 move (they used to
go to S3, now they stop at S4 first). Every other key is
UNAFFECTED. 🎉
Removing a node is symmetric: only ITS keys move to the next
server clockwise. Nothing else is disturbed.
mod N: nearly 100% of keys move on a change 😭 consistent hashing: only ~1/N of keys move on a change 😎
5. The Catch: Uneven Distribution → Virtual Nodes
Random placement of 3 servers can be lopsided — one server might land such that it owns a huge arc while another owns a tiny one. Also, removing a node dumps all its keys onto a single neighbor.
PROBLEM: uneven arcs → uneven load.
S1 owns a HUGE arc 🔥, S2 & S3 own tiny arcs 😴
Solution — virtual nodes (vnodes): instead of placing each server once, place it at many points around the ring (e.g. S1 appears as S1-a, S1-b, S1-c... 100+ times).
Each physical server = MANY virtual points scattered around
the ring:
S1-a S2-a S3-a S1-b S3-b S2-b S1-c ...
(interleaved all around the circle)
→ Load is now SMOOTH & even (law of large numbers).
→ Remove a server → its many small arcs spread across MANY
neighbors, not dumped on one. 🌟
→ Bigger servers can get MORE vnodes → proportionally more load.
Virtual nodes are why real systems (Cassandra, DynamoDB) use consistent hashing successfully — they make the distribution both even and gracefully rebalancing.
Interview Questions — Quick Fire!
Q: What problem does consistent hashing solve?
"It solves the massive reshuffling problem of simple modulo hashing. With hash mod N, changing the number of nodes remaps almost every key, causing a cache-miss storm or a huge data migration. Consistent hashing ensures that adding or removing a node moves only a small fraction — roughly one over N — of the keys, so the system rebalances gracefully."
Q: How does consistent hashing work?
"Both servers and keys are hashed onto a circular ring of hash values. To find which server owns a key, you hash the key onto the ring and walk clockwise to the first server you encounter — that server owns it. Each server is responsible for the arc of the ring leading up to it. When a node is added or removed, only the keys in the affected arc move; the rest stay put."
Q: What are virtual nodes and why do we need them?
"With only one point per server, random placement can create very uneven arcs, so load is unbalanced, and removing a node dumps all its keys onto a single neighbor. Virtual nodes fix this by placing each physical server at many points around the ring. This smooths the distribution evenly, spreads a removed node's keys across many neighbors, and lets more powerful servers take proportionally more load by assigning them more virtual nodes."
Q: Which real systems use consistent hashing?
"Distributed databases like Cassandra and DynamoDB use it to partition data across nodes, distributed caches like Memcached clients use it to spread keys, and it's used in load balancing. Anywhere you need to distribute data or requests across a changing set of nodes without massive reshuffling, consistent hashing is the standard tool."
Key Points to Remember
| Concept | Key Takeaway |
|---|---|
| The problem | hash mod N moves ~all keys when N changes → catastrophic. |
| The ring | Hash servers & keys onto a circle; a key walks clockwise to the first server. |
| The win | Adding/removing a node moves only ~1/N of keys, not all of them. |
| Virtual nodes | Many points per server → even load + graceful rebalancing + weighting. |
| Used by | Cassandra, DynamoDB, distributed caches, load balancers. |
What's Next?
Deep Dive 02 gives you the number-crunching superpower every interview loves: back-of-the-envelope estimation. You'll learn to size storage, bandwidth, and servers in seconds.
Keep designing, keep scaling! See you in the next one!
Post a Comment