devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

7种常见的生产级负载均衡算法_无差负载分配

作者：我家自动化 | 2024-07-23 03:26:43

赞

踩

无差负载分配

准备测试数据

  1. package com.example.demo.balance;
  2.  
  3. import java.util.*;
  4.  
  5. /**
  6.  * @author liwenchao
  7.  */
  8. public class ServerIps {
  9.     public static final List<String> LIST = Arrays.asList(
  10.             "192.168.0.1",
  11.             "192.168.0.2",
  12.             "192.168.0.3",
  13.             "192.168.0.4",
  14.             "192.168.0.5",
  15.             "192.168.0.6",
  16.             "192.168.0.7",
  17.             "192.168.0.8",
  18.             "192.168.0.9",
  19.             "192.168.0.10"
  20.     );
  21.  
  22.     public static final Map<String, Integer> WEIGHT_LIST = new HashMap<String, Integer>();
  23.  
  24.     static {
  25.         // 权重之和为50
  26.         WEIGHT_LIST.put("192.168.0.1", 1);
  27.         WEIGHT_LIST.put("192.168.0.2", 8);
  28.         WEIGHT_LIST.put("192.168.0.3", 3);
  29.         WEIGHT_LIST.put("192.168.0.4", 6);
  30.         WEIGHT_LIST.put("192.168.0.5", 5);
  31.         WEIGHT_LIST.put("192.168.0.6", 5);
  32.         WEIGHT_LIST.put("192.168.0.7", 4);
  33.         WEIGHT_LIST.put("192.168.0.8", 7);
  34.         WEIGHT_LIST.put("192.168.0.9", 2);
  35.         WEIGHT_LIST.put("192.168.0.10", 9);
  36.     }
  37.  
  38.     public static final Map<String, Integer> WEIGHT_ROUND_ROBIN_LIST = new HashMap<String, Integer>();
  39.  
  40.     static {
  41.         WEIGHT_ROUND_ROBIN_LIST.put("192.168.0.1", 5);
  42.         WEIGHT_ROUND_ROBIN_LIST.put("192.168.0.2", 1);
  43.         WEIGHT_ROUND_ROBIN_LIST.put("192.168.0.3", 1);
  44.     }
  45.  
  46.     /**
  47.      * 服务器当前的活跃数
  48.      */
  49.     public static final Map<String, Integer> ACTIVITY_LIST = new LinkedHashMap<String, Integer>();
  50.  
  51.     static {
  52.         ACTIVITY_LIST.put("192.168.0.1", 2);
  53.         ACTIVITY_LIST.put("192.168.0.2", 0);
  54.         ACTIVITY_LIST.put("192.168.0.3", 1);
  55.         ACTIVITY_LIST.put("192.168.0.4", 3);
  56.         ACTIVITY_LIST.put("192.168.0.5", 0);
  57.         ACTIVITY_LIST.put("192.168.0.6", 1);
  58.         ACTIVITY_LIST.put("192.168.0.7", 4);
  59.         ACTIVITY_LIST.put("192.168.0.8", 2);
  60.         ACTIVITY_LIST.put("192.168.0.9", 7);
  61.         ACTIVITY_LIST.put("192.168.0.10", 3);
  62.     }
  63. }

1，随机算法-RandomLoadBalance

  1. package com.example.demo.balance;
  2.  
  3. import java.util.Random;
  4.  
  5. /**
  6.  * 随机算法
  7.  *
  8.  * @author liwenchao
  9.  */
  10. public class RandomLoadBalance {
  11.  
  12.     public static String getServer() {
  13.         // 生成一个随机数作为list的下标值
  14.         Random random = new Random();
  15.         int randomPos = random.nextInt(ServerIps.LIST.size());
  16.         return ServerIps.LIST.get(randomPos);
  17.     }
  18.  
  19.     public static void main(String[] args) {
  20.         // 连续调用10次
  21.         for (int i = 0; i < 10; i++) {
  22.             System.out.println(getServer());
  23.         }
  24.     }
  25.  
  26. }

运行结果

