解密负载均衡技术和负载均衡算法

时间：2022-11-10 12:07:24

负载均衡器是一种软件或硬件设备，它起到了将网络流量分散到一组服务器的作用，可以防止任何一台服务器过载。负载均衡算法就是负载均衡器用来在服务器之间分配网络流量的逻辑（算法是一组预定义的规则），有时候也叫做负载均衡的类型。负载均衡算法的种类非常多，包括从简单的轮询负载均衡算法到基于响应状态信息的自适应负载均衡算法。

负载均衡算法的选择会影响负载分配机制的有效性，从而影响性能和业务连续性（也就是对外承诺的SLA），选择正确的负载均衡算法会对应用程序性能产生重大影响。

本文将会介绍常见的负载均衡算法，并结合主流负载均衡软件或硬件设备介绍各种负载均衡算法的实现方式

常见负载均衡算法介绍

Round Robin（轮询负载均衡算法）

在所有负载均衡算法中，轮询负载均衡算法是最简单的、最常用的负载均衡算法。客户端请求以简单的轮换方式分发到应用程序服务器上。例如，假设有三台应用程序服务器：第一个客户端请求发送到第一台应用程序服务器，第二个客户端请求发送到第二台应用程序服务器，第三个客户端请求发送到第三台应用程序服务器，第四个客户端请求重新从第一台应用程序服务器开始，依次往复。

 

 

轮询负载均衡适合所有客户端请求都需要相同的服务器负载，并且所有的服务器实例都具有相同的服务器容量和资源（比如网络带宽和存储）

Weighted Round Robin（加权轮询负载均衡算法）

加权负载均衡算法与轮询算法相似，增加了根据每个服务器的相对容量来将请求分散到不同服务器的能力。它适合将传入的客户端请求分散到一组具有不同功能或具有不同负载容量的服务器上。服务器集群管理员根据一个标准为每个应用程序服务器分配一个权重，这个标准表示每个服务器对请求的相对处理能力。

例如，如果在其他资源都是无穷多的情况下，假如服务器#1的CPU核心数是服务器#2和服务器#3的CPU核心数的二倍，那么服务器#1的权重更高，而服务器#2和#3的权重相同（都比#1低）。如果我们有4个连续的客户端请求，那么有2次请求发送到#1，另外2次请求分别发送到#2和#3。

加权轮询负载均衡算法描述的是在一段时间内负载的分布情况，不同的加权轮询负载均衡算法可能会产生不同的选择序列，不应该对处理下一次负载的服务器进行假设。

 

 

Least Connections（最少连接负载均衡算法）

最少连接负载均衡算法又叫做最少等待请求算法（Least Outstanding Request, LOR）。最少连接负载均衡是一种动态负载均衡算法，客户端请求被分发到在接收到请求时活动连接数最少的应用服务器。在应用服务器具有类似规格的情况下，一台服务器可能会因为连接数过多而过载（无法接收请求也属于过载），这个算法考虑了活动连接负载。这种技术适合具有不同连接时间的传入请求（多机房）以及一组在处理能力和可用资源方面相对相似的服务器。

Weighted Least Connections（加权最少连接负载均衡算法）

加权最少连接建立在最少连接负载均衡算法上，考虑不同的应用程序服务器特性。与加权轮询负载均衡算法相同，服务器集群管理员根据一个标准为每个应用程序服务器分配一个权重，这个标准表示每个服务器对请求的相对处理能力。负载均衡器根据活动链接和分配的服务器权重做出负载平衡决策（例如，使用连接数乘以权重的倒数，选择值最高的服务器）。

Resource Based（基于资源的负载均衡算法）

基于资源的负载均衡算法又叫做自适应负载均衡算法。基于资源的负载均衡算法根据后端服务器提供的状态指标来做出决策。这个状态指标可以由一个运行在服务器上的自定义应用程序（比如agent），或从基础设施提供方的开放接口获取。负载均衡器定期查询每台服务器的状态指标，然后适当地调整服务器的动态权重。

在这种方式下，负载均衡算法实际上是在每台真实服务器上执行健康检查。这个算法适用于任何需要来自每台服务器的详细健康检查信息来做出负载均衡决策的情况。

例如：此算法适用于工作负载多变且需要详细的应用程序性能和状态来评估服务器运行状态的任何应用程序（例如CPU密集型的最短路径计算，或其他高性能计算场景）。

Fixed Weighting（固定权重负载均衡算法）

