Consistent Hashing
What is Hashing?
Hashing is a process of converting a given key or string of characters into another value. The hash function is used to create new values according to a mathematical algorithm. One of the main applications of the Hash function is HashTables. A hash table stores key/value pairs in the form of a list where any element can be accessed using its index.
While designing a large-scale system the important aspect will be how the data is going to be partitioned and replicated across the systems. Data partitioning and replication are at the core of distributed systems because a good design enhances the availability, performance and reliability of the system.
Problem with Hashing
Assume that we have four cache-servers in our system and the common way to balance the load equally is using the formula
serverIndex = hash(key) % N,
where N is the size of the server pool.
By using the hashing algorithm if we try to distribute it equally, then this is how it looks.
This approach works very well where the server group is fixed, problem arises when there is an addition or removal of a server group. Considering the server group(S1) went down, now we have three servers among which we have to distribute the nodes equally.
Here the keys are not equally redistributed, when a server group goes down most of the cache clients will connect to the wrong servers to fetch the data. Consistent hashing saves the day in this situation.
Consistent Hashing
It is a distributed hashing scheme that operates independently of the number of servers and objects in a distributed hash table by assigning them a position on an abstract circle or a hash ring. It maps to physical nodes to ensure that only a small set of keys move when the servers are added or removed. This allows servers and objects to be scaled without affecting the overall system.
With Consistent hashing, the ring is divided into small, predefined ranges. Each node is assigned to one of these ranges. The server lookup generally happens in a clockwise manner. Also whenever the system wants to read/write the data, it first performs the MD5 hashing algorithm to the key, the output of the algorithm determines where exactly data will be stored.
Issues with Basic Approach
- When the node is added/removed from the ring, the next node becomes responsible for all the keys stored on the outgoing node. This results in uneven distribution of data across the nodes.
- Secondly, a partition is a hash space between adjacent servers. It is possible that the size of the partition on the ring assigned to each server is very small or fairly large which eventually makes some nodes to be Hotspots.
- Since each node’s data needs to be replicated on a fixed number of other nodes, when we need to rebuild a node, only its replica can provide data which results in a lot of load on replica nodes and can also lead to service degradation.
Virtual Nodes
The virtual node refers to a real node, and each server is represented by multiple virtual nodes on the ring. The server S0 is represented by s0_0, s0_1, s0_2 and S1 is represented by s1_0, s1_1, and s1_2. In real-time systems, there will be many more virtual nodes.
To find which server the key is stored on, we go on clockwise from the key’s location and find the first virtual node encountered on the ring. As the number of virtual nodes increases, the distribution of keys gets more balanced. When a new node is added it receives many Virtual nodes from the existing nodes to maintain a balanced cluster. When a node needs to be rebuilt, instead of getting data from a fixed number of replicas, many nodes participate in the rebuild process. Also, Virtual nodes help assign smaller ranges to each physical node, this decreases the probability of hotspots.
Real-world systems of Consistent Hashing
- Partitioning component of Amazon Dynamo database.
- Data partitioning across the cluster of Apache Cassandra.
- Akamai Content Delivery network.
- Maglev network load balancer.
References:
