What is Consistent Hashing

• Hash both keys and nodes in common space (e.g. SHA-1 → 0..2^160)
• Each key → closest node clockwise on ring
• Adding a node: only keys between previous and new node reshuffle
• Virtual nodes: 1 physical node = 100-200 virtual points on ring → better balance
• Alternative: Rendezvous Hashing (simpler, comparable properties)

// Pseudocode
function nodeForKey(key, ring):
  h = hash(key)
  for node in ring sorted by hash:
    if hash(node) >= h: return node
  return ring[0]  // wrap around

• Bloom Filter
• Load Balancer
• CDN

Consistent hashing is a technique that allows for the efficient distribution of keys across a set of nodes in a distributed system. The primary objective is to minimize the number of keys that need to be relocated when nodes are added or removed. This is achieved through a circular structure known as a hash ring.

In this model, both the keys and the nodes are hashed to produce a numeric value, which is then mapped onto a circular space. Here’s how the process works:

• Hashing Nodes: Each node in the system is assigned a unique identifier through a hashing function, such as SHA-256 or MD5. This identifier determines the position of the node on the hash ring.
• Hashing Keys: Similarly, each key is hashed to determine its position on the same ring.
• Key Assignment: A key is assigned to the nearest node in the clockwise direction on the ring. This ensures that each key is consistently mapped to a specific node.

When a node is added to the system, only the keys that lie between the new node and its predecessor on the ring need to be reassigned. This means that, on average, only ~1/N of the keys are affected, where N is the number of nodes. Conversely, when a node is removed, only the keys that were mapped to that node need to be redistributed.

This method scales well and provides a balanced distribution of data, minimizing the impact of node changes on overall system performance.

Implementing consistent hashing in a distributed application can be accomplished using various programming languages and frameworks. Below are practical examples demonstrating how to configure consistent hashing in a basic setup.

For instance, let’s consider a simple implementation using Python with the hashlib library:

import hashlib

class ConsistentHash:
    def __init__(self, nodes=None, replicas=3):
        self.replicas = replicas
        self.keys = []
        self.ring = {}

        if nodes:
            for node in nodes:
                self.add_node(node)

    def _hash(self, key):
        return int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16)

    def add_node(self, node):
        for i in range(self.replicas):
            key = self._hash(f'{node}:{i}')
            self.keys.append(key)
            self.ring[key] = node
        self.keys.sort()

    def remove_node(self, node):
        for i in range(self.replicas):
            key = self._hash(f'{node}:{i}')
            del self.ring[key]
        self.keys.sort()

    def get_node(self, key):
        if not self.ring:
            return None
        hashed_key = self._hash(key)
        for node_key in self.keys:
            if hashed_key <= node_key:
                return self.ring[node_key]
        return self.ring[self.keys[0]]

In this example, we define a ConsistentHash class that maintains a hash ring and allows adding or removing nodes. The get_node method retrieves the node responsible for a given key.

Another practical example can be seen in Apache Cassandra, which utilizes consistent hashing for data distribution:

CREATE TABLE users (
    user_id UUID PRIMARY KEY,
    name TEXT,
    email TEXT
);

CREATE KEYSPACE my_keyspace WITH REPLICATION = {
    'class': 'SimpleStrategy',
    'replication_factor': 3
};

This configuration ensures that user data is evenly distributed across nodes, leveraging consistent hashing to maintain performance and reliability.

Consistent hashing offers several advantages that make it a preferred choice for distributed systems, particularly in scenarios where scalability and fault tolerance are critical. Here are the key benefits:

• Minimal Key Movement: The most significant advantage of consistent hashing is that when nodes are added or removed, only a small fraction of keys (approximately 1/N) need to be relocated. This minimizes disruption and enhances efficiency during scaling operations.
• Load Balancing: By using virtual nodes (vnodes), consistent hashing can evenly distribute keys across physical nodes. Each physical node can represent multiple virtual nodes, which balances the load more effectively and prevents hotspots.
• Fault Tolerance: In the event of a node failure, consistent hashing allows for a straightforward reassignment of keys to the next available node. This redundancy supports high availability and reliability in distributed applications.
• Scalability: The algorithm scales well with the addition of new nodes, making it suitable for applications that expect to grow over time. The ability to add or remove nodes without significant overhead is crucial for modern cloud-based architectures.
• Decoupled Architecture: Consistent hashing decouples the distribution of data from the underlying nodes, allowing for greater flexibility in managing resources and optimizing performance without affecting the overall system architecture.

In summary, consistent hashing is an essential algorithm for distributed systems, providing efficiency, scalability, and reliability. Its benefits make it a cornerstone for technologies like distributed caching, content delivery networks (CDNs), and database sharding.