负载均衡算法

负载均衡算法

负载均衡算法说明

• 负载均衡介绍

• 负载均衡，英文名称为Load Balance，指由多台服务器以对称的方式组成一个服务器集合，每台服务器都具有等价的地位，都可以单独对外提供服务而无须其他服务器的辅助。
• 通过某种负载分担技术，将外部发送过来的请求均匀分配到对称结构中的某一台服务器上，而接收到请求的服务器独立地回应客户的请求。
• 负载均衡能够平均分配客户请求到服务器阵列，借此提供快速获取重要数据，解决大量并发访问服务问题，这种集群技术可以用最小的投资获得接近于大型主机的性能。

• 负载均衡方式

软件负载和 硬件负载

• 软件负载均衡

• 常见的负载均衡软件有：nginx，LVS，HAproxy

• 硬件负载均衡

• 常见的负载均硬件件有：Array，F5

• 负载均衡算法

随机算法，加权轮询，一致性hash，最小活跃数算法

负载均衡算法模拟

• 数据支持
• 

（1） 随机算法

1、简单随机算法

这个简单随机算法使用与每天机器的性能差不多的时候，实际上，生产中可能某些机器的性能更高一点，它可以处理更多的情况，所以，我们可以对每台服务器设置一个权重。

2、加权随机算法——V1

这个V1版本的加权随机算法的思路比较简单，每个服务器按它所对应的的权重进行复制。
这种实现方法在遇到权重之和特别大的时候就会比较消耗内存，因为需要对ip地址进行复制，权重之和越大那么上文中的ips就需要越多的内存。

3、加权随机算法——V2

下面，介绍另一种实现思路。
假设有一组服务器servers=[A，B，C]，对应的权重weights=[5，3，2]，权重总和为10。
（1）现在把这些权重平铺在一维坐标上，那么就会有[0，5]区间属于服务器A，[5，8]区间属于服务器B，[8，10]区间属于服务器C。
（2）接下来通过随机数生成一个范围在[0，10]之间的随机数，然后计算该随机数落在哪个区间上即可。

（2） 轮询算法

1、简单轮询算法

这种简单轮询算法，很公平，每台服务器轮流来进行服务，但是有的机器性能好，所以 能者多劳，和随机算法一样，所以，我们可以对每台服务器设置一个权重。

2、加权轮询算法

加权轮询算法：
思想：

1. 例如有服务器servers=[A,B,C]，对应权重weights=[2,5,1]，总权重为8。
2. 我们可以理解为有8台服务器，2台A，5台B，1台C，一次调用过来的时候，需
3. 要按顺序访问，如有10次调用，调用顺序为AABBBBBCAA。

步骤：

1. 因为调用次数会越来越大，而服务器是固定，需要将调用次数“缩小”，取余
2. 将权重值平铺在一维坐标值上：[0,2]为A，[2,7]为B，[7,8]为C
3. 接下来获取该次是第几次请求，需要对总权重做取余运算，获取offset

这种算法有一个缺点：一台服务器的权重特别大的时候，他需要连续的处理请求，但是实际上我们想达到的效果是，对于100次请求，只要有有100*8/50=16次就够了，这16次不一定要连续的访问，比如假设我们有三台服务器servers=[A,B,C]，对应权重weights=[2,5,1]，总权重为7，那么上述这算法的结果是AAAAABC，那么如果能够是这么一个结果呢：AABACAA，把B和C平均插入到5个A中间，这样是比较均衡的。

3、平滑加权轮询算法

那么就引出了平滑加权轮询
思路：

1. 每个服务器对应两个权重，分别为weight和currentWeight。其中weight是固定的，currentWeight会动态调整，初始值为0
2. 当有新的请求进来时，遍历服务器列表，让它的currentWeight加上自身权重，遍历完成后，找到最大的currentWeight。
3. 并将最大的currentWeight减去权重总和，然后返回相应的服务器即可。

假设：
测试数据：

WEIGHT_LIST.put("A", 5);
WEIGHT_LIST.put("B", 1);
WEIGHT_LIST.put("C", 1);

运算过程如下：

| 次数| 当前currentWeight数组 (currentWeight+=weight)| 选择结果max(currentWeight) |减去权重总和后的currentWeight数组 (max(currentWeight)-=sum(weight)) |

如表所示，经过平滑行处理后，得到的服务器序列为[A，A，B，A，C，A，A]，相比之前的序列[A，A，A，A，A，B，C]，分布性要好一些。初始情况下currentWeight=[0，0，0] ，在第7个请求处理完后，currentWeight再次变回[0，0，0]。
你会惊讶的发现在第8次的时候，当前currentWeight数组又变回了[5,1,1] !!!

• 具体代码实现如下图：
• 

（3） 一致性哈希算法

服务器集群接收到一次请求调用时，可以根据请求的信息，比如客户端的ip地址，或请求路径与参数等信息进行哈希，可以得出一个哈希值，特点是对于相同的ip地址，或请求路径和请求参数哈希出来的值是一样，只要能再增加一个算法，能够把这个哈希值映射成一个服务端ip的地址，就可以使相同的请求落到同一服务器上。

