Consistent hashing

Nodes on a ring: add and remove them and see how few keys move.

On the roadmap:Intermediate · step 3: Sharding

Intermediateabout 10 to 15 min6 experiments

Experiments

New here? A few short steps show what happens, one at a time.

Settings

Points on the ring per node1

3,000 keys are spread over the ring. A dot on the ring is one of the first 70, coloured by the node that holds it.

Nodes

Busiest node

2.25x even

Keys moved by the last change

none yet

Hash-mod-N would move

none yet

The busiest node holds 2.25 times an even share. With one point each the ring is lumpy. Raise the virtual nodes to even it out.

Who owns which part of the ring

N1covers 19% of the ring, holds 585 keys
N2covers 3% of the ring, holds 54 keys
N3covers 56% of the ring, holds 1,689 keys
N4covers 22% of the ring, holds 672 keys

In plain words

Consistent hashing places both the nodes and the keys on a ring. A key belongs to the first node clockwise from it. When a node joins or leaves, only the keys in its neighbourhood change owner, instead of nearly all of them.

Why it matters

Plain hashing by key modulo the number of servers is simple but brittle: change the number of servers and almost every key lands somewhere new. For a cache that means a flood of misses, and for a database a huge data move. The ring keeps most keys where they are. Virtual nodes then make the split fair.

How real systems do it

The simulation is a simplified model. Here is what production systems add or do.

Consistent hashing was introduced in 1997 by Karger and colleagues at MIT for spreading web caching load, and was a starting point for the CDN company Akamai.
Amazon's Dynamo paper (2007) uses consistent hashing with virtual nodes to place data, and Apache Cassandra does the same with tokens. Cassandra's default number of tokens per node is 16 in recent versions, down from 256.
Memcached clients such as ketama use a ring so that adding a cache server does not invalidate most of the cache. Envoy offers ring hash and Maglev load balancing for the same reason.
Not everything uses a ring. Redis Cluster divides the key space into 16,384 fixed hash slots and moves slots between nodes, which gives the same small moves with a table instead of a ring.