Consistent Hashing and the Hash Ring

Consistent hashing is an algorithm for building a load-balanced hash table by defining how keys will be mapped to nodes. It works really well as a distributed system, particularly in cases where there is a need to add or remove nodes. One can think of the good example of distributed caching, whereby one might want data to go to different nodes which will hold that data, then rebuild it on addition or removal of these nodes.

Hashing Algorithm with Consistency

The basic idea of consistent hashing essentially involves mapping nodes and keys to a circular space—a hash ring—and, subsequently, using the hash values for determining key placement.

Steps in Consistent Hashing:

1. Creating a Hash Ring:
– Map the whole space, like from `0` to `2^32-1` for a 32-bit hash, into a circular hash ring.
– Hash each node to a position on this ring.

2. Key Placement:
– Hash every key to a position on the ring.
– Assign the key to the first node whose position is equal or succeeds the position of the key on the ring.

3. Adding/Removing Nodes:
– When a node is added, it will handle some of the keys that other nodes used to handle.
– If a node is removed, its keys will be transferred to the next node in the ring.

Rebalancing:

The rebalancing under consistent hashing technique is reduced since most of the keys will remain at their earlier nodes. Only a fraction of keys get reassigned whenever nodes join or leave. This can be achieved as follows:

– Adding Nodes: Any new nodes will be assigned only those keys that lie between their position and the position of the next node on the ring.
– Removing Nodes: Keys for the removed node will be passed on to the next node on the ring.

Code Implementation (Pseudocode)

Below is a simple pseudo-code implementation of consistent hashing using a hash ring:

class ConsistentHashRing:
def __init__(self, nodes):
self.ring = {}
self.sorted_nodes = []
self.add_nodes(nodes)

def _hash(self, key):

#Use a hash function to map key to a position on the ring
return hash(key) % 2**32
def add_nodes(self, nodes):
for node in nodes:
pos = self._hash(node)
self.ring[pos] = node
self.sorted_nodes.append(pos)
self.sorted_nodes.sort()

def remove_node(self, node):
pos = self._hash(node)
if pos in self.ring:
del self.ring[pos]
self.sorted_nodes.remove(pos)

def get_node(self, key):
key_pos = self._hash(key)
# Find the smallest position greater than or equal to key_pos
for node_pos in self.sorted_nodes:
if key_pos <= node_pos:
return self.ring[node_pos]
# If none found, wrap around to the smallest position
return self.ring[self.sorted_nodes[0]]

# Example usage
nodes = [‘node1’, ‘node2’, ‘node3’]
hash_ring = ConsistentHashRing(nodes)

# Add a new node
hash_ring.add_nodes([‘node4’])

# Get the node responsible for a given key
key = ‘some_key’
responsible_node = hash_ring.get_node(key)

# Remove a node
hash_ring.remove_node(‘node2’)

Explanation:

1. Initialization:
– `__init__`: Initialize the ring with the given nodes.
– `_hash`: A hash function maps keys and nodes to positions on the ring.

2. Adding Nodes:
– `add_nodes`: Hashes nodes and puts them in the ring. The nodes are sorted to make it easier to find which node is responsible for a given key.

3. Removing Nodes:
– `remove_node`: Remove the node from the ring, updating the sorted list.

4. Getting Nodes:
– `get_node`: Given a key, find the responsible node by finding the closest node position on the ring that is >= to the position of the key.

Why Consistent Hashing?

1. Least Movement of Keys: When nodes are added/removed, only a very small subset of keys move.
2. Scalability: Gracefully handle dynamic addition or removal of nodes.
3. Fault Tolerance: It provides for the availability of the system in case any nodes go down by distributing the keys around failures.

Consistent hashing finds a lot of application in distributed systems and caching solutions because it is very efficient and dynamic changes can be handled with little disruption.