How to implement Consistent Hashing

This article deep dives into how to implement consistent hashing

Quick Recap

In today’s world, everyone knows that data cannot be stored in a single datastore node beyond a certain threshold. That’s because there is a physical limit to how much you can expand your machine's memory. That’s why horizontal scaling exists, which means storing data on multiple datastore nodes instead of a single datastore node.

Problem statement: Assuming we want to store multiple <key, value> pairs, which key should reside on which machine?

Brute force solution: Use the following formula to compute which key should reside on which datastore node.

Location of Key K = Hash(key) % (Number of Datastore Nodes)

This solution is not a good solution because the number of nodes can vary during scaling up and scaling down, which means the location of the key would also change. Thus, the Get(Key) function wouldn’t be able to retrieve the key correctly from the right datastore node. As a result, we would need to rehash and store all the keys again when a datastore node is added or removed.

Consistent Hashing: This algorithm removes the dependency on the number of datastore nodes and uses a very big integer to do the modulo operation. Thus, upon removal or addition of datastore nodes, we wouldn’t need to reshuffle all the keys but just have to account for a subset of keys. Hence, the cost of adding or removing a node is less.

Location of Key K = Hash(key) % (A very big integer)

If you want to read Consistent Hashing further, I recommend reading the previous article in depth:

What is Consistent Hashing?

I hope you read the topic in-depth and are well-equipped with the following terminologies: nodes, hash function, and hash ring. With that, let’s take a dig at the implementation.

Implementation

I am taking a stab using the Golang language but you can re-write the same code using similar libraries.

The HashRing structure

A few points around this structure:

1. The HashRing represents the consistent hash ring on which the datastore nodes are placed. This HashRing can be best visualized using this image considering only datastore nodes and not keys.

2. The nodes represent the sorted list of hash values i.e. from 0 to a very big integer(10^9 in our example) in a clockwise direction. For example: if 3 nodes are placed on the hash ring, then the nodes array would be of size 3 consisting of hash values: [2323, 4878, 1672536]

3. The nodeMap is a map from the hashed value to a unique node identifier. This mapping is required to refer to the original node string that was added. For example: the node string could be “172.32.1.2:8080“ and the node hash value could be 645829.

4. The hashFunction is a custom hash function for mapping node string to a hash value. As discussed in the previous article, the load will be uniformly distributed if the hashing function is producing uniformly random values.

5. The NewHashRing is the constructor which returns an instance of the HashRing struct.

AddNode function

The steps to place a datastore node on the hash ring are:

1. Compute the node hash value using the custom hash function.

2. Find the first index in the nodes array where nodes[index] >= node hash value. This index denotes where the new node should be placed.

3. Check if the index is out of bounds. Then, check if the node is already inserted in the nodes array. Panic in Golang is a way of representing Runtime Exception.

4. Append the node hash value in the nodes array and add the mapping of nodeHashValue to a node string in the nodeMap.

RemoveNode function

Similarly, the steps to remove a datastore node from the hash ring are:

1. Compute the node hash value using the custom hash function.

2. Find the first index in the nodes array where nodes[index] >= node hash value. This index denotes where the node should be present already and needs to be removed.

3. If the nodes[index] contains the same node hash value, then remove the node from the nodes array and delete the mapping of nodeHashValue to node from nodeMap map.

GetNode function

Now comes the interesting part. Until now, we discussed AddNode() and RemoveNode() methods to add and remove the datastore node on the hash ring. Now, we will see how an incoming key is decided on which node it should reside.

1. Firstly, check if the length of the nodes array = 0, then return an empty string since there is no datastore node to store the data.

2. Then, compute the key hash value using the same custom hash function.

3. Find the first index in the nodes array where nodes[index] >= key hash value.

4. If the index = length of nodes array, it means the key hash value is greater than all of the node hash values present in the nodes array, then reset the index = 0 which represents the incoming key should be stored on the first datastore node on the ring.

5. Lastly, use the index to get the node hash value from the nodes array and then fetch the unique node identifier from the nodeMap using the node hash value. This unique node identifier can be a combination of IP Address & Port (“172.23.21.3:8080“)

The main() function

1. Firstly, I am adding four nodes to the hash ring.

2. Then, for the 5 keys, I am computing which key should reside on which datastore node using the GetNode() function.

3. Then, I am removing a node to simulate scaling down.

4. Then, I call GetNode() again to recheck the mapping of each key.

The Output

As you can see in the above output, initially all the keys were distributed uniformly. Then, after we removed a node, only the keys “KeyA“ and “KeyD“ got assigned to Node B (which happens to be the next node on the ring in the circular fashion).

Summary

Well, that’s pretty much for this article. Here are a few takeaways:

1. In the above example, we used “Node A“, “Node B“ etc, hardcoded names for representing datastore nodes. But, we can use IP Address + Port as a string combination, and the rest of the algorithm remains the same.

2. We used nodeMap for mapping node hash value to a unique node identifier. We could have used an array as well. It would not have made much difference.

3. The time complexity for AddNode() and RemoveNode() = O(logN) + O(N) which translates to O(N). This complexity can be further reduced to only O(logN) by using a map data structure. It really depends on how many nodes you anticipate in your architecture that would be placed on the hash ring.

4. Remember, the consistent hashing algorithm helps you figure out which key should reside on which datastore node. It means that the algorithm would only give the IP address and port for a given key. You still need to write the logic to make a connection to your datastore node and insert the <key, value> pair in the datastore node.

5. At any moment, if a datastore node goes down, the keys present on that node would not be available. Thus, there needs to be a replication strategy that keeps replicating data from the primary datastore node to replicas. These replicas can also be placed on the hash ring itself to get a more uniform load distribution.

Do It Yourself

I am putting you up for a challenge to implement this in your language of choice and paste the GitHub or online IDE link in the comments. Let’s discuss more in the comments.

Here’s the Go PlayGround link which has the executable code: Consistent Hashing Implementation. Copy this to your IDE and try changing the hash function, and number of datastore nodes or number of keys. See, what happens next.

Hard Version: In the previous article, we talked about Virtual Copies which means that a single datastore node should be present as multiple nodes (1 original node + other replicas) on the hash ring. So, for each datastore node, use K different hash functions to generate K values and then plot them on the hash ring. This way, you would get a more uniform load distribution. Try to implement this and let me know how it pans out in the comments.

---

Hope you liked this edition. In the next article, I will talk about some cons of consistent hashing. Stay tuned for that.

Please consider liking 👍 and sharing with your friends as it motivates me to bring you good content. If you think I am doing a decent job, share this article in a nice summary with your network. Connect with me on Linkedin or Twitter for more technical posts in the future!