What Is Consistent Hashing?

Consistent hashing is a data-distribution technique that minimizes how many keys need to move when servers are added to or removed from a distributed system.

It is useful for distributed caches, databases, storage systems, load balancers, and other architectures where millions of keys must be spread across changing groups of nodes without reshuffling almost everything whenever cluster membership changes.

Table of Contents

• The Problem with Normal Hashing
• How Consistent Hashing Works
  • Placing Nodes on the Hash Ring
  • Placing Keys on the Hash Ring
• What Happens When a Node Is Added?
• What Happens When a Node Is Removed?
• Why Consistent Hashing Reduces Data Movement
• The Uneven Distribution Problem
• Virtual Nodes
• Weighted Consistent Hashing
• Consistent Hashing in Distributed Caches
• Consistent Hashing in Databases and Storage
• Consistent Hashing for Load Balancing
• Replication with Consistent Hashing
• Production Design Example
• Common Consistent Hashing Mistakes
• When to Use Consistent Hashing
• Conclusion
  • More Articles to Read

The Problem with Normal Hashing

Suppose a distributed cache has four servers:

cache-1
cache-2
cache-3
cache-4

A simple way to choose a server is to hash the cache key and use modulo arithmetic:

server_index = hash(key) % number_of_servers

For four servers:

server_index = hash(key) % 4

Suppose several keys produce these hashes:

user:1001 → 103 → 103 % 4 = 3
user:1002 → 208 → 208 % 4 = 0
user:1003 → 315 → 315 % 4 = 3
user:1004 → 422 → 422 % 4 = 2

This works well while the number of servers remains constant.

Now traffic increases and a fifth cache server is added.

server_index = hash(key) % 5

The mapping changes:

103 % 4 = 3    →    103 % 5 = 3
208 % 4 = 0    →    208 % 5 = 3
315 % 4 = 3    →    315 % 5 = 0
422 % 4 = 2    →    422 % 5 = 2

Many keys suddenly point to different servers even though only one server was added.

With millions of cached objects, most lookups may now go to nodes that do not contain the expected data. The result can be a massive cache miss spike.

The same problem appears when a server fails and the calculation changes from:

hash(key) % 5

to:

hash(key) % 4

Traditional modulo hashing tightly couples key placement to the total number of nodes.

Consistent hashing removes most of that coupling.

How Consistent Hashing Works

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

The hash space is usually visualized as a ring because the largest hash value wraps around to the smallest value.

0 ───────────────→ hash space ───────────────→ MAX
↑                                               |
└────────────────── wraps around ───────────────┘

For example, a simplified system could use a hash space from 0 to 999.

Placing Nodes on the Hash Ring

Each server is hashed to determine its position:

hash("cache-1") → 120
hash("cache-2") → 410
hash("cache-3") → 680
hash("cache-4") → 880

The logical ring contains:

120        410        680        880
 A          B          C          D

These positions define ownership ranges.

Placing Keys on the Hash Ring

Keys are hashed using the same hash space:

user:1001 → 150
user:1002 → 350
user:1003 → 700
user:1004 → 950

A common rule assigns each key to the first node encountered clockwise from the key's position.

The resulting mapping is:

user:1001 @ 150 → B @ 410
user:1002 @ 350 → B @ 410
user:1003 @ 700 → D @ 880
user:1004 @ 950 → A @ 120 after wraparound

The key is not assigned using the number of servers. Its placement depends on neighboring positions in the hash space.

That difference makes cluster membership changes much less disruptive.

What Happens When a Node Is Added?

Suppose a new server E hashes to position 300.

Before the change:

A @ 120
B @ 410
C @ 680
D @ 880

After adding E:

A @ 120
E @ 300
B @ 410
C @ 680
D @ 880

Previously, keys between positions 120 and 410 belonged to B.

After E joins, keys between 120 and 300 move to E. Keys between 300 and 410 remain on B.

Before:

120 ----------------------------- 410
 A                                 B
 |----------- owned by B ----------|

