System Design : Consistent Hashing

Why do we need Consistent Hashing ?

Imagine you are building a bookMyShow system which is used to book tickets. Initially what would be your system?

All user requests (search, booking, payments) go through the server and hit a single database.

Now as your system scales, the single database becomes a bottleneck.

• Writes: All booking operations (seat locking, payments) go to one database → means server overwhelms, disk I/O limits, locking issues.

• Reads: High traffic for browsing movies, checking availability → even reads can overwhelm a single node.

Even though reads can be improved using caching or replicas, eventually a single database cannot handle the load.

To solve this, we do horizontal scaling. Instead of one database, we now have multiple database servers.

Now data is distributed across these databases instead of storing everything in one place.

Hashing

Now the important question is:

How do we decide which data goes to which database?

There should be a mechanism to determine where a specific piece of data is stored so that we can fetch it correctly. For this, we use a shard key (eg: userid) and apply a hash function on it to determine the index of the server.

serverIndex = hash(key) % N, where N is the size of the server pool.

This gives us a deterministic mapping, meaning the same key will always go to the same server.

So this architecture looks good and works well for distributing load across multiple servers.

The rehasing problem

This approach works well when the size of servers is fixed and data is distributed evenly.

But there is some problems if size is not fixed…

As the scale grew more we added an another shard to distribute the load further now our hash function will give the same hash value for the key but now our number of servers udpated to 4 so now modulo values will be changed.

This means that the mapping of keys to servers changes.

From the above figure, we can see that:

• Most of the keys now point to different servers

• Only a few keys remain on the same shard

In other words:

A small change in the number of servers causes a large portion of the data to be remapped.

Why is this a problem?

To reflect this new mapping, we now need to:

• Move large amounts of data across servers

• Rebalance the entire system

• Update routing logic

This leads to:

• High network overhead

• Increased computation

• Possible downtime or performance degradation

So this hashing is not consistent thats why the concept of consistent hashing came into picture.

What is Consistent Hashing ?

Its a technique used in distributed systems where data is distributed across multiple servers efficiently. With this approach the data movement is minimized only subsets of keys needs to be remapped.

How Consistent Hashing works ?

Hash Servers

Arrangement of servers is in circular space called hash ring, the server is mapped onto the ring via server name or ip , let's understand with an example how the server is mapped in the ring.

• Create Hash Ring with fixed points(servers) for example lets take 1000

• Now we place 3 servers in our ring using function on server ip and suppose this is point where they will mapped (300,500,900)

Hash Keys

Place the keys by using same function but here we will not do the modulo will directly place the hash value of keys in the hash ring.

Server lookup

Now to determine which server the key is stored on we move in clockwise direction so k0(key0) is stored in server1 and this is how the server lookup is done

Adding and removing server

When we add new node (server 4) and it is placed somewhere on the ring, Only the keys between the new server and its previous neighbor need to move. All other keys remain untouched. Similarly, when a server is removed only the keys handled by that server are reassigned

This ensures minimal data movement compared to modulo hashing.

So far so good we successfully minimized the data movement. Now there is some bottlenecks in this architecture as well

Can you identify any problem from the below diagram

Problem with Basic Consistent Hashing

If not then let's discuss from the diagram you can see all keys(k0,k1 and k2) data are stored in server 1 and server 2, server 3 are empty and untouched so here hotspot problem will arise all load will go to the server 1 because following clockwise rotation that is the first server for all keys so the problem arises with this approach is

• non-uniform key distribution on the ring

• it is impossible to keep the same size of partitions on the ring for all servers considering a server can be added or removed

How do we solve this problem ?

Virtual Nodes

What we gonna do is we till take suppose 3 random sparse points from hash ring and we will map the server addresses on the hash ring keep in mind that no server is added just their address will be added there so that when any key moves clockwise if they found any server address they will be stored to that particular server see below diagram for better understanding

Summary

• Single database becomes a bottleneck as system scales (reads + writes)

• Horizontal scaling introduces multiple database shards

• Modulo hashing (hash(key) % N) distributes data across shards

• Works well only when number of servers is fixed

• Adding/removing servers causes most keys to be remapped

• Leads to heavy data movement, overhead, and instability

• Consistent hashing maps servers and keys on a hash ring

• Only a small subset of keys move when servers change

• Improves scalability and stability

• Virtual nodes ensure better load distribution and reduce hotspots

References

• https://bytebytego.com/courses/system-design-interview/design-consistent-hashing

• https://www.hellointerview.com/learn/system-design/core-concepts/consistent-hashing

• https://docs.aws.amazon.com/wellarchitected/latest/reducing-scope-of-impact-with-cell-based-architecture/consistent-hashing.html

• https://highscalability.com/consistent-hashing-algorithm/

• https://arpitbhayani.me/blogs/consistent-hashing/