因为客户端发起的请求情况是无穷大的，所以对于哈希值也是无穷大的，所以不能把所有的哈希值都进行映射到服务器ip上，所以这里需要用到哈希环。如下图：

上面的情况是比较均匀，如果出现ip4服务器宕机了，那就是这样的了：

会发现ip3和ip1直接的范围是比较大的，会有更多的请求落到ip1上，这是不公平的，解决这个问题需要加入虚拟节点：

其中ip2-1，ip3-1就是虚拟结点，并不能处理节点，而是等同于对应的ip2和ip3服务器。
实际上，这只是处理这种不均衡性的一种思路，实际上就算哈希环本身是均衡的，你也可以增加更多的虚拟节点来使这个环更加平衡，比如：

这个彩环也是公平的，并且只有ip1，ip2，ip3，ip4是实际的服务器ip，其他的都是虚拟ip。
那么我们怎么实现呢？

1. 对于我们的服务器ip地址，我们肯定是知道共有多少个，需要多少个虚拟节点也是我们自己控制，虚拟节点多则流量越均衡，另外哈希算法也是很关键的，哈希算法越散列流量也将越均衡。
2. 这种环，可以使用TreeMap来存储；当一次请求过来，获取该请求的hash值，根据hash值从TreeMap中，拿大于该hash值的子树。
3. 再从得到的子树中，拿第一个元素即可。

• 具体代码实现：
• 

（4） 最小活跃数算法

前面几种方法主要目标是使服务端分配到的调用次数尽量均衡，但是实际情况是这样吗?
调用次数相同，服务器的负载就均衡吗?
当然不是，这里还要考虑每次调用的时间，而最小活跃数算法则是解决这种问题的。

活跃调用数越小，表明该服务提供者效率越高，单位时间内可处理更多的请求。此时应优先将请求分配给该服
务提供者。在具体实现中，每个服务提供者对应一个活跃数。初始情况下，所有服务提供者活跃数均为0。每
收到一个请求，活跃数加1，完成请求后则将活跃数减1。在服务运行一段时间后，性能好的服务提供者处理请
求的速度更快，因此活跃数下降的也越快，此时这样的服务提供者能够优先获取到新的服务请求、这就是最小
活跃数负载均衡算法的基本思想。除了最小活跃数，最小活跃数算法在实现上还引入了权重值。所以准确的来
说，最小活跃数算法是基于加权最小活跃数算法实现的。举个例子说明一下，在-一个服务提供者集群中，有两
个性能优异的服务提供者。某一时刻它们的活跃数相同，则会根据它们的权重去分配请求，权重越大，获取到
新请求的概率就越大。如果两个服务提供者权重相同，此时随机选择一个即可。

实现:
因为活跃数是需要服务器请求处理相关逻辑配合的，- -次调用开始时活跃数+1，结束是活跃数-1， 所以这里就
不对这部分逻辑进行模拟了，直接使用一个map来进行模拟。

• 具体代码实现：

//最小活跃算法
public class LeastActive {
    private static String getServer() {
        //找出当前活跃数最小的服务器
        Optional<Integer> minValue = ServerIps.ACTIVITY_LIST.values().stream().min(Comparator.naturalOrder());
        if (minValue.isPresent()) {
            List<String> minActivityIps = new ArrayList<>();
            ServerIps.ACTIVITY_LIST.forEach((ip, activity) -> {
                if (activity.equals(minValue.get())) {
                    minActivityIps.add(ip);
                }
            });
            //最小活跃数的ip有多个，则根据权重来选，权重大的优先
            if (minActivityIps.size() > 1) {
                //过滤出对应的ip和权重
                Map<String, Integer> weightList = new LinkedHashMap<>();
                ServerIps.WEIGHT_LIST.forEach((ip, weight) -> {
                    if (minActivityIps.contains(ip)) {
                        weightList.put(ip, ServerIps.WEIGHT_LIST.get(ip));
                    }
                });
                int totalWeight = 0;
                boolean sameWeight = true;
                Object[] weights = weightList.values().toArray();
                //计算出总的权重，判断所有权重是否一样
                for (int i = 0; i < weights.length; i++) {
                    Integer weight = (Integer) weights[i];
                    totalWeight += weight;
                    if (sameWeight && i > 0 && !weight.equals(weights[i - 1])) {
                        sameWeight = false;
                    }
                }
                //生成一个在[0,totalWeight]区间内的随机数
                java.util.Random random = new java.util.Random();
                int randomPos = random.nextInt(totalWeight);
                if (!sameWeight) {
                    for (String ip : weightList.keySet()) {
                        Integer weight = weightList.get(ip);
                        if (randomPos < weight) {
                            return ip;
                        }
                        randomPos = randomPos - weight;
                    }
                }
                //如果所有权重都一样，就使用随机算法
                randomPos = random.nextInt(weightList.size());
                return (String) weightList.keySet().toArray()[randomPos];
            } else {
                return minActivityIps.get(0);
            }
        } else {
            java.util.Random random = new java.util.Random();
            int randomPos = random.nextInt(ServerIps.WEIGHT_LIST.size());
            return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[randomPos];
        }
    }
    public static void main(String[] args) {
        for (int i=0; i<10; i++){
            System.out.println(getServer());
        }
    }
}