Consistent Hashing: The key to distributed databases.

Consider a database with billions of rows and huge amounts of data. In order to retrieve values, you would need to query the database and wait for the results. The efficiency and speed of retrieving the results is dependent on 2 major factors:

1. How optimised the query is
2. How powerful the hardware is

We will be focusing on the latter for the scope of this article.

Improving the hardware specifications of a machine is known as vertical scaling. It involves using a more powerful CPU, increasing the RAM, and including a better disk. Let’s say we have reached the peak of vertical scaling on our machine but the database is still too large and our CPU still cannot handle the queries. What next?

That’s where distributed systems come into place.

We create multiple instances of our machine(server) and then we distribute the database by sharding it into smaller sets and giving each set to a different instance of our server. In this way we convert a billion row dataset into smaller datasets of millions of rows, divided between multiple servers which decreases the load on the CPUs of each of these servers respectively.

Yay! problem solved, CPU usage is low and crisis is averted. Right? Nope. In software engineering, every solution to a problem comes with its own new set of intermediary problems. In order to understand the problem with our newly found approach of distributed databases, let us get a brief and crude overview of how databases work.

Retrieving a piece of data boils down to fetching a value given its key.

Many databases implement this by keeping the key of a value as its address in the memory, denoted by an index. In order to fetch the value, we look up the index and find mapped values in constant time (blazingly fast 🔥). This is a considerably simple operation when the database is on a single machine, however when the database is distributed between multiple servers, we face the problem of not knowing which instance of the server has our key. In simpler terms, we do not know which set of millions of rows has the particular row we want to find. The first solution to this problem is as follows:

Consider an array of size 4 (number of server instances).

Servers = S0, S!, S2, S3

When we want to retrieve a value by key, we find the hash value of that key using a HASH( ) function and then mod it with 4 (number of servers) that tells us which server instance has the value we need.

Let’s say our key is “Red Shoes”. After passing through the hash function,

HASH(Red Shoes) = 6.

Server Instance with our value = 6 % 4 = 2 (S2)

Similarly, for “Blue Shoes”, assume HASH(Blue Shoes) = 8.

Server Instance with our value = 8 % 4 = 0 (S0)

Yay! problem solved, looking up values is still done in constant time, and the only overhead is the time needed to perform the hash function (still really fast). Crisis averted, right? Nope.

Let’s say our application became really popular and we face a large influx of data. 4 servers are also unable to handle the load so we decide to add another server, S4.

We can immediately see the problem.

Initially, S2 had the value for key “Red Shoes” and S0 had the value for key “Blue Shoes” but now after adding another server,

Server instance with value for “Red Shoes” = HASH(Red Shoes) % 5 = 6 % 5 = 1 (S1)

Server instance with value for “Blue Shoes” = HASH(Blue Shoes) % 5 = 8 % 5 = 3 (S3)

Uh oh, The consistency is broken and the original key values are shuffled. In order to rectify this, we would need to move all the data around and disturb the entire cluster of servers. This is a very costly operation and definitely not worth it, considering the fact that we might need to increase or decrease server instances multiple times. So what’s next?

Enter, Consistent Hashing.

Instead of using a linear data structure to keep a track of our server instances, let’s imagine a circle (360 degrees). We take each server instance, hash its ID(can be IP address or user defined ID) using a function C_HASH( ) and place it on the circle after modding with 360. Let’s assume:

C_HASH(S0) % 360 = 0

C_HASH(S1) % 360 = 90

C_HASH(S2) % 360 = 180

C_HASH(S3) % 360 = 270

The way consistent hashing works, is that

1. We take a key
2. Compute its C_HASH( )
3. Mod it with 360
4. Put it on the circle and find the immediate next server instance on the circle.

This particular instance is responsible for handling our request.

Let’s say C_HASH(Red Shoes) % 360 = 40, therefore S1(90) will have its value.

C_HASH(Blue Shoes) % 360 = 280, therefore S0(0) will have its value.

Coming back to our initial problem, what if we add another server?

Let’s say we add server S4 and:

C_HASH(S4) % 360 = 50

We will place S4 between S0 and S1, and according to our logic, any key with C_HASH( ) <= 50 should be handled by S4.

So what about the keys already present in S1 with C_HASH( ) <= 50? We establish a connection between S1 and S4 and transfer all this data from S1 to S4. In this way, the only disturbance happens with the next immediate neighbour of our newly added server, making this process much better than our previous solution.

You may be wondering, what if there are more than 360 servers? How do we map them? Well, I chose 360 as an example in this article. We can choose more or less slots depending on the scale of our application.

Yay! Problem solved, crisis averted, right? You already know the answer.

Crisis is never averted in software engineering. Servers can crash unexpectedly, data backup and recovery is costly, redirecting requests is not a trivial operation, things can and do go wrong all the time. That is why we constantly research, innovate and solve Leetcode medium questions to invent the next breakthrough technology 👍

On a closing note, a lot of engineers hurry to scale up their systems and distribute the database when a single machine is very much capable of handling the load, but is unable to do so because the queries are not optimised.

Using new tech and frameworks is very lucrative but logic level optimisation should always be preferred over hardware level optimisation, no matter the scale.

P.S — I hope you have realised by now that the title of this article is a pun well intended XD