Consistent Hashing

Background

While designing a scalable system, the most important aspect is defining how the data will be partitioned and replicated across servers. Let's first define these terms before moving on:

Data partitioning: It is the process of distributing data across a set of servers. It improves the scalability and performance of the system.

Data replication: It is the process of making multiple copies of data and storing them on different servers. It improves the availability and durability of the data across the system.

Data partition and replication strategies lie at the core of any distributed system. A carefully designed scheme for partitioning and replicating the data enhances the performance, availability, and reliability of the system and also defines how efficiently the system will be scaled and managed.

David Karger et al. first introduced Consistent Hashing in their 1997 paper and suggested its use in distributed caching. Later, Consistent Hashing was adopted and enhanced to be used across many distributed systems. In this lesson we will see how Consistent Hashing efficiently solves the problem of data partitioning and replication.

What is data partitioning?

As stated above, the act of distributing data across a set of nodes is called data partitioning. There are two challenges when we try to distribute data:

1. How do we know on which node a particular piece of data will be stored?

2. When we add or remove nodes, how do we know what data will be moved from existing nodes to the new nodes? Additionally, how can we minimize data movement when nodes join or leave?

A naive approach will use a suitable hash function to map the data key to a number. Then, find the server by applying modulo on this number and the total number of servers. For example:

The scheme described in the above diagram solves the problem of finding a server for storing/retrieving the data. But when we add or remove a server, all our existing mappings will be broken. This is because the total number of servers will be changed, which was used to find the actual server storing the data. So to get things working again, we have to remap all the keys and move our data based on the new server count, which will be a complete mess!

Consistent Hashing to the rescue

Distributed systems can use Consistent Hashing to distribute data across nodes. Consistent Hashing maps data to physical nodes and ensures that only a small set of keys move when servers are added or removed.

Consistent Hashing stores the data managed by a distributed system in a ring. Each node in the ring is assigned a range of data. Here is an example of the consistent hash ring:

With consistent hashing, the ring is divided into smaller, predefined ranges. Each node is assigned one of these ranges. The start of the range is called a token. This means that each node will be assigned one token. The range assigned to each node is computed as follows:

Range start:  Token value
Range end:    Next token value - 1

Here are the tokens and data ranges of the four nodes described in the above diagram:

Whenever the system needs to read or write data, the first step it performs is to apply the MD5 hashing algorithm to the key. The output of this hashing algorithm determines within which range the data lies and hence, on which node the data will be stored. As we saw above, each node is supposed to store data for a fixed range. Thus, the hash generated from the key tells us the node where the data will be stored.

The Consistent Hashing scheme described above works great when a node is added or removed from the ring, as in these cases, since only the next node is affected. For example, when a node is removed, the next node becomes responsible for all of the keys stored on the outgoing node. However, this scheme can result in non-uniform data and load distribution. This problem can be solved with the help of Virtual nodes.

Modulo vs consistent hashing: the numbers

The whole point of consistent hashing is the fraction of keys that must move when the cluster changes size.

A tiny concrete example makes this precise. Suppose keys 1–8 are spread over 4 nodes by modulo (key % 4). When a 5th node is added, the mapping becomes key % 5. A key keeps its node only when key % 4 == key % 5 — true only for keys 1, 2, 3; keys 4, 5, 6, 7, 8 all move, so 5 of 8 (62.5%) relocate here, trending to the asymptotic n/(n+1) = 4/5 = 80% as the keyspace grows. Under consistent hashing, the 5th node takes over one contiguous arc of the ring; only the keys in that arc move — about 1/(n+1) ≈ 1/5 = 20%. As n grows, that gap becomes the difference between a cluster-wide migration and a routine rebalance.

Virtual nodes

Adding and removing nodes in any distributed system is quite common. Existing nodes can die and may need to be decommissioned. Similarly, new nodes may be added to an existing cluster to meet growing demands. To efficiently handle these scenarios, Consistent Hashing makes use of virtual nodes (or Vnodes).

As we saw above, the basic Consistent Hashing algorithm assigns a single token (or a consecutive hash range) to each physical node. This was a static division of ranges that requires calculating tokens based on a given number of nodes. This scheme made adding or replacing a node an expensive operation, as, in this case, we would like to rebalance and distribute the data to all other nodes, resulting in moving a lot of data. Here are a few potential issues associated with a manual and fixed division of the ranges:

