Not quite — there are two major drawbacks with this approach, namely, Horizontal Scalability and Non-Uniform data distribution across servers.
Horizontal Scalability:-The above scheme is not horizontally scalable.
If we add or remove servers from the set, all our existing mappings are broken.
This is because the value of “n” in our function that calculates the serverIndex changes.
The result is that all existing data needs to be remapped and migrated to different servers.
This might be a humungous task.
Let us see what happens when we add another server (server4) to the original pool of server.
Notice that we’ll need to update 3 out of the original 4 servers which mean 75% of servers need to be updated.
Effect of adding a new server to the cluster and the redistribution of the keysThe effect is more severe when a server goes down as shown below.
In this case, we’ll need to update ALL servers.
Effect of removing a server from the cluster and the redistribution of the keysData Distribution — Avoiding “Data Hot Spots” in Cluster:-We cannot expect a uniform distribution of data coming in all the time.
There may be many more keys whose hashValue maps to server number 1 than any other servers, in which case server number 1 will become a hotspot for keys.
Consistent hashing allows up to solve both these problems.
What exactly is Consistent Hashing?So, how can this problem be solved? We need a distribution scheme that does not depend directly on the number of servers, so that, when adding or removing servers, the number of keys that need to be relocated is minimized.
Consistent hashing facilitates the distribution of data across a set of nodes in such a way that minimizes the re-mapping/ reorganization of data when nodes are added or removed.
Here’s how it works:Consistent Hashing is a distributed hashing scheme that operates independently of the number of servers or objects in a distributed hash table by assigning them a position on a hash ring.
This allows servers and objects to scale without affecting the overall system.
Here’s how it works:Creating the Hash Key Space: Consider we have a hash function that generates hash values in the range [0,2³²-1).
We can represent this as an array of integers with 2³² -1 slot.
We’ll call the first slot x0 and the last slot x^n — 1.
Linear Hash Key Space2.
Representing the hash space as a Ring: Imagine that these integers generated after hashing are placed on a ring such that the last value wraps around and forms a cycle.
3.
Placing servers on the HashRing: We’re given a list of servers to start with.
Using the hash function, we map each server to a specific place on the ring.
This simulates placing the four servers into a different place on the ring as shown below.
Placing servers on a hash ring4.
Determining Placement of Keys on Servers: To find which server an incoming key resides on, we do the following:Calculate the hash for the key using the hash function.
After hashing the key, we’ll get an integer value which will be contained in the hash space, i.
e.
, it can be mapped to some position in the hash ring.
There can be two cases:The hash value maps to a place on the ring which does not have a server.
In this case, we travel clockwise on the ring from the point where the key is mapped to until we find the first server.
Once we find the first server traveling clockwise on the ring, we insert the key there.
The same logic would apply while trying to find a key in the ring.
The hash value of the key maps directly onto the same hash value of a server — in which case we place it on that server.
Example: Assume we have 4 incoming keys: key0, key1, key2, key3 and none of them directly maps to the hash value of any of the 4 servers on our hash ring.
So we travel clockwise from the point these keys maps to in our ring till we find the first server and insert the key there.
This is shown below diagram.
Key placements on servers in a hash ring5.
Adding a server to the Ring: If we add another server to the hash Ring, server 4, we’ll need to remap the keys.
However, only the keys that reside between server 3 and server 0 needs to be remapped to server 4.
On average, we’ll need to remap only k/n keys, where k is the number of keys and n is the number of servers.
In modulo based approach we needed to remap nearly all the keys.
The figure below shows the effect of inserting a new server4.
As server 4 is between key3 and server4, key3 will be remapped from server0 to server4.
Effect of adding a server to the hash ring6.
Removing a server from the ring: A server might go down and consistent hashing scheme ensures that it has minimal effect on the number of keys and servers affected.
As we can see in the figure below, if server0 goes down, only the keys in between server3 and server 0 will need to be remapped to server 1.
The rest of the keys are unaffected.
Effect of removing a server from the hash ringHence we can say that consistent hashing successfully solves the horizontal scalability problem by ensuring that every time we scale up or down, we do not have to redistribute all the keys.
Now let us talk about the second problem of non-uniform distribution of data across servers.
To ensure object keys are evenly distributed among servers, we need to apply a simple trick: To assign not one, but many labels to each server on the hash ring.
So instead of having labels server0, server1, server2, server3 we could have, say server00…server03, server10…server13, server20…server23, and server30…server33 all interspersed along the circle.
As the number of replicas or virtual nodes in the hash ring increase, the key distribution becomes more and more uniform.
The factor by which to increase the number of labels (server keys), known as weight, depends on the situation (and may even be different for each server) to adjust the probability of keys ending up on each.
For example, if server0 were twice as powerful as the rest, it could be assigned twice as many labels, and as a result, it would end up holding twice as many objects (on average).
Using virtual nodes/ replication to create a better key distribution in a hash ringNow imagine server0 is removed.
To account for this, we must remove labels server00…server03 from the circle.
This results in the object keys formerly adjacent to the deleted labels now being randomly labeled server 3x and sever1x, reassigning them to server3 and server1.
But what happens with the other object keys, the ones that originally belonged in server3 and server1?.Nothing!.That’s the beauty of it: The absence of server0 labels does not affect those keys in any way.
So, removing a server results in its object keys being randomly reassigned to the rest of the servers, leaving all other keys untouched.
And this is how consistent hashing solves the non-uniform distribution problem.
Thank you for reading.
You can find me on Twitter @Rohitpatil5, or connect with me on LinkedIn.
.. More details