Consistent Hashing: Limiting Data Movement as Clusters Change

A simple way to distribute keys across N servers is:

hash(key) mod N

When N changes, the result changes for most keys, causing a large cache miss or data movement event.

Consistent hashing arranges keys and nodes in a logical space so membership changes move only nearby key ranges.

It is useful for distributed caches, stores, and routing.

A concrete example: adding a cache server

Four cache nodes hold millions of keys.

With modulo hashing, adding a fifth changes the destination for roughly most keys.

With consistent hashing, the new node takes selected ranges from neighboring nodes. Most other keys keep their existing owner, reducing cold-cache load on the origin database.

Hash space

A hash function maps identifiers into a large numeric range.

Visualize the range as a ring:

• after the maximum value comes zero,
• keys and nodes occupy positions,
• a key belongs to the next node clockwise.

The ring is a conceptual ordering, not physical network topology.

Placing nodes

Each node receives one or more positions based on a stable identifier.

For a key:

1. calculate its hash,
2. locate that point,
3. walk clockwise,
4. choose the first node.

An ordered lookup structure makes this efficient.

Adding a node

A new node is inserted at positions on the ring.

It takes ownership of the range between its predecessor and itself. Only keys in those ranges move.

The fraction depends on placement and number of virtual nodes.

Removing a node

When a node leaves, its ranges move to the next owners.

Planned removal can transfer data before routing changes. Failure requires replicas or origin refill.

Membership information must converge among clients.

Balance problem

One physical node at one random position can receive a very large range while another receives a small range.

The result is uneven storage and traffic.

Virtual nodes reduce this variance.

Virtual nodes

Each physical machine owns many positions.

Its ranges are spread around the ring. Adding or removing a machine transfers many small ranges across several peers rather than one large contiguous range.

Virtual nodes also support weighted capacity.

Weighted nodes

A larger machine can receive more virtual positions.

Weight should reflect the constrained resource:

• memory,
• storage,
• throughput,
• or CPU.

Changing weights also moves keys and should be staged.

Replication

For durability, a key can be stored on several successive distinct physical nodes.

The replication factor determines copies. Placement should span failure domains such as racks or zones, not just adjacent virtual points on one machine.

Reads and writes need consistency rules across replicas.

Cache use

In a cache, missing data can be fetched from the origin.

Consistent hashing reduces remapping and cache churn during membership changes. Client-side hashing also avoids a central router, but every client needs current membership.

A proxy-based cache ring centralizes that knowledge.

Data-store use

For durable data, movement requires:

• streaming,
• checksums,
• ownership handoff,
• replication,
• and repair.

Routing should not switch before the destination can serve safely.

Consistent hashing chooses placement; it does not implement migration by itself.

Membership

Nodes must agree on:

• which members exist,
• their tokens,
• health,
• and topology.

Stale membership can send clients to old owners. Coordination systems, gossip, and versioned ring configurations distribute changes.

Failure detection

A timeout does not prove a node is permanently gone.

Immediately removing a slow node can trigger movement and overload. Systems may temporarily route to replicas, mark suspicion, and change membership only after stronger evidence.

Membership churn is expensive even with limited redistribution.

Hot keys

Even balanced ranges cannot distribute one extremely popular key.

Solutions include:

• local replicas,
• request coalescing,
• extra caching,
• key splitting,
• or dedicated handling.

Hash balance solves aggregate placement, not skew within keys.

Bounded loads

Classic consistent hashing can still place uneven request volume.

Bounded-load variants choose among nearby or multiple candidate nodes while respecting capacity limits.

The added routing logic trades simplicity for tighter balance.

Rendezvous hashing

Rendezvous, or highest-random-weight hashing, scores each key against each node and selects the highest.

It also minimizes remapping during membership changes and can be simpler for smaller node sets.

Consistent-hash rings are one family of stable-placement techniques.

Rebalancing impact

Movement consumes:

• network,
• disk,
• CPU,
• and cache origin capacity.

Throttle transfers, preserve foreground service, and monitor completion. Adding capacity can temporarily reduce performance during rebalancing.

Failure domains

Placement should understand zones, racks, or hosts.

Three virtual replicas on one physical server do not provide durability. Select distinct failure domains for replicas.

Topology-aware placement extends the basic ring rule.

Testing

Test:

• key distribution,
• node add and remove,
• weighted capacity,
• stale membership,
• failure and recovery,
• replica placement,
• and hot key.

Measure both fraction moved and temporary operational load.

Knowledge check

1. Why does modulo hashing move many keys when node count changes?
2. How does the ring assign a key?
3. Why do virtual nodes improve balance?
4. What does consistent hashing not provide for durable migration?
5. Why can a hot key remain a problem on a balanced ring?

The one idea to remember

Consistent hashing places keys and nodes in a stable logical space so cluster membership changes remap only nearby ranges. Virtual nodes, weights, topology-aware replication, membership coordination, and controlled rebalancing turn the basic idea into an operational system.