简介

负载平衡（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个，和我们初始化定义的权重是一致的，只不过访问更加随机了，这样服务器的压力就变得更小了。