固定权重负载均衡算法允许服务器集群管理员根据他们的标准为每个应用程序服务器分配一个权重，以表示每个服务器的相对流量处理能力。权重最高的应用服务器将接收所有流量。如果权重最高的应用服务器出现故障，所有流量将会被引导到下一个权重最高的应用服务器。此方法适用于单个服务器能够处理所有预期传入请求的工作负载，如果当前活动的服务器发生故障，一个或多个“热备用”服务器可以直接用于承担负载。

时间负载均衡算法）

加权响应时间负载均衡算法使用应用程序的响应时间来计算服务器权重。响应速度最快的应用程序服务器接收下一个请求。此方法适用于应用程序响应时间是最重要的问题的场景。

当应用程序提供的是对外开放服务时尤为重要，因为对外开放服务都会为合作伙伴提供服务级别协议（Service Level Argument，SLA），而SLA中承诺的主要就是服务的可用性与服务的响应时间（TP99、TP999等）。

Source IP Hash（源地址哈希负载均衡算法）

源地址哈希负载均衡算法使用客户端请求的源IP与目标IP地址生成唯一的哈希密钥，用于将客户端请求分配给特定的服务器。如果传输层会话中断，可以重新密钥，因此客户端请求将会被定向到它之前使用的统一服务器。当客户端对于每个连续连接始终返回到同一服务器至关重要时，此方法最适用。

服务端研发经常接触的数据库事务就适用于此场景

Consistent Hash（一致性哈希负载均衡算法）

一致性哈希负载均衡算法类似于源地址哈希，不同在于一致性哈希负载均衡算法可以使用任意应用参数组成唯一的哈希密钥，并且当服务器集群发生变化时可以尽可能少地进行数据迁移。

常见负载均衡算法实现

本节将会介绍各种常见负载均衡算法的实现方式，某些负载均衡算法具有多种不同的实现方式，并且每种实现方式都有各自适用的场景，这些不同的实现方式也会在本节进行介绍。同时本节中会假设所有的请求都是线性的，不会处理并发安全相关的细节。

Round Robin（轮询负载均衡算法）

在所有负载均衡算法中，轮询负载均衡算法实现起来最简单，只需要一个变量表示当前位置并不断增加即可。

public class RoundRobinLoadBalancer {

    private final List instances;

    private int position;

    public RoundRobinLoadBalancer(List instances) {
        this.instances = instances;
        this.position = ThreadLocalRandom.current().nextInt(instances.size());
    }

    public ServiceInstance peek(HttpServletRequest request) {
        int peeked = (position++) & Integer.MAX_VALUE;
        return instances.get(peeked % instances.size());
    }
}

 

这里有两个需要注意的点

  1. 当我们初始化位置时，需要将其设置为一个随机值，避免多个负载均衡器同时请求同一个服务器，造成服务器的瞬时压力

  2. Spring Cloud #1074)

Weighted Round Robin（加权轮询负载均衡算法）

加权轮询负载均衡算法有很多主流的实现，并且各自都有各自的优点。虽然加权负载均衡产生任意符合全总分配比例分布的选择序列都是合适的，但在短时间窗口内是否能够选择尽可能多的节点提供服务仍是评价加权负载均衡实现的质量的关键指标。

数组展开方式

数组展开实现方式是一种适用空间换时间的策略，适用于较小的服务器集群或专用型负载均衡设备。它的优点是速度非常快，与Round Robin实现完全一致。它的缺点也很明显，当权重的总和很大时会带来很大的内存开销

public class WeightedLoadBalancer {

    private final List instances;

    private int position;

    public WeightedLoadBalancer(List instances) {
        this.instances = expandByWeight(instances);
    }

    public ServiceInstance peek(HttpServletRequest request) {
        int peeked = (position++) & Integer.MAX_VALUE;
        return instances.get(peeked % instances.size());
    }

    private List expandByWeight(List instances) {
        List newInstances = new ArrayList<>();

        for (ServiceInstance instance : instances) {
            int bound = instance.getWeight();
            for (int w = 0; weight < bound; weight++) {
                newInstances.add(instance);
            }
        }

        Collections.shuffle(newInstances);
        return newInstances;
    }
}

 

这里有三个需要注意的点：

  1. Spring Cloud #1140）

  2. 在实例按权重展开成数组后，需要对得到的数组进行洗牌，以保证流量尽可能均匀，避免连续请求相同实例（Java中实现的洗牌算法是Fisher-Yates算法，其他语言可以自行实现）

  3. 因为是在构建负载均衡器的时候按权重展开成数组的，所以在负载均衡器构建完成后无法再改变实例的权值，对于频繁动态变更权重的场景不适用

