发表更新架构设计 / 负载均衡设计24 分钟读完 (大约3626个字)

负载均衡算法及实现

负载均衡（Load Balance）：指将负载（工作任务）进行均衡，分摊到多个处理节点上。负载均衡是一个统一的流量入口节点，映射了多个处理请求的映节点，入口节点将请求任务分发到不同的处理节点，实现分治。

互联网应用服务为了能满足大流量请求处理，通常会集群部署，使用负载均衡来分担单台服务器的压力，避免单点故障。

负载均衡

负载均衡方案大致可分为 软件负载均衡 和 硬件负载均衡 两类。

软件负载均衡：基于软件的重定向或反向代理功能实现，属于应用层的负载均衡，如 Nginx 的反向代理。

硬件负载均衡：直接在内部服务器和外部网络间安装硬件负载均衡设备（负载均衡器），直接解析修改数据报中的目的地址，属于网络层的负载均衡，例如 F5负载均衡器。

本篇主要描述软件负载均衡。

负载均衡算法

现有的负载均衡算法主要分为静态负载均衡和动态负载均衡两类。

静态负载均衡算法：以固定的概率分配任务，不考虑服务器的状态信息，如轮转算法、加权轮转算法等。

动态负载均衡算法：以服务器的实时负载状态信息来决定任务的分配，如最小连接法、加权最小连接法等。

静态负载均衡

随机算法

随机法

随机选择一台服务器来分配任务。借助随机函数来最大保证请求的分散性达到均衡的目的。

随机法是没有状态的，不需要维持上次的选择状态和均衡因子。但是随着任务量的增大，效果趋向轮询算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LBRandom {

    public static void main(String[] args) {
        List<String> serverList = new ArrayList<>();
        serverList.add("192.168.1.1");
        serverList.add("192.168.1.2");
        serverList.add("192.168.1.3");

        Random random = new Random();
        for (int i = 0; i < 8; i++) {
            //生成随机数做为索引获取目标
            int index = random.nextInt(serverList.size());
            String serverIP = serverList.get(index);
            System.out.println(serverIP);
        }
    }
}

加权随机法

加权随机法是给每个服务器增加一个加权分属性，按照加权比重随机请求后端服务器。分配到权重大的服务器概率大些，分配到权重小的服务器概率小些。

  1. 方案一：按加权分重建一个 serverList

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    public class LBRandomWeight {

        public static void main(String[] args) {
            Map<String, Integer> serverMap = new HashMap<>();
            serverMap.put("192.168.1.1", 1);
            serverMap.put("192.168.1.2", 3);
            serverMap.put("192.168.1.3", 5);

            // 取得Ip地址List
            Set<String> keySet = serverMap.keySet();
            Iterator<String> iterator = keySet.iterator();
            // 根据加权分重新装配服务器
            List<String> serverList = new ArrayList<>();
            while (iterator.hasNext()) {
                String server = iterator.next();
                int weight = serverMap.get(server);
                for (int i = 0; i < weight; i++){
                    serverList.add(server);
                }
            }

            Random random = new Random();
            for (int i = 0; i < 20; i++) {
                int index = random.nextInt(serverList.size());
                String server = serverList.get(index);
                System.out.println(server);
            }
        }
    }

  2. 方案二：按权重比率分配

    假如 A 服务器权重为 2，B 服务器权重为 6，C 服务器权重为 10，则总权重为 18，

    A的权重值有（1，2），B的权重值有（3，4，5，6，7，8），C的权重值有（9，10，11，12，13，14，15，16，17，18）

    1
    2
    3
    4
    5
    权重比率区间如下：

       2              6                       10
    --------|--------------------|--------------------------------------|
    1 - 2   |       3  - 8       |           9 - 18                     |

    如果生成随机数为 2，2 = 2 落在 A 服务器。

    如果生成随机数为 8，8 > 2 不在 A 服务器，(8-2) = 6 落在B服务器。

    如果生成随机数为 9，9 >２不在Ａ服务器，(9-2) > 6，不在 B服务器，(9 - 6) < 10，落在 C服务器。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    public class LBRandomWeight1 {

        public static void main(String[] args) {

            Map<String, Integer> serverMap = new HashMap<>();
            serverMap.put("192.168.1.1", 2);
            serverMap.put("192.168.1.2", 6);
            serverMap.put("192.168.1.3", 10);
            int sumScore = serverMap.values().stream().mapToInt(score -> score).sum();
            Random random = new Random();

            for (int i = 0; i < 10; i++) {
                String server = serverKey(serverMap, random, sumScore);
                System.out.println(server);
            }
        }

        private static String serverKey(Map<String, Integer> serverMap, Random random, int sumScore) {
            int score = random.nextInt(sumScore);
            for (Map.Entry<String, Integer> entry : serverMap.entrySet()) {
                if (entry.getValue() >= score) {
                    return entry.getKey();
                }
                score = score - entry.getValue();
            }
            return "";
        }
    }

轮询算法

轮询法