After:

120 ------------ 300 ------------ 410
 A                E                B
 |-- owned by E --|-- owned by B --|

Other ranges remain unchanged.

Keys owned by C and D do not need to move simply because E joined the cluster.

This localized redistribution is the main advantage of consistent hashing.

What Happens When a Node Is Removed?

The same property applies when a node disappears.

Suppose the ring contains:

A @ 120
B @ 410
C @ 680
D @ 880

If C fails, only the range previously assigned to C needs a new owner.

Using clockwise ownership, those keys move to D.

Before:
B @ 410 → keys → C @ 680 → D @ 880

After C fails:
B @ 410 → keys ─────────→ D @ 880

A and B keep their existing ranges.

This makes consistent hashing useful for systems where nodes frequently join, leave, restart, fail, or scale automatically.

Why Consistent Hashing Reduces Data Movement

With modulo hashing, changing the number of servers changes the divisor:

hash(key) % N

Changing N changes the result for a large portion of keys.

With consistent hashing, node membership changes only alter nearby ownership boundaries on the ring.

With a well-balanced ring containing N equal-capacity nodes, adding one node should move roughly the new node's share of keys rather than redistributing the entire dataset.

For a large cluster, this difference can be enormous.

Imagine 100 cache nodes storing 500 million keys. Adding node 101 should ideally move roughly 1% of the keyspace, not invalidate mappings for hundreds of millions of unrelated keys.

The Uneven Distribution Problem

A naive implementation hashes each physical server to one position on the ring.

Random placement can create very uneven ranges.

Suppose four servers land at:

A → 100
B → 150
C → 200
D → 800

The ranges are very different in size.

A → small range
B → small range
C → small range
D → very large range

If keys are distributed uniformly across the hash space, the node responsible for the large range receives much more data and traffic.

Adding more physical nodes improves statistical balance, but production systems generally need a more reliable solution.

That solution is usually virtual nodes.

Virtual Nodes

Instead of placing each physical server on the ring once, a system places it many times.

These positions are called virtual nodes, often shortened to vnodes.

For example:

Server A:
A-1 → 80
A-2 → 310
A-3 → 720

Server B:
B-1 → 190
B-2 → 520
B-3 → 900

The physical nodes are now spread across multiple parts of the hash space.

A simple implementation can generate positions from a server identifier and virtual-node number:

import hashlib


def hash_value(value: str) -> int:
    digest = hashlib.sha256(value.encode()).digest()
    return int.from_bytes(digest[:8], "big")


def vnode_positions(server: str, count: int) -> list[int]:
    return [
        hash_value(f"{server}:{index}")
        for index in range(count)
    ]

With enough virtual nodes, uneven individual ranges are averaged across the same physical server.

Virtual nodes also make rebalancing smoother.

If one physical server disappears, its virtual-node ranges can be distributed across multiple surviving servers instead of transferring one large contiguous range to a single neighbor.

The number of virtual nodes is a trade-off. More vnodes generally improve distribution but increase ring metadata, lookup structures, membership updates, and rebalancing complexity.

Weighted Consistent Hashing

Not every server has the same capacity.

A cluster might contain:

server-a → 8 CPU, 32 GB RAM
server-b → 8 CPU, 32 GB RAM
server-c → 32 CPU, 128 GB RAM

Giving each server the same share of keys wastes the additional capacity of server-c.

Virtual nodes provide a straightforward way to introduce weighting.

For example:

server-a → 100 virtual nodes
server-b → 100 virtual nodes
server-c → 400 virtual nodes

The larger server receives approximately four times as many positions and therefore a larger portion of the keyspace.

Weights should reflect the actual bottleneck. CPU capacity alone may not represent useful capacity if the workload is constrained by memory, network throughput, storage IOPS, or connection limits.

Consistent Hashing in Distributed Caches

Distributed caches are a classic use case for consistent hashing.

Suppose an application has eight cache servers and needs to find the node responsible for:

product:847219