192.168.0.8
192.168.0.6
192.168.0.6
192.168.0.6
192.168.0.9
192.168.0.3
192.168.0.9
192.168.0.1
192.168.0.1
192.168.0.3

当调用次数比较少时，Random 产生的随机数可能会比较集中，此时多数请求会落到同一台服务器上，只有在经过多次请求后，才能使调用请求进行“均匀”分配。调用量少这一点并没有什么关系，负载均衡机制不正是为了应对请求量多的情况吗，所以随机算法也是用得比较多的一种算法。

但是，上面的随机算法适用于每天机器的性能差不多的时候，实际上，生产中可能某些机器的性能更高一点，它可以处理更多的请求，所以，我们可以对每台服务器设置一个权重。
在ServerIps类中增加服务器权重对应关系MAP，权重之和为50。

那么现在的随机算法应该要改成权重随机算法，当调用量比较多的时候，服务器使用的分布应该近似对应权重的分布。

2，权重随机算法-RoundRobinLoadBalance

简单的实现思路是，把每个服务器按它所对应的服务器进行复制，具体看代码更加容易理解

  1. package com.example.demo.balance;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Random;
  6.  
  7. /**
  8.  * 权重随机算法
  9.  *
  10.  * @author liwenchao
  11.  */
  12. public class WeightRandomLoadBalance {
  13.  
  14.     public static String getServer() {
  15.         //生成一个随机数作为list的下标值
  16.         List<String> ips = new ArrayList<>();
  17.         for (String ip : ServerIps.WEIGHT_LIST.keySet()) {
  18.             Integer weight = ServerIps.WEIGHT_LIST.get(ip);
  19.             //按权重进行复制
  20.             for (int i = 0; i < weight; i++) {
  21.                 ips.add(ip);
  22.             }
  23.         }
  24.         Random random = new Random();
  25.         int randomPos = random.nextInt(ips.size());
  26.         return ips.get(randomPos);
  27.     }
  28.  
  29.    
  30.     public static void main(String[] args) {
  31.         // 连续调用10次
  32.         for (int i = 0; i < 10; i++) {
  33.             System.out.println(getServer());
  34.         }
  35.     }
  36. }
  37.

执行结果

192.168.0.1
192.168.0.2
192.168.0.3
192.168.0.4
192.168.0.5
192.168.0.6
192.168.0.7
192.168.0.8
192.168.0.9
192.168.0.10
192.168.0.1

这种实现方法在遇到权重之和特别大的时候就会比较消耗内存，因为需要对ip地址进行复制，权重之和越大那么上文中的ips就需要越多的内存，下面介绍另外一种实现思路。
假设我们有一组服务器 servers = [A, B, C]，他们对应的权重为 weights = [5, 3, 2]，权重总和为10。现在把这些权重值平铺在一维坐标值上，[0, 5) 区间属于服务器 A，[5, 8) 区间属于服务器 B，[8, 10) 区间属于服务器 C。接下来通过随机数生成器生成一个范围在 [0, 10) 之间的随机数，然后计算这个随机数会落到哪个区间上。比如数字3会落到服务器 A 对应的区间上，此时返回服务器 A 即可。权重越大的机器，在坐标轴上对应的区间范围就越大，因此随机数生成器生成的数字就会有更大的概率落到此区间内。只要随机数生成器产生的随机数分布性很好，在经过多次选择后，每个服务器被选中的次数比例接近其权重比例。比如，经过一万次选择后，服务器 A 被选中的次数大约为5000次，服务器 B 被选中的次数约为3000次，服务器 C 被选中的次数约为2000次。
假设现在随机数offset=7：