轮询法：请求轮流分配给服务器。这种算法比较简单，具有绝对均衡的优点，但也存在较大的缺陷，例如它无法保证分配任务的合理性，无法根据服务器承受能力来分配任务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LBPolling {

    private static AtomicInteger index = new AtomicInteger();

    public static void main(String[] args) {
        List<String> serverList = new ArrayList<>();
        serverList.add("192.168.1.1");
        serverList.add("192.168.1.2");
        serverList.add("192.168.1.3");

        for (int i = 0; i < 10; i++) {

            if(index.get() == serverList.size()){
                index.set(0);
            }

            String server = serverList.get(index.get());
            index.set(index.get() + 1);
            System.out.println(server);
        }
    }
}

加权轮询法

给服务器设置加权比重，性能高的给更高的权重，性能低的给低权重。

加权轮询法也存在一定的缺陷，会生成不均匀的实例序列，可能存在权重高的服务器忙的要死，其它服务闲的无事可做。

  1. 方案一：按权重比将服务器IP重新装入到一个新的容器。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    public class LBPollingWeight {

        private static AtomicInteger index = new AtomicInteger();

        public static void main(String[] args) {
            Map<String, Integer> serverMap = new HashMap<>();
            serverMap.put("192.168.1.1", 2);
            serverMap.put("192.168.1.2", 6);
            serverMap.put("192.168.1.3", 10);

            Set<String> keySet = serverMap.keySet();
            Iterator<String> iterator = keySet.iterator();
            List<String> serverList = new ArrayList<>();
            while (iterator.hasNext()) {
                String server = iterator.next();
                int weight = serverMap.get(server);
                for (int i = 0; i < weight; i++) {
                    serverList.add(server);
                }
            }

            for (int i = 0; i < 20; i++) {
                if (index.get() == serverList.size()) {
                    index.set(0);
                }
                String server = serverList.get(index.get());
                index.set(index.get() + 1);

                System.out.println(server);
            }
        }
    }

  2. 方式二：按权重比轮询

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    public class LBPollingWeight {

        private static AtomicInteger index = new AtomicInteger();

        public static void main(String[] args) {

            Map<String, Integer> serverMap = new HashMap<>();
            serverMap.put("192.168.1.1", 2);
            serverMap.put("192.168.1.2", 6);
            serverMap.put("192.168.1.3", 10);

            int allWeight = serverMap.values().stream().mapToInt(score -> score).sum();
            for (int i = 0; i < 20; i++) {
                String server = serverKey(serverMap, allWeight);
                System.out.println(server);
            }
        }

        private static String serverKey(Map<String, Integer> serverMap, int allWeight) {
            int idx = (index.get() + 1) % allWeight;
            for (Map.Entry<String, Integer> entry : serverMap.entrySet()) {
                if (entry.getValue() >= idx) {
                    index.set(index.get() + 1);
                    return entry.getKey();
                }
                idx = idx - entry.getValue();
            }
            return "";
        }
    }

平滑加权轮询

平滑加权轮询是为了弥补轮询法的不足，通过动态计算当前权重并与初始权重比较，选择还没达到权重的服务，使轮询可以交叉执行。

  1. 方案一：动态计算权重占比

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    /**
     * 动态计算权重占比
     */
    public class LBPollingWeight2 {
        private static AtomicInteger index = new AtomicInteger();
        
        public static void main(String[] args) {

            Map<String, Integer> serverMap = new HashMap<>();
            serverMap.put("192.168.1.1", 2);
            serverMap.put("192.168.1.2", 6);
            serverMap.put("192.168.1.3", 10);

            //总权重
            int allWeight = serverMap.values().stream().mapToInt(weight -> weight).sum();
            //初始权重比
            Map<String, Float> initWeightMap = new HashMap<>();
            for (Map.Entry<String, Integer> entry : serverMap.entrySet()) {
                float rate = (float) entry.getValue() / allWeight;
                DecimalFormat df = new DecimalFormat("0.00");//格式化小数
                rate = Float.valueOf(df.format(rate));
                initWeightMap.put(entry.getKey(), rate);
            }

            List<String> serverList = serverMap.keySet().stream().collect(Collectors.toList());
            //当前权重
            Map<String, Integer> currentWeightMap = new ConcurrentHashMap<>();

            for (int i = 0; i < 20; i++) {
                String server = getServer(initWeightMap, serverList, currentWeightMap);
            }
        }

        private static String getServer(Map<String, Float> initWeightMap, List<String> serverList, Map<String, Integer> currentWeightMap) {
            if (index.get() == serverList.size()) {
                index.set(0);
            }

            for (String server : serverList) {
                if (!currentWeightMap.containsKey(server)) {
                    index.set(index.get() + 1);
                    currentWeightMap.put(server, 1);
                    return server;
                } else {
                    int num = currentWeightMap.get(server);
                    int total = currentWeightMap.values().stream().mapToInt(times -> times).sum();
                    float rate = (float) num / total;
                    DecimalFormat df = new DecimalFormat("0.00");//格式化小数
                    rate = Float.valueOf(df.format(rate));
                    if (rate <= initWeightMap.get(server)) {
                        index.set(index.get() + 1);
                        currentWeightMap.put(server, currentWeightMap.get(server) + 1);
                        return server;
                    }
                }

            }
            return null;
        }
    }

  2. 方案二：Nginx 开发者提供的算法，见 phusion / nginx。

    此算法的逻辑看了多遍仍不太好理解，具体实现可参考 负载均衡算法 — 平滑加权轮询，Java 平滑加权轮询算法实现与讲解。

