Consistent Hashing with Virtual Nodes

Introduction

In our last lesson, we focused on data replication, exploring how creating copies of data across multiple nodes enhances availability and fault tolerance. We compared leader-follower and multi-leader architectures and delved into strategies for resolving write conflicts.

Now, we shift our focus from copying data to splitting it. This lesson introduces data partitioning (or sharding), a key technique for achieving horizontal scalability. Specifically, we will address the learning outcome of applying consistent hashing with virtual nodes to distribute load or data evenly across a dynamic set of nodes. We will start by understanding why simple hashing methods fail in distributed systems and then build up the consistent hashing algorithm, piece by piece, to see how it provides a robust and scalable solution.

The Problem: Data Distribution in a Dynamic Cluster

Imagine you need to distribute data—perhaps user sessions for a large-scale web application or keys in a distributed cache—across a cluster of servers. A naive approach would be to use a simple modulo hash: server_index = hash(key) % N, where N is the number of servers. This method distributes keys fairly evenly, but it has a catastrophic weakness in dynamic environments.

The following video provides an excellent summary of this problem and sets the stage for why a better solution is needed.

Consistent Hashing ~ Key Concepts in System Design

This video from the "Hello Byte" channel introduces the data distribution problem in distributed systems.

Please watch the first part of the video, from the beginning until the end of the section on traditional hashing. Pay close attention to the example of how adding just one node forces a massive redistribution of existing keys.

As the video demonstrates, if you add or remove a server, the value of N changes. This changes the result of the modulo operation for the vast majority of keys, forcing a massive reshuffle of data across the entire cluster. For a distributed cache, this would trigger a "thundering herd" of cache misses, overwhelming your databases. For a distributed database, it would mean a costly and disruptive data migration. This is precisely the problem consistent hashing was designed to solve.

The Solution: The Consistent Hashing Ring

Consistent hashing tackles this remapping problem by decoupling the key-to-server mapping from the total number of servers. It does this by mapping both keys and servers onto the same abstract space, which is visualized as a circular ring.

The core algorithm works as follows:

Define the Ring: A hash space (e.g., from 0 to $2^{32} - 1$ ) is conceptualized as a ring.
Place Servers: Each server is assigned a position on the ring by hashing its identifier (e.g., its IP address or name).
Place Keys: To determine where a piece of data lives, its key is hashed to get a position on the same ring.
Assign Ownership: The data is assigned to the first server encountered when moving clockwise from the key's position on the ring.

This video segment provides a clear visual walkthrough of this process.

Consistent Hashing ~ Key Concepts in System Design

This part of the "Hello Byte" video explains the mechanics of the consistent hashing ring.

Watch the section that details how consistent hashing works. Focus on the ring visualization and how adding or removing a node only affects the data in the immediate preceding segment, not the entire ring.

The key insight is that when a server is added, it only takes ownership of the keys that fall between its new position and the next server's position. Similarly, when a server is removed, its keys are re-assigned to the next server clockwise. In either case, the change is localized, and the vast majority of keys remain on their original servers. On average, only 1/N of the keys need to move, a dramatic improvement over the (N-1)/N keys affected by modulo hashing.

From Theory to Practice: Virtual Nodes

While the basic consistent hashing ring solves the remapping problem, it introduces two new potential issues:

Non-uniform distribution: Servers might not land on the ring at evenly spaced intervals, causing some servers to be responsible for a much larger portion of the hash space than others.
Hotspots: If a server fails, all of its load is transferred to a single successor node, potentially overwhelming it.

To solve these problems, we introduce an enhancement: virtual nodes. Instead of placing a single point on the ring for each physical server, we place multiple virtual nodes. Each physical server is mapped to hundreds or even thousands of virtual nodes, each at a different position on the ring. For example, server-A might be represented by virtual nodes server-A:0, server-A:1, etc. A key is still assigned to the next node found clockwise, which will be a virtual node; that request is then routed to the physical server that owns the virtual node.