1offset<5 is false，所以不在[0, 5)区间，将offset = offset - 5（offset=2）
2offset<3 is true，所以处于[5, 8)区间，所以应该选用B服务器 实现如下：

  1. package com.example.demo.balance;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Random;
  6.  
  7. /**
  8.  * 权重随机算法
  9.  *
  10.  * @author liwenchao
  11.  */
  12. public class WeightRandomLoadBalance {
  13.  
  14.  
  15.     public static String getServer() {
  16.         int totalWeight = 0;
  17.         //如果所有权重都相等，那么随机一个ip就好了
  18.         boolean sameWeight = true;
  19.         Object[] weights = ServerIps.WEIGHT_LIST.values().toArray();
  20.         for (int i = 0; i < weights.length; i++) {
  21.             Integer weight = (Integer) weights[i];
  22.             totalWeight += weight;
  23.             if (sameWeight && i > 0 && !weight.equals(weights[i - 1])) {
  24.                 sameWeight = false;
  25.             }
  26.         }
  27.         Random random = new Random();
  28.         int randomPos = random.nextInt(totalWeight);
  29.         if (!sameWeight) {
  30.             for (String ip : ServerIps.WEIGHT_LIST.keySet()) {
  31.                 Integer value = ServerIps.WEIGHT_LIST.get(ip);
  32.                 if (randomPos < value) {
  33.                     return ip;
  34.                 }
  35.                 randomPos = randomPos - value;
  36.             }
  37.         }
  38.         return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[new Random().nextInt(ServerIps.WEIGHT_LIST.size())];
  39.     }
  40.  
  41.     public static void main(String[] args) {
  42.         // 连续调用10次
  43.         for (int i = 0; i < 10; i++) {
  44.             System.out.println(getServer());
  45.         }
  46.     }
  47. }

这就是另外一种权重随机算法。

3，轮询算法-RoundRobinLoadBalance

  1. package com.example.demo.balance;
  2.  
  3. import java.util.concurrent.atomic.AtomicInteger;
  4.  
  5. /**
  6.  * @author liwenchao
  7.  */
  8. public class RoundRobinLoadBalance {
  9.  
  10.     /**
  11.      * 当前循环的位置
  12.      */
  13.     private static final AtomicInteger POS = new AtomicInteger(0);
  14.  
  15.     public static String getServer() {
  16.         if (POS.get() >= ServerIps.LIST.size()) {
  17.             POS.set(0);
  18.         }
  19.         return ServerIps.LIST.get(POS.getAndIncrement());
  20.     }
  21.  
  22.     public static void main(String[] args) {
  23.         // 连续调用10次
  24.         for (int i = 0; i < 11; i++) {
  25.             System.out.println(getServer());
  26.         }
  27.     }
  28.  
  29.  
  30. }

执行结果

192.168.0.1
192.168.0.2
192.168.0.3
192.168.0.4
192.168.0.5
192.168.0.6
192.168.0.7
192.168.0.8
192.168.0.9
192.168.0.10
192.168.0.1

这种算法很简单，也很公平，每台服务轮流来进行服务，但是有的机器性能好，所以能者多劳，和随机算法一下，加上权重这个维度之后，其中一种实现方法就是复制法，这里就不演示了，这种复制算法的缺点和随机算法的是一样的，比较消耗内存，那么自然就有其他实现方法。

4，权重轮询算法-WeightRoundRobinLoadBalance

这种算法需要加入一个概念：调用编号，比如第1次调用为1， 第2次调用为2， 第100次调用为100，调用编号是递增的，所以我们可以根据这个调用编号推算出服务器。
假设我们有三台服务器 servers = [A, B, C]，对应的权重为 weights = [ 2, 5, 1], 总权重为8，我们可以理解为有8台“服务器”，这是8台“不具有并发功能”，其中有2台为A，5台为B，1台为C，一次调用过来的时候，需要按顺序访问，比如有10次调用，那么服务器调用顺序为AABBBBBCAA，调用编号会越来越大，而服务器是固定的，所以需要把调用编号“缩小”，这里对调用编号进行取余，除数为总权重和，比如：

1号调用，1%8=1；
2号调用，2%8=2；
3号调用，3%8=3；
8号调用，8%8=0；
9号调用，9%8=1；
100号调用，100%8=4； 我们发现调用编号可以被缩小为0-7之间的8个数字，问题是怎么根据这个8个数字找到对应的服务器呢？和我们随机算法类似，这里也可以把权重想象为一个坐标轴

