负载均衡算法

负载均衡（Load Balance）

模拟IP列表的类

public class IPMap {
    // 待路由的IP列表，key代表IP，value代表IP的权重。
    public static HashMap<String, Integer> serverWeightMap = new HashMap<>();
    
    static {
        serverWeightMap.put("192.168.1.100", 1);
        serverWeightMap.put("192.168.1.101", 4);
        serverWeightMap.put("192.168.1.102", 3);
    }

}

1. 轮询法

轮询调度算法原理：每一次把来自用户的请求轮流分配给内部的服务器。从1开始，到N（内部服务器个数），然后重新开始循环。
特点：简洁，无需记录当前所有连接的状态，是无状态调度。

// 轮询法的参考程序
public class RoundPolling {
    private static Integer pos = 0;
    
    public static String getServer() {
        // 重建一个map，避免服务器的上下线导致的并发问题。
        Map<String, Integer> serverMap = new HashMap<>()；
        // 填充带权重的IP列表
        serverMap.putAll(IPMap.serverWeightMap);
        // 取得IP地址的list
        Set<String> keySet = serverMap.keySet();
        ArrayList<String> keyList = new ArrayList<>();
        keyList.addAll(keySet);

        String server = null;
        //加锁（synchronized是重量级悲观锁，该轮询代码的并发吞吐量明显下降。）
        synchronized (pos) {    
             if (pos > keySet.size()) {
                 pos = 0;
            }
            server = keyList.get(pos);
            pos++;
        }
        return server;
    }
}

2. 随机法

通过系统的随机算法，根据后端服务器数量来随机选择一台服务器进行访问。随着客户端调用服务器的次数增多，其实际效果越来越接近平均分配，也就是轮询的结果。

// 随机法的参考程序
public class RandomPolling {
    public static String getServer() {
        //重建一个map，避免服务器的上下线导致的并发问题。
        Map<String, Integer> serverMap = new HashMap<>();
        serverMap.putAll(IPMap.serverWeightMap);

        Set<String> keySet = serverMap.keySet();
        ArrayList<String> keyList = new ArrayList<>();
        keyList.addAll(keySet);

        Random random = new Random();
        int rnadomPos = random.nextInt(keyList.size());
        
        return keyList.get(randomPos);
    }
}

3. 源地址哈希法

根据客户端的IP地址，通过哈希函数计算得到一个数值，用该数值付服务器列表的大小进行取模运算，得到的结果便是客户端要访问服务器的序号。
采用源地址哈希法进行负载均衡，同一IP地址的客户端，当后端服务器列表不变时，它每次都会映射到同一台后台服务器上。

// 源地址哈希法的参考程序
public class HashPolling {
    public static String getServer() {
        //重建一个map，避免服务器的上下线导致的并发问题。
        Map<String, Integer> serverMap = new HashMap<>();
        serverMap.putAll(IPMap.serverWeightMap);

        Set<String> keySet = serverMap.keySet();
        ArrayList<String> keyList = new ArrayList<>();
        keyList.addAll(keySet);

        // Web中可用HttpServlet.getRemoteIp()方法获取IP。
        String clientIP = "127.0.0.1";
        int hashcode = clientIP.hashcode();
        int serverListSize = keyList.size();
        int serverPos = hashcode % serverListSize;
      
        return keyList.get(serverPos);
    }
}

4. 加权轮询法

不同的后端服务器可能配置和系统当前的负载并不一样，因此服务器的抗压能力也不同。
配置高、负载低的服务器配置更高的权重；配置低、负载低的服务器配置更低的权重。将客户端请求按序且按照权重分配到后端。

// 加权轮询的参考程序
public class RandomPolling {
    private static Integer pos;

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

        Set<String> keySet = serverMap.keySet();
        Iterator<String> iterator = keySet.iterator();

        List<String> serverList = new ArrayList<>();
        while (iterator.hasNext()) {
            String server = iterator.next();
            int weight = serverMap.get(server);
            for (int i = 0; i < weight; i++) {    // 根据权重大小添加server
                serverList.add(server);
            }

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

5. 加权随机法

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

// 加权轮询的参考程序
public class RandomPolling {
    private static Integer pos;

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

        Set<String> keySet = serverMap.keySet();
        Iterator<String> iterator = keySet.iterator();

        List<String> serverList = new ArrayList<>();
        while (iterator.hasNext()) {
            String server = iterator.next();
            int weight = serverMap.get(server);
            for (int i = 0; i < weight; i++) {    // 根据权重大小添加server
                serverList.add(server);
            }

        Random random = new Random();
        // 随机获取server序号
        int randomPos = random.nextInt(serverList.size());  
        return serverList.get(randomPos);
    }
}

6. 最小连接数法

由于后端服务器的配置不尽相同，对于请求的处理有快有慢，根据后端服务器的连接情况，动态地选择其中积压的连接数最少的服务器来处理当前的请求。尽可能地提高后端服务的利用率。从后端服务器的视角来观察系统的负载。