Consistent Hashing - System Design

Source: Dev.to

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

❓ The Scenario

In a distributed system (many 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 start with 3 servers and store data using hash(key) % 3.
• When you add a 4th server, the output of hash(key) % N changes for almost all keys (because N changed).
• This forces huge data reshuffling across all 3 servers – terrible at scale.

Server failures reassign all keys

• If one server dies, N changes again, so most keys are recomputed to new locations – even if the data itself didn’t move.
• This causes many cache or lookup failures.

➡ Result: 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 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

The space wraps around like a circle — 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 this looks 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
• From after A to B
• From after B to C

📍 Step B — Assign Data Keys

• Key1 hashed → 100

  • Traverse clockwise from 100 → next server clockwise = B(150)
  • Key1 is stored on server B.

• Key2 hashed → 320

  • Traverse clockwise → next server clockwise = A(50) (after wrap‑around)
  • Key2 is stored on server A.

This clockwise rule ensures:

• 👉 Every key maps to exactly one server.
• 👉 No gaps exist — 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, causing huge data movement.

What Consistent Hashing Does Instead

Add a new server:

Server D → hash = 200

The ring becomes:

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

Only keys that fell between B (150) and D (200) used to be assigned to C.
After inserting D, those keys move to D, while all other keys stay exactly where they are.

🧠 Only the keys in the range that D takes over change their assignment. Everything else stays the same.
That’s the essence of “consistent” – only a small, predictable subset is redistributed.

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

Assume server B (hash 150) fails.

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

Thus most keys stay where they were; only the keys 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 roughly 1 / N of the total keys – a small portion moves, enabling the system to scale beautifully.

📌 7) 🧠 Load Balancing & Virtual Nodes

⚠ Uneven Load Problem

Without extra care, a server could 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, give each server many virtual points (replicas) scattered around the circle.

Example:

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

These virtual nodes spread 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

• Distributed caches (e.g., Memcached, Redis Cluster)
• Sharded databases (Cassandra, DynamoDB)
• Peer‑to‑peer networks (BitTorrent, Kademlia)
• Load balancers and CDN edge selection

Consistent hashing provides scalable, fault‑tolerant data placement with minimal reshuffling, making it a cornerstone technique for modern distributed systems.

Real‑world examples

• Distributed caching (e.g., Memcached, Redis) – cache nodes can scale without evicting everything.
• Distributed databases (e.g., Cassandra, Dynamo) – shard data efficiently.
• Content Delivery Networks (CDNs) – cache content close to clients with minimal reshuffle.
• Load balancing in micro‑services – route requests consistently by user/session.

📌 9) Summary: Why It Matters in Real Systems

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