上界收敛选择方式

issue #44上分析了这种算法）

 

 解密负载均衡技术和负载均衡算法

 

 解密负载均衡技术和负载均衡算法

 

 

public class WeightedLoadBalancer {

    private final List instances;

    private final int max;

    private final int gcd;

    private int bound;

    private int position;

    public WeightedLoadBalancer(List instances) {
        this.instances = instances;
        this.max = calculateMaxByWeight(instances);
        this.gcd = calculateGcdByWeight(instances);
        this.position = ThreadLocalRandom.current().nextInt(instances.size());
    }

    public ServiceInstance peek(HttpServletRequest request) {
        if (bound == 0) {
            bound = max;
        }

        while (instances.size() > 0) {
            for (int peeked = position; peeked < instances.size(); peeked++) {
                ServiceInstance instance = instances.get(peeked);
                if (instance.getWeight() >= bound) {
                    position = peeked + 1;
                    return instance;
                }
            }
            position = 0;
            bound = bound - gcd;
        }
        return null;
    }

    private static int calculateMaxByWeight(List instances) {
        int max = 0;
        for (ServiceInstance instance : instances) {
            if (instance.getWeight() > max) {
                max = instance.getWeight();
            }
        }
        return max;
    }

    private static int calculateGcdByWeight(List instances) {
        int gcd = 0;
        for (ServiceInstance instance : instances) {
            gcd = gcd(gcd, instance.getWeight());
        }
        return gcd;
    }

    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

 

这里面有四个需要注意的点：

  1. 如果是短频率请求，将会一直访问高权重实例，导致在短时间窗口内负载看起来并不均匀。这个可以通过改变方向，从下界向上界逼近来解决。

  2. 每一轮后降低上界的值可以取所有权重的最大公约数，因为如果每次下降1的话，中间这些轮会反复请求权重最高的那些实例，导致负载不均衡。

  3. 虽然最大公约数可以减少下降次数，但是如果权重相差非常多，并且所有元素都是互质的（n与n+1互质，任意自然数n与1互质，在实践中非常容易出现），那么在上界下降的过程中将会带来很多空转。这个可以参考广度优先遍历的思想，使用先入先出的队列来减少空转。

  4. 与数组展开方式遇到的问题相同，因为是在构建负载均衡器的时候计算最大公约数的值，所以对于频繁动态变更权重的场景依旧会有很大的性能开销，但是相较于数组展开方式可以避免频繁动态分配数组导致的性能与内存碎片问题

权重轮转实现

NGINX）。这种算法的优势是它很平滑，低权重节点的等待时间较短，并且每轮权重轮转的最小正周期很小，是所有服务器实例权重的和。。

在NGINX中又叫做平滑加权负载均衡（Smooth Weighted Load Balancing，SWRR）。

 

 

public class WeightedLoadBalancer {

    private final List instances;

    public WeightedLoadBalancer(List instances) {
        this.instances = instances;
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = null;
        int total = 0;
        for (ServiceInstance instance : instances) {
            total += instance.getWeight();
            instance.setCurrentWeight(instance.getCurrentWeight() + instance.getWeight());
            if (best == null || instance.getCurrentWeight() > best.getCurrentWeight()) {
                best = instance;
            }
        }
        if (best != null) {
            best.setCurrentWeight(best.getCurrentWeight() - total);
        }
        return best;
    }
}

 

这里面有三个需要注意的点：

  1. 权重轮转非常适合实例变化频率非常高的集合，因为它不需要提前构建数据结构

  2. Spring Cloud #1111）

  3. 权重轮转实现需要修改服务器实例的数据结构，当服务实例是由其他机构提供时无法使用此实现

EDF（Earliest Deadline First）实现

EDF算法最早被用在CPU调度上，EDF是抢占式单处理器调度的最佳调度算法。EDF实现与权重轮转实现相似，引入了名为deadline的额外变量，可以认为权重越高的服务器实例完成任务的时间越快，那么在假设所有请求的成本相同时，所需要花费的时间是权重的倒数，所以可以很自然地选择可以最早空闲出来提供服务的服务器实例，并将任务分配给它。

mosn #1920）

public class WeightedLoadBalancer {

    private final PriorityQueue entries;

    public WeightedLoadBalancer(List instances) {
        this.entries = instances.stream().map(EdfEntry::new).collect(Collectors.toCollection(PriorityQueue::new));
    }

