Consistent Hashing

Placing keys on nodes so that adding a node moves a small slice of data instead of nearly all of it.

A hash ring moves 1/N of keys when the cluster changes; hash % N moves almost everything.

partitioningvirtual nodesrebalancing

Try it

Move the dials — the sentence under the picture changes.

Virtual nodes1 per node

4 nodes · 160 keys

Each key sits at a point on the ring and belongs to the first node clockwise from it. Add or remove a node and watch how much has to move — then compare it to what hash(key) % N would have cost. Busiest node is currently 150% above a fair share.

The problem it solves

You have keys and you have nodes, and you need a rule that says which node owns which key. The obvious rule is hash(key) % N.

It works perfectly until N changes. Go from 10 nodes to 11 and roughly 90% of keys map somewhere new. Every one of them has to move before the system is correct again, which means you cannot add capacity without a full reshuffle — and you especially cannot lose a node gracefully.

The ring

Hash both keys and nodes onto the same circular space. A key belongs to the first node clockwise from its position. Adding a node inserts one point on the ring, which takes ownership of the arc between it and the previous node — and only that arc. About 1/N of keys move, and they all come from one neighbour.

Removing a node is the mirror image: its arc falls to the next node clockwise, and nothing else is disturbed.

Virtual nodes are not optional

With one point per node, random placement produces genuinely uneven arcs — some nodes own a large slice and others a sliver. Worse, when a node leaves, its entire share lands on a single neighbour, which is how one failure becomes two.

Placing each physical node at 100-200 points on the ring fixes both. Load evens out because each node owns many small arcs instead of one large one, and a departing node's work spreads across every survivor rather than one. The widget shows this directly: turn virtual nodes up and watch the per-node shares converge.

What it does not solve

Consistent hashing distributes keys evenly. It says nothing about traffic. One extremely popular key still lands on exactly one node no matter how good the ring is, so hot keys need a separate answer — replication of that key, or a cache in front.

It also does not give you ordering. Keys adjacent in the ring are unrelated in value, so range scans ("every key between A and B") are gone. That is the same trade hash partitioning makes.

Where you meet it

Cassandra and DynamoDB for data placement, Memcached client libraries for cache sharding, and most CDN request routing. Anywhere a set of nodes has to agree on ownership without a coordinator.

Take this with you

The one idea: put nodes and keys on the same ring, so adding or losing a node moves about 1/N of the keys instead of nearly all of them.
In an interview, explain hash % N first, then the ring, then virtual nodes — and say plainly that it balances keys, not traffic.
At work, check whether your cache client already does this (most do). If it uses modulo, a scale-out is a cache wipe.