Consistent Hashing - System Design

📌 1) 💥 The Core Problem: Traditional Hashing Breaks in Distributed Systems

❓ The Scenario

In a distributed system (lots of servers handling data), we must decide which server stores what data.

A naive approach might be:

serverIndex = hash(key) % N

Where N = number of servers.

🚨 What Goes Wrong with This?

• Data Reassignment on Scale Changes:
  Suppose you initially have 3 servers, so you store data using hash(key) % 3. If you add a 4th server — the output of hash(key) % N changes for almost all keys instead of just the new ones, because N changed. This forces huge data reshuffling across all 3 servers — terrible at scale.

• Server Failures Reassign All Keys:
  If one server dies, now N changes again, so most keys will get recomputed to new locations — even if the data itself didn’t move — causing many cache or lookup failures.

➡ That means every server change leads to data migrations proportional to the size of the dataset — extremely expensive for millions of keys.

---

📌 2) 🧠 The Core Idea of Consistent Hashing

Consistent hashing solves exactly the above problems by reshaping the hashing strategy:

✔ Both servers and keys are placed onto the same circular hash space (“hash ring”).

Each server and each data key gets a hash value that represents a position on this circle.

Imagine the hash output as degrees on a clock:

0 ——————————————— 359

It wraps around like a circle — meaning address 359 is next to 0.

✔ The rule for placing data:

To decide where a piece of data belongs, hash the key and then move clockwise around the circle until you find the first server.
That server becomes the owner of that piece of data.

This clockwise traversal is the fundamental idea — and here’s why it matters.

---

📌 3) 🌀 How Clockwise Traversal Works — Step by Step

📍 Step A — Place Servers on a Ring

When the system starts, each server’s identity (e.g., IP address) is hashed to a position:

Server A -> hash = 50  
Server B -> hash = 150  
Server C -> hash = 300  

On the hash ring, that might look like:

0 — A(50) — B(150) — C(300) — (wraps to 0)

This division implicitly creates ranges of the ring managed by each server:

• From after C back to A covers one region
• From after A to B covers another
• And so on

📍 Step B — Assign Data Keys

Now if you receive a data key:

Key1 hashed -> 100

You traverse clockwise from position 100:

100 -> next server clockwise = B(150)

So Key1 is stored on server B.

Another example:

Key2 hashed -> 320  
320 -> next server clockwise = A(50, after wraparound)

Key2 is stored on A — because after you go past the highest server hash, you wrap to the lowest one.

This clockwise rule ensures:

👉 Every key maps to exactly one server
👉 You never have gaps — because the ring loops indefinitely

---

📌 4) 🧩 What Happens When a Server Is Added?

📌 The Problem Before Consistent Hashing

Adding a new server normally forces remapping of all keys. That means huge data movement.

📌 What Consistent Hashing Does Instead

Suppose we add:

Server D -> hash = 200

Now the ring looks like:

0 — A(50) — B(150) — D(200) — C(300)

Only keys that fell between B and D in the ring used to be assigned to C, before D existed.

Now when you insert D, data whose hashes lie between B(150) and D(200) will be transferred to D — but all other keys stay exactly where they are.

This is the critical benefit:

🧠 Only the keys in the range that D takes over change their assignment. Everything else stays the same.

And that’s exactly what “consistent” means — only a small, predictable subset is redistributed.

---

📌 5) 🧠 What Happens When a Server Is Removed or Fails?

Let’s say server B (at hash 150) fails.

Then:

• All keys that were assigned to B go to the next server clockwise — which now is D (at 200).
• Keys originally mapped to A and C remain untouched.

This means most keys stay where they were, only the ones belonging to the removed server migrate.

---

📌 6) 📌 Why This Minimizes Disruption

Traditional % N hashing redistributes almost all keys when N changes.

Consistent hashing redistributes only the keys that were mapped to:

✔ the area between the new server’s predecessor and itself (on addition)

✔ the removed server’s range (on removal)

That’s only ~1/N of the total keys — meaning only a small portion moves.

This is why consistent hashing scales beautifully.

---

📌 7) 🧠 Load Balancing & Virtual Nodes

⚠ Uneven Load Problem

Without extra care, a server could accidentally be placed such that it covers a large arc of the ring — leading to uneven load: one server gets many keys, others get few.

🎯 Solution: Virtual Nodes

Instead of mapping each server once on the ring, each server gets many virtual points (replicas) scattered around the circle.

For example:

Server A -> spots at 10, 110, 210  
Server B -> spots at 40, 140, 240  

This spreads the data load more evenly, because each server participates in many regions of the hash space — smoothing out uneven gaps.

---

📌 8) 🔎 Practical Uses & Why It Matters

Consistent hashing is widely used in real production systems to enable:

✅ Distributed caching (e.g., Memcached, Redis) — so cache nodes can scale without evictions everywhere.
✅ Distributed databases (e.g., Cassandra, Dynamo) — to shard data efficiently.
✅ Content Delivery Networks (CDNs) — to cache content close to clients with minimal reshuffle.
✅ Load Balancing in microservices — to route requests consistently by user/session.

---

📌 9) Summary: Why It Matters in Real Systems

Problem	Traditional Hashing	Consistent Hashing
Key mapping	Simple	Circular traversal
Node addition	Redistributes almost all keys	Only ~1/N keys move
Node removal	Redistributes almost all keys	Only keys from removed node move
Load balance	Can be uneven	Virtual nodes smooth it

Consistent hashing turns what would be a chaotic, system-wide reshuffle into a local, predictable relocation — ideal for high-scale, dynamic infrastructure.

---