    public ServiceInstance peek(HttpServletRequest request) {
        EdfEntry entry = entries.poll();
        if (entry == null) {
            return null;
        }
        ServiceInstance instance = entry.instance;
        entry.deadline = entry.deadline + 1.0 / instance.getWeight();
        entries.add(entry);
        return instance;
    }

    private static class EdfEntry implements Comparable {

        final ServiceInstance instance;

        double deadline;

        EdfEntry(ServiceInstance instance) {
            this.instance = instance;
            this.deadline = 1.0 / instance.getWeight();
        }

        @Override
        public int compareTo(EdfEntry o) {
            return Double.compare(deadline, o.deadline);
        }
    }
}

 

EDF每次选择的算法复杂度为O(log(n))，相较于数组展开要慢，但相较于上界收敛选择在最坏情况下以及权重轮转都需要O(n)的时间复杂度来说，其性能表现的非常好，并且对于超大集群，其性能下降不明显。其空间复杂度为O(n)，不会造成很大的内存开销。

Least Connections（最少连接负载均衡算法）

遍历比较方式

最简单的实现方式，遍历所有实例，并找出当前连接数最少的实例

public class LeastConnectionLoadBalancer {

    private final List instances;

    public LeastConnectionLoadBalancer(List instances) {
        this.instances = instances;
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = null;
        for (ServiceInstance instance : instances) {
            if (best == null || instance.getConnections() < best.getConnections()) {
                best = instance;
            }
        }
        if (best != null) {
            best.setConnections(best.getConnections() + 1);
        }
        return best;
    }
}

 

堆维护方式

所有动态有序集合都可以通过优先队列来实现，与EDF算法相同，取出队首的元素，修改它的优先级，并放回队列中

public class LeastConnectionLoadBalancer {

    private final PriorityQueue instances;

    public LeastConnectionLoadBalancer(List instances) {
        this.instances = instances.stream().collect(toCollection(
                () -> new PriorityQueue<>(comparingInt(ServiceInstance::getConnections))));
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = instances.poll();
        if (best == null) {
            return null;
        }
        best.setConnections(best.getConnections() + 1);
        return best;
    }
}

 

Weighted Least Connections（加权最少连接负载均衡算法）

加权最少连接负载均衡算法的实现方式与最少连接负载均衡算法相同，只是在计算时增加了权重相关的参数

遍历比较方式

public class LeastConnectionLoadBalancer {

    private final List instances;

    public LeastConnectionLoadBalancer(List instances) {
        this.instances = instances;
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = null;
        for (ServiceInstance instance : instances) {
            if (best == null || instance.getConnections() * best.getWeight() < best.getConnections() * instance.getWeight()) {
                best = instance;
            }
        }
        if (best != null) {
            best.setConnections(best.getConnections() + 1);
        }
        return best;
    }
}

 

Tips，在不等式中 a/b < c/d 与 ad < bc等价，并且可以避免除法带来的性能与精度问题

堆维护方式

public class LeastConnectionLoadBalancer {

    private final PriorityQueue instances;

    public LeastConnectionLoadBalancer(List instances) {
        this.instances = instances.stream().collect(toCollection(
                () -> new PriorityQueue<>(comparingDouble(ServiceInstance::getWeightedConnections))));
    }

    public ServiceInstance peek(HttpServletRequest request) {
        ServiceInstance best = instances.poll();
        if (best == null) {
            return null;
        }
        best.setConnections(best.getConnections() + 1);
        best.setWeightedConnections(1.0 * best.getConnections() / best.getWeight());
        return best;
    }
}

 

时间负载均衡算法）

APISIX）。

通过历史的响应时间来得到预测值这个操作通常是CPU开销很大的，实际使用时可以不用遍历所有元素，而是使用K-临近元素或直接随机选择两个元素进行比较即可，这种启发式方法办法无法保证全局最优但是可以保证不至于全局最差。

Source IP Hash（源地址哈希负载均衡算法）

源地址哈希负载均衡以任意算法将请求地址映射成整型数，并将这个整型数映射到实例列表的下标

public class IpHashLoadBalancer {

    private final List instances;

    public IpHashLoadBalancer(List instances) {
        this.instances = instances;
    }

    public ServiceInstance peek(HttpServletRequest request) {
        int h = hashCode(request);
        return instances.get(h % instances.size());
    }

    private int hashCode(HttpServletRequest request) {
        String xForwardedFor = request.getHeader("X-Forwarded-For");
        if (xForwardedFor != null) {
            return xForwardedFor.hashCode();
        } else {
            return request.getRemoteAddr().hashCode();
        }
    }
}

 

这里有一个需要注意的点：

