Consistent Hashing

In one line

The ring-based mapping that makes adding/removing nodes move only a tiny slice of keys — the trick behind Redis clusters, Cassandra, and LB affinity.

0/10 · 0%

Think of it like this

A game of musical chairs where, if one chair is removed, only the people right next to it need to move — everyone else stays seated. Compare that to a version of the game where removing one chair forces EVERY player to find a new seat.

Key ideas

01
Problem: hash(key) % N moves EVERYTHING when N changes (add a node → ~all keys remap → cache miss storm).
02
Idea: hash nodes AND keys onto a ring; each key maps to the next node clockwise — only keys between two nodes move when a node joins/leaves.
03
Virtual nodes (vnodes): each physical node owns several ring positions → smooths imbalance and load spread.
04
Result: adding a node migrates ~1/N of keys instead of ~all.
05
Used in: Cassandra's token ring, Redis cluster slot maps, consistent-hash load balancers.
06
Interview line: 'I'll use consistent hashing so cache rebalancing doesn't empty the fleet on every scale-up'.

Java / Spring map

→
Implement a sorted-ring with TreeMap<Long, Node> + virtual node hashing for practice.

Code & diagrams

the hash ring with virtual nodesdiagram

Rendering diagram…

ConsistentHashRing.javajava

The core ring with virtual nodes.

public class ConsistentHash<T> {
  private final SortedMap<Long, T> ring = new TreeMap<>();
  private final int vnodesPerNode;
  private final java.util.function.Function<String, Long> hash;

  public ConsistentHash(int vnodesPerNode, java.util.function.Function<String, Long> hash) {
    this.vnodesPerNode = vnodesPerNode;
    this.hash = hash;
  }

  public void addNode(T node) {
    for (int v = 0; v < vnodesPerNode; v++)
      ring.put(hash.apply(node.toString() + "#" + v), node);
  }
  public void removeNode(T node) {
    for (int v = 0; v < vnodesPerNode; v++)
      ring.remove(hash.apply(node.toString() + "#" + v));
  }

  public T route(String key) {
    if (ring.isEmpty()) throw new IllegalStateException("no nodes");
    Long h = hash.apply(key);
    var it = ring.tailMap(h, false).entrySet().iterator();
    long slot = it.hasNext() ? it.next().getKey() : ring.firstKey(); // wrap
    return ring.get(slot);
  }
}
// Add node #4 of 100 → keys on ~1% of ring move, not 100%.

Explain without notes

Show why '% N' rehashes everything on resize, then how the ring avoids it.

Practice

Put 3 nodes + 1000 keys on the ring, add a 4th, count moved keys (expect ~250).

Trade-offs

↔
Vnodes trade a fatter ring for balance; too many vnodes = more memory, less skew.

Run it in production

You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:

Networking · Load balancing: L4 vs L7

Algorithms, health checks, draining, and sticky sessions.

Stateful · Redis Sentinel, Cluster & locks

Hash slots, failover, and why distributed locks need fencing.

Completion checklist

I can draw the ring and say what moves when a node joins.

Back to phase

Command Palette