Consistent Hashing for Scalable Load Distribution

The Rehashing Problem: A Brittle Foundation

Imagine you have a cluster of cache servers. A common and simple way to distribute data keys (or user requests) across them is to use a hash function combined with the modulo operator: server_index = hash(key) % N, where N is the number of servers. This works perfectly fine as long as N never changes.

But in any real-world, scalable system, servers are added to handle more load or removed due to failures or scale-down events. What happens to our simple formula when N changes?

The video below from ByteByteGo clearly illustrates the catastrophic consequence.

As you saw, changing N from 4 to 3 caused a massive reshuffling of keys. Almost every key now maps to a different server. In a caching scenario, this is disastrous. Suddenly, almost all requests will miss the cache, as the data they are looking for is now on a different server (or gone entirely, if the data wasn't replicated). This flood of cache misses will overwhelm your backend databases or origin servers, potentially causing a system-wide outage. This is often called the re-hashing problem.

We need a distribution scheme that is more stable and minimizes data movement when the set of servers changes.

Consistent Hashing: The Ring of Stability

Consistent hashing is a technique designed specifically to solve the re-hashing problem. The core idea is to map both the servers and the data keys onto the same abstract coordinate space, which is visualized as a ring—the hash ring.

Let's break down how this works.

1. The Hash Ring: A hash function (like SHA-1) produces a large range of output values (e.g., 0 to $2^{160}-1$). We can imagine this range as a circle, where the maximum value wraps around to the minimum.
2. Mapping Servers: We take the ID of each server (e.g., its IP address or name) and use the same hash function to get a numerical value. This value determines the server's position on the hash ring.
3. Mapping Keys: We take the key of a data object (or any request identifier) and hash it using the same function to find its position on the ring.
4. Assigning Keys to Servers: To determine which server is responsible for a given key, we start at the key's position on the ring and move clockwise until we encounter a server. That server is the owner of the key.

This video from ByteByteGo continues from where the last one left off and provides a clear visual explanation of this process.

The key insight is that when a server is added or removed, it only affects the keys in its immediate vicinity on the ring.

• When a new server is added: It takes ownership of the keys that lie between its position and the position of the next server in the anti-clockwise direction. Only the keys from that one specific predecessor server need to be moved.
• When a server is removed: All the keys it owned are re-assigned to its immediate successor in the clockwise direction.

The following image provides a static view of this process, showing exactly what happens when a new node, "Node D," is added to a 3-node ring.

Correction on the diagram's logic: The standard rule is to walk clockwise from the key to find the first server.

• Before: Key K1 (1000) -> clockwise -> Node B (2500). Key K2 (2800) -> clockwise -> Node C (4000). Key K3 (3800) -> clockwise -> Node C (4000). This differs from the diagram's color-coding, which is a common point of confusion in visualizations. Let's focus on the principle: each server owns the arc of the ring preceding it.
• After adding Node D (3000): Key K1 (1000) still maps to Node B (2500). Key K3 (3800) still maps to Node C (4000). However, Key K2 (2800) now maps to the new Node D (3000), as it's the first server encountered clockwise. Only the keys between Node B and the new Node D are affected. The key takeaway is the minimal data movement.

For a more detailed written explanation of this mechanism, you can review the following resource.

Addressing Hotspots and Imbalance: Virtual Nodes

The basic algorithm is a huge improvement, but it has two potential weaknesses:

1. Non-uniform node distribution: Randomly placing a small number of servers on the ring can lead to some servers being responsible for a much larger portion of the ring (and thus more keys) than others.
2. Non-uniform key distribution: Even if servers are perfectly spaced, a few very popular keys ("hotspots") can still overload the servers they are assigned to.

The solution to these problems is a technique called virtual nodes (or replicas). Instead of mapping each physical server to a single point on the ring, we map it to multiple points. For example, server-A might be mapped to server-A-1, server-A-2, ..., server-A-100 by hashing its name with different suffixes.

This has the effect of chopping the ring into much smaller, more numerous segments, leading to a significantly more uniform distribution of keys across the physical servers. If a node is removed, its load is now distributed across many other physical servers, not just dumped onto a single neighbor.

The number of virtual nodes is a tunable parameter. More virtual nodes lead to better load balance but increase the memory required to store the ring's metadata.

Consistent Hashing in the Wild: A Practical Case Study

Consistent hashing isn't just a theoretical concept; it's used everywhere in large-scale infrastructure.

• NoSQL Databases: Amazon DynamoDB and Apache Cassandra use it to partition data across the cluster. This is highly relevant to Vector Databases, many of which use Cassandra or similar systems for scalable metadata and vector storage.
• Content Delivery Networks (CDNs): Systems like Akamai use it to distribute content to edge servers.
• Load Balancers: As we've been discussing, it's used to distribute traffic.

However, as your experience as a tech lead suggests, simple solutions often meet complex realities. What happens when consistent hashing's statistical load distribution isn't enough? A classic problem is a power-law distribution of traffic—a few items get astronomically more traffic than others. This can still overload a server, even with virtual nodes.

The following talk from a Vimeo engineer at Google is a fantastic real-world case study. It describes their journey from using basic consistent hashing, hitting its limits due to "hot" videos, and ultimately implementing a more advanced algorithm called consistent hashing with bounded loads.

This case study is a perfect example of engineering at scale: starting with a solid algorithm, identifying its practical limitations under real-world load, and evolving the solution to be more robust. The "bounded loads" concept—using consistent hashing as the primary choice but having a fallback to the next available server if the primary is overloaded—is a powerful pattern.

Conclusion

This lesson completes our journey through the foundations of distributed systems. We've tackled the core challenges of building systems that are reliable, scalable, and performant in the face of partial failures and dynamic load.

Here are the key takeaways on consistent hashing:

• It solves the re-hashing problem by mapping servers and keys to a circular hash space, ensuring that adding or removing nodes causes minimal data redistribution.
• The use of virtual nodes is a critical refinement that ensures a more uniform distribution of load and prevents hotspots.
• It is a foundational algorithm used in countless real-world distributed systems, from NoSQL databases that might power a vector index to sophisticated load balancers.
• Advanced implementations, like consistent hashing with bounded loads, combine its benefits with additional safeguards to handle real-world challenges like power-law traffic distributions.

We have now covered the essential software principles for building scalable systems: the CAP theorem, consistency models, consensus, data partitioning and replication, communication patterns, and load distribution. With this foundation, you are well-equipped to reason about the architecture of any large-scale AI service.

In our next module, we will shift our focus from the distributed software layer to the specialized hardware that makes large-scale AI possible. We'll begin with GPU and AI Hardware Fundamentals, starting with an exploration of the GPU architecture itself to understand how its design is uniquely suited for the massive parallelism required by AI workloads.