Performance & Scalability consistent-hashing distributed-systems scalability Oleksandr Andrushchenko Published on — Modified on 1

What Is Consistent Hashing?

5.0 out of 5 from 1 votes
1 0

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 especially useful for distributed caches, key-value stores, storage systems, and request routing where millions of keys must be distributed across a changing group of nodes. Instead of reshuffling most keys whenever cluster membership changes, consistent hashing limits movement primarily to the ranges affected by the change.

Consistent Hashing
Consistent Hashing

Table of Contents

Hash Space

Consistent hashing starts with a hash space: a fixed range of possible hash values. Both data keys and, later, server identifiers are mapped into this same space.

A hash function converts an arbitrary key into a position in the hash space:

Hash Space
Hash Space

For example:

Input                    Hash Function               Hash Space

"user:1001" ────────────────→ H() ─────────────────→ 1842
"user:1002" ────────────────→ H() ─────────────────→ 7281
"product:42" ───────────────→ H() ─────────────────→ 3910

0 ─────────────────────────────────────────────── MAX

A real hash function usually produces a much larger number, but a simplified range from 0 to 9999 makes the placement logic easier to see.

The hash space itself is not yet consistent hashing. The important step is using the same stable space to position both keys and nodes. Consistent hashing then determines which node owns each part of that space.

The space is commonly visualized as a ring by treating the maximum hash value as wrapping back to zero. This creates the hash ring used for key placement.

The Problem with Modulo Hashing

Before looking at the hash ring, consider a simpler way to distribute keys across servers. A system can hash each key and use modulo arithmetic to select a server:

server_index = hash(key) % number_of_servers

With four servers:

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

This works while the number of servers remains constant. The problem appears when the cluster changes.

After adding a fifth server:

Before                 After

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

Changing the number of servers changes the divisor, so a large portion of keys can suddenly map to different servers even though only one server was added.

For a distributed cache, this can create a large cache-miss spike. For persistent storage, it can require moving a significant amount of data.

The same problem occurs when a server is removed and the calculation changes from:

hash(key) % 5

to:

hash(key) % 4

Consistent hashing avoids this dependency on the total number of servers. Instead of using the server count to calculate ownership, it gives both keys and nodes stable positions in the hash space. The next section turns that space into a ring and shows how those positions determine ownership.

Choosing a Stable Hash Function

The hash function is part of the placement algorithm. The same input must consistently produce the same position, and values should be distributed reasonably uniformly across the hash space.

A simple deterministic implementation can use SHA-256 and take part of the digest:

import hashlib


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

Cryptographic security is not normally the main requirement for consistent hashing. Stability and sufficiently uniform distribution are more important.

The hash function must also remain consistent across all participants. If two clients calculate different positions for the same key, they can disagree about which node owns it. Changing the hash function in an existing system can similarly remap a large part of the keyspace.

Hash Ring

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

The hash space is usually visualized as a ring because the maximum value wraps around to zero:

0 ───────────────────────────────→ MAX
↑                                   │
└──────────── wraparound ───────────┘

The ring is a logical representation. No physical circular structure is required. Implementations commonly store sorted hash positions and perform a lookup for the next position.

Hash Ring
Hash Ring

Placing Nodes on the Ring

Each server is hashed to determine its position.

hash("node-a") → 120
hash("node-b") → 410
hash("node-c") → 680
hash("node-d") → 880

The simplified ring now contains:

0
│
├── 120 → Node A
│
├── 410 → Node B
│
├── 680 → Node C
│
├── 880 → Node D
│
└── wrap to 0

These positions create ownership ranges around the ring.

Placing Keys on the Ring

Keys use the same hash space:

key-1 → 150
key-2 → 350
key-3 → 700
key-4 → 950

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

key-1 @ 150 → Node B @ 410
key-2 @ 350 → Node B @ 410
key-3 @ 700 → Node D @ 880
key-4 @ 950 → Node A @ 120 after wraparound

The number of servers does not appear in the placement calculation. The key belongs to a position in a stable hash space, and the ring determines which node owns that position.

Finding the Owner of a Key

An implementation does not need to scan every node.

If node positions are sorted:

[120, 410, 680, 880]

the system can use binary search to find the first position greater than or equal to the key hash.

import bisect


positions = [120, 410, 680, 880]

key_position = 350

index = bisect.bisect_left(positions, key_position)

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

