Java implements multiple load balancing algorithms

First of all, let me introduce to you what load balancing is (from encyclopedia)

Load balancing is built on the existing network structure , it provides a cheap, effective and transparent method to expand the bandwidth of network devices and servers, increase throughput, enhance network data processing capabilities, and improve network flexibility and availability.

Load balancing, the English name is Load Balance, which means to allocate execution to multiple operating units, such as Web servers, FTP servers, enterprise key application servers and other mission-critical servers, etc., so as to complete the work together Task.

This article talks about various algorithms for "evenly distributing requests sent from the outside to a certain server in a symmetric structure", and demonstrates the specific implementation of each algorithm in Java code. OK, below Let’s get to the point. Before entering the topic, first write a class to simulate the IP list:

import java.util.HashMap;

/**
 * @author [email protected]
 * @date 二月 07, 2017
 */

public class IpMap   {
    // 待路由的Ip列表，Key代表Ip，Value代表该Ip的权重
    public static HashMap<String, Integer> serverWeightMap =
            new HashMap<String, Integer>();

    static
    {
        serverWeightMap.put("192.168.1.100", 1);
        serverWeightMap.put("192.168.1.101", 1);
        // 权重为4
        serverWeightMap.put("192.168.1.102", 4);
        serverWeightMap.put("192.168.1.103", 1);
        serverWeightMap.put("192.168.1.104", 1);
        // 权重为3
        serverWeightMap.put("192.168.1.105", 3);
        serverWeightMap.put("192.168.1.106", 1);
        // 权重为2
        serverWeightMap.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);
    }
}

The Round Robin method

The principle of the round robin scheduling algorithm is to send the IP address from the user every time. Requests are assigned to internal servers in turn, starting from 1, until N (the number of internal servers), and then restarting 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 [email protected]
 * @date 二月 07, 2017
 */

class RoundRobin   {
    private static Integer pos = 0;

    public static String getServer()
    {
        // 重建一个Map，避免服务器的上下线导致的并发问题
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        // 取得Ip地址List
        Set 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;
    }
}

Since the address list in serverWeightMap is dynamic, machines may go online, go offline, or crash at any time. Therefore, in order to avoid possible concurrency problems, A new local variable serverMap needs to be created inside the method. Now copy the contents of serverMap to the thread local to avoid being modified by multiple threads. This may introduce new problems. Modifications to serverWeightMap after replication cannot be reflected to serverMap. That is to say, during this round of server selection, the load balancing algorithm will not be able to know whether new servers or offline servers are added. It doesn't matter if you add a new one. If a server goes offline or crashes, you may access a non-existent address. Therefore, the service caller needs to have corresponding fault tolerance processing, such as reinitiating server selection and call.

For the currently polled position variable pos, in order to ensure the order of server selection, it needs to be locked during operation so that only one thread can modify the value of pos at the same time. Otherwise, when the pos variable If it is modified concurrently, the order of server selection cannot be guaranteed, and it may even cause the keyList array to go out of bounds.

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

The disadvantage of the polling method is that in order to achieve an absolute balance of request transfer, a considerable price must be paid, because in order to ensure the mutual exclusion of pos variable modifications, a heavyweight pessimistic lock synchronized needs to be introduced. This This will cause a significant drop in the concurrent throughput of this polling code.

Random method