“0-----2-----7-----8”

1号调用，1%8=1，offset = 1, offset <= 2 is true，取A；
2号调用，2%8=2；offset = 2，offset <= 2 is true, 取A;
3号调用，3%8=3；offset = 3, offset <= 2 is false, offset = offset - 2, offset = 1, offset <= 5，取B
8号调用，8%8=0；offset = 0, 特殊情况，offset = 8，offset <= 2 is false, offset = offset - 2, offset = 6, offset  <= 5 is false, offset = offset - 5, offset = 1, offset <= 1 is true, 取C;
9号调用，9%8=1；// ...
100号调用，100%8=4； //...

  1. package com.example.demo.balance;
  2.  
  3. import java.util.Random;
  4. import java.util.concurrent.atomic.AtomicInteger;
  5.  
  6. /**
  7.  * @author liwenchao
  8.  */
  9. public class WeightRoundRobinLoadBalance {
  10.  
  11.     private static final AtomicInteger POS = new AtomicInteger(0);
  12.  
  13.     public static String getServer() {
  14.         int totalWeight = 0;
  15.         //如果所有权重都相等，那么随机一个ip就好了
  16.         boolean sameWeight = true;
  17.         Object[] weights = ServerIps.WEIGHT_LIST.values().toArray();
  18.         for (int i = 0; i < weights.length; i++) {
  19.             Integer weight = (Integer) weights[i];
  20.             totalWeight += weight;
  21.             if (sameWeight && i > 0 && !weight.equals(weights[i - 1])) {
  22.                 sameWeight = false;
  23.             }
  24.         }
  25.         int sequenceNum = POS.getAndIncrement();
  26.         int offset = sequenceNum % totalWeight;
  27.         offset = offset == 0 ? totalWeight : offset;
  28.         if (!sameWeight) {
  29.             for (String ip : ServerIps.WEIGHT_LIST.keySet()) {
  30.                 Integer weight = ServerIps.WEIGHT_LIST.get(ip);
  31.                 if (offset <= weight) {
  32.                     return ip;
  33.                 }
  34.                 offset = offset - weight;
  35.             }
  36.         }
  37.         if (sequenceNum >= ServerIps.WEIGHT_LIST.size() - 1) {
  38.             POS.set(0);
  39.         }
  40.         return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[sequenceNum];
  41.     }
  42.  
  43.     public static void main(String[] args) {
  44.         // 连续调用11次
  45.         for (int i = 0; i < 12; i++) {
  46.             System.out.println(getServer());
  47.         }
  48.     }
  49.  
  50. }

执行结果

192.168.0.7
192.168.0.2
192.168.0.2
192.168.0.2
192.168.0.2
192.168.0.2
192.168.0.2
192.168.0.2
192.168.0.2
192.168.0.1
192.168.0.4
192.168.0.4

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

我们这里可以改成平滑加权轮询。

5，平滑加权轮询算法-WeightRoundSmoothRobinLoadBalance

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

请求编号

currentWeight 数组 (current_weight += weight)

选择结果(max(currentWeight))

减去权重总和后的currentWeight 数组（max(currentWeight) -= sum(weight))

1

[5, 1, 1]

A

[-2, 1, 1]

2

[3, 2, 2] 

A

[-4, 2, 2]

3

[1, 3, 3]

B

[1, -4, 3]

4

[6, -3, 4]

A

[-1, -3, 4]

5

[4, -2, 5]

C

[4, -2, -2]

6

[9, -1, -1]

A

[2, -1, -1]

7

[7, 0, 0]

A

[0, 0, 0]

如上，经过平滑性处理后，得到的服务器序列为 [A, A, B, A, C, A, A]，相比之前的序列 [A, A, A, A, A, B, C]，分布性要好一些。初始情况下 currentWeight = [0, 0, 0]，第7个请求处理完后，currentWeight 再次变为 [0, 0, 0]。

  1. package com.example.demo.balance;
  2.  
  3. /**
  4.  * 增加一个Weight类，用来保存ip, weight（固定不变的原始权重）, currentWeight（当前会变化的权重）
  5.  */
  6. public class Weight {
  7.  
  8.     private String ip;
  9.     private Integer weight;
  10.     private Integer currentWeight;
  11.  
  12.     public Weight(String ip, Integer weight, Integer currentWeight) {
  13.         this.ip = ip;
  14.         this.weight = weight;
  15.         this.currentWeight = currentWeight;
  16.     }
  17.  
  18.     public String getIp() {
  19.         return ip;
  20.     }
  21.  
  22.     public void setIp(String ip) {
  23.         this.ip = ip;
  24.     }
  25.  
  26.     public Integer getWeight() {
  27.         return weight;
  28.     }
  29.  
  30.     public void setWeight(Integer weight) {
  31.         this.weight = weight;
  32.     }
  33.  
  34.     public Integer getCurrentWeight() {
  35.         return currentWeight;
  36.     }
  37.  
  38.     public void setCurrentWeight(Integer currentWeight) {
  39.         this.currentWeight = currentWeight;
  40.     }
  41. }
  1. package com.example.demo.balance;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author liwenchao
  8.  */
  9. public class WeightRoundSmoothRobinLoadBalance {
  10.  
  11.     private static Map<String, Weight> weightMap = new HashMap<>();
  12.  
  13.     public static String getServer() {
  14.         int totalWeight = ServerIps.WEIGHT_ROUND_ROBIN_LIST.values().stream().reduce(0, Integer::sum);
  15.         //初始化weightMap，初始时将currentWeight赋值为weight
  16.         if (weightMap.isEmpty()) {
  17.             ServerIps.WEIGHT_ROUND_ROBIN_LIST.forEach((key, value) -> {
  18.                 weightMap.put(key, new Weight(key, value, value));
  19.             });
  20.         }
  21.         // 找出currentWeight最大值
  22.         Weight maxCurrentWeight = null;
  23.         for (Weight weight : weightMap.values()) {
  24.             if (maxCurrentWeight == null || weight.getCurrentWeight() > maxCurrentWeight.getCurrentWeight()) {
  25.                 maxCurrentWeight = weight;
  26.             }
  27.         }
  28.         // 将maxCurrentWeight减去总权重和
  29.         maxCurrentWeight.setCurrentWeight(maxCurrentWeight.getCurrentWeight() - totalWeight);
  30.         // 所有的ip的currentWeight统一加上原始权重
  31.         for (Weight weight : weightMap.values()) {
  32.             weight.setCurrentWeight(weight.getCurrentWeight() + weight.getWeight());
  33.         }
  34.         // 返回maxCurrentWeight所对应的ip
  35.         return maxCurrentWeight.getIp();
  36.     }
  37.  
  38.     public static void main(String[] args) {
  39.         // 连续调用10次
  40.         for (int i = 0; i < 10; i++) {
  41.             System.out.println(getServer());
  42.         }
  43.     }
  44.  
  45. }

执行结果

192.168.0.1
192.168.0.1
192.168.0.2
192.168.0.1
192.168.0.3
192.168.0.1
192.168.0.1
192.168.0.1
192.168.0.1
192.168.0.2

这就是轮询算法，一个循环很简单，但是真正在实际运用的过程中需要思考更多。

6，一致性哈希算法-ConsistentHashLoadBalance

服务器集群接收到一次请求调用时，可以根据根据请求的信息，比如客户端的ip地址，或请求路径与请求参数等信息进行哈希，可以得出一个哈希值，特点是对于相同的ip地址，或请求路径和请求参数哈希出来的值是一样的，只要能再增加一个算法，能够把这个哈希值映射成一个服务端ip地址，就可以使相同的请求（相同的ip地址，或请求路径和请求参数）落到同一服务器上。
因为客户端发起的请求情况是无穷无尽的（客户端地址不同，请求参数不同等等），所以对于的哈希值也是无穷大的，所以我们不可能把所有的哈希值都进行映射到服务端ip上，所以这里需要用到哈希环。如下图：