• Adding or removing nodes: Adding or removing nodes will result in recomputing the tokens causing a significant administrative overhead for a large cluster.
• Hotspots: Since each node is assigned one large range, if the data is not evenly distributed, some nodes can become hotspots.
• Node rebuilding: Since each node's data might be replicated (for fault-tolerance) on a fixed number of other nodes, when we need to rebuild a node, only its replica nodes can provide the data. This puts a lot of pressure on the replica nodes and can lead to service degradation.

To handle these issues, Consistent Hashing introduces a new scheme of distributing the tokens to physical nodes. Instead of assigning a single token to a node, the hash range is divided into multiple smaller ranges, and each physical node is assigned several of these smaller ranges. Each of these subranges is considered a Vnode. With Vnodes, instead of a node being responsible for just one token, it is responsible for many tokens (or subranges).

Advantages of Vnodes

Vnodes gives the following advantages:

1. As Vnodes help spread the load more evenly across the physical nodes on the cluster by dividing the hash ranges into smaller subranges, this speeds up the rebalancing process after adding or removing nodes. When a new node is added, it receives many Vnodes from the existing nodes to maintain a balanced cluster. Similarly, when a node needs to be rebuilt, instead of getting data from a fixed number of replicas, many nodes participate in the rebuild process.
2. Vnodes make it easier to maintain a cluster containing heterogeneous machines. This means, with Vnodes, we can assign a high number of sub-ranges to a powerful server and a lower number of sub-ranges to a less powerful server.
3. In contrast to one big range, since Vnodes help assign smaller ranges to each physical node, this decreases the probability of hotspots.

Why the basic ring is unbalanced — and how many Vnodes are enough

The imbalance of the single-token ring is not bad luck; it is a property of random arc sizes. Place n tokens at random on the ring and the arcs between them come out wildly unequal: the expected largest arc is about (ln n)/n of the ring — several times the fair share of 1/n. Concretely, with 10 nodes the biggest arc averages roughly 29% of the keyspace (H₁₀/10 ≈ 2.93 × the fair 10% share), so one node systematically absorbs about 3× the average load while its luckiest peer sits nearly idle. A uniform hash function cannot fix this — the keys are spread evenly, but the arcs they land in are not.

Virtual nodes fix this statistically, and they give you a sizing dial. With V tokens per physical node, a node's total share is the sum of V independent small arcs, so a typical node's deviation from its fair share shrinks roughly as 1/√V: about ±10% at V = 100, about ±6% at V = 256 (the worst node in a cluster runs somewhat hotter, around 1.8× that one-sigma figure). This is exactly the dial production systems expose: Cassandra's num_tokens defaulted to 256 for years, and Cassandra 4.0 lowered the default to 16 — affordable only because it pairs the smaller count with a deliberate token-placement algorithm (allocate_tokens_for_local_replication_factor) instead of random tokens. More vnodes buy balance but cost ring-metadata size, gossip and repair bookkeeping, and more overlapping replica sets, so you pick the smallest V that meets your balance target.

Data replication using Consistent Hashing

To ensure high availability and durability, Consistent Hashing replicates each data item on N nodes (the replication factor).

The replication factor is the number of nodes that will receive the copy of the same data. For example, a replication factor of two means there are two copies of each data item, where each copy is stored on a different node.

Each key is assigned to a coordinator node (generally the first node that falls in the hash range), which first stores the data locally and then replicates it to clockwise successor nodes on the ring. This results in each node owning the region on the ring between it and its predecessor. In an eventually consistent system, this replication is done asynchronously (in the background).

In eventually consistent systems, copies of data don't always have to be identical as long as they are designed to eventually become consistent. In distributed systems, eventual consistency is used to achieve high availability.

Replica placement with Vnodes: skip your own tokens

Vnodes introduce a correctness trap in the replication scheme above. "Replicate to the N−1 clockwise successors" walks tokens, and adjacent tokens can belong to the same physical node. Worked failure case: nodes A, B, C each hold several vnodes, and one stretch of the ring reads … 20 → A2, 25 → A3, 33 → C1, 41 → B2 … A key in A2's range with N = 3 is copied to the next two tokens — A3 and C1 — leaving two of the three replicas on physical machine A. You believe you have 3-way redundancy, but if machine A dies you are down to a single copy on C, and one more failure loses the data. That is why real systems walk the ring but skip successors until N distinct physical nodes (or racks) are found: Dynamo builds its preference list exactly this way, and Cassandra's NetworkTopologyStrategy additionally skips tokens in the same rack. In the trace above, the corrected walk is A2 → C1 → B2: three replicas, three machines.

