Consistent Hashing: The Algorithm That Stopped Me From Nuking My Entire Cache 🔄💾
Consistent Hashing: The Algorithm That Stopped Me From Nuking My Entire Cache 🔄💾
Storytime: It was 11 PM on a Wednesday. We'd just scaled our Redis cache from 3 nodes to 4 nodes to handle Black Friday traffic. Simple horizontal scaling, right?
Within 60 seconds:
- Cache hit rate: 94% → 9%
- Database CPU: 12% → 96%
- API response time: 45ms → 8,400ms
- My heart rate: 📈📈📈
Me: "What the— why is the database on fire?!" Senior Dev (from his couch, phone buzzing): "Did you add a cache node?" Me: "...yes?" Senior Dev: "Did you rehash?" Me: "...what's rehash?" Senior Dev: audible sigh "I'll be online in 5 minutes."
That night I learned about consistent hashing. It's the algorithm that separates "I added a server" from "I accidentally reset the entire cache."
The Problem With Naive Cache Distribution 🤔
When you have multiple cache nodes, you need a way to decide which node stores which key. The obvious solution:
node = hash(key) % number_of_nodes
Let's say you have 3 nodes and key user:42:
hash("user:42") = 1,847,293
1,847,293 % 3 = 1 → Node 1
Simple! Beautiful! Works perfectly… until you add or remove a node.
What happens when you add Node 4:
Before (3 nodes): After (4 nodes):
hash("user:42") % 3 = 1 hash("user:42") % 4 = 1 ✅ (lucky!)
hash("order:9") % 3 = 0 hash("order:9") % 4 = 1 ❌ DIFFERENT NODE
hash("cart:77") % 3 = 2 hash("cart:77") % 4 = 3 ❌ DIFFERENT NODE
hash("sess:5") % 3 = 0 hash("sess:5") % 4 = 0 ✅ (lucky!)
hash("prod:12") % 3 = 1 hash("prod:12") % 4 = 0 ❌ DIFFERENT NODE
On average, when you add 1 node to N nodes:
Keys remapped = (N / N+1) = ~75% of ALL keys!
3 → 4 nodes: ~75% of keys land on wrong nodes (cache MISS)
9 → 10 nodes: ~90% of keys land on wrong nodes (cache MISS)
Translation: Every time you scale, you're essentially flushing most of your cache. Your database absorbs all those misses. It's like adding a lane to a highway and somehow all the cars end up in a traffic jam.
This is EXACTLY what happened to us that Wednesday night.
Enter Consistent Hashing: The Ring 💍
Consistent hashing is clever. Instead of hash(key) % N, you imagine both your keys AND your nodes mapped onto a ring (a circular space from 0 to 2^32).
0
┌───────┐
330° │ │ 30°
╱ │ RING │ ╲
╱ │ │ ╲
300° ─────┘ └───── 60°
│ │
│ [Node C] [Node A] │
270° 90°
│ │
│ [Node B] │
240° ─────┐ ┌───── 120°
╲ │ │ ╱
╲ │ │ ╱
210° └───────┘ 150°
180°
How it works:
- Hash each node name → place it on the ring at that position
- Hash each cache key → place it on the ring at that position
- A key is stored on the first node clockwise from the key's position
Ring position (0 → 360°):
Node A → hashes to position 60°
Node B → hashes to position 200°
Node C → hashes to position 320°
"user:42" → hashes to 45° → stored on Node A (first clockwise: 60°)
"order:9" → hashes to 130° → stored on Node B (first clockwise: 200°)
"cart:77" → hashes to 280° → stored on Node C (first clockwise: 320°)
"sess:5" → hashes to 350° → stored on Node A (wrap around → 60°)
Now watch what happens when you add Node D at position 150°:
BEFORE adding Node D:
45° → Node A ✅
130° → Node B ✅
280° → Node C ✅
350° → Node A ✅
AFTER adding Node D (at 150°):
45° → Node A ✅ unchanged
130° → Node D ← only keys between 60° and 150° move to D!
280° → Node C ✅ unchanged
350° → Node A ✅ unchanged
Only the keys that were between Node A (60°) and Node D (150°) move. Everything else stays put.
The math changes dramatically:
Naive hashing: add 1 node → ~75% of keys remapped 💀
Consistent: add 1 node → ~1/N keys remapped 🎉
4 → 5 nodes: only ~20% of keys move (not 80%!)
9 → 10 nodes: only ~10% of keys move (not ~90%!)
When designing our e-commerce backend, this is the difference between "we scaled smoothly" and "we got paged at 11 PM."
Real Code: How This Looks In Practice 🛠️
Here's a simplified consistent hash ring in Node.js:
const crypto = require('crypto');
class ConsistentHashRing {
constructor(nodes = [], replicas = 150) {
this.replicas = replicas; // virtual nodes per server
this.ring = new Map();
this.sortedKeys = [];
nodes.forEach(node => this.addNode(node));
}
hash(key) {
return parseInt(
crypto.createHash('md5').update(key).digest('hex').slice(0, 8),
16
);
}
addNode(node) {
// Add 'replicas' virtual nodes for each physical node
for (let i = 0; i < this.replicas; i++) {
const virtualKey = this.hash(`${node}:${i}`);
this.ring.set(virtualKey, node);
this.sortedKeys.push(virtualKey);
}
this.sortedKeys.sort((a, b) => a - b);
}
removeNode(node) {
for (let i = 0; i < this.replicas; i++) {
const virtualKey = this.hash(`${node}:${i}`);
this.ring.delete(virtualKey);
}
this.sortedKeys = this.sortedKeys.filter(k => this.ring.has(k));
}
getNode(key) {
if (this.ring.size === 0) return null;
const keyHash = this.hash(key);
// Find first node clockwise (binary search)
for (const ringKey of this.sortedKeys) {
if (keyHash <= ringKey) {
return this.ring.get(ringKey);
}
}
// Wrap around: return first node on ring
return this.ring.get(this.sortedKeys[0]);
}
}
// Usage
const ring = new ConsistentHashRing(['redis-1', 'redis-2', 'redis-3']);
console.log(ring.getNode('user:42')); // → "redis-2"
console.log(ring.getNode('order:99')); // → "redis-1"
console.log(ring.getNode('cart:7')); // → "redis-3"
// Add a new node — only ~25% of keys remapped!
ring.addNode('redis-4');
console.log(ring.getNode('user:42')); // → "redis-2" (probably same!)
console.log(ring.getNode('order:99')); // → "redis-4" (might have moved)
In production with Laravel + Redis, this is handled automatically by Redis Cluster using consistent hashing under the hood. You don't write the ring yourself — but knowing how it works saves you from the Wednesday-night incident I had.
Virtual Nodes: Why One Server Lives in Many Places 👥
There's a gotcha with the basic ring: uneven distribution.
If Node A hashes to 10°, Node B to 15°, Node C to 300°, then Node C handles 85% of all keys. That's not balanced.
Solution: Virtual nodes (vnodes) — each physical server maps to multiple points on the ring:
Physical servers: redis-1, redis-2, redis-3
Virtual nodes (replicas=3 for simplicity):
redis-1:0 → 45° redis-1:1 → 140° redis-1:2 → 290°
redis-2:0 → 80° redis-2:1 → 210° redis-2:2 → 320°
redis-3:0 → 20° redis-3:1 → 170° redis-3:2 → 255°
Ring (sorted):
20° → redis-3 ← actually redis-3:0
45° → redis-1 ← actually redis-1:0
80° → redis-2 ← actually redis-2:0
140° → redis-1 ← actually redis-1:1
170° → redis-3 ← actually redis-3:1
210° → redis-2 ← actually redis-2:1
255° → redis-3 ← actually redis-3:2
290° → redis-1 ← actually redis-1:2
320° → redis-2 ← actually redis-2:2
Now each server is interspersed across the ring. Keys are distributed much more evenly.
In production: Redis Cluster uses 16,384 hash slots distributed across nodes — effectively a form of consistent hashing with virtual slots. Cassandra uses 256 vnodes per node by default.
Where You're Already Using This (Without Knowing It) 🕵️
As a Technical Lead, I've found consistent hashing hiding in places I didn't expect:
1. Redis Cluster
# Redis automatically shards keys across cluster nodes
# CLUSTER KEYSLOT shows which slot (0-16383) a key maps to
CLUSTER KEYSLOT "user:42" → 1847
# Redis then maps slot 1847 to a specific node
2. AWS DynamoDB DynamoDB partitions use consistent hashing internally. When you add provisioned throughput, new partitions are added and only the affected key ranges move. This is why DynamoDB can scale without downtime.
3. Nginx/HAProxy upstream hashing
upstream backend {
hash $request_uri consistent; # <-- consistent hashing!
server app1.example.com;
server app2.example.com;
server app3.example.com;
}
# Same URL always routes to same server (useful for page caches!)
4. Apache Cassandra
# Cassandra uses a token ring (consistent hashing variant)
# Data distributes based on partition key hash
# Add a node? Only neighboring token ranges are affected!
When designing our e-commerce backend, I used consistent hashing explicitly in our API gateway for sticky routing — sending the same customer's requests to the same app server instance to maximize local in-memory cache hits.
The Trade-Offs (Nothing Is Free) ⚖️
Advantages:
- Adding/removing nodes only remaps
~1/Nof keys - Works well with dynamic node counts
- No central coordinator needed
- Scales to thousands of nodes elegantly
Disadvantages:
// 1. Hot spots still possible without enough virtual nodes
// If two nodes are close together on the ring, one carries more load
// Solution: use 150+ virtual nodes (Redis Cluster uses 16,384 slots)
// 2. Replication complexity
// "Store on the next 3 nodes clockwise" — works but adds complexity
// DynamoDB, Cassandra both handle this for you
// 3. Not great for tiny node counts
// With 2 nodes, consistent hashing over naive hashing barely helps
// Shines at 5+ nodes
// 4. Initial distribution can be uneven
// Solved by virtual nodes, but adds memory overhead for the ring structure
When NOT to use it:
- You have 2-3 cache nodes and never change them → simple
mod Nis fine - You're using a managed service (Redis Cluster, DynamoDB, Elasticache) → it's handled for you
- You need strong consistency → consistent hashing is an availability optimization
Common Mistakes I Made (And You Can Avoid) ❌
Mistake 1: Adding nodes without warmup
// BAD: Add all 3 new nodes at once (massive redistribution)
ring.addNode('redis-4');
ring.addNode('redis-5');
ring.addNode('redis-6');
// Cache hit rate drops immediately - DB gets hammered
// BETTER: Add one node, let cache warm up, then add next
ring.addNode('redis-4');
// Wait 30 minutes for cache to warm on new node
ring.addNode('redis-5');
// Wait 30 minutes...
ring.addNode('redis-6');
Mistake 2: Forgetting replication
// Naive: store on exactly 1 node
const node = ring.getNode(key);
redis.set(node, key, value);
// Reality: that node can die
// Better: replicate to next N nodes on the ring
const nodes = ring.getReplicaNodes(key, 3); // next 3 nodes
nodes.forEach(node => redis.set(node, key, value)); // write to all 3
// Read from first responsive node
Mistake 3: Not testing node removal
A scalability lesson that cost us a full incident: we'd tested adding nodes but never tested removing one. When we decommissioned a node, we forgot to migrate its keys first. Cache miss spike, same story as adding a node.
# Before removing a node:
# 1. Mark it as draining (don't route new writes)
# 2. Wait for TTLs to expire OR migrate keys
# 3. Then remove from ring
TL;DR 🎯
The 30-second version:
Naive hashing (hash(key) % N):
Add 1 node → ~75% of cache GONE 💀
Consistent hashing (hash(key) on a ring):
Add 1 node → ~1/N of cache affected 🎉
How it works:
1. Place nodes AND keys on an imaginary circle
2. Each key goes to the first node clockwise from it
3. Adding a node only steals keys from its neighbors
Where you already use it:
Redis Cluster, DynamoDB, Cassandra, Nginx upstream hashing
When to care:
✅ Dynamic cache clusters (scaling up/down)
✅ Building your own distributed cache/DB
✅ Load balancing with session affinity
✅ Understanding why Cassandra doesn't lose data when you add a node
As a Technical Lead, I've learned: you don't need to build consistent hashing yourself in most cases — Redis Cluster, DynamoDB, and Cassandra do it for you. But the day you scale your cache under pressure and need to understand why 80% of your keys are suddenly on the wrong node, you'll be glad you know this.
My 11 PM incident? We rolled back to 3 nodes, let the cache warm overnight, then migrated to Redis Cluster (which handles this automatically). The second scale-out was boring. Boring is good. 🙏
Hit a scaling wall? Connect with me on LinkedIn — I've been in the 11 PM incident Slack call more times than I'd like to admit.
Curious about my e-commerce backend setup? Check out my GitHub for architecture patterns and production lessons.
Build smart, scale boring. 🔄✨
P.S. If you're still using hash(key) % N for a distributed cache with more than 3 nodes, please read this post twice. I'm begging you. Your future on-call self will thank you. ❤️