Consistent Hashing in System Designing

advance · System Designing

The concept you are describing is Consistent Hashing , which is the foundational algorithm used to scale distributed systems dynamically without crippling performance. When building large-scale distributed caches (like a multi-node Redis cluster) or distributed databases (like Apache Cassandra or Amazon DynamoDB), you need a way to determine exactly which machine stores a particular piece of data. Standard hashing falls apart when you change the cluster size, but consistent hashing solves this elegantly. 1. The Core Problem with Naive Hashing In a standard distributed database with $N$ servers, you typically map a data key to a server using the modulo operator: $\text{Server ID} = \text{Hash}(\text{key}) \pmod N$ While simple, this approach introduces a catastrophic flaw when scaling. If one server crashes, or if you add a new server to handle a traffic spike, your pool size changes from $N$ to $N \pm 1$ . Because the divisor in your formula has changed, the mathematical result for nearly every single key changes instantly. * In a cache system: This triggers a near-100% cache miss storm, forcing your backend databases to handle all traffic simultaneously, which usually crashes the system. In a database system: This forces you to move up to 90% of your data across the network to re-locate them to their new server IDs. 2. The Consistent Hashing Solution Consistent hashing decouples data routing from the total number of servers by mapping both the servers and the keys to a conceptual geometric circle called a Hash Ring . The Hash Ring: The ring represents a fixed numeric range (e.g., from $0$ to

Careeroza — One-stop Zone for Aspirants

Study material, Careeroza mentorship, tech jobs, and career guidance on careeroza.com.

Public study materials

^{32}-1$ ). Mapping Servers: Each physical server is passed through a hash function based on its IP address or name, mapping it to a specific point along the perimeter of the ring. Mapping Keys: When a data key needs to be written or read, its key string is hashed using the exact same function, placing it at a specific point on the ring. Data Routing (The Clockwise Rule): To find out which server owns a key, the system locates the key on the ring and travels clockwise until it encounters the very first server. That server is the data owner. 3. Adding and Removing Nodes ( $\sim1/N$ Shift) Because data routing is based on walking clockwise to the next server, adding or removing nodes has a highly localized impact: Adding a Server: If you insert a new Server X onto the ring, it will only intercept keys that fall between it and its counter-clockwise neighbor. The rest of the ring remains completely unaffected. Removing a Server: If a server crashes, its keys simply roll over clockwise to the next available server on the ring. On average, when the cluster size changes, only $\frac{1}{N}$ of the total keys need to be remapped or moved (where $N$ is the total number of nodes). This turns a system-wide re-sharding disaster into a minor background task. 4. Virtual Nodes: Optimizing Load Distribution In a pure consistent hashing ring, servers are mapped randomly based on their hashes. This introduces two major real-world scaling problems: Hotspots: Servers might wrap unevenly around the ring, creating massive data gaps where one server is forced to hold 70% of the keys while another holds only 5%. Heterogeneous Hardware: A massive bare-metal server with 128 cores will sit on the ring with the exact same presence as a tiny virtual machine instance with 2 cores. To solve this, systems implement Virtual Nodes (Vnodes) . Instead of mapping a physical machine ( Server A ) to a single point on the ring, the system generates hundreds of virtual tokens for it (e.g., Server A-1 , Server A-2 , Server A-100 ) and scatters them randomly all over the ring. The Benefits of Virtual Nodes: Uniform Distribution: By breaking physical servers into hundreds of virtual points, the data keys get distributed across the physical hardware with near-perfect uniformity, eliminating hotspots. Proportional Scaling: If Server B is twice as powerful as Server A , you can allocate 200 virtual nodes to Server B and only 100 to Server A . The powerful machine will naturally absorb a proportional workload. Blazing Fast Recovery: If a physical server dies, its virtual nodes are scattered everywhere. Instead of a single neighbor server getting slammed with 100% of the dead server's traffic, the load is distributed evenly among all remaining servers on the ring. 5. Industry Footprint Consistent hashing is the hidden engine behind some of the most resilient distributed architectures globally: Amazon DynamoDB & Apache Cassandra: Use it to determine which partition nodes hold specific primary keys in a masterless distributed cluster. Memcached & Redis Clusters: Use it to distribute cached keys evenly across a farm of memory servers to prevent cache stampedes during node recycles. Akamai CDN: Uses it to ensure web requests for specific content always land on the same edge proxy server, maximizing local cache hit ratios.

Back to System Designing

Browse all study material on Careeroza