Let’s dive directly into the topic. To understand WHAT consistent hashing is, let’s first explore the purpose of WHY behind it and to understand why consistent hashing is necessary, let’s begin by understanding the concept of hashing.
HASHING
At its core, hashing is a process of transforming data of any size into a fixed-length value, known as a hash code or hash value. This transformation is achieved using a function called a hash function.
Hashing can be used in multiple domains including Data integrity and security, data compression for faster network transfers, data partitioning function and obviously load balancing(which is why you are here :P)
Example of a hash func can be as simple as key%n to a complex md5 sum or a Cryptographic algorithm like SHA, DSA, AES etc
The choice of a hash function depends on the specific use-case requirements and considerations. It is important to select a hash function that aligns with the desired outcomes and properties for the given application.
CONSISTENT HASHING
Now since we understood what hashing is now lets dive into our use case of load balancer.
So, the typical functionality of a load balancer is to balance the load among a set of nodes. For example, if you have 5 servers, you would place a load balancer between your Route53 and these five server nodes. The load balancer determines which requests should be directed to which server, maintaining an even distribution of the load across all five servers.
Now the typical algorithm of evenly distribution of load would be Round robin technique where incoming requests are evenly distributed in a cyclic manner across a group of servers. This is easy to implement but has it own drawbacks like it does not consider the server’s current load capacity. You may also have a use-case where you want to route particular requests to a specific set of servers. This is where hashing based approach comes in.
Hash-based load balancing uses a hash function to map incoming requests to specific servers. The hash function generates a hash value based on a chosen attribute like let’s say User id, region or IP.
Lets assume you have 10 servers(0–9) for simplicity and you can use a simple hash func user_id%size to determine the server to which the request should be routed.
Lets look at some small code to do the same.
server_pool = ['Server0', 'Server1', 'Server2', 'Server3', 'Server4', 'Server5', 'Server6', 'Server7', 'Server8', 'Server9']
def hash_based_load_balancing(user_id):
hash_value = user_id % len(server_pool)
selected_server = server_pool[hash_value]
return selected_server
# Example usage
user_id = 12345
selected_server = hash_based_load_balancing(user_id)
print(f"User {user_id} is directed to {selected_server}")So this looks straightforward so what is the issue ? The issue is that this works fine only when we have a fixed number of servers and the number never changes.
Lets assume one of the servers gets removed/corrupted. Now the server pool becomes 9 and user hash func becomes user_id%9 which completely changes the hash locations of all requests. One of the major advantages of hash based load balancing is sticky sessions which is not possible now. Because of the change in the hash func, the hash locations have changed
The simple hash based load balancing works when we have fixed no of servers or hash locations but that wouldn’t be the case in the real world especially in a world where distributed systems are taking over. The size of hash locations or the no of servers keeps changing(Auto-Scaling) based on the load.
This is where consistent hashing comes in. So first lets define what consistent hashing means according to wikipedia
Consistent hashing is a distributed hashing technique that allows for the even distribution of data across multiple nodes or servers in a scalable and efficient manner. It solves the challenge of maintaining balanced load distribution and minimizing data redistribution when nodes are added or removed from the system.
So minimizing data redistribution is the key advantage of consistent hashing.
Hash space and Hash ring
Now we understand the definition of consistent hashing, let us find out how it works. Assume we use a simple hash func(SHA1) and the output range is x0 to xn.
By collecting both ends, we get a hash ring
Using the same hash function we map servers on the hash ring. For simplicity lets assume 4 servers so that it can be easily portrayed.
Now lets place the hash keys on which when the hash func is applied it will determine on which server they will be stored on.
To determine which server a key is stored on, we go clockwise from the key position on the ring until a server is found.
Now according to the defination of consistent hashing when a server is added or removed only a small portion of keys should be redistributed.
When a server is Added
After a new server 4 is added, only key0 needs to be redistributed. k1, k2, and k3 remain on the same servers. Let us take a close look at the logic. Before server 4 is added, key0 is stored on server 0. Now, key0 will be stored on server 4 because server 4 is the first server it encounters by going clockwise from key0’s position on the ring. The other keys are not redistributed based on consistent hashing algorithm.
When a server is removed
When server 1 is removed, only key1 must be remapped to server 2. The rest of the keys are unaffected.
If you observe carefully you can clearly state out that there is a non uniform key distribution post adding/removing of a server. When you add/remove a server a small portion of keys are redistributed which is an advantage but the redistribution happens to the next adjacent server in the ring cycle which cause the issue of uniform distribution of keys which may cause issue in performance degradation and uneven resource utilization. These servers which handles significantly larger portion of the load compared to others are called Hot Spots.
So how to avoid this ?
Virtual Nodes
As the name suggest a virtual node just represents a real/physical node. It’s just a phantom node used to solve the issue of uneven distribution. Virtual nodes improve load balancing and distribution of keys among physical/actual servers. Instead of mapping each physical server to a single point in the hash ring, virtual nodes allow multiple virtual points to be assigned to each server.
The use of virtual nodes increases the number of positions in the hash ring, making it easier to distribute keys evenly. It helps ensure that the load is spread more uniformly among the servers,
As the number of virtual nodes increases, the distribution of keys becomes more balanced. This is because the standard deviation gets smaller with more virtual nodes, leading to balanced data distribution. Standard deviation measures how data are spread out.
Lets close this with a code for consistent hashing.
import hashlib
class ConsistentHashing:
def __init__(self, replicas=3):
self.replicas = replicas # Number of replicas per server
self.server_ring = {}
self.sorted_keys = []
def _get_hashed_key(self, key):
hash_object = hashlib.sha1(key.encode())
hash_key = int(hash_object.hexdigest(), 16)
return hash_key
def add_server(self, server):
for i in range(self.replicas):
replica_key = self._get_hashed_key(f"{server}-{i}")
self.server_ring[replica_key] = server
self.sorted_keys.append(replica_key)
self.sorted_keys.sort()
def remove_server(self, server):
keys_to_remove = []
for key, value in self.server_ring.items():
if value == server:
keys_to_remove.append(key)
for key in keys_to_remove:
self.sorted_keys.remove(key)
del self.server_ring[key]
def get_server(self, key):
if not self.server_ring:
return None
hashed_key = self._get_hashed_key(key)
for server_key in self.sorted_keys:
if hashed_key <= server_key:
return self.server_ring[server_key]
return self.server_ring[self.sorted_keys[0]]
# Example usage
ch = ConsistentHashing(replicas=3)
servers = ['Server1', 'Server2', 'Server3']
for server in servers:
ch.add_server(server)
keys = ['Key1', 'Key2', 'Key3', 'Key4', 'Key5']
for key in keys:
server = ch.get_server(key)
print(f"Key {key} is directed to {server}")
ch.add_server('Server4')
added_server = 'Server4'
print(f"Server {added_server} has been added.")
key = 'Key6'
server = ch.get_server(key)
print(f"Key {key} is directed to {server} after server addition.")
ch.remove_server('Server2')
removed_server = 'Server2'
print(f"Server {removed_server} has been removed.")
key = 'Key7'
server = ch.get_server(key)
print(f"Key {key} is directed to {server} after server removal.")Hope this article was helpful. Thanks for reading
My Linkedin ☺️.
