design·lab

Distributed systems

Consistent Hashing

A hash ring lets you add or remove a cache/DB node while remapping only a tiny slice of your keys, instead of almost all of them.

✗ The problem

Naive sharding: hash(key) % N

Modulo hashing ties every key's owner to the total node count N. Change N and almost every key's owner changes too.

// naive: hash(key) % N picks the node
owner(key, N) = hash(key) % N

// N = 3 nodes
owner(k1,3)=1  owner(k2,3)=2
owner(k3,3)=0  owner(k4,3)=1

// N = 4 nodes (one added!)
owner(k1,4)=3  owner(k2,4)=0
owner(k3,4)=1  owner(k4,4)=2
// → every key points at a new node
Node 0
k3
Node 1
k1, k4
Node 2
k2

+ 1 node (N: 3 → 4)

Node 0
k2
Node 1
k3
Node 2
k4
Node 3
k1
Adding one node reshuffled 4 of 4 keys (100%). At scale that's a cache stampede — every client misses at once and slams the database.
✓ How it works

Put nodes and keys on the same ring

  • Hash every node and every key onto the same ring: 0 … 2³².
  • A key belongs to the first node clockwise from its position.
  • Add or remove a node → only the keys in one arc (~K/N) change owner. Everyone else stays put.
  • Virtual nodes: place each physical node at many ring points so load stays balanced even with few nodes.
✓ See it live

Add or remove a node — watch how few keys move

3 nodes own 8 keys around the ring. Insert node N4 and only the keys inside its new arc change owner — everyone else stays exactly where it was.

N1 N2 N3 N4 (added)
3 nodes · keys moved: — of 8
✓ Takeaway

Only the arc moves

  • Scaling from N to N+1 nodes remaps only ~K/N keys — not "almost all" like hash % N.
  • Virtual nodes spread each physical node across many ring points, smoothing out uneven load.
  • Powers distributed caches — Memcached client hashing, Redis Cluster slots — plus DynamoDB / Cassandra partitioning and consistent-hash load balancers.
  • Pairs with service discovery (finding live nodes) and sharding strategies (assigning data to nodes).
Back to all topics →