Shulou(Shulou.com)06/02 Report--

This article shows you how to understand a variety of load balancing algorithms and their Java code implementation, the content is concise and easy to understand, absolutely can make your eyes bright, through the detailed introduction of this article, I hope you can get something.

First of all, I will introduce to you what is load balancing.

Load balancing is based on the existing network structure, which provides a cheap, effective and transparent way to expand the bandwidth of network devices and servers, increase throughput, enhance network data processing capacity, and improve network flexibility and availability.

Load balancer, known as Load Balance in English, means to distribute it to multiple operating units for execution, such as Web server, FTP server, enterprise critical application server and other critical task servers, so as to complete the task together.

This article describes various algorithms of "evenly distributing external requests to a server in a symmetric structure", and demonstrates the specific implementation of each algorithm with Java code. OK, let's get to the point. Before we get to the point, write a class to simulate the Ip list:

Import java.util.HashMap;/** * @ author ashang.peng@aliyun.com * @ date February 07, 2017 * / public class IpMap {/ / list of Ip to be routed, Key represents Ip,Value represents the weight of the Ip public static HashMap serverWeightMap = new HashMap (); static {serverWeightMap.put ("192.168.1.100", 1); serverWeightMap.put ("192.168.1.101", 1) / / weight is 4serverWeightMap.put ("192.168.1.102", 4); serverWeightMap.put ("192.168.1.103", 1); serverWeightMap.put ("192.168.1.104", 1); / / weight is 3serverWeightMap.put ("192.168.1.105", 3); serverWeightMap.put ("192.168.1.106", 1); / / weight is 2serverWeightMap.put ("192.168.1.107", 2) ServerWeightMap.put (192.168.1.108, 1); serverWeightMap.put (192.168.1.109, 1); serverWeightMap.put (192.168.1.110, 1);} polling (Round Robin)

The principle of the polling scheduling algorithm is that each request from the user is assigned to the internal server in turn, starting from 1 to N (the number of internal servers), and then restart the cycle. The advantage of the algorithm is its simplicity, it does not need to record the status of all current connections, so it is a stateless scheduling.

The code implementation is roughly as follows:

Import java.util.ArrayList;import java.util.HashMap;import java.util.Map;import java.util.Set;/** * @ author ashang.peng@aliyun.com * @ date February 07, 2017 * / class RoundRobin {private static Integer pos = 0; public static String getServer () {/ / rebuild a Map to avoid concurrency problems caused by server uploading and downloading Map serverMap = new HashMap (); serverMap.putAll (IpMap.serverWeightMap) / / get the Ip address ListSet keySet = serverMap.keySet (); ArrayList keyList = new ArrayList (); keyList.addAll (keySet); String server = null; synchronized (pos) {if (pos > keySet.size ()) pos = 0; server = keyList.get (pos); pos + +;} return server;}}

Because the address list in serverWeightMap is dynamic, and machines may go online, offline or downtime at any time, in order to avoid possible concurrency problems, a new local variable serverMap is created inside the method, and the contents of serverMap are copied locally to the thread to avoid being modified by multiple threads. This may introduce new problems, and the modification of serverWeightMap after replication cannot be reflected to serverMap, that is, during this round of server selection, new servers or offline servers will not be known by the load balancing algorithm. It doesn't matter if the server goes offline or goes down, an address that doesn't exist may be accessed. Therefore, the service caller needs to have corresponding fault-tolerant processing, such as re-initiating a server selection and invocation.

For the current polling location variable pos, in order to ensure the sequence of server selection, it is necessary to lock it during operation, so that only one thread can modify the value of pos at the same time, otherwise, when the pos variable is modified concurrently, the sequence of server selection can not be guaranteed, and it may even cause the keyList array to cross the bounds.

The advantage of polling method is that it tries to achieve the absolute balance of request transfer.

The disadvantage of the polling method is that in order to achieve the absolute balance of request transfer, a considerable price must be paid, because in order to ensure the mutual exclusion of pos variable modification, it is necessary to introduce a heavy pessimistic lock synchronized, which will lead to a significant decrease in the concurrent throughput of the polling code.

Random (Random) method

Through the random algorithm of the system, one of the servers is randomly selected for access according to the list size of the back-end servers. According to the theory of probability and statistics, with the increase of the number of times the client calls the server,

The actual effect is getting closer and closer to the average allocation of calls to each server at the back end, that is, the result of polling.

The code implementation of the random method is roughly as follows:

Import java.util.ArrayList;import java.util.HashMap;import java.util.Map;import java.util.Set;/** * @ author ashang.peng@aliyun.com * @ date Feb 07, 2017 * / class Random {public static String getServer () {/ / rebuild a Map to avoid concurrency problems caused by server uploading and downloading Map serverMap = new HashMap (); serverMap.putAll (IpMap.serverWeightMap) / / get the Ip address List Set keySet = serverMap.keySet (); ArrayList keyList = new ArrayList (); keyList.addAll (keySet); java.util.Random random = new java.util.Random (); int randomPos = random.nextInt (keyList.size ()); return keyList.get (randomPos);}}

The whole code idea is consistent with the polling method, first rebuild the serverMap, and then get the server list. When server is selected, a random value of 0~keyList.size () interval is taken by Random's nextInt method, and a server address is randomly obtained from the server list to return. Based on the theory of probability and statistics, the greater the throughput, the closer the effect of the random algorithm to that of the polling algorithm.

Source address hash (Hash) method

The idea of source address hashing is that according to the IP address of the client, a value calculated by the hash function is used to modulo the size of the server list, and the result is the serial number of the server to be accessed by the customer server. The source address hash method is used for load balancing. Clients with the same IP address will be mapped to the same backend server for access every time when the list of backend servers remains unchanged.

The code implementation of the source address hashing algorithm is roughly as follows:

Import java.util.ArrayList;import java.util.HashMap;import java.util.Map;import java.util.Set;/** * @ author ashang.peng@aliyun.com * @ date Feb 07, 2017 * / class Hash {public static String getServer () {/ / rebuild a Map to avoid concurrency problems caused by server uploading and downloading Map serverMap = new HashMap (); serverMap.putAll (IpMap.serverWeightMap) / / obtain the Ip address ListSet keySet = serverMap.keySet (); ArrayList keyList = new ArrayList (); keyList.addAll (keySet); / / in Web applications, you can obtain String remoteIp = "127.0.0.1"; int hashCode = remoteIp.hashCode (); int serverListSize = keyList.size (); int serverPos = hashCode% serverListSize;return keyList.get (serverPos);}}

The first two parts are the same as polling method and random method, but the difference lies in the routing part. Through the client's ip, that is, remoteIp, get its hash value, model the size of the server list, and the result is the index value of the selected server in the server list.

The advantage of the source address hash method is that it ensures that the same client IP address will be hashed to the same back-end server until the list of back-end servers changes. Based on this feature, stateful session sessions can be established between service consumers and service providers.

The disadvantage of the source address hashing algorithm is that unless the servers in the cluster are very stable and will not go online or offline, once the servers are online or offline, the probability that the server routed through the source address hash algorithm is the server online and offline is very low. If it is session, it can not get session, if it is cache, it may cause "avalanche". If this explanation is not suitable for understanding, you can see my previous article MemCache super-detailed interpretation, consistent Hash algorithm section.

Weighted polling (Weight Round Robin) method

Different back-end servers may not have the same machine configuration and current system load, so their resilience is also different. Machines with high configuration and low load are configured with higher weights to handle more requests, while machines with low and high loads are assigned lower weights and lower system load. Weighted polling can handle this problem well and assign requests sequentially and according to weights to the backend. The code implementation of the weighted polling method is roughly as follows:

Import java.util.*;/** * @ author ashang.peng@aliyun.com * @ date Feb 07, 2017 * / class WeightRoundRobin {private static Integer pos; public static String getServer () {/ / rebuild a Map to avoid concurrency problems caused by server uploading and downloading Map serverMap = new HashMap (); serverMap.putAll (IpMap.serverWeightMap); / / get Ip address ListSet keySet = serverMap.keySet (); Iterator iterator = keySet.iterator () List serverList = new ArrayList (); while (iterator.hasNext ()) {String server = iterator.next (); int weight = serverMap.get (server); for (int I = 0; I

KeySet.size () pos = 0; server = serverList.get (pos); pos + +;} return server;}}

Similar to the polling method, only a section of weight calculation code is added before obtaining the server address, and the address is repeatedly added to the server address list according to the size of the weight. The greater the weight, the more requests the server gets per round.

Weighted random (Weight Random) method

Like the weighted polling method, the weighted random method allocates different weights according to the configuration of the back-end machine and the load of the system. The difference is that it requests back-end servers randomly according to weight, not in order.

Import java.util.*;/** * @ author ashang.peng@aliyun.com * @ date Feb 07, 2017 * / class WeightRandom {public static String getServer () {/ / rebuild a Map to avoid concurrency problems caused by server uploading and downloading Map serverMap = new HashMap (); serverMap.putAll (IpMap.serverWeightMap); / / get Ip address ListSet keySet = serverMap.keySet (); Iterator iterator = keySet.iterator () List serverList = new ArrayList (); while (iterator.hasNext ()) {String server = iterator.next (); int weight = serverMap.get (server); for (int I = 0; I < weight; ionization +) serverList.add (server);} java.util.Random random = new java.util.Random (); int randomPos = random.nextInt (serverList.size ()); return serverList.get (randomPos) }}

This code is equivalent to the combination of random method and weighted polling method, which is easy to understand and does not explain.

Minimum number of connections (Least Connections) method

The minimum number of connections algorithm is flexible and intelligent. Due to the different configurations of the back-end servers, the processing of requests can be fast or slow. It dynamically selects the current number of requests according to the current connection situation of the back-end servers.

A server with the least backlog of connections to handle current requests, improve the utilization efficiency of back-end services as much as possible, and will be responsible for reasonable diversion to each server.

The previous methods make great efforts to balance the allocation of service consumer requests. Of course, it is right to do so. You can distribute the workload equally to multiple servers in the backend and improve the server utilization to a certain extent. But is this really the case? In fact, can the balance of the number of requests really represent the balance of load? This is a question worth thinking about.

The above question, to put it another way, is to observe the load of the system from the perspective of the back-end server, rather than requesting the initiator to observe it. The minimum number of connections method falls into this category.

The minimum number of connections algorithm is flexible and intelligent. Because the configuration of the back-end server is different, the processing of requests is fast and slow. It is precisely according to the current connection situation of the back-end server, dynamically select the server with the least backlog of connections to deal with the current request, improve the utilization efficiency of the back-end server as much as possible, and divert the load to each machine reasonably. Due to the minimum number of connections to design the summary and perception of the number of server connections, the design and implementation is more tedious, not to mention its implementation.

The above content is how to understand a variety of load balancing algorithms and their Java code implementation, have you learned the knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.