Original address:Blog.csdn.net/lihao21/art…
This paper describes common algorithms for load balancing.
Round Robin
Polling method is the most common algorithm in load balancing, it is easy to understand and easy to implement. Polling means that the load balancer allocates client requests to the back-end server in turn for load balancing purposes. Suppose you now have six client requests and two back-end servers. When the first request reaches the load-balancing server, the load-balancing server dispatches the request to back-end server 1. When the second request hits, the load balancing server dispatches the request to back-end server 2. Then the third request arrives, and since there are only two back-end servers, request 3 is dispatched to back-end server 1. The analogy is shown in Figure 1.
Figure 1: Polling load balancing
Weighted Round Robin
The simple polling method does not take into account the performance and load differences of the back-end machines. Assign higher weights to high-performance, low-load machines to handle more requests; Low-performance, high-load machines, on the other hand, are configured with lower weights to handle fewer requests. Weighted polling is a good way to handle this problem by ordering and weighting requests to the back-end server. Suppose there are six client requests and two back-end servers. Backend server 1 is assigned weight 5, and backend server 2 is assigned weight 1. In this way, client requests 1, 2, 3, 4, 5 are dispatched to server 1; Client request 6 is dispatched to server 2 for processing. Next, requests 7,8,9,10,11 are dispatched to server 1, request 12 is dispatched to server 2, and so on. This request dispatch process can be represented in Figure 2.
Figure 2: Weighted polling load balancing
Least Connections method
Even though the back-end machine has the same performance and load, different client requests have different complexity resulting in different processing times. The minimum number of connections method dynamically selects the server with the smallest number of backlogged connections to process the current requests according to the current number of connections on the back-end server, so as to improve the utilization efficiency of the back-end server as much as possible and distribute the requests to each server reasonably. Why is it reasonable to utilize the server to process requests based on the number of connections? Considering that the processing logic of a client request is complex and takes a long time for the server to process it, the client needs to keep the connection with the server because it needs to wait for the response from the server. In this way, the client needs to keep the connection with the server for a long time. Assume that client requests 1, 2, 3, 4, 5 have been dispatched to server 1 and server 2, as shown in Figure 3:
Figure 3: Schematic diagram of minimum connection method (1)
At this point, request 1, request 3 on the server has been processed, and the connection to the client has been disconnected. Requests 2, 4, and 5 are still being processed on the server, that is, the server remains connected to the client of those requests. If requests are again dispatched to server 2, it will result in more requests from the server and a higher load on server 2. If you consider the number of connections to the server, the current number of connections to server 1 is 1, and the number of connections to server 2 is 2, and the request is dispatched to server 1, the load is relatively balanced. The dispatch method using the minimum connection number method is shown in Figure 4:
Figure 4: Schematic diagram of minimum connection method (2)
Random method
Random method is also very simple, is to randomly select a back-end server to process the request. Since the server is selected with equal probability each time, client requests can be distributed evenly across all back-end servers.
Source Hashing
The idea of source address hashing is to obtain the IP address of the client through the hash function to calculate a value, with the value of the size of the server list modular operation, the result is the serial number of the client to access the server. The source address hash method is used for load balancing. When the list of back-end servers remains unchanged, clients with the same IP address will be mapped to the same back-end server each time for access. If the back-end server is a cache system, when the back-end server increase or decrease, the use of simple hashing modulus method, will greatly reduce the hit ratio, this problem can be solved by using consistent hashing method. For an introduction to Consistent Hashing, see the analysis of file Consistency Hash(Consistent Hashing).