  1. 面向公网提供服务的负载均衡器前面可能会经过任意多层反向代理服务器，为了获取到真实的源地址，需要先获取X-Forwarded-For头部，如果该头部不存在再去获取TCP连接的源地址

负载均衡技术扩展

服务注册表与发现（Service Registry and Service Discovery）

在维护大型服务器集群时，服务器实例随时都有可能被创建或移除，当服务器被创建或移除时，集群管理员需要到各个负载均衡设备上去更新服务器实例列表。

服务注册表会在内部维护服务对应的服务器实例列表。在服务器实例被创建并成功运行服务后，服务器实例会去服务注册表中注册自身，包括网络地址（IPv4/IPv6）、服务端口号、服务协议（TCP/TLS/HTTP/HTTPS）以及自身提供的服务名称等等，有的服务注册表本身也会提供主动健康检查的能力（如Eureka与Consul）。在服务器实例正常退出时会在服务注册表执行反注册逻辑，这个时候服务注册表就会将这个服务器实例从服务器实例列表中移除。即使服务器实例异常退出导致无法执行反注册逻辑，服务注册表也会通过主动健康检查机制将这个异常的服务器实例从服务器实例列表中移除。

在拥有服务注册表后，负载均衡设备不需要再手动维护服务器实例列表，而是当请求到来时从服务注册表中拉取对应的服务器实例列表，并在这个服务器实例列表中进行负载均衡。为了提高服务的可用性，负载均衡设备会在本地（内存或本地文件注册表）缓存这些服务器实例列表，以避免由于负载均衡设备与服务注册表无法连接而导致服务不可用。

Spring Cloud），当服务注册表不可用时，因为负载均衡设备中无可用的服务器备份而导致服务完全不可用；在大部分的负载均衡设备中将缓存获取与更新逻辑改为定时器主动刷新的机制，这样当服务注册表不可用时可以主动决定是否将旧数据标记为过期。尽管本地缓存可以提高服务的可用性，但是要注意负载均衡设备在使用的仍旧是旧的服务提供方列表，当长时间无法获取到新的服务提供方列表时，负载均衡设备应当舍弃旧的服务提供方列表，并将服务不可用的问题暴露出来，通过基础设施提供的监控与告警能力通知集群管理员来进行处理。

健康检查（Health Check）

健康检查本质是一个预定规则，它向负载均衡器背后的服务器集群中的所有成员发送相同的请求，以确定每个成员服务器是否可以接受客户端请求。

对于某些类型的健康检查，通过评估来自服务器的响应以及收到服务器响应所需的时间以确定每个成员服务器的运行状态。通常情况下，当成员服务器的状态变为不健康时，负载均衡器应该快速地将其从服务器实例列表中移除，并在成员服务器状态恢复正常时将其重新添加回服务器实例列表中。

  1. 对于网络层负载均衡器（也叫做NLB或L4LB），通过建立TCP连接，根据是否能够成功建立连接以及建立连接所需要的时间来确定成员服务器的状态。

  2. 对于应用层负载均衡器（也叫做ALB或L7LB），通过发送应用层协议（不只是HTTP协议）定义的用于健康检查的请求报文，并根据响应报文内容以及整个请求从建立连接到完整收到所有响应所花费的时间来确定成员服务器的状态。

RFC 6455）。

慢启动（Slow Start）

Java Developer Guide）。

同时，现代应用程序都不可避免的会使用本地缓存，当应用程序刚刚启动时内存中的缓存是空的，随着应用程序的运行，不断地访问外部系统获取数据并将数据写入到内存缓存中，应用程序与外部系统的交互会不断减少，应用程序的系统承载能力也会逐渐达到峰值。

上面是应用程序在启动后性能不断提升的因素中最常见的，初次之外还有很多的因素。所以为了避免大量请求涌入刚刚启动完成的应用程序的现象发生，负载均衡器会通过慢启动的方式，随着服务器运行不断增加这些服务器实例的权重，最终达到服务器的实际权重，从而达到动态调整分配给这些服务器实例的流量的效果。

envoy slow start）。

总结

负载均衡技术是网络代理与网关组件最核心的组成部分，本文简单介绍了什么是负载均衡技术、常见的负载均衡算法以及常见负载均衡算法的实现，并给出了负载均衡技术的扩展，为将来更深入学习网络代理相关技术打下基础。

因本人才学疏浅经验能力有限，文中难免会有疏忽和遗漏，以及不连贯的地方，欢迎大家与我沟通交流给出建议。

标签：

相关文章