owner_position = positions[index]

For position 350, the result is 410, so Node B owns the key.

Adding a Node

The main advantage of consistent hashing becomes visible when cluster capacity changes.

Suppose the current ring contains:

Node A → 120
Node B → 410
Node C → 680
Node D → 880

A new Node E is added at position 300:

Node A → 120
Node E → 300   ← new
Node B → 410
Node C → 680
Node D → 880

Before Node E existed, Node B owned the range after Node A up to Node B:

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

After Node E joins:

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

Only the part of Node B's previous range captured by Node E changes ownership.

Keys belonging to unrelated ranges owned by Nodes A, C, and D do not need to move.

Adding a Node
Adding a Node

How Much Data Moves?

With traditional modulo hashing, adding one node can change the destination of a large percentage of keys because the divisor changes globally.

With a well-balanced consistent-hashing ring, adding one equal-capacity node primarily transfers approximately that node's new share of the keyspace.

Consider 100 cache servers holding 500 million keys. Adding server 101 should ideally move roughly the new server's share of keys rather than invalidating mappings for hundreds of millions of unrelated objects.

Approach Adding a Node
Modulo hashing Large portion of keys can be remapped
Consistent hashing Primarily affected ownership ranges move

This property makes consistent hashing useful in systems that scale horizontally.

Removing a Node

The same principle applies when a node is intentionally removed or unexpectedly disappears.

Suppose the ring contains:

Node A → 120
Node B → 410
Node C → 680
Node D → 880

If Node B disappears, only the range previously owned by Node B needs another owner.

Before:

Node A ── keys ──→ Node B ── keys ──→ Node C


After Node B disappears:

Node A ─────────── keys ────────────→ Node C

Using clockwise ownership, Node C becomes responsible for Node B's former range.

Other ranges remain unchanged.

Removing a Node
Removing a Node

Node Failure

Consistent hashing determines where keys should be routed after a failure. It does not automatically guarantee that the data is available there.

For a disposable cache, the new owner can simply receive a cache miss:

Node B fails
     ↓
key now maps to Node C
     ↓
MISS
     ↓
read database
     ↓
populate Node C

For persistent storage, that is not sufficient. The data must already be replicated somewhere or recovered and transferred to its new owner.

This distinction is important: consistent hashing solves placement, not durability.

Virtual Nodes

Placing every physical server at only one random point on the ring can produce poor distribution.

Consider four nodes:

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

The ownership ranges are dramatically different in size. If keys are uniformly distributed, one node can receive much more data than another.

Virtual nodes, or vnodes, solve this by representing every physical server at multiple positions around the ring.

Physical Node A:

A-0 → 80
A-1 → 310
A-2 → 720


Physical Node B:

B-0 → 190
B-1 → 520
B-2 → 900

Instead of owning one contiguous section of the ring, each physical server owns many smaller ranges distributed throughout the hash space.

Virtual Nodes
Virtual Nodes

Why Virtual Nodes Matter

Virtual nodes improve several properties at once.

  • Key distribution becomes more even.
  • Physical-node failures affect many smaller ranges rather than one large range.
  • Rebalancing can spread transferred ranges across multiple surviving servers.
  • Different physical capacities can receive different numbers of virtual nodes.

A simple vnode generator:

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

If every physical server receives 200 virtual nodes, a 20-server cluster contains:

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

More virtual nodes generally improve statistical balance, but they also increase ring metadata, membership-update work, and rebalancing complexity.

Weighted Consistent Hashing

Physical nodes are not always equal.

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

Assigning all three nodes the same amount of data may underuse Node C while overloading the smaller machines.

Virtual nodes can represent capacity:

node-a → 100 vnodes
node-b → 100 vnodes
node-c → 400 vnodes

Node C receives approximately four times as many positions and therefore a larger expected share of the keyspace.

Weights should reflect the actual workload bottleneck. CPU count may be irrelevant if the service is constrained primarily by memory, network throughput, storage IOPS, or connection limits.

Replication with Consistent Hashing

Assigning each key to only one physical node creates a single point of failure for that key.

A common extension stores replicas on additional distinct nodes around the ring.

Key K
  │
  ├── Primary → Node B
  ├── Replica → Node C
  └── Replica → Node D

With virtual nodes, the implementation must distinguish between virtual positions and physical failure domains.

Three consecutive virtual nodes might all belong to the same physical server:

K → B-17 → B-81 → B-122

That is not three independent replicas.

Replica placement should therefore select distinct physical nodes and, where required, distinct racks, availability zones, or regions.

Replication also creates consistency questions. Multiple copies require rules for reads, writes, synchronization, conflicts, and recovery. Consistency Models in Distributed Systems covers those trade-offs in more detail.

Consistent Hashing in Distributed Caches

Distributed caching is one of the classic consistent-hashing use cases.

Suppose an application has eight cache servers and needs to locate:

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

Repeated lookups for the same key route to the same cache node as long as relevant ring membership does not change.

If cache-3 disappears, only keys belonging to its virtual-node ranges need new owners.

This matters because cache membership changes can otherwise trigger a miss storm:

Cache node change
       ↓
mass key remapping
       ↓
cache misses
       ↓
database traffic spike
       ↓
database overload

Consistent hashing reduces the amount of cache state disturbed by the membership change.

It does not eliminate the need to design for cache failures. Caching Best Practices for Distributed Applications covers cache availability, invalidation, fallback behavior, and production scaling in more detail.

Consistent Hashing in Databases and Storage

Consistent hashing can also map database partitions or storage objects to nodes.

image:1001
image:1002
image:1003
image:1004
     │
     ↓
   hash()
     │
     ↓
partition / node ownership

When capacity changes, only affected ranges need new owners.

For durable data, however, changing ownership is not enough.

Old owner
    │
    │ copy range
    ↓
New owner
    │
    │ verify / synchronize
    ↓
ownership switch
    │
    ↓
old copy removed when safe

A range can contain terabytes of data, so rebalancing may consume storage bandwidth, network capacity, CPU, and replication resources for hours.

Consistent hashing answers:

Which node should own this key?

It does not by itself answer:

How is durable data safely transferred to that node?

This also distinguishes consistent hashing from sharding. Sharding describes partitioning a dataset across database partitions; consistent hashing is one possible mechanism for mapping keys or partitions to nodes. Database Sharding Strategies and Trade-Offs covers the broader database design problem.

Consistent Hashing for Load Balancing

Consistent hashing can route requests as well as data.

A load balancer can hash a stable attribute such as:

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

For example:

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

This creates routing affinity without maintaining an explicit mapping for every key.

It can be useful when backend servers maintain local caches because repeated requests for the same key tend to reach the same machine.

But consistent hashing distributes hash ranges, not necessarily real traffic.

tenant-a → 1% traffic
tenant-b → 2% traffic
tenant-c → 35% traffic

If tenant-c hashes to one backend, that server can become overloaded even when every backend owns an equal portion of the hash space.

Hot-key and workload skew therefore still need separate handling. Round Robin vs Least Connections vs Consistent Hashing compares these different routing objectives.

Production Design Example

Consider a distributed cache storing 500 million product, session, and user objects across 20 equal-capacity servers.

Each physical server receives 200 virtual nodes:

20 servers
× 200 vnodes
= 4,000 positions

The application maintains the ring as a sorted list of positions.

A simplified implementation:

import bisect
import hashlib


class ConsistentHashRing:
    def __init__(self, virtual_nodes: int = 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]]

Nodes are registered:

ring = ConsistentHashRing()

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

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

The lookup hashes the key and uses binary search to locate the next vnode clockwise.

Now traffic increases and cache-21 is added.

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

Because this is a cache, explicit migration may not even be necessary:

old mapping:
product:847219 → cache-7

new mapping:
product:847219 → cache-21
                      │
                      ↓
                    MISS
                      │
                      ↓
                  database
                      │
                      ↓
                 populate cache

The affected cache entries can warm naturally on demand.

This temporarily increases database traffic, so scaling should still be controlled. Adding many cache nodes simultaneously could move enough ranges to produce a significant origin-load spike.

Suppose production metrics before scaling are:

Cache hit rate:          97.5%
Cache requests:         180k/s
Database fallback:      4.5k/s
Cache GET p95:           1.8 ms
Database read p95:        24 ms

After adding five nodes at once:

Cache hit rate:          82.0%
Database fallback:       32k/s
Database CPU:              91%

The ring behaved correctly, but operationally the change was too aggressive.

A safer rollout can add capacity gradually, monitor the miss rate and database load, and continue only when the system stabilizes.