The application hashes the key and finds its owner on the ring.

product:847219
      ↓
hash(key)
      ↓
find next vnode
      ↓
cache-6

If cache-3 disappears, only keys assigned to cache-3's virtual nodes need new owners.

Without stable distribution, changing cache capacity can trigger a large miss storm. Requests that previously hit memory suddenly reach the database or origin service.

This can turn a harmless cache scaling event into database overload.

Caching Best Practices for Distributed Applications covers additional failure, invalidation, and scaling concerns for distributed caches.

Consistent Hashing in Databases and Storage

Consistent hashing can also assign partitions or objects to storage nodes.

Consider objects identified by keys:

image:1001
image:1002
image:1003
image:1004

Each key can be hashed into a partitioning space, and ownership can be assigned to nodes responsible for nearby ranges.

When capacity is added, only affected ranges need to migrate.

This does not make rebalancing free. Moving a range can still involve terabytes of data, background network traffic, replication, consistency coordination, and temporary capacity pressure.

Consistent hashing solves the placement problem: determining which keys should move and where they belong. The storage system still needs mechanisms for safely transferring that data.

This distinction is important when comparing consistent hashing with database sharding. Sharding describes dividing data across multiple database partitions, while consistent hashing is one possible technique for mapping keys or partitions to nodes.

Database Sharding Strategies and Trade-Offs covers the broader data-partitioning decisions involved in horizontally scaled databases.

Consistent Hashing for Load Balancing

Consistent hashing can also be used for request routing.

A load balancer might hash a stable request attribute such as:

• customer ID;
• session ID;
• tenant ID;
• URL;
• cache key.

The resulting hash determines which backend receives the request.

This provides routing affinity. Requests with the same key tend to reach the same backend.

For example:

tenant-42 → hash → backend-c
tenant-42 → hash → backend-c
tenant-42 → hash → backend-c

If a backend is added, only part of the traffic mapping changes.

This can be valuable when backends maintain local caches. Stable routing improves the probability that repeated requests reach a node that already has the relevant data in memory.

However, the distribution of request keys matters. If one tenant produces 30% of all traffic, consistent hashing can repeatedly send that traffic to the same backend and create a hot node.

Consistent hashing balances hash ranges, not necessarily real workload.

Round Robin vs Least Connections vs Consistent Hashing compares consistent hashing with load-balancing algorithms designed around connections or simple request distribution.

Replication with Consistent Hashing

Assigning each key to exactly one server creates a durability and availability problem.

If the owner fails, its keys become unavailable unless the data exists elsewhere.

A ring can support replication by storing a key on multiple distinct nodes encountered around the ring.

With replication factor three:

Key K
  ↓
Primary → Node B
Replica → Node C
Replica → Node D

Virtual nodes require extra care because several consecutive vnode positions might belong to the same physical server.

Replication should normally choose distinct failure domains rather than blindly selecting the next three virtual positions.

In larger systems, placement may consider:

• physical server;
• rack;
• availability zone;
• region.

For example, three replicas on three virtual nodes backed by the same physical machine provide no protection from machine failure.

Replication also introduces consistency decisions. Multiple copies need rules for reads, writes, synchronization, conflict handling, and recovery.

Consistency Models in Distributed Systems explains the broader trade-offs that appear when data exists on multiple nodes.

Production Design Example

Consider a distributed cache with 20 servers. Each server has approximately the same memory and network capacity.

The system stores tens of millions of product and user objects.

A practical design could assign 200 virtual nodes to each physical cache server:

20 physical servers
× 200 virtual nodes
= 4,000 ring positions

The application maintains the ring as a sorted collection of hash positions.

A simplified Python implementation looks like this:

import bisect
import hashlib