●哈希值如果需要ip1和ip2之间的，则应该选择ip2作为结果；
●哈希值如果需要ip2和ip3之间的，则应该选择ip3作为结果；
●哈希值如果需要ip3和ip4之间的，则应该选择ip4作为结果；
●哈希值如果需要ip4和ip1之间的，则应该选择ip1作为结果；

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

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

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

 这个彩环也是“公平的”，并且只有ip1,2,3,4是实际的服务器ip，其他的都是虚拟ip。 那么我们怎么来实现呢？ 对于我们的服务端ip地址，我们肯定知道总共有多少个，需要多少个虚拟节点也有我们自己控制，虚拟节点越多则流量越均衡，另外哈希算法也是很关键的，哈希算法越散列流量也将越均衡。 实现：

  1. package com.example.demo.balance;
  2.  
  3. import java.util.SortedMap;
  4. import java.util.TreeMap;
  5.  
  6. /**
  7.  * 一致性哈希算法
  8.  *
  9.  * @author liwenchao
  10.  */
  11. public class ConsistentHashLoadBalance {
  12.  
  13.     private static final SortedMap<Integer, String> INTEGER_STRING_TREE_MAP = new TreeMap<>();
  14.  
  15.     /**
  16.      * 虚拟节点个数
  17.      */
  18.     private static final int VIRTUAL_NODES = 160;
  19.  
  20.     static {
  21.         //对每个真实节点添加虚拟节点，虚拟节点会根据哈希算法进行散列
  22.         for (String ip : ServerIps.LIST) {
  23.             for (int i = 0; i < VIRTUAL_NODES; i++) {
  24.                 int hash = getHash(ip + "VN" + i);
  25.                 INTEGER_STRING_TREE_MAP.put(hash, ip);
  26.             }
  27.         }
  28.     }
  29.  
  30.     private static String getServer(String client) {
  31.         int hash = getHash(client);
  32.         //得到大于该Hash值的排好序的Map
  33.         SortedMap<Integer, String> subMap = INTEGER_STRING_TREE_MAP.tailMap(hash);
  34.         //大于该hash值的第一个元素的位置
  35.         Integer nodeIndex = subMap.firstKey();
  36.         //如果不存在大于该hash值的元素，则返回根节点
  37.         if (nodeIndex == null) {
  38.             nodeIndex = INTEGER_STRING_TREE_MAP.firstKey();
  39.         }
  40.         // 返回对应的虚拟节点名称
  41.         return subMap.get(nodeIndex);
  42.     }
  43.  
  44.     private static int getHash(String str) {
  45.         final int p = 16777619;
  46.         int hash = (int) 2166136261L;
  47.         for (int i = 0; i < str.length(); i++) {
  48.             hash = (hash ^ str.charAt(i)) * p;
  49.         }
  50.         hash += hash << 13;
  51.         hash ^= hash >> 7;
  52.         hash += hash << 3;
  53.         hash ^= hash >> 17;
  54.         hash += hash << 5;
  55.         // 如果算出来的值为负数则取其绝对值
  56.         if (hash < 0) {
  57.             hash = Math.abs(hash);
  58.         }
  59.         return hash;
  60.     }
  61.  
  62.     public static void main(String[] args) {
  63.         // 连续调用10次,随机10个client
  64.         for (int i = 0; i < 10; i++) {
  65.             System.out.println(getServer("client" + i));
  66.         }
  67.     }
  68.  
  69.  
  70. }

执行结果

192.168.0.9
192.168.0.9
192.168.0.6
192.168.0.5
192.168.0.10
192.168.0.3
192.168.0.4
192.168.0.5
192.168.0.5
192.168.0.8

7，最小活跃数算法-LeastActiveLoadBalance

