A visual guide to consistent hashing

Caching is an important aspect of high-performance applications. As the data volume increases, the cached data needs to be distributed across multiple servers. We need to make sure the following objectives are met while doing so.

  • Maximize the cache hits: This will reduce the load on the primary data source and reduce the overall latency.

As the title of this post suggests, we will look into how consistent hashing can be used to achieve the above objectives. Before that, let’s look at using a straightforward approach to solving the problem.

Note: This article was initially published here. It has been adapted for medium format using CodePen for embedding simulations.

Modulo Hashing

In this approach, we hash the requests based on a key and use the formula hash(key) % number_of_servers to route the request to the appropriate cache server. For example: If a key "apple" hashes to 14 and we have 3 cache servers, the request for "apple" will be forwarded to server number 2 as 14 % 3 = 2.

Let’s simulate this for 3 cache servers, 100 unique keys, 300 random requests and see how it performs.

Click the CodePen below and check the stats. Increase the speed to fast forward.

Note: If you are on mobile, please click here for a better view of the simulation.

Modulo Hashing: Static nodes

Let’s analyze the results

  • Cache Hit Ratio: As expected, 2/3rd of the requests(67%) are returned from the cache. This is good.

Modulo hashing works well for a fixed number of servers. But in many cases, we need to add or remove servers as per the variation in traffic volume. And, servers can crash sometimes. Let’s simulate the following dynamic nodes scenario with modulo hashing and see how it performs.

  • 3 servers(S0, S1, S2), 100 unique keys, 300 random requests as earlier

Note: If you are on mobile, please click here for a better view of the simulation.

Modulo Hashing: Elastic nodes

Let’s analyze the results

  • Cache Hit Ratio: This drops from ~67% earlier to ~45%.

This is because many keys are mapped to a different server when the number of servers changes. For example, a key “orange” with hash value 11 is initially routed to the server S2 when there are 3 servers(11 % 3 = 2), whereas it is routed to the server S3 when there are 4 servers(11 % 4 = 3). This leads to ineffective use of cache.

Consistent Hashing

Consistent Hashing has a different approach to address the drawbacks of the modulo hashing with dynamic nodes. Let’s start with the basic concepts of consistent hashing.

  • The servers(called nodes) are hashed and mapped to a number in a fixed range. This range can be imagined as a real number(not an integer) between 0 and 360 to represent it as points on a circle. The node is placed on this circular ring based on its hash value mapped to range 0–360. For example: If the hash value of the server S1 maps to 90, it will be placed as the point at 90 degrees on the circumference of the circle.

Let’s play this simulation at 0.5x speed and visualize this basic concept.

Note: If you are on mobile, please click here for a better view of the simulation.

Consistent Hashing: Basic Concept

Now that we understand the basic concept, let’s run the simulation and observe the stats for 3 servers, 100 unique keys, 300 random requests. (Please increase the simulation speed when required to fast forward to the final stats)

Note: If you are on mobile, please click here for a better view of the simulation.

Consistent Hashing(Basic): Static nodes

We can observe that cache hit ratio and load distribution is very similar to that of modulo hashing. This is expected as the algorithm behaves almost the same for a fixed number of servers.

Let’s see how this basic concept of consistent hashing handles the addition and removal of the nodes using the below scenario

  • 3 servers(S1, S2, S3), 100 unique keys, 300 random requests as earlier

Note: If you are on mobile, please click here for a better view of the simulation.

Consistent Hashing(Basic): Elastic nodes

Let’s analyze the results

  • Cache Hit Ratio: The cache hit ratio is ~60% compared to ~50% in modulo hashing. This is because very few keys are remapped when a node is added or removed.

Consistent hashing solves this load distribution problem by placing each node at multiple points on the ring. These points are called virtual nodes. For example, if we need to represent node S1 as 4 points on the ring, we place virtual nodes S1-1 to S1-4 on the ring using the same logic as earlier. This allows multiple small fragments of the ring to be mapped to a single node.

Let’s simulate the previous elastic nodes scenario with 12 virtual nodes per node.

Note: If you are on mobile, please click here for a better view of the simulation.

Consistent Hashing(Full): Elastic nodes

Let’s analyze the results

  • Cache Hit Ratio: The cache hit ratio remains good i.e. ~60% compared to ~50% in modulo hashing.

Conclusion

Consistent hashing has proven to be a useful technique since its inception in 1997 and it is used in many well-known distributed systems because of the simplicity and the benefits it offers. The optimization of consistent hashing does not end with what we have read so far. For example: check out this blog or the video by Vimeo engineering on their practical usage and adaptation.

Acknowledgments

  • The idea of the visual simulation was inspired by the amazing interactive posts like this by @bciechanowski

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store