Load balancing and Consistent hashing

If you read my previous articles, probably you will notice I’m the one who really sees the importance of application deployment, distribution, and operations. Making an app is straightforward, but know how to distribute the product and making our customers having the same experience with our localhost is not that easy. Let’s have a look at a simple architect below for an application:

A client, via the internet, makes a request to our server. Our server receives the request, makes some operations with the database, gets the result, and returns back to our client. It seems to work with everybody in the company, so we decide to publish it to our clients.

Now, after months of praying in the pagoda (or going to the church), some magical Gods know about our app and suddenly the product goes viral. So instead of only receiving requests from our neighbor and family, our only server now receives thousands or even millions of requests, making it become overwhelming and eventually crashes.

However, luckily, it turns out the Gods doing this is Cai Shen Ye ( a God of money in Chinese Taoism), The company has much more money thanks to the increase in the number of customers. So we decide to buy more servers so that we can support all of our customers. This leads to the problem of this post. When we have multiple servers and a request comes in, which server should it direct to?

Load balancing

This is where the term load balancing comes in. A load balancer is actually a separate service from our backend, and it only has one job: to direct the incoming request to a suitable server. So how can it do this thing, I will write about some popular algorithms that people are using in their systems around the world, from the simple one to more complicated one, together with their pros and cons, (so be prepared for a bit technical).

Round Robin Algorithm

I must say this algorithm is the most popular one. The reason is it very easy to implement thanks to its simple logic. The idea is straightforward, we keep directs it to the next server on a cyclical basis. Let’s say we have 2 servers, then the first request comes to server a, the second comes to server B, the third comes back to server A, and go on… One big drawback of this algorithm is it assumes that all server having the same infrastructure and capacity. In the event of having one more powerful server than the other, this distribution is equal but of course not optimized for the whole system.

One optimized version of Round Robin to solve this drawback is Weighted Round Robin, which takes the machine infrastructure into consideration. Each server will be assigned a weighted value. So if server B has twice processing capacity compared to A, it will be assigned two times of requests on a cyclical basis.

Least Connection Algorithm

After that, we look into the logs and realize not all incoming requests are the same. Some requests need a longer time than others and consist of more complex operations on the server. Let’s continue from our 2 servers above, if all odd requests are just simple database query, whereas all even requests are much more complicated (maybe an update, which involves many services), then the system will not be optimized anymore.

Unlike Round Robin, Least Connection Algorithm will consider the currently active sessions of all the servers in our system. When the request comes in, the balancer will direct to the server which is handling the least number of active sessions By doing this, the number of sessions on each server is not the same, however, the overall system will be much more optimized.

This algorithm also has a Weighted version (Weighted Least Connection) which involves the infrastructure of each server by assigning the weighted value. The reason and logic are quite the same as mentioned in Weighted Round Robin.

Hashing and caching

As the system grows, we always want to implement caching. I will write another article to deeply discuss caching and its importance in the system. However, in this post, lets simply agree on one thing: For similar and frequent requests, caching will help reduce the complex operations in our backend and database, leading to a faster time of returning the result. So how is it related to our topic today. As we discussed the two algorithms above, we realize that the request of one particular user will not always go to one server. This making the cache implementation becomes difficult and nearly impossible to optimize.

That’s where the Hashing algorithm comes in. The idea is when a request comes in, we will use its value(usually IP address and port number) and put in a hash function (usually a uniform hash function, to ensure the output is uniformly distributed). The hash function will return a number that we can map into a corresponding server. For the same input, hash function always returns the same output. By utilizing this, we can always direct the request from a user to a corresponding server every single time, making the cache implementation more feasible.

Modular distribution

This leads to the question, after hashing value, how to map them to the server. One easy way is to use a modular operator for the number of servers we have.

By doing this. let’s say my request-id is 192168118080 which then becomes 20 after the hashing function, and then always go to server A thanks to the modular operators. By knowing this, the server can cache all my particular information in server A’s cache. Therefore, my subsequent request can be returned from server A’s cache.

Consistent hashing

As we can see, I put the name of this algorithm in the title of this post. I do really appreciate the idea of consistent hashing, especially on what problem it’s trying to solve and how elegant the solution is. So far what we implemented with modular operator works fine with caching and balancing the system. But there is always a new problem in every solution. Modular operators have a downside that it will only work well when our number of servers is fixed. As a business grows or shrinks, there will be a time when we need to change our number of the server. As I prefer optimism, let’s assume the business grows and now we need to buy one more server, resulting in a total of 5. This would mean that instead of doing modular 4, we change to modular 5. As a result, in the worst case, all incoming requests now directs to a completely new server and all of our previous caches are useless. So we need to replace modular operators with a different mechanism, which can reuse our current cache in the event of changing number of servers. That’s is where people use consistent hashing.

The idea is we also hash our server ID to a number, and map it to corresponding places in a big circle. When a request (red dots in the picture) comes in, we also do the same thing. Now, we can do a clockwise traversing, and direct the request to its nearest server. We can also modify the places via our function based on the infrastructure of each server (bigger server may be placed further from its previous server so that it serves more request)

What’s making the difference from the modular operator?

Now, let’s try putting the 5th server in the circle.

We can realize that only the requests in the red eclipse are affected. They can either direct to server E or still go to server A. The rest )outside of red eclipse) remains the same. This would mean that we still can utilize most of our cache in our servers.

A further upgrade of simple consistent hashing is the implementation of Virtual node, where we put the server id through many hash functions and mark them many places on the circle. This will helps the request distribution become less skewed, leading to a reduction in the likelihood that one server becomes overwhelming.

I think this post is long enough so I’m gonna stop here. Actually all of the mentioned algorithms are nothing new, and usually are possible to configure by all of the current load balancers. Each of the mentioned algorithms has its own pros and cons, so depending on our situation, we can find the most suitable one.