Distributed Systems

Consistent Hashing

Add or remove a server and almost nothing should move. Place nodes and keys on a hash ring and watch why only a thin slice of keys shifts, while mod-N reshuffles nearly everything.

consistent-hashingdistributed-systemsshardingload-balancing

LiveInteractive · drag, toggle, run it

Distributed Systems · Sharding

Consistent Hashing

Every node and every key gets hashed onto one circle. A key belongs to the first node you meet going clockwise. That single rule is what keeps data put when the cluster grows or shrinks.

3 nodes · 40 keys

Filled diamonds are physical nodes, small open diamonds are virtual replicas, dots are keys

Tune the ring

Keys on the ring40

Virtual nodes per physical node1

With one position per node the arcs are lumpy, so load is uneven. Each virtual node drops another diamond for the same server, slicing the circle into many small arcs that average out.

Load per node

Keys owned by each physical server. Even bars mean balanced load.

Imbalance: 150% gap between busiest and quietest, relative to a perfectly even split. Raise virtual nodes and watch it fall.

The point: adding a node moves almost nothing

Compare what happens to your 40 keys when the cluster grows from 3 to 4 servers.

Naive: hash(key) mod N

~75%

of keys land on a different server (about 30 of 40). Changing the divisor reshuffles nearly the whole table, so every cache misses at once.

Consistent hashing

~33%

only the keys in the new node's arc move, roughly K/N. Everyone else keeps their owner. Press Add node above to see exactly which dots get ringed.

Why it works

Why clockwise. Picking the next node clockwise is just a rule everyone agrees on, so any client computes the same owner from the same ring with no coordinator. The direction itself does not matter, only that it is fixed.

Why only a slice moves. A new node lands at one spot and captures only the keys between it and the previous node clockwise. Every key outside that arc still meets the same node it did before, so it stays put. That is the K/N intuition: with N nodes each owns about 1/N of the circle, so a new node steals roughly 1/(N+1) of the keys and leaves the rest alone.

Why virtual nodes. A handful of random points split a circle into wildly uneven arcs, so a few servers get overloaded by luck. Giving each server many positions makes its total ownership the sum of many small arcs, and those averages converge toward an even share. The bar chart flattens as you raise the slider.

Positions are FNV-1a hashes of the node and key ids, mapped from 0..2³² onto 0..360°