class ConsistentHashRing:
    def __init__(self, virtual_nodes=200):
        self.virtual_nodes = virtual_nodes
        self.positions = []
        self.owners = {}

    def _hash(self, value: str) -> int:
        digest = hashlib.sha256(value.encode()).digest()
        return int.from_bytes(digest[:8], "big")

    def add_node(self, node: str) -> None:
        for index in range(self.virtual_nodes):
            position = self._hash(f"{node}:{index}")

            bisect.insort(self.positions, position)
            self.owners[position] = node

    def get_node(self, key: str) -> str:
        if not self.positions:
            raise RuntimeError("Hash ring is empty")

        key_position = self._hash(key)

        index = bisect.bisect_left(
            self.positions,
            key_position,
        )

        if index == len(self.positions):
            index = 0

        return self.owners[self.positions[index]]

A lookup is straightforward:

ring = ConsistentHashRing()

ring.add_node("cache-1")
ring.add_node("cache-2")
ring.add_node("cache-3")

node = ring.get_node("product:847219")

The sorted positions allow the application to locate the next virtual node efficiently.

Now suppose traffic increases and cache-21 is added.

Its 200 virtual nodes are inserted throughout the ring. Only ranges captured by those new positions change ownership.

For a cache, the application might not physically migrate every cached object. It can simply begin routing affected keys to the new owners and allow those entries to populate on demand.

That approach is much cheaper than explicit migration, but it temporarily increases cache misses.

A persistent database cannot usually discard old data this way. It needs controlled range migration before ownership changes are considered complete.

The same placement algorithm therefore leads to different operational procedures depending on whether the underlying data is disposable or durable.

Common Consistent Hashing Mistakes

Consistent hashing reduces remapping, but it does not automatically solve every distribution problem.

• Using one ring position per server. Random placement can create severely uneven ownership.
• Using too few virtual nodes. Distribution can remain unbalanced, especially in small clusters.
• Assuming equal ranges mean equal load. Hot keys or large tenants can dominate traffic regardless of hash distribution.
• Changing the hash function unexpectedly. A new hash algorithm can remap nearly the entire keyspace.
• Using inconsistent ring membership. Clients with different node lists may route the same key to different servers.
• Ignoring heterogeneous capacity. Equal placement can overload smaller nodes.
• Confusing placement with migration. Knowing the new owner does not safely transfer persistent data to it.
• Ignoring failure domains during replication. Multiple replicas can accidentally reside on infrastructure that fails together.
• Using unstable keys. If the routing key changes frequently, consistent hashing provides little affinity.

Production designs should monitor both key distribution and actual resource utilization. A mathematically balanced ring can still have badly unbalanced CPU, memory, network, or request load.

When to Use Consistent Hashing

Consistent hashing is useful when three properties appear together:

• many keys need to be distributed across multiple nodes;
• the node set changes over time;
• moving or remapping keys is expensive.

Common examples include distributed caches, partitioned storage, request affinity, and horizontally scaled key-value systems.

It is less useful when data already has stable explicit partition ownership, when all requests can be sent to any stateless backend, or when another coordinator controls placement centrally.

Consistent hashing is also not automatically the best sharding algorithm. Range partitioning may be preferable when range scans are important. Directory-based partitioning may be preferable when explicit placement control is required. Other hashing schemes can provide different balancing and movement properties.

The decision should come from the workload rather than from treating consistent hashing as a universal distributed-systems primitive.

Conclusion

Consistent hashing distributes keys across a changing set of nodes while limiting how much of the mapping changes when nodes join or leave. Instead of calculating placement with hash(key) % N, keys and nodes share a stable hash space.

Production implementations usually combine consistent hashing with virtual nodes, capacity weighting, replication, membership management, monitoring, and workload-aware balancing. The algorithm determines ownership efficiently, but data migration, consistency, hot-key handling, and failure recovery still require separate engineering decisions.

The key benefit is straightforward: changing cluster capacity should move only the data that needs a new owner, not reshuffle the entire distributed system.

More Articles to Read

• Load Balancing Explained: Distributing Traffic at Scale
• Database Scaling Explained: Vertical vs Horizontal Scaling
• Key-Value NoSQL Databases — Patterns, Trade-Offs, and Real-World Use Cases