Consistent Hashing in System Design Interviews

As we saw above, Consistent Hashing helps with efficiently partitioning and replicating data; therefore, any distributed system that needs to scale up or down or wants to achieve high availability through data replication can utilize Consistent Hashing. A few such examples could be:

• Any system working with a set of storage (or database) servers and needs to scale up or down based on the usage, e.g., the system could need more storage during Christmas because of high traffic.
• Any distributed system that needs dynamic adjustment of its cache usage by adding or removing cache servers based on the traffic load.
• Any system that wants to replicate its data shards to achieve high availability.

Consistent Hashing use cases

Amazon's Dynamo and Apache Cassandra use Consistent Hashing to distribute and replicate data across nodes.

Worked Example: Virtual Nodes in Action

Imagine a cluster with four physical nodes (A, B, C, D) and a hash ring of 64 positions. Without virtual nodes, each physical node owns one large arc:

• A owns positions 0–15, B owns 16–31, C owns 32–47, D owns 48–63.

If keys are not uniformly distributed, node A might get 60% of the traffic while node D gets 10%. With virtual nodes, each physical node is assigned, say, four virtual nodes (four keeps the picture readable; real systems use tens to hundreds per node, per the 1/√V sizing rule above):

• A owns virtual nodes A1, A2, A3, A4 at positions 3, 19, 35, 51.
• B owns B1, B2, B3, B4 at positions 7, 23, 39, 55.
• C and D similarly scatter four tokens each around the ring.

Now each physical node is responsible for many small arcs. A hot key still lands on one virtual node, but the average load per physical node smooths out because every physical node has tokens spread across the ring. If node E joins, it receives a few virtual nodes from each existing node; the data moved is roughly 1/5 of the total, and the transfer load is distributed across all nodes, not just one neighbor.

Rebalancing Cost Trace

Suppose 100M keys are stored across 10 nodes. A new node joins.

• Modulo sharding: key % 10 becomes key % 11. Roughly 9/10 of the keys (90M) change node assignment. In practice, almost every key must be rehashed and moved.
• Consistent hashing without virtual nodes: The new node takes over one contiguous arc from its successor. Approximately 1/10 of the keys (10M) move.
• Consistent hashing with virtual nodes (e.g., 100 virtual nodes per physical node — enough, by the 1/√V rule above, to hold a typical node within roughly ±10% of average load): The new node receives about 10% of the virtual nodes, and those virtual nodes are stolen evenly from all existing nodes. Again ~10M keys move, but the work is parallelized across the cluster instead of concentrated on one node.

Why this matters in production: Rebalancing is not free. 90M key moves can saturate network and disk for minutes; 10M evenly distributed moves can finish in the background without noticeable latency spikes. Virtual nodes also speed up recovery: when a node fails, its virtual-node replicas are spread across many peers, so rebuild traffic is not concentrated on one backup.

Consistent Hashing vs. Modulo Sharding: A Deeper Comparison

When NOT to Use Consistent Hashing

• Small, static clusters: Modulo sharding is simpler and perfectly fine if nodes rarely change.
• Strong locality requirements: If clients or queries depend on keys being colocated in a specific way, a range-based partition scheme may be clearer.
• When even load is critical and hash quality is poor: Consistent hashing can still produce hotspots if the hash function or token distribution is bad; virtual nodes help but do not eliminate the need for a good hash.

Modern alternatives to the ring

The ring is one construction of consistent hashing, not the only one — and the when-NOT list above has newer answers than "fall back to modulo." Note first that ring lookup itself is cheap: tokens live in a sorted array, so finding a key's successor is a binary search — O(log T) for T total tokens (T = nodes × vnodes per node).

Interactive walkthrough

Predict the next step in the consistent-hashing scenario.

Interview Checklist

• Draw the hash ring and explain how a key finds its node.
• Quantify the keys that move when a node joins or leaves, with and without virtual nodes.
• Explain why virtual nodes improve load balance and recovery parallelism.
• Compare to modulo sharding and name a scenario where modulo is the better choice.
• Discuss replication: how many clockwise successors hold replicas, and what happens when a node fails?