Overview

Principle of operation

Balancing algorithms

When creating a group of real servers, we must choose an algorithm for balancing the load on them. Here is a list of available algorithms:

 Round robin algorithm

1. Weighted round robin algorithm

2. Least connections algorithm

3. Weighted least connections algorithm

4. Source IP address-based hash algorithm

5. Weighted source IP address-based hash algorithm

Let me remind you that all balancing works only for the first packet of the flow (session), then nothing is calculated and is sent along the same route as the first packet of the flow. Please note that there are only three main types of balancing and for each of them there is a subspecies "Weighted".

Round robin algorithm and weighted round robin algorithm

These are the simplest balancing algorithms. They distribute sessions in turn to each server. You can think of servers as pipes into which session balls are rolled. If a packet comes from a previously created session, then it is sent down the pipe to the previous ones.

In the case of the Weighted version of this algorithm, we can adjust the number of pipes for each of the real servers. If you do this, then each server will receive in turn as many new sessions as its "weight". In the figure below, the first server has a weight of 2, and the rest have a weight of one.

Least connections algorithm и Weighted least connections algorithm

Good enough balancing option. It sends a new flow to the server with fewer active connections. Consider the example in the figure.

The squares indicate the active connections (flows, sessions) on the servers. When the first flow arrives to the virtual server, all servers are equally loaded. The balancer selects the first server for the new flow. When the packet of the second flow arrives, the first server is already loaded a little harder than the others, so the packet is sent not to it, but to the second server. Then the third package arrives. It is associated with the first flow, so it is immediately sent to the first server, despite the fact that the first server is loaded more than the third. The fourth packet belongs to the new flow and the most free server at the moment is selected for it - the third.

Now let's see how it works in the case of server weights.

The first server has weight "2", the second and third servers are "1". Therefore, the first server has two "pipes", while the others have one. Squares – older active on servers. The first and third servers have four such old sessions, the second has three. But due to the fact that the first server has a weight of "2", it divides the old sessions between its "pipes" and in the end looks like two servers with two sessions on each.

In this case, the first packet of the new session 1 will be sent to the most idle first server. The second packet, which starts a new session, will go to the most unoccupied server, which again turns out to be the first (its second "pipe"), the third packet is connected by one flow with the first, and therefore will be sent again to the first server. But the fourth will choose the less busy second server. The fifth packet, if it were a packet of a new flow, could get to the third server, but it refers to the flow started by the fourth packet, and therefore is sent to the second server.

Source IP address-based hash algorithm и Weighted source IP address-based hash algorithm

These sorting algorithms calculate the server number to which the flow will be sent based on the IP address of the packet sender. The senders address is processed by some hash function, which always gives the same result for the same address - the number of the real server for the new flow. Hash functions are quite a convenient and popular thing in information technology. Their essence lies in the fact that they quickly convert input data (it can be data of arbitrary length, and fixed) into a clearly limited output range of values. At the same time, they try to make them such that the distribution of the output values is as uniform as possible. That is, if we pass an IP address to such function, then it will generate a result so that all our real servers are evenly loaded. This will be the case with a large number of clients. If there are few of them, then they can be distributed unevenly. The hash function produces a result in a certain range of values. We can have a different number of real servers. To combine these two ranges, we need to use some quick math function, for example, taking the remainder of dividing the result of a hash function by the number of real servers. This can be represented as follows:

In this mode, the server load will be approximately equal for a large number of different clients. But if we have already started balancing the load on the servers, then we probably have them. In the case of "weights" of servers, those servers with a higher weight receive wider ranges of hash results.

In this example, the hash function for the first client sends all its packets to the first server, and the packets from the second and third clients to the third server. Because the result of the hash function for the second and third clients fell into the wide range of the third server. But a not very pleasant situation could have happened when all clients would get on one server, and the rest would be idle.