Distributed systems often need a stable way to decide which node owns a key.

Examples:

A simple approach is:

That works while the node count stays fixed. It breaks badly when nodes are added or removed. If number_of_nodes changes from 5 to 6, most keys get a different result. For a cache, that means a large cache miss storm. For a storage system, it means a large data movement event. For a stateful worker fleet, it means many keys move to new owners at once.

Consistent hashing solves this by minimizing key movement when membership changes. When a node is added or removed, only the keys near that node move. Most keys keep the same owner.

Consistent hashing is used in distributed caches, Dynamo-style databases, storage systems, load balancers for stateful traffic, queue partitioning, and routing layers. The exact implementation varies, but the design goal is the same: stable ownership with controlled movement.

Modulo hashing maps a key to a node by taking the hash modulo the number of nodes.

Suppose we have 5 nodes:

For each key:

This gives deterministic routing. The same key goes to the same node as long as the node list and node count do not change.

Adding a Node

Now add S5.

The formula changes from:

to:

That small formula change remaps most keys.

This is painful because the system does not just change a routing table. It also moves operational load:

Removing a Node

If S4 fails, the formula changes from:

to:

Again, most keys move even though only one node changed.

Modulo hashing is fine for fixed partition counts. For example, Kafka-style partitioning often hashes keys into a stable number of partitions, then moves partitions between brokers separately. The problem appears when the hash target is the live node count.

Consistent hashing maps both nodes and keys into the same fixed hash space.

The hash space is usually shown as a ring:

Mapping a Key

To route user:123:

If the key lands exactly on a node position, it belongs to that node. In practice, with a large hash space, exact collisions are rare. A real implementation still needs deterministic collision handling.

Adding a Node

When a new node joins, it claims the range between its predecessor and itself.

Suppose S5 is placed between S1 and S2.

Only keys in the range (S1, S5] move from S2 to S5. Keys owned by other nodes stay where they are.

With N evenly balanced nodes, adding one node moves roughly 1 / (N + 1) of the keys. It does not remap the whole keyspace.

Removing a Node

When a node leaves, only its range moves to the next clockwise node.

If S4 leaves, the keys previously assigned to S4 move to its successor. Other ranges are unchanged.

This is the central benefit: membership changes cause local movement, not global reshuffling.

Basic consistent hashing places each physical node at one point on the ring. That is usually not enough.

With only one point per node, the ranges can be uneven. One node may own a large slice of the ring while another owns a small slice. If a node fails, its entire range moves to one successor, which can overload that successor.

Virtual nodes, often called vnodes, fix this by placing each physical node at many positions on the ring.

Instead of this:

use this:

Each virtual node maps back to a physical node.

Benefits:

Virtual nodes are the difference between the clean classroom version of consistent hashing and a version you can operate in production.

Consistent hashing decides the primary owner of a key. Many real systems also need replicas.

A common approach is:

For a replication factor of 3, a key may be stored on:

Production systems usually add placement constraints:

Consistent hashing is placement logic. It does not by itself provide replication, quorum reads, conflict resolution, or durability. Those are separate parts of the storage design.

The implementation below uses:

For production code, use a fast, stable, well-distributed non-cryptographic hash such as MurmurHash, xxHash, or CityHash. The examples use SHA-256 because it is available in the standard libraries and produces stable output across runs.

Lookup is O(log V), where V is the number of virtual nodes. Adding or removing a physical server is O(R log V), where R is the number of virtual nodes assigned to that server.

Consistent hashing is useful, but production systems still need operational guardrails.

Use a Stable Node Identity

The node identifier must not change accidentally. If the ring uses an IP address and the instance gets a new IP, the system may treat the same machine as a different node and move keys unnecessarily.

Prefer stable identifiers:

Use Enough Virtual Nodes

Too few virtual nodes produce uneven load. Too many increase memory usage and membership update cost.

The right number depends on fleet size, key distribution, node capacity differences, and how often membership changes. In many cache clients, tens to hundreds of virtual nodes per physical node is a common starting point. Storage systems may use a more deliberate token or partition assignment strategy.

Account for Uneven Key Popularity

Consistent hashing balances key ownership, not request volume.

If one key is extremely hot, the node that owns it can still overload. Common mitigations include:

Do Not Confuse Routing with Rebalancing

Changing the ring changes where keys should live. It does not move the data by itself.

A storage system needs background migration, repair, checksums, throttling, and progress tracking. A cache can often tolerate cold misses, but a database cannot simply forget the old owner.

Keep Membership Consistent Enough

Clients need a reasonably consistent view of the ring. If two clients use different membership lists, they may route the same key to different owners.

This is usually handled with:

Consider Alternatives

Consistent hashing is not the only stable assignment technique.

Many modern systems use fixed logical partitions rather than hashing directly to physical nodes. Keys map to partitions, and partitions move between nodes through a control plane. This gives operators more control over rebalancing, placement, and failure recovery.

Consistent hashing is a good fit when:

Common use cases:

It is less useful when requests are stateless and any node can serve any request. In that case, ordinary load balancing is usually simpler and more flexible.

Consistent hashing provides stable key ownership in a changing cluster.

Key takeaways:

Use consistent hashing when stable ownership matters. Do not use it as a substitute for ordinary load balancing when every node can handle every request.