By adding many virtual nodes per physical server, the load is spread much more evenly across the ring, a result of the law of large numbers.

This diagram illustrates how virtual nodes create a more balanced distribution. Server B, having twice the capacity (weight 2.0), is assigned twice as many virtual nodes (4) as Server A (weight 1.0, 2 virtual nodes), ensuring it receives a proportional share of the load.

This image perfectly captures the benefits. Not only does it create a smoother distribution, but it also allows for weighted distribution. A more powerful server can simply be assigned more virtual nodes, naturally attracting a larger share of the keys.

The following reading provides a pattern-oriented view, showing how to progressively build a robust consistent hashing implementation.

How to Build Consistent Hashing Implementation

This article from OneUptime provides a practical guide to implementing consistent hashing, starting from the basics and adding key features like virtual nodes and weighting. It aligns perfectly with your preference for implementation patterns.

First, quickly read the introduction to see a side-by-side comparison of traditional vs. consistent hashing. Skim the basic implementation to understand the data structures involved (typically a sorted map or array for the ring). Carefully read the sections on virtual nodes. The code example and the simulated distribution results clearly demonstrate the improvement. Finally, read the section on weighted nodes. This shows how to use a different number of virtual nodes to direct more traffic to more capable servers, a crucial technique for real-world heterogeneous clusters.

The HARIL blog post reinforces this with experimental data, showing how increasing the number of virtual nodes from 10 to 100 drastically improves load balancing when a node fails. Feel free to review the graphs in Case 5 and Case 6 of that article if you wish to see a quantitative analysis.

A Real-World Architectural View

Consistent hashing is not just a theoretical algorithm; it's a cornerstone of many large-scale distributed systems, including databases like Cassandra and DynamoDB, and caches like Memcached.

The following architecture diagram shows how consistent hashing can be used in a high-throughput log ingestion pipeline.

A log ingestion system using consistent hashing. The "Storage Coordinator" manages the hash ring (with 150 virtual nodes per storage node) to distribute incoming logs from Kafka evenly across a cluster of PostgreSQL storage nodes.

In this system:

The Storage Coordinator is the component responsible for maintaining the consistent hash ring. It knows which physical storage nodes are active and where their virtual nodes are placed on the ring.
When a log message is consumed from Kafka, the coordinator hashes a key (e.g., the log's source) to find a position on the ring.
It then routes the log to the appropriate Storage Node (Node 1, 2, or 3) based on the clockwise assignment rule.
The use of 150 virtual nodes per server ensures that the logs are distributed almost perfectly evenly, as shown by the percentages (33.4%, 33.1%, 33.5%).
If a storage node were to fail, the coordinator would remove its virtual nodes from the ring, and logs would automatically be rerouted to their new owners with minimal disruption.

This architecture directly applies the patterns we've discussed to achieve a scalable and resilient storage layer.

Conclusion

In this lesson, we explored consistent hashing as a fundamental pattern for distributing data and load in a dynamic cluster. By moving beyond simple modulo hashing, we gain a system that can gracefully handle nodes joining and leaving without massive data reshuffling.

Key Takeaways:

Traditional Hashing (% N) is brittle: It works for static clusters but causes massive data migration when the number of nodes changes.
Consistent Hashing uses a ring: By mapping both keys and servers to a common hash ring, it localizes the impact of node changes, affecting only a small fraction of keys.
Virtual Nodes are essential for uniform load: They solve the problems of non-uniform key distribution and hotspotting by creating many smaller partitions per physical server.
Weighting is achieved via virtual nodes: Servers with higher capacity can be assigned more virtual nodes to handle a proportionally larger share of the load.
It's a foundational pattern: Consistent hashing is the underlying mechanism for partitioning in many distributed databases, caches, and load balancers.

In our next lesson, we will begin our deep dive into caching. We've just learned a critical technique for distributing data across a cluster of cache servers. Now, we will explore the caching patterns themselves, such as cache-aside, read-through, and write-through, to understand how applications should interact with a cache to maximize performance and maintain data consistency.