What is consistent hashing?

A scheme that places both keys and nodes on the same ring — a circle of hash values from 0 to 2³² — and assigns each key to the first node found walking clockwise. Because the nodes live on the ring too, adding or removing one only reassigns the keys in a single arc (about K/n of them) instead of remapping nearly the whole keyspace the way plain hash-mod-N does.

Why does hash mod N remap almost all keys when N changes?

Because the slot is hash(key) mod N, and changing N changes the divisor for every key at once. Going from 10 shards to 11, a key keeps its slot only when hash mod 10 equals hash mod 11 — which is true for about 1 key in 11. So roughly 91% of keys move, and for a cache that means about 91% of it is invalidated the instant you add a server. As libketama put it, before consistent hashing "whenever we added or removed servers from the pool, everything hashed to different servers, which effectively wiped the entire cache."

How many keys move when a node is added or removed under consistent hashing?

Only the keys in the affected arc. Wikipedia states it exactly: "when a hash table is resized, only n/m keys need to be remapped on average where n is the number of keys and m is the number of slots." That is one node’s share — about K/n — not the whole keyspace. Adding the nth node relocates roughly a 1/n fraction of keys, and the rest never move.

What are virtual nodes and why are they needed?

With only a handful of nodes, the random gaps between them on the ring are uneven, so some nodes own a much bigger arc than others and load is lumpy. Virtual nodes fix this by hashing each physical node to many points on the ring, so its share becomes the sum of many small arcs and averages out. Cassandra assigns "multiple tokens in the token ring to each physical node," and libketama hashes each server to 100–200 points on the continuum.

How do jump hash and rendezvous hashing compare to ring-based consistent hashing?

All three move only about 1/N of keys when the node count changes. The ring stores every node’s position and supports arbitrary add and remove. Jump consistent hash needs no storage and is faster — "about 5 lines of code" — but its buckets must be numbered 0..N-1, so it only grows or shrinks at the end. Rendezvous (highest-random-weight) hashing scores every (key, node) pair with a hash and picks the maximum; it is simpler, and consistent hashing "can be shown to be a special case of HRW."

Consistent Hashing

Add a machine to a sharded system and plain hash-mod-N reshuffles almost everything. Consistent hashing puts the nodes on the same ring as the keys — walk clockwise to the owner — so a membership change moves only one arc, and virtual nodes even out the load. Drawn, computed, and animated.

Concept · Systems. The source ↗

A free, interactive, animated visual explainer of Consistent Hashing — built to be understood, not skimmed.

Questions

What is consistent hashing?: A scheme that places both keys and nodes on the same ring — a circle of hash values from 0 to 2³² — and assigns each key to the first node found walking clockwise. Because the nodes live on the ring too, adding or removing one only reassigns the keys in a single arc (about K/n of them) instead of remapping nearly the whole keyspace the way plain hash-mod-N does.
Why does hash mod N remap almost all keys when N changes?: Because the slot is hash(key) mod N, and changing N changes the divisor for every key at once. Going from 10 shards to 11, a key keeps its slot only when hash mod 10 equals hash mod 11 — which is true for about 1 key in 11. So roughly 91% of keys move, and for a cache that means about 91% of it is invalidated the instant you add a server. As libketama put it, before consistent hashing "whenever we added or removed servers from the pool, everything hashed to different servers, which effectively wiped the entire cache."
How many keys move when a node is added or removed under consistent hashing?: Only the keys in the affected arc. Wikipedia states it exactly: "when a hash table is resized, only n/m keys need to be remapped on average where n is the number of keys and m is the number of slots." That is one node’s share — about K/n — not the whole keyspace. Adding the nth node relocates roughly a 1/n fraction of keys, and the rest never move.
What are virtual nodes and why are they needed?: With only a handful of nodes, the random gaps between them on the ring are uneven, so some nodes own a much bigger arc than others and load is lumpy. Virtual nodes fix this by hashing each physical node to many points on the ring, so its share becomes the sum of many small arcs and averages out. Cassandra assigns "multiple tokens in the token ring to each physical node," and libketama hashes each server to 100–200 points on the continuum.
How do jump hash and rendezvous hashing compare to ring-based consistent hashing?: All three move only about 1/N of keys when the node count changes. The ring stores every node’s position and supports arbitrary add and remove. Jump consistent hash needs no storage and is faster — "about 5 lines of code" — but its buckets must be numbered 0..N-1, so it only grows or shrinks at the end. Rendezvous (highest-random-weight) hashing scores every (key, node) pair with a hash and picks the maximum; it is simpler, and consistent hashing "can be shown to be a special case of HRW."

Consistent Hashing

Questions

Related explainers