Java教程

初探负载均衡算法【随机、轮询、加权随机、加权轮询、平滑加权轮询】

本文主要是介绍初探负载均衡算法【随机、轮询、加权随机、加权轮询、平滑加权轮询】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

简介

负载平衡(Load balancing)是一种在多个计算机(网络、CPU、磁盘)之间均匀分配资源,以提高资源利用的技术。使用负载均衡可以最大化服务吞吐量,可能最小化响应时间,同时由于使用负载均衡时,会使用多个服务器节点代单点服务,也提高了服务的可用性。

负载均衡的实现可以软件可以硬件,硬件如大名鼎鼎的 F5 负载均衡设备,软件如 NGINX 中的负载均衡实现,又如 Springcloud Ribbon 组件中的负载均衡实现。本文主要从软件层面来说明其实现算法。

负载均衡算法主要分为以下6大类:

  • 随机
  • 轮询
  • 加权随机
  • 加权轮询
  • 一致性哈希
  • 平滑加权轮询
    在这里插入图片描述

代码示例:
先把三台服务器放在集合中去:

//服务器IP
public class ServerIps {
	//不带权重的三台服务器,用List存储
    public static final List<String> LIST = Arrays.asList(
            "A",
            "B",
            "C"
    );
    //带权重,用于加权xx算法
    public static final Map<String,Integer> WEIGHT_LIST = new LinkedHashMap<String, Integer>();
    static {
        WEIGHT_LIST.put("A",2);
        WEIGHT_LIST.put("B",3);
        WEIGHT_LIST.put("C",5);
    }
}

随机访问

很简单,对三台服务器随机抽取一个进行访问即可。

//随机
public class RandomSelect {
    public static String getServer() {
        Random random = new Random();
        int rand = random.nextInt(ServerIps.LIST.size());
        return ServerIps.LIST.get(rand);
    }
}

轮询算法

也很简单,每次按照顺序依次对服务器进行访问即可,用一个pos指针来记录轮询的位置。

//轮询
public class RoundRobin {
    //位置
    public static Integer pos = 0;
    public static String getServer() {
        String ip = null;
        synchronized (pos) {
            if(pos >= ServerIps.LIST.size()) {
                pos = 0;
            } else {
                ip = ServerIps.LIST.get(pos);
                pos++;
            }
        }
        return ip;
    }
}

加权轮询

在前面ServerIps类的带权重的服务器定义中,每个服务器A、B、C被储存在一个WEIGHT_LIST中,并分别带有权重2、3、5,意思就是服务器C访问的次数可以相对最大…,前面我们的轮询算法中,遍历的集合是A、B、C组成的,现在无非是放入2个A,3个B,5个C即可,如下图所示:
在这里插入图片描述
相当于,10次请求里面有2次是去访问A,3次去访问B,5次去访问C,这样就实现了加权轮询的功能。

加权随机

和加权轮询类似,依旧是按照权重把List集合中放满服务器元素,再去随机取即可,无非是取每个服务器的概率不是均等的罢了。

//缺点 权重大 ips越大 占内存 带权重随机
public class WeightRandom {
    public static String getServer() {
        //生成随机数作为List下标
        List<String> ips = new ArrayList<>();

        for (String ip: ServerIps.WEIGHT_LIST.keySet()) {
            Integer weight = ServerIps.WEIGHT_LIST.get(ip);
            //weight多少 在ips里面存多少 例 A 权重为2 在ips里面存两个
            for (int i = 0; i < weight ; i++) {
                ips.add(ip);
            }
        }
        Random random = new Random();
        int randomPos = random.nextInt(ips.size());
        return ips.get(randomPos);
    }
}

加权轮询优化

前面讲了加权轮询的实现很容易,无非是按照权重数量把服务器放进集合中,但是如果有一万个服务器呢,一百万个服务器呢?那我们还这样去装集合然后遍历,其实是很浪费资源的!
这里看另一种优化加权轮询的算法:这里总共是10的权重,我们的三台服务器的权重分别是2、3、5,那么我们的10次请求就应该按照比例分配到这三台服务器上,如下图所示:
在这里插入图片描述
这里能发现一个规律,如果请求次数小于该权重,就会放到该权重下,比如我第0次、第1次请求都小于2,所以都击中了第一台服务器。
简单来说:如果请求的次数小于某权重,就可以放到该权重中来,如果不小于,则继续往后找

代码:

//轮询优化
public class WeightRoundRobin {
    public static String getServer(Integer num) {

        int totalWeights = ServerIps.WEIGHT_LIST.values().stream().mapToInt(w -> w).sum();
		//把请求对总权重和取模,就落在0到9之间
        Integer pos = num % totalWeights;

        for(String ip: ServerIps.WEIGHT_LIST.keySet()) {
            Integer weight = ServerIps.WEIGHT_LIST.get(ip);
            if(pos < weight) {
                return ip;//如果小于该权重,直接返回该服务器(击中)
            }
            pos = pos - weight;//如果不小于,继续往后看哪个权重满足
        }

        return "";
    }
    public static void main(String[] args) {
        for (int i=0 ; i<10 ; i++) {
            System.out.println(getServer(i));
        }
    }
}

加权轮询、加权随机都是基于这种方式进行实现的,它解决了List放重复数据的问题,但是也有一个缺陷,就是如果某台服务器的权重很大的时候,那么在一段时间内就会一直击中它,服务器压力也很大,我们希望将请求尽可能的打散会好一点,所以就提出了平滑加权轮询算法。

平滑加权轮询算法

在这里插入图片描述
简单来说就是通过数学公式,在保证每次权重和不变的前提下,使用动态变化权重去更新每一次的权重,是的击中服务器更加分散,但是整体的权重又是满足初始化定义的。

public class WeightRoundRobinV2 {
	//初始化动态权重
    public static Map<String,Weight> currWeights = new HashMap<>();

    public static String getServer() {

        int totalWeights = ServerIps.WEIGHT_LIST.values().stream().mapToInt(w -> w).sum();

        //currentWeight 默认值 0
        if(currWeights.isEmpty()) {
            ServerIps.WEIGHT_LIST.forEach((ip,weight)->
            {
                currWeights.put(ip,new Weight(ip,weight,0));
            });
        }

        for(Weight weight: currWeights.values()) {
            weight.setCurrentWeight(weight.getCurrentWeight() + weight.getWeight());
        }

        //找最大值
        Weight maxCurrentWeight = null;
        for(Weight weight: currWeights.values()) {
            if(maxCurrentWeight == null || weight.getCurrentWeight() > maxCurrentWeight.getCurrentWeight()) {
                maxCurrentWeight = weight;
            }
        }

        maxCurrentWeight.setCurrentWeight( maxCurrentWeight.getCurrentWeight() - totalWeights);

        return maxCurrentWeight.getIp();
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(getServer());
        }
    }
}

在这里插入图片描述
整体来看,C有5个,B有3个,A有2个,和我们初始化定义的权重是一致的,只不过访问更加随机了,这样服务器的压力就变得更小了。

这篇关于初探负载均衡算法【随机、轮询、加权随机、加权轮询、平滑加权轮询】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!