# Consistent Hashing Explained: Add Servers Without Reshuffling Everything (with Python) Imagine you run a distributed cache with four servers. Whenever a request arrives, you need to decide which server should store the corresponding key. A simple solution is to use modulo hashing: ```python server = hash(key) % 4 ``` This works until your application grows and you add a fifth server. Now your formula becomes: ```python server = hash(key) % 5 ``` The problem? Most keys may now map to different servers. Your cache loses much of its usefulness, requests fall through to the database, and database traffic can spike unexpectedly. This is where **consistent hashing** comes in. Consistent hashing is a technique used in distributed systems to minimize how many keys need to move when servers are added or removed. In this guide, we'll explore why modulo hashing breaks during scaling, how a hash ring works, why virtual nodes improve load distribution, and how to implement consistent hashing in Python. ## 1\. Why Does Hash Modulo N Break? The modulo approach assigns a key to a server using the remainder of its hash divided by the number of servers. ```python server_index = hash(key) % number_of_servers ``` For example: - Four servers produce indices from `0` to `3`. - Five servers produce indices from `0` to `4`. When the number of servers changes, the remainder changes for many keys. Let's demonstrate the problem using a simplified example: ```python keys = range(100_000) moved = sum( 1 for key in keys if key % 4 != key % 5 ) print(f"Keys moved: {moved / len(keys):.1%}") ``` Output: ```text Keys moved: 80.0% ``` This example uses the keys themselves as hash values to make the calculation easy to understand. With well-distributed hash values, adding one server to a modulo-based arrangement of N servers typically remaps approximately N/(N+1) of the keys. That means adding a fifth server to four existing servers can remap around 80% of the keys. For a distributed cache, this can cause a large increase in cache misses. For a sharded database, it can mean substantial data redistribution. **The goal:** Add or remove servers while moving as few keys as possible. ## 2\. What Is Consistent Hashing? Consistent hashing places both servers and keys on the same logical hash ring. Imagine a circle representing the hash space. Every server and every key is assigned a position on that circle using a hash function. To determine which server owns a key: 1. Hash the server identifiers and place them on the ring. 2. Hash the key to find its position. 3. Move clockwise from the key's position. 4. Assign the key to the first server encountered. 5. If the search passes the end of the ring, wrap around to the beginning. This creates a stable mapping between keys and servers. ### What happens when a server is added? Suppose a new server is inserted into the ring. It takes responsibility for keys in the portion of the ring between its position and the preceding server's position. Most other keys remain assigned to their existing servers. When a server is removed, its keys move to the next server clockwise. This is the main advantage of consistent hashing: **membership changes generally affect only a portion of the key space instead of remapping almost everything.** For a ring with N evenly distributed servers, adding one server is expected to move approximately 1/(N+1) of the keys under the usual uniform-distribution assumptions. ## 3\. Why Do We Need Virtual Nodes? A basic hash ring places each physical server at a single position. This can create uneven partitions. For example, one server might own a large section of the ring, while another owns a much smaller section. Even if both servers have identical capacity, their key distributions could differ significantly. Virtual nodes help reduce this imbalance. Instead of assigning one position to each physical server, assign multiple positions to every server. For example: ```text cache-1#0 cache-1#1 cache-1#2 ... cache-1#99 ``` Each identifier represents a virtual node belonging to the same physical server. With 100 virtual nodes per server, the ring has 100 positions per physical server. These additional positions tend to produce a more balanced distribution of keys. Virtual nodes also provide flexibility: - More virtual nodes generally improve distribution. - Servers with higher capacity can receive more virtual nodes. - Removing a physical server removes all of its virtual nodes. - The ring becomes larger, increasing memory use and membership-update work. Virtual nodes improve balance statistically; they do not guarantee equal traffic or eliminate hot keys. ## 4\. Implement Consistent Hashing in Python Let's build a simple consistent hash ring using Python's `hashlib` and `bisect` modules. We'll use MD5 to generate stable hash positions. MD5 is used here for distribution, not security. import bisect import hashlib class ConsistentHashRing: def **init**(self, nodes=None, vnodes=100): if vnodes < 1: raise ValueError("vnodes must be at least 1") ```plaintext self.vnodes = vnodes self.ring = [] self.owner = {} for node in nodes or []: self.add_node(node) def _hash(self, value: str) -> int: digest = hashlib.md5(value.encode()).digest() return int.from_bytes(digest, "big") def add_node(self, node: str): for i in range(self.vnodes): pos = self._hash(f"{node}#{i}") if pos in self.owner: raise ValueError( "Hash collision detected; use a collision-handling strategy" ) bisect.insort(self.ring, pos) self.owner[pos] = node def remove_node(self, node: str): for i in range(self.vnodes): pos = self._hash(f"{node}#{i}") if self.owner.get(pos) != node: raise ValueError(f"Node not found on ring: {node}") self.ring.remove(pos) del self.owner[pos] def get_node(self, key: str) -> str: if not self.ring: raise ValueError("No nodes in the ring") pos = self._hash(key) # Find the first ring position at or after the key. # Wrap around to the first position if necessary. idx = bisect.bisect_left(self.ring, pos) % len(self.ring) return self.owner[self.ring[idx]] ``` Understanding the implementation \_hash() Converts an identifier into a stable integer position using the full MD5 digest. add_node() Creates virtual nodes, calculates their positions, and inserts those positions into the sorted ring. remove_node() Removes the virtual nodes associated with a physical server. get_node() Finds the first server position at or after the key's hash position. If the key lies beyond the last position, the modulo operation wraps the search to the beginning. ### What is the time complexity? Let V represent the total number of virtual nodes across all physical servers. - Hashing a key: O(1) for a fixed-size digest. - Looking up a key: O(log V) using binary search. - Inserting a virtual node into a Python list: O(V) in the worst case because elements may need to shift. - Removing a virtual node from a Python list: O(V) in the worst case. The lookup is efficient, but Python's list-based implementation is not optimized for frequent server membership changes. ## 5\. Test the Ring: Add a Server Now let's create four cache servers, assign keys to them, and observe what happens when a fifth server joins. ```python ring = ConsistentHashRing( ["cache-1", "cache-2", "cache-3", "cache-4"], vnodes=100 ) keys = [f"user:{i}" for i in range(10_000)] before = { key: ring.get_node(key) for key in keys } ring.add_node("cache-5") after = { key: ring.get_node(key) for key in keys } moved = sum( 1 for key in keys if before[key] != after[key] ) print(f"Keys moved: {moved / len(keys):.1%}") ``` The program calculates the actual movement percentage for this particular implementation and key set. Run it to obtain the result rather than assuming a fixed percentage. With four original servers and a fifth server added, the expected movement is approximately 20% under the usual uniform-distribution assumptions. The exact result varies with virtual-node placement and the tested keys. Unlike modulo hashing, consistent hashing moves keys to the new server without randomly redistributing all the remaining keys among the original servers. You can also test removal: ```python ring.remove_node("cache-5") restored = { key: ring.get_node(key) for key in keys } print("Mapping restored:", before == restored) ``` Expected output: ```text Mapping restored: True ``` This holds for this example because the original servers and their ring positions have not changed. In a real distributed system, moving data between servers is a separate operation from changing the ring's logical mapping. 6. Where Is Consistent Hashing Used? Distributed caches Consistent hashing helps cache clients map keys to cache servers while minimizing remapping when the server pool changes. Distributed databases Distributed databases can use consistent-hashing-style partitioning to distribute keys across nodes. Dynamo is a well-known example of a distributed key-value store that uses consistent hashing concepts. Read the Dynamo paper summary on ScaleDojo to learn more about the design. Content delivery networks A CDN can use hashing-based routing to distribute objects across cache nodes and reduce unnecessary movement when infrastructure changes. Distributed storage systems Consistent hashing can help determine which nodes should be responsible for particular keys or objects. For fault tolerance, systems may replicate data to multiple distinct nodes. Replication is a separate design decision; assigning a key to one node does not automatically make its data resilient to failures. 7. Trade-Offs You Should Know Consistent hashing reduces unnecessary movement, but it does not eliminate every distributed-systems challenge. Data still needs to move. When a new server takes ownership of keys, the corresponding data may need to be copied or reconstructed. Virtual nodes consume resources. More virtual nodes increase ring size and membership-update costs. Hot keys remain a problem. A key receiving disproportionately high traffic can overload its owner even when keys are distributed evenly. Load balancing is not guaranteed. Virtual nodes improve statistical distribution, but actual traffic and key sizes can still vary. Alternatives exist. Rendezvous hashing and jump consistent hashing offer other approaches to distributing keys, each with different properties and trade-offs. ## 8\. Consistent Hashing Interview Tips If an interviewer asks you to design a distributed cache or sharded storage system, explain the concept in this order: 1. Explain why `hash(key) % N` causes extensive remapping when N changes. 2. Draw a hash ring and explain clockwise ownership. 3. Demonstrate how adding or removing a server affects only part of the ring. 4. Introduce virtual nodes to improve distribution. 5. Discuss replication, hot keys, data migration, and operational trade-offs. A strong system design answer explains not just how consistent hashing works, but also why it is useful and where it falls short. ## 9\. Learn More About Consistent Hashing Want to explore the algorithm beyond the theory? - [Consistent Hashing Wiki on ScaleDojo](https://scaledojo.dev/wiki/consistent-hashing) — review the core concept. - [Consistent Hashing in the HLD Course](https://scaledojo.dev/hld/learn/unique-ids-distributing-data/consistent-hashing-revisited) — explore its role in high-level system design. - [Scale a Cache with Consistent Hashing](https://scaledojo.dev/forge/learn/algorithms-behind-caching/consistent-hashing-scaling-a-cache) — practise implementing the algorithm. ## Conclusion Consistent hashing is a practical technique for distributing keys across changing server pools without remapping most of the key space every time infrastructure changes. By combining a hash ring with virtual nodes, you can improve key distribution and make scaling more manageable. The important takeaway is simple: **consistent hashing minimizes unnecessary key movement, while virtual nodes help improve balance.** Together, they provide a useful foundation for designing scalable distributed caches, storage systems, and other distributed applications.