负载均衡算法

什么是负载均衡

由于微服务架构的广泛应用，对于负载较高的服务来说，往往对应着多台服务器组成的集群。请求来临时，为了将请求均衡的分配到后端服务器，负载均衡程序将从注册中心查询可用的服务节点，通过负载均衡算法和规则，选取一台服务器进行访问，这个过程称为服务的负载均衡。

为什么要使用负载均衡

让所有节点以最小的代价、最好的状态对外提供服务，快速获取重要数据，最大化降低了单个节点过载、甚至crash的概率，解决大量并发访问服务问题；

负载均衡算法

轮询法

将请求顺序轮流分配到节点上；

随机法

根据节点列表的大小，随机选择一台进行访问，当请求无限大的时候，效果等同于平均分配；

源地址哈希法

根据客户端的IP生成一个hash值，与节点列表大小进行取模，当节点列表不发生改变的时候，请求恒打在固定服务器上；

加权轮询法

不同服务器的配置不同，为其设置权重，使得能者多劳；

加权随机法

同加权轮询法

最小连接法

由于后端服务器的配置不同，对于请求响应速度也不同，每次选择请求积压条数最少的服务器被选中；

自适应最优选择方法

这种算法的主要思路是在客户端本地维护一份同每一个服务节点的性能统计快照，并且每隔一段时间去更新这个快照。在发起请求时，根据“二八原则”，把服务节点分成两部分，找出 20% 的那部分响应最慢的节点，然后降低权重。这样的话，客户端就能够实时的根据自身访问每个节点性能的快慢，动态调整访问最慢的那些节点的权重，来减少访问量，从而可以优化长尾请求。由此可见，自适应最优选择算法是对加权轮询算法的改良，可以看作是一种动态加权轮询算法。它的实现关键之处就在于两点：第一点是每隔一段时间获取客户端同每个服务节点之间调用的平均性能统计；第二点是按照这个性能统计对服务节点进行排序，对排在性能倒数 20% 的那部分节点赋予一个较低的权重，其余的节点赋予正常的权重。

 //负载均衡算法
public class LoadBalancingTest {
    public static final Map<String,Integer> serverWeightMap = new HashMap<>();
    static {
        serverWeightMap.put("127.0.0.1",1);
        serverWeightMap.put("127.0.0.2",1);
        serverWeightMap.put("127.0.0.3",5);
        serverWeightMap.put("127.0.0.4",1);
        serverWeightMap.put("127.0.0.5",1);
        serverWeightMap.put("127.0.0.6",1);
    }
    public static Integer pos = 0;
    public static void main(String[] args) {
        String server = "";
        //轮询法
        server = polling();
        server = random();
        server = ipHash("127.0.0.1");
        server = weightedPolling();
        server = weightedRandom();
        server = leastConnection();
        System.out.println(server);
    }

    //轮询法
    private static String polling(){
        //重新创建一个map，避免出现由于服务器上线与下线造成的并发问题
        Map<String,Integer> serverMap = new HashMap<>();
        serverMap.putAll(serverWeightMap);
        //获取IP地址list
        Set<String> keySet = serverMap.keySet();
        ArrayList<String> keyList = new ArrayList<>();
        keyList.addAll(keySet);

        String server = null;
        synchronized (pos){
            if (pos >= keySet.size()){
                pos = 0;
            }
            server = keyList.get(pos);
            pos++;
        }
        return server;
    }
    //随机法
    private static String random(){
        //重新创建一个map，避免出现由于服务器上线与下线造成的并发问题
        Map<String,Integer> serverMap = new HashMap<>();
        serverMap.putAll(serverWeightMap);
        //获取IP地址list
        Set<String> keySet = serverMap.keySet();
        ArrayList<String> keyList = new ArrayList<>();
        keyList.addAll(keySet);

        Random random = new Random();
        int randomPos = random.nextInt(keySet.size());
        String server = keyList.get(randomPos);
        return server;
    }
    //源地址哈希法
    private static String ipHash(String ip){
        //重新创建一个map，避免出现由于服务器上线与下线造成的并发问题
        Map<String,Integer> serverMap = new HashMap<>();
        serverMap.putAll(serverWeightMap);
        //获取IP地址list
        Set<String> keySet = serverMap.keySet();
        ArrayList<String> keyList = new ArrayList<>();
        keyList.addAll(keySet);

        int hashCode = ip.hashCode();
        int serverPos = hashCode%keySet.size();//keyset 不为null
        String server = keyList.get(serverPos);
        return server;
    }
    //加权轮询法
    private static String weightedPolling(){
        //重新创建一个map，避免出现由于服务器上线与下线造成的并发问题
        Map<String,Integer> serverMap = new HashMap<>();
        serverMap.putAll(serverWeightMap);
        //获取IP地址list
        Set<String> keySet = serverMap.keySet();
        Iterator<String> it = keySet.iterator();
        ArrayList<String> keyList = new ArrayList<>();
        String server = null;
        while (it.hasNext()){
            server = it.next();
            Integer weight = serverMap.get(server);
            for (int i = 0 ; i < weight ; i++){
                keyList.add(server);
            }
        }
        server = null;
        synchronized (pos){
            if (pos >= keySet.size()){
                pos = 0;
            }
            server = keyList.get(pos);
            pos++;
        }
        return server;
    }
    //加权随机法
    private static String weightedRandom(){
        //重新创建一个map，避免出现由于服务器上线与下线造成的并发问题
        Map<String,Integer> serverMap = new HashMap<>();
        serverMap.putAll(serverWeightMap);
        //获取IP地址list
        Set<String> keySet = serverMap.keySet();
        Iterator<String> it = keySet.iterator();
        ArrayList<String> keyList = new ArrayList<>();
        String server = null;
        while (it.hasNext()){
            server = it.next();
            Integer weight = serverMap.get(server);
            for (int i = 0 ; i < weight ; i++){
                keyList.add(server);
            }
        }
        Random random = new Random();
        int randomPos = random.nextInt(keyList.size());
        server = keyList.get(randomPos);
        return server;
    }
    //最小连接法,将权重作为连接数在该方法中使用
    private static String leastConnection(){
        //重新创建一个map，避免出现由于服务器上线与下线造成的并发问题
        Map<String,Integer> serverMap = new HashMap<>();
        serverMap.putAll(serverWeightMap);

        String server = null;
        int minConnections = -1;
        for (String key : serverMap.keySet()){
            if (serverMap.get(key)<minConnections){
                minConnections = serverMap.get(key);
                server = key;
            }
        }
        serverMap.put(server,minConnections);
        serverWeightMap.put(server,minConnections);
        return server;
    }
}