126-负载均衡算法

深度讲解微服务架构中的负载均衡算法实现
负载均衡算法–平滑加权轮询法

1. Random随机法

1
2
3
4
5
6
7
8
9
10
11
12
13
public class RandomLoadBalance implements LoadBalance {
    private List<String> nodeList;

    public RandomLoadBalance(List<String> nodeList) {
        this.nodeList = nodeList;
    }

    @Override
    public String select() {
        int n = nodeList.size();
        return nodeList.get((int) (Math.random() * n));
    }
}

2. Weight Random权重随机算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class WeightRandomLoadBalance implements LoadBalance {
    private List<String> nodeList;

    public WeightRandomLoadBalance(Map<String, Integer> nodeWeight) {
        nodeList = new ArrayList<>();
        nodeWeight.entrySet().stream().forEach(pair -> {
            String host = pair.getKey();
            for (int i = 0; i < pair.getValue(); i++) {
                nodeList.add(host);
            }
        });
    }

    @Override
    public String select() {
        return nodeList.get((int) (Math.random() * nodeList.size()));
    }
}

3. Round Robin轮询法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class RoundRobinLoadBalance implements LoadBalance{
    private AtomicInteger counter = new AtomicInteger(0);
    private List<String> nodeList;

    public RoundRobinLoadBalance(List<String> nodeList) {
        this.nodeList = nodeList;
    }

    @Override
    public String select() {
        if (counter.get() >= nodeList.size()){
            counter.set(0);
        }
        return nodeList.get(counter.getAndIncrement());
    }
}

4. Weighted Round Robin加权轮询法

https://blog.csdn.net/claram/article/details/90268868

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class WeightedRoundRobinLoadBalance implements LoadBalance {
    private List<String> nodeList;
    private AtomicInteger counter = new AtomicInteger(0);

    public WeightedRoundRobinLoadBalance(Map<String, Integer> nodeWeight) {
        nodeList = new ArrayList<>();
        nodeWeight.entrySet().stream().forEach(pair -> {
            String host = pair.getKey();
            for (int i = 0; i < pair.getValue(); i++) {
                nodeList.add(host);
            }
        });
    }
    
    @Override
    public String select() {
        if (counter.get() >= nodeList.size()) {
            counter.set(0);
        }
        return nodeList.get(counter.getAndIncrement());
    }
}

5. Smooth Weighted Round Robin平滑的加权轮询法

nginx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class SmoothWeightedRoundRobinLoadBalance implements LoadBalance {
    class SmoothWeightedServer {
        String serverName;
        int originWeight, currentWeight;

        public SmoothWeightedServer(String serverName, int originWeight, int currentWeight) {
            this.serverName = serverName;
            this.originWeight = originWeight;
            this.currentWeight = currentWeight;
        }
    }

    List<SmoothWeightedServer> serverList = new ArrayList<>();
    int originWeightSum = 0;

    public SmoothWeightedRoundRobinLoadBalance(Map<String, Integer> map) {
        for (String server : map.keySet()) {
            int w = map.get(server);
            serverList.add(new SmoothWeightedServer(server, w, w));
            this.originWeightSum += w;
        }
    }

    @Override
    public String select() {
        SmoothWeightedServer maxWeightServer = null;
        int maxWeight = 0;

        for (SmoothWeightedServer server : serverList) {
            if (server.currentWeight > maxWeight) {
                maxWeightServer = server;
            }
        }

        maxWeightServer.currentWeight -= originWeightSum;
        for (SmoothWeightedServer server : serverList) {
            server.currentWeight += server.originWeight;
        }
        return maxWeightServer.serverName;
    }
}

6. ConsistentHash一致性哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class ConsistentHashLoadBalance implements LoadBalance {
    private static int virtualCountPerNode = 1000;
    private TreeMap<Long, String> hashHostMap;

    public ConsistentHashLoadBalance(List<String> nodes) {
        this.hashHostMap = new TreeMap<>();
        for (String host : nodes) {
            for (int i = 0; i < virtualCountPerNode; i++) {
                hashHostMap.put(hash(host + "virtualnode" + i), host);
            }
        }
    }

    @Override
    public String select(String client) {
        long clientHash = hash(client);

        Map.Entry<Long, String> entry = hashHostMap.ceilingEntry(clientHash);
        if (entry == null) {
            return hashHostMap.firstEntry().getValue();
        }
        return entry.getValue();
    }

    public long hash(String s) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < s.length(); i++)
            hash = (hash ^ s.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        return Math.abs(hash);
    }
}

7. LeastActive最小活跃数

8. LeastConnected最小连接数