Through the random algorithm of the system, one of the servers is randomly selected for access according to the list size value of the back-end server. It can be known from the theory of probability and statistics that as the number of times the client calls the server increases, the actual effect is getting closer and closer to evenly distributing the calls to each server in the backend, which 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 [email protected]
 * @date 二月 07, 2017
 */

 class Random   {
    public static String getServer()
    {
        // 重建一个Map，避免服务器的上下线导致的并发问题   
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        // 取得Ip地址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 overall code idea is consistent with the polling method. The serverMap is rebuilt first, and then the server list is obtained. When selecting a server, use Random's nextInt method to take a random value in the range of 0~keyList.size(), thereby randomly obtaining a server address from the server list and returning it. Based on the theory of probability statistics, the greater the throughput, the closer the effect of the random algorithm is to that of the polling algorithm.

Source address hash (Hash) method

The idea of ​​source address hash is to obtain a value calculated by a hash function based on the IP address of the client, and use this value to compare the server list Perform a modulo operation on the size, and the result obtained is the serial number of the server that the client wants to access. 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 backend server list remains unchanged.

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

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author [email protected]
 * @date 二月 07, 2017
 */

 class Hash      {
    public static String getServer()
    {
        // 重建一个Map，避免服务器的上下线导致的并发问题
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        // 取得Ip地址List
        Set keySet = serverMap.keySet();
        ArrayList keyList = new ArrayList();
        keyList.addAll(keySet);

        // 在Web应用中可通过HttpServlet的getRemoteIp方法获取
        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 the polling method and the random method. The difference lies in the routing part. Obtain its Hash value through the client's IP, which is remoteIp, and modulo the size of the server list. The result is the

index

value of the selected server in the server list. The advantage of the source address hashing method is that it ensures that the same client IP address will be hashed to the same backend server until the backend server list changes. According to this feature, a stateful session can be established between service consumers and service providers.

　　源地址哈希算法的缺点在于：除非集群中服务器的非常稳定，基本不会上下线，否则一旦有服务器上线、下线，那么通过源地址哈希算法路由到的服务器是服务器上线、下线前路由到的服务器的概率非常低，如果是session则取不到session，如果是缓存则可能引发"雪崩"。如果这么解释不适合明白，可以看我之前的一篇文章MemCache超详细解读，一致性Hash算法部分。

　　加权轮询（Weight Round Robin）法

　　不同的后端服务器可能机器的配置和当前系统的负载并不相同，因此它们的抗压能力也不相同。给配置高、负载低的机器配置更高的权重，让其处理更多的请；而配置低、负载高的机器，给其分配较低的权重，降低其系统负载，加权轮询能很好地处理这一问题，并将请求顺序且按照权重分配到后端。加权轮询法的代码实现大致如下：

import java.util.*;

/**
 * @author [email protected]
 * @date 二月 07, 2017
 */
class WeightRoundRobin   {
    private static Integer pos;

    public static String getServer()
    {
        // 重建一个Map，避免服务器的上下线导致的并发问题
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        // 取得Ip地址List
        Set 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; i++)
                serverList.add(server);
        }

        String server = null;
        synchronized (pos)
        {
            if (pos > keySet.size())
                pos = 0;
            server = serverList.get(pos);
            pos ++;
        }

        return server;
    }
}

　　与轮询法类似，只是在获取服务器地址之前增加了一段权重计算的代码，根据权重的大小，将地址重复地增加到服务器地址列表中，权重越大，该服务器每轮所获得的请求数量越多。

　　加权随机（Weight Random）法

　　与加权轮询法一样，加权随机法也根据后端机器的配置，系统的负载分配不同的权重。不同的是，它是按照权重随机请求后端服务器，而非顺序。

import java.util.*;

/**
 * @author [email protected]
 * @date 二月 07, 2017
 */

 class WeightRandom   {
    public static String getServer()
    {
        // 重建一个Map，避免服务器的上下线导致的并发问题
        Map<String, Integer> serverMap =
                new HashMap<String, Integer>();
        serverMap.putAll(IpMap.serverWeightMap);

        // 取得Ip地址List
        Set 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; i++)
                serverList.add(server);
        }

        java.util.Random random = new java.util.Random();
        int randomPos = random.nextInt(serverList.size());

        return serverList.get(randomPos);
    }
}

　　这段代码相当于是随机法和加权轮询法的结合，比较好理解，就不解释了。

　　最小连接数（Least Connections）法

　　最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它是根据后端服务器当前的连接情况，动态地选取其中当前

　　积压连接数最少的一台服务器来处理当前的请求，尽可能地提高后端服务的利用效率，将负责合理地分流到每一台服务器。

　　前面几种方法费尽心思来实现服务消费者请求次数分配的均衡，当然这么做是没错的，可以为后端的多台服务器平均分配工作量，最大程度地提高服务器的利用率，但是实际情况是否真的如此？实际情况中，请求次数的均衡真的能代表负载的均衡吗？这是一个值得思考的问题。

　　上面的问题，再换一个角度来说就是：以后端服务器的视角来观察系统的负载，而非请求发起方来观察。最小连接数法便属于此类。

　　最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它正是根据后端服务器当前的连接情况，动态地选取其中当前积压连接数最少的一台服务器来处理当前请求，尽可能地提高后端服务器的利用效率，将负载合理地分流到每一台机器。由于最小连接数设计服务器连接数的汇总和感知，设计与实现较为繁琐，此处就不说它的实现了。

The above is the detailed content of Java implements multiple load balancing algorithms. For more information, please follow other related articles on the PHP Chinese website!