前面几种方法主要目标是使服务端分配到的调用次数尽量均衡，但是实际情况是这样吗？调用次数相同，服务器的负载就均衡吗？当然不是，这里还要考虑每次调用的时间，而最小活跃数算法则是解决这种问题的。
活跃调用数越小，表明该服务提供者效率越高，单位时间内可处理更多的请求。此时应优先将请求分配给该服务提供者。在具体实现中，每个服务提供者对应一个活跃数。初始情况下，所有服务提供者活跃数均为0。每收到一个请求，活跃数加1，完成请求后则将活跃数减1。在服务运行一段时间后，性能好的服务提供者处理请求的速度更快，因此活跃数下降的也越快，此时这样的服务提供者能够优先获取到新的服务请求、这就是最小活跃数负载均衡算法的基本思想。除了最小活跃数，最小活跃数算法在实现上还引入了权重值。所以准确的来说，最小活跃数算法是基于加权最小活跃数算法实现的。举个例子说明一下，在一个服务提供者集群中，有两个性能优异的服务提供者。某一时刻它们的活跃数相同，则会根据它们的权重去分配请求，权重越大，获取到新请求的概率就越大。如果两个服务提供者权重相同，此时随机选择一个即可。
实现：
因为活跃数是需要服务器请求处理相关逻辑配合的，一次调用开始时活跃数+1，结束是活跃数-1，所以这里就不对这部分逻辑进行模拟了，直接使用一个map来进行模拟。

  1. package com.example.demo.balance;
  2.  
  3. import java.util.*;
  4.  
  5. /**
  6.  * 最小活跃数算法
  7.  *
  8.  * @author liwenchao
  9.  */
  10. public class LeastActiveLoadBalance {
  11.  
  12.     private static String getServer() {
  13.  
  14.         // 找出当前活跃数最小的服务器
  15.         Optional<Integer> minValue = ServerIps.ACTIVITY_LIST.values().stream().min(Comparator.naturalOrder());
  16.         if (minValue.isPresent()) {
  17.             List<String> minActivityIps = new ArrayList<>();
  18.             ServerIps.ACTIVITY_LIST.forEach((ip, activity) -> {
  19.                 if (activity.equals(minValue.get())) {
  20.                     minActivityIps.add(ip);
  21.                 }
  22.             });
  23.             // 最小活跃数的ip有多个，则根据权重来选，权重大的优先
  24.             if (minActivityIps.size() > 1) {
  25.                 // 过滤出对应的ip和权重
  26.                 Map<String, Integer> weightList = new LinkedHashMap<String, Integer>();
  27.                 ServerIps.WEIGHT_LIST.forEach((ip, weight) -> {
  28.                     if (minActivityIps.contains(ip)) {
  29.                         weightList.put(ip, ServerIps.WEIGHT_LIST.get(ip));
  30.                     }
  31.                 });
  32.                 int totalWeight = 0;
  33.                 // 如果所有权重都相等，那么随机一个ip就好了
  34.                 boolean sameWeight = true;
  35.                 Object[] weights = weightList.values().toArray();
  36.                 for (int i = 0; i < weights.length; i++) {
  37.                     Integer weight = (Integer) weights[i];
  38.                     totalWeight += weight;
  39.                     if (sameWeight && i > 0 && !weight.equals(weights[i - 1])) {
  40.                         sameWeight = false;
  41.                     }
  42.                 }
  43.                 Random random = new Random();
  44.                 int randomPos = random.nextInt(totalWeight);
  45.                 if (!sameWeight) {
  46.                     for (String ip : weightList.keySet()) {
  47.                         Integer value = weightList.get(ip);
  48.                         if (randomPos < value) {
  49.                             return ip;
  50.                         }
  51.                         randomPos = randomPos - value;
  52.                     }
  53.                 }
  54.                 return (String) weightList.keySet().toArray()[new Random().nextInt(weightList.size())];
  55.             } else {
  56.                 return minActivityIps.get(0);
  57.             }
  58.         } else {
  59.             return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[new Random().nextInt(ServerIps.WEIGHT_LIST.size())];
  60.         }
  61.     }
  62.  
  63.     public static void main(String[] args) {
  64.         // 连续调用10次,随机10个client
  65.         for (int i = 0; i < 10; i++) {
  66.             System.out.println(getServer());
  67.         }
  68.     }
  69.  
  70. }

这里因为不会对活跃数进行操作，所以结果是固定的（担任在随机权重的时候会随机）。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号