System Design - Load Balancing

What is Load Balancing?

Load Balancing is a technique to efficiently and uniformly distribute network traffic across multiple servers. When we are horizontally scaling our application then we add multiple servers to handle a large amount of network traffic. Here load balancing ensures that no single server receives too many requests and the network traffic is evenly distributed. This improves the whole application responsiveness.

Load Balancing By Normal Hashing:

A Hash map is a data structure that is used to map a given value with a particular key for faster access of elements, and hashing is the technique to map a value to a particular key using a special function. This special function is called a hash function. To know more about hashing and collision resolution techniques, check this article. Now how this hashing is used for Load Balancing?

Each request that a client makes contains a unique request id. Also, each of the multiple servers in the application is numbered. So the technique is to use a hash function which will take in the request ID of the server and generates a key that represents the server number to which this request will be redirected. Let's understand this with the help of an example.

Suppose we have four servers numbered 0-3. Our hash function is defined as h(x) = x % m, where x is the request ID and m is the no. of servers. The below table represents how three requests with request IDs 1000, 1010 and 1027 are mapped.

Request ID	Hash Function	Key/Server No.
1000	h(1000) = 1000%4	0
1010	h(1010) = 1010%4	2
1027	h(1027) = 1027%4	3

So, like this each request will be processed by the server to which it gets mapped after hashing its request ID value.

Drawbacks of using normal hashing:

The above-mentioned method works fine if the number of servers is fixed. But suppose now the total incoming traffic to the application increases over time and we have to scale up our application more. For that reason suppose one more server gets added in our above example. Now we have 5 servers. So now 1000,1010 both will be mapped to server 0 and 1027 to server 2. So now all the requests are being completely being mapped to different servers. So, what is the issue here?

First of all the request Id are not random, they usually contain some client/user information within it. Like here if we assume requests having 100 in the beginning is from a user having user id as U0, then requests having request starting with 101 is from user U1 and requests staring with 102 is from user U2. Now each server has a local cache in which it can store the response of a request for a particular user. All the time the server doesn't fetch from the database, if the request is from the same user within a specific interval of time it returns data from the cache, this improves the response time. Now initially when there were four servers the data of user U1 and U2 were being stored in local cache of server 2 and server 3 respectively. Now after adding another server, the requests from these users are going to different servers which does not have the cached data for these users. So all the cached data stored for all the users at different servers are lost. This operation can reduce the overall speed of the application when there are large no. of requests coming in and also the number of servers are much more.

This can be solved by a concept known as Consistent Hashing.

Load Balancing By Consistent Hashing:

The main difference between normal hashing and consistent hashing is the data structure that is being used. In normal hashing, the data structure is generally a linear array or an object with key-value pair. In the case of consistent hashing, we use a circular array data structure which is also known as consistent hash ring.
Also for consistent hashing we have a pre-defined search space. Let us denote it by N. Here the servers are also hashed into the hash ring. Each server has a unique id too. We can use those server IDs to hash the servers. Let us take our previous example with 4 servers and hash function as h(x) = x % N, here X will be ID of server and N = 100

Server ID	Hash Function	Position
1024(S1)	h(1024) = 1024%100	24
1049(S2)	h(1049) = 1049%100	49
1074(S3)	h(1074) = 1027%100	74
1099(S4)	h(1099) = 1099%100	99

Now lets assume there are these 4 requests with IDs 1023(R1), 1145(R2), 1270(R3) and 1375(R4). These 4 request will also be hashed and mapped on the circular hash ring.

The diagram shows how each server and request is mapped to the hash ring. The idea here is that each request here will be served by the nearest server to the right of it. Like R1 will be served by S1, R2 by S2, like this. Now as the requests and servers are hashed uniformly over the hash ring so the distribution of traffic will also be uniform.

Now if we add a new server here with a server ID 1080, it will hash to the position 1080%100 = 80 in the hash ring. The hash ring after adding this server will look like this:

Here unlike normal hashing, all the requests are not being re-mapped to different servers. The requests R1,R2 and R3 will be still be processed by the same server. Only R4 will now be served by S5 instead of S4. In the case of normal hashing, whenever a new server was added then each request was re-mapped to different servers and as a result, every useful information stored on local cache of servers was lost. Here that is reduced as only one server is being re-mapped. So, consistent hashing is more efficient.

One drawback of consistent hashing is that choosing an improper hash function might result in a skewed distribution of the servers over the hash map and that results in a particular server handling more load as compared to other servers. But still, with large no. of servers and a relatively large search space, consistent hashing is way more efficient than normal hashing.

Hope this article has given enough idea on Load Balancing and how normal hashing and consistent hashing works. Do mention in the comments your views on this article or any suggestions for improvement. Stay Safe and Happy coding!