Consistent hashing explained with a key movement example

A cache cluster has three nodes and wants to add a fourth. With hash(key) % 3, the answer to “where does this key live?” depends on the number three. Change it to four and many existing keys get a different answer, even though the old nodes did not move. Consistent hashing makes node membership a smaller change to the assignment rule. It says where a key belongs; it does not move the bytes or make replicas agree by itself.

If retrieval by key is unfamiliar, start with the key-value access model and its Redis example. Choosing which node owns a key is a separate question from what the store lets you do with it.

Why modulo reshuffles#

Label the current nodes A, B and C as buckets 0, 1 and 2. A key with hash 20 maps to bucket 2 under 20 % 3; after adding D as bucket 3, 20 % 4 maps it to bucket 0. Hash 55 moves from bucket 1 to bucket 3. These are not failures of the hash function. The modulus is part of the location, so changing node count changes answers throughout the space. In a cache this creates misses; in a storage system it can require a large migration.

The goal is to make a membership change alter as few assignments as practical while preserving a way to find each key. The original consistent-hashing paper describes this as changing the hash function’s range with minimal disruption. A ring is the easiest concrete model of the idea.

Walk the ring before and after#

In this illustrative example, use a tiny hash space from 0 to 99. Node positions are A at 10, B at 40 and C at 70. Place each key at its hash value and walk clockwise to the first node. Key 5 belongs to A; 20 to B; 55 to C; 85 wraps past 99 and belongs to A. Now insert D at 30. Only keys after A at 10 and up to D at 30 switch from B to D. In this four-key sample, that is key 20. The other three keep their original owner.

Hash space: 0 … 99, clockwise, wrapping after 99
Before:  A@10  B@40  C@70
After:   A@10  D@30  B@40  C@70

Owner(key) = first node clockwise from hash(key)
Only keys in (10, 30] change owner on this join: B → D.

A node leaving reverses this handoff: its successor takes its interval. The amount moved depends on the interval’s size and the distribution of real keys, not a promise that every join moves exactly one quarter of the data. A real ring uses a much larger stable hash space, and every participant must agree on the same hash function and membership view. During a disagreement about membership, clients can compute different owners for the same key, so routing and recovery still need an operational protocol.

Virtual nodes and weighted capacity#

Three physical nodes at three points can own very uneven arcs by chance. Instead, place each physical node at many independently hashed positions, such as hash(“A:0”), hash(“A:1”) and so on. The physical node owns the union of its small intervals. This tends to smooth the distribution of many keys and gives a practical capacity knob: assign a larger node more positions. It also makes one physical node’s join or departure involve many small intervals rather than one contiguous arc. Amazon’s Dynamo paper describes using virtual nodes for heterogeneous capacities and recovery.

More positions mean more membership metadata and more ranges to track or transfer. A weight is a target share, not a guarantee: skewed key sizes or request rates can dominate the observed load. Measure bytes, request rate and tail latency after a rebalance, not just the number of hash ranges.

What the ring does not solve#

A hot key remains hot. Dividing the key space into more intervals distributes different keys, but every request for one key still reaches its owner. Replicas or caches may help reads; splitting or aggregating the workload may help writes. Each changes application semantics and needs its own consistency decision. Likewise, a ring can nominate the next two distinct physical nodes as replicas, but it must account for failure domains so all copies do not end up in one rack or zone.

Limited reassignment is not free migration. A storage service must copy or stream the affected records, serve reads while transfer is incomplete, decide when ownership changes, recover from interrupted transfers and verify that replicas converge. A cache may simply accept misses; a database cannot casually do that. Replication and change data capture answer different parts of that migration story. CRDT merge rules address a narrower convergence problem for supported replicated data types; the hash ring itself does not merge concurrent updates.

The adjective “consistent” here does not mean linearizable reads, CAP consistency or ACID transactions. It means the key-to-owner assignment changes minimally when the set of owners changes. The storage protocol determines what a reader observes during a write or failure.

Alternatives and when to use them#

A ring is not the only stable-placement scheme. Jump consistent hash is compact and balances numbered buckets without storing a ring, but its original formulation expects sequential bucket numbers, which makes arbitrary node removal awkward. Rendezvous hashing scores each candidate node for a key and picks the highest; it is simple to reason about and can support weighted placement, though a straightforward lookup scores every candidate. An explicit lookup table can be the better answer for a small cluster when operators need exact placement or careful migrations.

Choose the assignment scheme after defining what a membership change is allowed to interrupt and what data must be copied. For an ephemeral cache, bounded misses may be enough. For durable storage, migration, replicas and recovery dominate the implementation regardless of the hash function.