For persistent storage, the process is different. Data cannot simply disappear from the old owner and be recreated on demand. Ownership changes need coordinated range migration, replication, verification, and recovery behavior.

This is an important production distinction: the same consistent-hashing algorithm can require very different rebalancing procedures depending on whether the underlying data is disposable or durable.

Common Consistent Hashing Mistakes

  • Using one ring position per physical node. Random placement can create severely uneven ownership.
  • Using too few virtual nodes. Small clusters can remain poorly balanced.
  • Assuming equal key ranges mean equal workload. Hot keys and large tenants can dominate traffic.
  • Changing the hash function. A new function can remap nearly the entire keyspace.
  • Using inconsistent membership views. Two clients with different rings can route the same key to different nodes.
  • Ignoring heterogeneous hardware. Equal ownership can overload smaller nodes.
  • Confusing placement with migration. Calculating the new owner does not move durable data safely.
  • Confusing placement with replication. Consistent hashing alone does not create redundant copies.
  • Ignoring failure domains. Multiple vnode replicas can accidentally map to the same physical machine or availability zone.
  • Using unstable routing keys. Frequently changing keys eliminate the affinity benefit.
  • Adding too much capacity at once. Even limited remapping can create a significant cache miss or migration spike.
  • Monitoring only key counts. Balanced key ownership can still produce unbalanced CPU, memory, network, or request load.

When to Use Consistent Hashing

Consistent hashing is especially useful when three conditions appear together:

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

Common use cases include distributed caches, partitioned key-value stores, object placement, request affinity, and horizontally scaled storage systems.

It is less useful when all backends are stateless and any request can go anywhere, when data already has fixed explicit partition ownership, or when a central coordinator manages placement directly.

Consistent hashing is also not automatically the right database-partitioning algorithm. Range partitioning can be preferable when range scans matter. Explicit directory-based placement can be better when operators need precise control over where data lives.

The algorithm should solve a concrete movement or affinity problem rather than being added simply because the system is distributed.

Frequently Asked Questions

Consistent hashing is conceptually simple, but several related concepts are easy to mix together. The most important distinction is between key placement, load balancing, replication, and physical data migration.

How Is Consistent Hashing Different from Normal Hashing?

The hash function itself is not necessarily special. The important difference is how the hash output is mapped to nodes.

Modulo-based placement depends directly on the number of servers, so changing that number can remap many keys. Consistent hashing places keys and nodes in a stable hash space so membership changes affect primarily neighboring ownership ranges.

Does Consistent Hashing Guarantee Balanced Load?

No. Virtual nodes can improve keyspace distribution, but actual workload can still be uneven.

One hot key, customer, or tenant can generate far more traffic than thousands of other keys combined. Production systems should monitor actual CPU, memory, network, latency, and request distribution rather than assuming a balanced ring means balanced load.

Does Consistent Hashing Replicate Data?

No. Consistent hashing determines placement.

A system can build replication on top of the ring by selecting additional physical nodes for each key, but replication factor, failure-domain placement, consistency, synchronization, and recovery are separate design decisions.

How Many Virtual Nodes Are Needed?

There is no universal number. More virtual nodes generally improve distribution but increase metadata and membership-management overhead.

The appropriate count depends on cluster size, capacity differences, acceptable imbalance, implementation cost, and how frequently nodes join or leave. Distribution should be measured rather than relying on an arbitrary vnode count.

Is Consistent Hashing the Same as Sharding?

No. Sharding is the broader technique of dividing data across multiple partitions or databases.

Consistent hashing is one possible strategy for deciding which node should own a key or partition. A sharded database can instead use range partitioning, directory-based routing, fixed hash buckets, or other placement strategies.

Conclusion

Consistent hashing distributes keys across a changing group of nodes while minimizing how much of the mapping changes when nodes join or leave. Instead of tying placement to hash(key) % N, keys and nodes occupy a stable hash space represented as a ring.

Adding or removing a node changes only affected ownership ranges. Virtual nodes improve distribution and enable capacity weighting, while replication can add availability and durability across physical failure domains.

The algorithm does not solve every distributed-data problem. Migration, replication, consistency, hot keys, membership coordination, and failure recovery remain separate engineering concerns.

Key takeaway: consistent hashing is primarily a placement strategy. Its value is that changing cluster capacity can move only the keys that need a new owner instead of reshuffling the entire distributed system.

Comments (0)

Related articles