Hashing for Systems Design, particularly for Load Balancing

This post is a continuation of my Systems Design series I share on LinkedIn.

Introduction

In large-scale systems, load balancing and caching are crucial components for ensuring high performance and availability. Today, I’ll be focusing on the concept of Hashing and its significance in Load Balancing.

Explanation of Hashing

First, let’s understand what Hashing is all about. Hashing is a process that turns an input, such as an IP address, email, or HTTP request (using their respective data types like a string or custom classes), into a fixed-size value, typically an integer. The purpose of hashing is to create a unique representation of the input data, which is essential for various applications in computer science.

One of the critical aspects of a good hashing function is its ability to maximize uniformity, which means minimizing collisions. A collision occurs when the hashing function outputs the same result for different inputs. In practice, you won’t need to build your own hashing function; instead, you can use an industry-grade one like SHA-3, which ensures a high level of uniformity.

Load Balancing and its Challenges

Before diving into how hashing plays a role in load balancing, let’s recap what load balancing is all about. As I explained in one of my recent LinkedIn post, load balancing is the process of distributing clients’ requests across a group of servers to ensure optimal resource utilization and prevent overloading any single server.

Now, let’s consider a specific challenge related to load balancing when we implement in-memory caches per server to store computationally expensive requests. The problem arises when the load balancer is set to use strategies like round-robin or randomly selecting servers. In such cases, there is no guarantee that same client’s request will be directed to a server where the response could be found cached. This leads to a decrease in cache hits, which can have adverse effects on the system’s performance, scalability, and user experience. The consequences may include financial losses, service disruptions, higher latencies, and reduced throughput.

Hashing to the Rescue: Targeted Load Balancing

To address the caching challenge in load balancing, we can leverage the power of hashing in Systems Design. By intelligently incorporating hashing into the load balancing process, we can ensure that clients’ requests are directed to the right server with the cached data.

Solution 1:

One approach to achieve targeted load balancing is by hashing what identifies the client, such as its email or IP address. We then use the modulo operation on the resulted hash and the number of servers to know which server to target for this client (assuming we’ve numbered our servers from 0 to the number of servers exclusive). However, Solution 1 has a significant limitation — it maximizes cache hits only as long as we don’t add or remove servers. If the number of servers changes, we risk losing most, if not all, of the cached data, as clients will end up targeting different servers after new modulos calculations. Therefore, Solution 1 is not suitable for systems that require frequent scaling.

Solution 2: Consistent Hashing

Consistent Hashing is a powerful solution that addresses the scaling problem of Solution 1. In this approach, we imagine placing servers and clients (or requests, IPs, etc.) in a circle and let each client target the server directly next to it in the circle, following either the clockwise or counter-clockwise direction as per preference. We use hashing to determine the position of servers and clients on the circle, with the resulting number corresponding to a degree in the circle between 0 and 360° if we decide to use degrees for example.

This architecture significantly reduces the impact of adding or removing servers. For example, take this circle:

Client 1 → Server 1 → Client 2 → Client 3 → Server 2 → Client 1

If we remove Server 1, only Client 1 is affected as it needs to target Server 2. However, Client 2 and 3 continue to target Server 2 and have their caches stable.

If we add a new server “Server 3,” like:

Client 1 → Server 1 → Client 2 → Server 3 → Client 3 → Server 2 → Client 1

In this case, only Client 2 is affected and needs to target Server 3 instead of Server 2, but most of the mapping remains consistent post-addition.

To further improve the distribution of clients to servers and reduce skew, you can duplicate the presence of servers on the circle by passing them through multiple hashing functions (each hashing function for a new placement on the circle per server).

Solution 3: Rendezvous Hashing

Rendezvous Hashing, also known as Highest Random Weight Hashing, is another excellent solution that ensures maximum mapping stability post the addition or removal of servers. In this approach, servers are ranked per client, IP address, username, or any criterion you wish to cache dependently to. The client then targets the server with the highest ranking. Ranking is made by hashes but again you unlikely need to implement a ranking function but instead use a premade one.

For example, suppose we have Client 1 and Client 2, along with Server 1 and Server 2. Our scoring function ranks Server 1 for Client 1 as the most suitable match, and Server 2 for Client 2. If we remove Server 2, Client 1 won’t be affected, and similarly, if we add a new server, both clients won’t be affected.

Conclusion

Hashing is a powerful concept in Systems Design, particularly when it comes to Load Balancing and caching. By implementing techniques like Consistent Hashing and Rendezvous Hashing, we can ensure targeted load balancing, maximizing cache hits, and achieving optimal system performance even as the infrastructure scales.

Thanks for reading, and I welcome your feedback in comments!

Here is my LinkedIn profile.