Hash负载均衡

在动态变化的分布式环境中，哈希算法应该满足的几个条件：平衡性、单调性和分散性。

  • 平衡性：是指 Hash 的结果应该平均分配到各个节点，这样从算法上解决了负载均衡问题。
  • 单调性：是指在新增或者删减节点时，不影响系统正常运行。
  • 分散性：是指数据应该分散地存放在分布式集群中的各个节点(节点自己可以有备份)，不必每个节点都存储所有的数据。

源地址Hash

源地址Hash，也称为简单哈希算法， 是根据请求来源的地址，通过哈希函数计算得到一个哈希值，将哈希值与目标服务建立映射关系（例如，哈希值取模运行，运算结果即为目标服务器的索引）。

源地址哈希法进行负载均衡，同一源地址的请求，每次都会映射到同一台服务器（服务器列表或序号不变）。

源地址Hash 算法的实现是比较简单的，可以把多个服务器地址存入列表（List，或 Map），将源地址哈希后计算（例如取模 %）的值作为索引去 List 中取值，或作为 Map 中的 Key 来取 Map 中的值。

源地址Hash 缺点：

  1. 存在热点问题。即由于用户的活跃度不同，可能会有大量的同的活跃用户被哈希到相同的服务器上，造成该服务器特别繁忙，大量的非活跃用户被哈希到相同的服务器上，造成该服务器几乎没有请求，造成请求不均衡。
  2. 源地址 Hash 法实现简单，但伸缩性很差。一旦新增或下线服务器时，源地址Hash再计算后的ID与服务器的映射就失效，直到服务恢复或者服务器列表中去掉该服务器。（服务器数量发生变化，计算后的哈希值就发生变化，获取得目标服务IP也会发生变化）不适用于现代互联网服务器根据业务量动态扩展的需求。

一致性Hash

一致性哈希算法是当前较主流的分布式哈希表协议之一，它对简单哈希算法进行了修正，解决了热点(hotPot)问题，在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系，尽可能满足单调性的要求。

一致性哈希解决了简单哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的动态伸缩等问题。

一个设计良好的分布式系统应该具有良好的单调性，即服务器的添加与移除不会造成大量的哈希重定位，而一致性哈希恰好可以解决这个问题。

一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环，整个哈希空间的取值范围为02的32次方-1。整个空间按顺时针方向组织。02的32次方-1在零点中方向重合。

一致性哈希算法逻辑：

接下来使用如下算法对服务请求进行映射，将服务请求使用哈希算法算出对应的hash值，然后根据hash值的位置沿圆环顺时针查找，第一台遇到的服务器就是所对应的处理请求服务器。当增加一台新的服务器，受影响的数据仅仅是新添加的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其他都不会受到影响。综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性

动态负载均衡

最小连接法

最小连接法，将任务分配给此时具有最小连接数的节点，因此它是动态负载均衡算法。一个节点收到一个任务后连接数就会加1，当节点故障时就将节点权值设置为0，不再给节点分配任务。

最小连接法适用于各个节点处理的性能相似时。任务分发单元会将任务平滑分配给服务器。但当服务器性能差距较大时，就无法达到预期的效果。因为此时连接数并不能准确表明处理能力，连接数小而自身性能很差的服务器可能不及连接数大而自身性能极好的服务器。所以在这个时候就会导致任务无法准确的分配到剩余处理能力强的机器上。

最短响应法

负载均衡器对内部各服务器发出一个探测请求(例如Ping)。然后根据内部各服务器对探测请求的最快响应时间来决定哪一台服务器来响应客户端的服务请求。

此种均衡算法能较好地反映服务器的当前运行状态。但这最快响应时间仅仅指的是负载均衡设备与服务器间的最快响应时间，而不是客户端与服务器间的最快响应时间。

相关参考

  1. 负载均衡
  2. 网络负载均衡
  3. 浅谈负载均衡算法与实现
  4. 高性能负载均衡之算法
  5. 分布式系统常见负载均衡算法
  6. 负载均衡算法的几种常见方案
  7. 关与负载均衡的总结与思考
  8. 一篇吃透负载均衡
  9. F5 常见负载均衡算法详解
  10. Dubbo 的负载均衡策略实现源码
  11. Dubbo 的负载均衡策略官方文档

负载均衡算法及实现

http://blog.gxitsky.com/2019/12/26/ArchitectureDesign-LoadBalance-algorithm-impl/

作者

光星

发布于

2019-12-26

更新于

2022-07-22

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

关注我
×