随机和加权随机算法

1 基础

1.1 随机算法

概念：将请求随机分发到候选服务器

使用场景：请求调用量大的情况较为适用，调用量越大，负载越均衡；调用量越小，容易出现热点

代码实现：ThreadLocalRandom.current().nextInt(随机数)

优点：简单易用，通用性强，容易实现

缺点：不考虑服务器实时负载，存在累积请求的问题

1.2 加权随机算法

概念：为每个服务器分配一个权重值，根据权重比例进行随机访问

使用场景：服务器资源分配不均衡，后端服务器硬件配置，性能存在差异

代码实现：Next Page

优点：资源优化，易于实现，灵活性

缺点：不考虑服务器实时负载，可能造成服务阻塞

实现思路

1.收集可用服务器列表。2.确定权重。3.生成随机数。4.选择服务器。5.处理重复选择。6.错误提示

伪代码实现：

package edu.algorithm.loadbalance;

import edu.algorithm.entity.Server;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ThreadLocalRandom;

public class RandomLoadBalance {

    private boolean needWeightLoadBalance = false;

    protected int getWeight(Server server){
        int weight;
        return Math.max(weight = server.getWeight() > 0 ? server.getWeight() : 100, 0);
    }

    public Server select(List<Server> serverList){
        int length = serverList.size();
        if(!needWeightLoadBalance){
             return serverList.get(ThreadLocalRandom.current().nextInt(length));
        }else {
            boolean sameWeight = true;
            int[] weights = new int[length];
            int totalWeight = 0;

            int offset;
            int i;
            for(offset = 0; offset < length; ++offset) {
                i = this.getWeight(serverList.get(offset));
                totalWeight += i;
                weights[offset] = totalWeight;
                // 目的是为了算出整个列表里的权重是存在差异的
                // 通过 总权重 是否等于 当前权重 * index 去校验是否存在差异
                if (sameWeight && totalWeight != i * (offset + 1)) {
                    sameWeight = false;
                }
            }
            if(totalWeight > 0 && !sameWeight){
                // 计算权重综合sum，在1和sum 之间选择一个offset。
                offset = ThreadLocalRandom.current().nextInt(totalWeight);
                // 遍历整个权重list，如果遇到大于 offset 就选择该项
                for(i = 0; i < length; ++i) {
                    if (offset < weights[i]) {
                        return  serverList.get(i);
                    }
                }
            }
            return serverList.get(ThreadLocalRandom.current().nextInt(length));
        }
    }

    public static void main(String[] args) throws InterruptedException {
        List<Server> serverList = new ArrayList<>();
        serverList.add(new Server(1,"服务器1","8080","192.168.2.2",80));
        serverList.add(new Server(2,"服务器2","8080","192.168.2.5",30));
        serverList.add(new Server(3,"服务器3","8080","192.168.2.8",40));
        serverList.add(new Server(4,"服务器4","8080","192.168.3.2",10));
        serverList.add(new Server(5,"服务器5","8080","192.168.3.5",89));
        serverList.add(new Server(6,"服务器6","8080","192.168.3.8",60));

        RandomLoadBalance loadBalance = new RandomLoadBalance();
        loadBalance.needWeightLoadBalance = true;
        Server server = loadBalance.select(serverList);
        System.out.println(server.toString());
    }
}