Load Balancing - Discussing Statefulness and need for Consistent Hashing

Introduction

Load Balancing is one of the most widely used topics when we design systems. Almost every system which deals with a considerable number of clients/requests will need Load balancers at some point of time.

Suppose you built a service which you want others to use. You have also set up a payment model which will allow your clients to pay you as they use your service. Since you have just launched your service and there are not many people aware about it, you might be having a handful of clients willing to use your service. So, initially with a small number of clients you can directly set up your service with a single server without thinking about Load Balancing. The initial architecture may look like this.

But, with time your service will start getting popular and people will come to know about it. You have made a flawless service and your clients liked it so much that they are going to tell others as well. Soon you will be having a lot of Clients willing to use your service and pay you for that.

Now you have a lot of requests coming in and you realise that one system won’t be able to handle this amount of load. With the money you received from the clients , you decide to buy multiple servers in order to handle the increasing load. With multiple servers with yourself now you need something to distribute the incoming client’s requests to these servers evenly. This process of distributing the incoming requests evenly to the multiple machines is known as Load Balancing. The component which performs this is known as Load Balancer.

With Load Balancers in the picture, now your architecture will look like this.

Health Checks by Load Balancers

Load Balancers are also widely used to perform Health Checks of the backend servers in order to know their availability. In this scenario the load balancers ping the backend servers and the servers reply to them with their States, whether they are available to take requests or not.

Types of Load Balancers

We will discuss two types of Load Balancers which have been around for quite some time and are popular as well.

1. L4 Load Balancers or Network Load Balancers: L4 Load Balancer routes the request on the basis of the address information of the incoming requests. It does not inspect the content of the request. The Layer 4 (L4) Load Balancer makes the routing decisions based on address information extracted from the first few packets in the TCP stream.
2. L7 Load Balancers or Application Load Balancers: L7 Load Balancer routes the request on the basis of the packet content. There can be dedicated servers which could serve the requests based on their content, like URLs, Images, Graphics and Video contents. You can set up the system in such a way that the static contents are served by one dedicated server and requests demanding certain information which needs a db call can be served by another dedicated server.

Maintaining States in Load Balancing

Suppose your system wants to maintain states between multiple requests. Load Balancers can ensure this Statefulness. They can make sure that a particular incoming request is always routed to the same server. And the backend server can then use a Local Cache to store the metadata regarding the requests to be used at a later point of time. (We have discussed Caching in detail in one of our previous editions under this Newsletter. Do check it out.)

One possible way a Load Balancer can achieve this is by memorising the IP address of the incoming Client’s request. The Load balancer can use a constant Hash Function that can build a Hash out of the incoming Client’s IP address and the total number of available backend servers at that point of time. We can assume that the chosen Hash Function will evenly distribute the incoming requests to the backend servers.

Suppose we have M backend servers currently available and a hash function H that hashes the incoming requests on the basis of IP Address and number of backend servers (M). The hash function hashes the incoming client’s request on the basis of the IP address and later modulo the generated hash by the total number of available backend servers (M). It does the modulo in order to direct the incoming hashed request to one of the available backend servers.

Hashing the Client’s request on the basis of its IP address allows the request coming from the same IP address to be handled by the same backend server most of the times. This allows the backend server to make use of its Local Cache and reduce the service response time. Hence increasing the system performance.

But what if the number of Servers changes frequently? There can be scenarios where some servers may get worn out or multiple new servers are introduced into the system to handle the increasing load. In those situations since the number of servers have changed, our Hash Function will route the same requests to completely different sets of backend servers. This can make the Local Cache of the servers completely useless and can also increase the response time of the service and ultimately degrade its performance.

We solve this problem with the help of Consistent Hashing. It allows a minimal change in the hash function of all the earlier Requests whenever any new server is added or removed. We have discussed Consistent Hashing in one of our previous editions in this Newsletter. Do check that out to understand how Consistent Hashing works.

Concluding

I believe this article would have cleared your concepts on Load Balancing and multiple terminologies used widely under it. Do check out the other editions which were referenced in this article in order to have a more clear picture on Load Balancing. In the meantime, I will come up with more conceptual topics on System Design and Distributed Systems.

Do like and share this edition with your peers and also subscribe to this Newsletter so that you can get notified when I come up with more content in future.

Until next time, Dive Deep and Keep Learning!