Mugdha

Consistent Hashing.

The first step in consistent hashing is selecting an appropriate hash function. This function takes an input, such as a key or an object identifier, and produces a fixed-size output, typically a numerical value.

Properties of a good hash function:

Uniform distribution: The hash function should evenly distribute keys across the hash space to ensure a balanced load distribution among servers.

It should be deterministic: Given the same input, the hash function should always produce the same output. This property ensures that keys consistently map to the same server, maintaining data locality.

Collision Resistance: Collisions occur when different inputs produce the same hash output. While some collisions are inevitable due to the finite size of the hash space, a good hash function minimizes collisions to prevent uneven load distribution.

The next step involves mapping keys to the hash space.

Once a hash function is selected, keys are hashed to determine their position in the hash space. Typically, the hash function output is mapped to a fixed range, such as integers between 0 and 2^32 or a continuous ring. The hash function output is mapped to a position on a ring. If the hash space ranges from 0 to 99, and the hash output is 126, the hash would be mapped to 126%100 which is 26 on the ring.

The next step involves mapping servers to the hash space.

Similarly, servers are also mapped to positions on the same hash space. Each server is represented by a point or multiple points on the ring. Servers are typically assigned positions on the hash space using the same hash function that maps keys. The output of the hash function determines the position of each server on the ring.

The next step is key server assignment.

Once both keys and servers are mapped onto the hash space, each key is assigned to the nearest server in a clockwise direction on the ring. This assignment is determined by comparing the positions of keys and servers on the hash space. The key-server assignment remains consistent even if servers are added or removed, as long as the majority of the hash space remains unchanged. This property minimizes the redistribution of keys when the server pool changes, thereby reducing disruption.

The next step involves handling skewed distribution:

In real-world scenarios, the distribution of keys may not be uniform, leading to hotspots where a few servers receive a disproportionate number of requests. Techniques like virtual nodes and weighted servers are used to mitigate these issues by distributing the load more evenly.

Advantages of consistent hashing:

Load Distribution: Consistent hashing ensures that the load is evenly distributed across the servers, reducing hotspots and overloading of individual servers.

Scaling: Adding or removing servers can be done without significant reshuffling of data, minimizing the impact on the system and reducing the need for data migration.

Fault Tolerance: In case of server failures, only the data hosted on the failed server needs to be redistributed, rather than redistributing the entire dataset.

Implementation of Consistent Hashing involves the following steps:

Hash Functions: Choosing a good hash function is crucial. The function should evenly distribute keys across the hash space to avoid skewness in load distribution.

Virtual Nodes: To further improve load balancing, each physical server can be represented by multiple virtual nodes in the hash space. This ensures that the load is distributed more evenly, especially for servers with different capacities.

Consistent Hashing Algorithms: There are variations in consistent hashing algorithms, such as Rendezvous (Highest Random Weight, HRW), Jump Consistent Hashing, and others, each with its advantages and use cases.

Use Cases of Consistent Hashing:

Caching: Content delivery networks (CDNs) and caching systems use consistent hashing to distribute cached content across multiple caching servers.

Load Balancing: Load balancers distribute incoming requests across multiple backend servers using consistent hashing to maintain session affinity while evenly spreading the load.

Distributed Databases: Systems like DynamoDB and Cassandra use consistent hashing to distribute data partitions across multiple nodes in a distributed database cluster.

List of Consistent Hashing Algorithms:

Rendezvous Hashing (Highest Random Weight).

Jump Consistent Hashing.

Ring Hashing.

Ketama Hashing.

Consistent Buckets.

MurmurHash.

Maglev Hashing.

Featured Image Courtesy: Internet.