Exploring Key Distributed System Algorithms and Concepts Series: 2 — Consistent Hashing

Consistent hashing is a technique used in distributed computing and computer networking to efficiently distribute data or workload across multiple nodes in a way that minimizes the disruption caused by adding or removing nodes from the system.

It’s particularly useful in scenarios where the number of nodes in a cluster can change dynamically, such as in content delivery networks, distributed databases, or load balancers.

The primary problem consistent hashing addresses is the issue of distributing data or tasks evenly across a set of nodes while minimizing the need to reshuffle everything when a node is added or removed. Traditional hashing techniques, like modulo hashing, tend to break down when the number of nodes changes because they lead to a complete redistribution of data across the nodes, resulting in a lot of unnecessary data movement.

Consistent hashing achieves its goals through the following principles:

1. Ring Structure: Consistent hashing uses a virtual ring, which is represented mathematically as a circle. Each node in the system is placed at a specific point on this circle using a hash function that maps nodes’ identifiers to points on the circle. This hash function ensures that the entire hash space is covered by the circle.
2. Data/Task Placement: Data or tasks to be distributed are also assigned a hash value using the same hash function. This hash value is then mapped onto the circle, and the nearest node clockwise to the hash value’s location on the circle becomes the owner of that data or task.
3. Node Additions and Removals: When a new node is added to the system, its identifier is hashed, and its position is determined on the circle. Data that was previously assigned to the nodes “clockwise” to the new node now gets assigned to the new node. However, only a fraction of the data needs to be remapped, proportional to the new node’s position on the circle. Similarly, when a node is removed, only the data that was assigned to that node needs to be redistributed, minimizing data migration.
4. Load Balancing: Since each node occupies a certain segment of the circle, the load is balanced among the nodes based on the portion of the circle they cover. Nodes that are closer together on the circle might have a larger portion of data/tasks assigned to them, but the load distribution is still relatively even due to the distribution of data across the entire circle.
5. Replication and Fault Tolerance: To ensure redundancy and fault tolerance, consistent hashing can be extended to replicate data across multiple neighboring nodes on the circle. This way, if a node fails, its adjacent nodes can handle its data.

How does it Work?

1. Hash Function: At the core of consistent hashing is a hash function. This function takes an input (such as a node ID, data ID, or key) and produces a numerical value. This value is used to determine the position of the virtual ring or circle. Importantly, a good hash function should distribute values uniformly across the ring to ensure an even distribution of data.
2. Virtual Ring: Imagine a circle (the hashing ring) with a range of values (usually numerical). Each node in the system is placed on this circle based on the output of the hash function applied to its identifier. The result is that each node is associated with a point on the circle, creating a distributed spectrum of positions.
3. Data Placement: When data needs to be stored or retrieved, it’s also hashed using the same hash function. The resulting hash value is then mapped onto the circle. Starting from this point, you can traverse clockwise to find the first node you encounter. This node becomes the owner of that particular data. The clockwise traversal ensures that each data point belongs to the nearest node following its position on the circle.
4. Node Addition: When a new node is added to the system, it’s also assigned a position on the circle using the hash function. The data that was originally assigned to the node(s) located clockwise from the new node will need to be reassigned to the new node. However, the reassignment is localized and affects only the data that would naturally fall within the segment between the new node and its clockwise neighbor.
5. Node Removal: When a node is removed from the system, the data that was assigned to it must be redistributed. This process involves identifying the neighboring nodes on the circle and transferring ownership of the data they cover to ensure that the data remains available in the system.
6. Load Balancing: The nature of consistent hashing ensures that the data distribution among nodes is relatively balanced. Nodes are distributed across the circle according to their hash values, so the load tends to spread evenly as long as the hash function behaves well and the number of nodes is sufficiently large.
7. Replication and Fault Tolerance: Consistent hashing can be extended to handle replication. Instead of mapping data to a single node, data can be mapped to multiple consecutive nodes on the circle. This provides redundancy and fault tolerance. If a node fails, its adjacent nodes can take over the responsibility of serving its data.

Let’s say we have a circle representing our hashing space, and we’ll place nodes and data on this circle. We’ll use a hash function that produces values between 0 and 99.

Node Placement: We have three nodes in our system with IDs A, B, and C. We’ll hash their IDs and place them on the circle:

• Node A: ID hash = hash(“A”) = 27
• Node B: ID hash = hash(“B”) = 72
• Node C: ID hash = hash(“C”) = 11

Data/Task Placement: Now let’s distribute data onto the circle. We’ll hash the data IDs and place them on the circle as well:

• Data 1: ID hash = hash(“data1”) = 40
• Data 2: ID hash = hash(“data2”) = 88
• Data 3: ID hash = hash(“data3”) = 15

Assigning Data/Task to Nodes: For each data item, we find the nearest node clockwise on the circle. This node becomes the owner of the data.

• Data 1 (hash 40): Node B
• Data 2 (hash 88): Node A
• Data 3 (hash 15): Node C

Node Addition: Now, let’s add a new node D to the system. We hash its ID and place it on the circle:

• Node D: ID hash = hash(“D”) = 60

After adding Node D, the data ownership might change:

• Data 1: Stays with Node B
• Data 2: Moves from Node A to Node D
• Data 3: Stays with Node C

Node Removal: Let’s say we remove Node A from the system. Only the data assigned to Node A needs to be redistributed:

• Data 2: Stays with Node D

Trade-Offs

While consistent hashing offers several benefits for distributed systems, it also comes with certain trade-offs and considerations that need to be taken into account when implementing it:

Benefits:

1. Load Balancing: Consistent hashing provides excellent load balancing, as data is distributed uniformly across nodes on the ring. This helps prevent hotspots (overloaded nodes) and ensures that resources are efficiently utilized.
2. Scalability: Adding or removing nodes has a limited impact on the overall system, as only a fraction of data needs to be reassigned. This makes consistent hashing scalable and suitable for dynamic environments.
3. Data Locality: Data is assigned to the node closest to it on the ring, which can improve data retrieval performance by reducing the distance between data and the node serving it.
4. Fault Tolerance: By replicating data across neighboring nodes on the ring, consistent hashing can provide fault tolerance. If a node fails, its adjacent nodes can take over its responsibilities.

Trade-offs:

1. Uneven Data Distribution: While consistent hashing aims for even data distribution, it’s not guaranteed in all scenarios. Variations in hash values or skewed data access patterns can lead to uneven data distribution despite the mechanism’s intentions.
2. Node Addition/Removal Complexity: Although consistent hashing simplifies node addition and removal compared to other methods, it still involves some complexity, especially in handling edge cases and ensuring seamless transitions.
3. Limited Control over Data Placement: Since data placement is determined by the hash values, you might not have direct control over where specific data items are stored. This can be a concern in scenarios where you want to ensure specific data co-location.
4. Changing Hash Function: Changing the hash function used for consistent hashing can be challenging, as it would require remapping all data and nodes. This makes the choice of hash function critical from the start.
5. Complexity of Replication: Implementing replication in consistent hashing requires careful consideration. Too much replication might lead to wasted resources, while too little might compromise fault tolerance.
6. Virtual Nodes: Some implementations introduce the concept of virtual nodes to improve load balancing and address issues related to uneven data distribution. While this can enhance the system, it also increases the complexity of implementation.

Real Life examples

Distributed Databases — Apache Cassandra:

Apache Cassandra is a distributed NoSQL database designed for scalability and high availability. It uses consistent hashing to manage the distribution of data across nodes in its cluster.

• Hashing and Data Distribution: In Cassandra, each node is assigned a token value based on consistent hashing. The range of tokens forms a ring, and the data is distributed among nodes based on the tokens they own. This ensures that data is evenly distributed across the nodes in the cluster.
• Adding and Removing Nodes: When a new node is added, it takes responsibility for a range of tokens from its neighbors. Data in those token ranges is then gradually moved to the new node. Similarly, when a node is removed, its data is transferred to its neighboring nodes. This gradual and localized data movement minimizes disruptions.
• Load Balancing: Since tokens are distributed evenly on the ring, data distribution is balanced. Even when nodes have different capacities or loads, the token-based approach ensures that data is distributed proportionally to their capacity.

Distributed Caching — Memcached and Redis Cluster:

Distributed caching systems like Memcached and Redis Cluster use consistent hashing to optimize data caching across multiple cache nodes.

• Data Distribution: In these systems, data keys are hashed using a consistent hashing algorithm, and the resulting hash values are mapped onto the hash ring. Each cache node is assigned a position on the ring. When a data item needs to be cached or retrieved, its key is hashed, and the nearest cache node on the ring is responsible for storing or serving the data.
• Adding and Removing Nodes: When new cache nodes are added or removed, only a fraction of the data needs to be remapped. This ensures that the impact on the system is minimized, and data movement is efficient.
• Load Balancing: Consistent hashing helps distribute data uniformly across cache nodes, preventing the overloading of certain nodes and optimizing cache utilization.
• Data Eviction and Replication: When the cache reaches its capacity, some data might need to be evicted. In systems that support replication, consistent hashing also aids in determining where replicas of data should be placed to ensure fault tolerance.

Content Delivery Networks (CDNs):

A Content Delivery Network (CDN) is a system of distributed servers that work together to deliver web content, such as images, videos, stylesheets, and scripts, to users. CDNs are used to optimize the delivery of content by serving it from servers that are geographically closer to the user, reducing latency and improving load times.

Consistent hashing is used in CDNs to efficiently distribute and cache content across their network of servers. Here’s how it works:

1. Hashing and Server Placement: Each server in the CDN is assigned a unique identifier or name. This identifier is hashed using a consistent hashing algorithm to determine its position on the virtual ring. This hashing process ensures that the servers are distributed uniformly around the ring.
2. Data (Content) Placement: Content items, such as images or videos, are also assigned a unique identifier. When a user requests a specific content item, its identifier is hashed, and the CDN uses the consistent hashing algorithm to find the nearest server on the virtual ring. This server is responsible for delivering the content to the user.
3. Load Balancing: Since the servers are distributed evenly on the virtual ring, the load is naturally balanced across the servers. This prevents a single server from becoming overwhelmed with requests while others remain underutilized.
4. Node Addition and Removal: When a new server is added to the CDN or an existing server goes offline, only a fraction of the content needs to be remapped. The neighboring servers on the virtual ring take over the responsibility for the affected content, minimizing disruption.
5. Fault Tolerance: Many CDNs implement replication. Content can be stored on multiple servers, typically the ones adjacent to the primary server on the ring. This redundancy ensures that if a server fails, its neighboring servers can still serve the content, maintaining a seamless user experience.

Conclusion

Consistent hashing is a foundational concept for efficient data distribution in distributed systems, facilitating load balancing, scalability, and fault tolerance. However, it’s essential to weigh the benefits against the trade-offs and tailor its implementation to your specific system requirements and constraints. When used thoughtfully, consistent hashing contributes to the construction of robust, responsive, and scalable distributed systems.