Skip to main content
PreparationZone Logo
PrepZone

Consistent Hashing

Add or remove cache nodes without remapping every key — the ring that powers distributed caches.

Pass checkpoint below

Read these first

The problem with modulo hashing

Java
3 cache nodes, key "user:42"
  slot = hash("user:42") % 3  →  node 1

Add node 4:
  slot = hash("user:42") % 4  →  node 2   ← MOVED! cache miss storm

When StreamHub expanded Redis from 4 to 6 nodes using naive modulo, cache hit ratio dropped from 92% to 41% until keys repopulated — a classic cache stampede on the database.

The hash ring

Hash ring0 … 2^32-1
Node Akeys 0–25%
Node Bkeys 25–50%
Node Ckeys 50–75%
Node Dkeys 75–100%

New node E joins → only ~1/N keys move, not all keys.

Adding a node only remaps keys adjacent to it on the ring.

Ring mechanics

  1. Hash space is a fixed ring (0 to 2³²−1 or 0 to 1.0).
  2. Each node is placed at one or more positions on the ring (via hash of node ID).
  3. Each key is hashed to a position on the ring.
  4. Walk clockwise from the key's position — the first node encountered owns the key.
  5. Adding a node steals only keys between its predecessor and itself.

Only keys in the affected arc move — typically 1/N of total keys when adding one of N nodes.

Virtual nodes (vnodes)

Physical machines get multiple positions on the ring for even distribution:

Java
Physical node A → vnode A0, A1, A2, A3 on ring
Physical node B → vnode B0, B1, B2, B3 on ring

Without vnodes, uneven key density clusters on a few nodes. Redis Cluster and Dynamo use vnode-style partitioning.

Java
# Redis Cluster — key must include hash tag for multi-key ops
SET user:{42}:session abc123
GET user:{42}:profile
# {42} ensures both keys land on same slot

The {...} hash tag forces related keys to the same slot — required for atomic multi-key operations.

The rest of this guide is part of Pro

Free covers every fresher guide in full. Pro unlocks Senior, Staff and Architect guides across every track.

Still to come · 5 sections

  • Consistent hashing use cases
  • Adding and removing nodes
  • Comparison with alternatives
  • Hot keys and mitigation
  • Rendezvous hashing (alternative)

Test yourself

Answer these before moving on — recall is what makes it stick.