负载均衡器是一种软件或硬件设备，它起到了将网络流量分散到一组服务器的作用，可以防止任何一台服务器过载。负载均衡算法就是负载均衡器用来在服务器之间分配网络流量的逻辑（算法是一组预定义的规则），有时候也叫做负载均衡的类型。负载均衡算法的种类非常多，包括从简单的轮询负载均衡算法到基于响应状态信息的自适应负载均衡算法。
负载均衡算法的选择会影响负载分配机制的有效性，从而影响性能和业务连续性（也就是对外承诺的SLA），选择正确的负载均衡算法会对应用程序性能产生重大影响。
本文将会介绍常见的负载均衡算法，并结合主流负载均衡软件或硬件设备介绍各种负载均衡算法的实现方式
在所有负载均衡算法中，轮询负载均衡算法是最简单的、最常用的负载均衡算法。客户端请求以简单的轮换方式分发到应用程序服务器上。例如，假设有三台应用程序服务器：第一个客户端请求发送到第一台应用程序服务器，第二个客户端请求发送到第二台应用程序服务器，第三个客户端请求发送到第三台应用程序服务器，第四个客户端请求重新从第一台应用程序服务器开始，依次往复。
轮询负载均衡适合所有客户端请求都需要相同的服务器负载，并且所有的服务器实例都具有相同的服务器容量和资源（比如网络带宽和存储）
加权负载均衡算法与轮询算法相似，增加了根据每个服务器的相对容量来将请求分散到不同服务器的能力。它适合将传入的客户端请求分散到一组具有不同功能或具有不同负载容量的服务器上。服务器集群管理员根据一个标准为每个应用程序服务器分配一个权重，这个标准表示每个服务器对请求的相对处理能力。
例如，如果在其他资源都是无穷多的情况下，假如服务器#1的CPU核心数是服务器#2和服务器#3的CPU核心数的二倍，那么服务器#1的权重更高，而服务器#2和#3的权重相同（都比#1低）。如果我们有4个连续的客户端请求，那么有2次请求发送到#1，另外2次请求分别发送到#2和#3。
加权轮询负载均衡算法描述的是在一段时间内负载的分布情况，不同的加权轮询负载均衡算法可能会产生不同的选择序列，不应该对处理下一次负载的服务器进行假设。
最少连接负载均衡算法又叫做最少等待请求算法（Least Outstanding Request, LOR）。最少连接负载均衡是一种动态负载均衡算法，客户端请求被分发到在接收到请求时活动连接数最少的应用服务器。在应用服务器具有类似规格的情况下，一台服务器可能会因为连接数过多而过载（无法接收请求也属于过载），这个算法考虑了活动连接负载。这种技术适合具有不同连接时间的传入请求（多机房）以及一组在处理能力和可用资源方面相对相似的服务器。
加权最少连接建立在最少连接负载均衡算法上，考虑不同的应用程序服务器特性。与加权轮询负载均衡算法相同，服务器集群管理员根据一个标准为每个应用程序服务器分配一个权重，这个标准表示每个服务器对请求的相对处理能力。负载均衡器根据活动链接和分配的服务器权重做出负载平衡决策（例如，使用连接数乘以权重的倒数，选择值最高的服务器）。
基于资源的负载均衡算法又叫做自适应负载均衡算法。基于资源的负载均衡算法根据后端服务器提供的状态指标来做出决策。这个状态指标可以由一个运行在服务器上的自定义应用程序（比如agent），或从基础设施提供方的开放接口获取。负载均衡器定期查询每台服务器的状态指标，然后适当地调整服务器的动态权重。
在这种方式下，负载均衡算法实际上是在每台真实服务器上执行健康检查。这个算法适用于任何需要来自每台服务器的详细健康检查信息来做出负载均衡决策的情况。
例如：此算法适用于工作负载多变且需要详细的应用程序性能和状态来评估服务器运行状态的任何应用程序（例如CPU密集型的最短路径计算，或其他高性能计算场景）。
固定权重负载均衡算法允许服务器集群管理员根据他们的标准为每个应用程序服务器分配一个权重，以表示每个服务器的相对流量处理能力。权重最高的应用服务器将接收所有流量。如果权重最高的应用服务器出现故障，所有流量将会被引导到下一个权重最高的应用服务器。此方法适用于单个服务器能够处理所有预期传入请求的工作负载，如果当前活动的服务器发生故障，一个或多个“热备用”服务器可以直接用于承担负载。
加权响应时间负载均衡算法使用应用程序的响应时间来计算服务器权重。响应速度最快的应用程序服务器接收下一个请求。此方法适用于应用程序响应时间是最重要的问题的场景。
当应用程序提供的是对外开放服务时尤为重要，因为对外开放服务都会为合作伙伴提供服务级别协议（Service Level Argument，SLA），而SLA中承诺的主要就是服务的可用性与服务的响应时间（TP99、TP999等）。
源地址哈希负载均衡算法使用客户端请求的源IP与目标IP地址生成唯一的哈希密钥，用于将客户端请求分配给特定的服务器。如果传输层会话中断，可以重新密钥，因此客户端请求将会被定向到它之前使用的统一服务器。当客户端对于每个连续连接始终返回到同一服务器至关重要时，此方法最适用。
服务端研发经常接触的数据库事务就适用于此场景
一致性哈希负载均衡算法类似于源地址哈希，不同在于一致性哈希负载均衡算法可以使用任意应用参数组成唯一的哈希密钥，并且当服务器集群发生变化时可以尽可能少地进行数据迁移。
本节将会介绍各种常见负载均衡算法的实现方式，某些负载均衡算法具有多种不同的实现方式，并且每种实现方式都有各自适用的场景，这些不同的实现方式也会在本节进行介绍。同时本节中会假设所有的请求都是线性的，不会处理并发安全相关的细节。
在所有负载均衡算法中，轮询负载均衡算法实现起来最简单，只需要一个变量表示当前位置并不断增加即可。
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()); } }
这里有两个需要注意的点
当我们初始化位置时，需要将其设置为一个随机值，避免多个负载均衡器同时请求同一个服务器，造成服务器的瞬时压力
在位置自增时，需要忽略符号位，因为Java没有无符号整数，所以当位置的值超出整型最大值时会变成负值导致抛出异常。至于为什么不能使用绝对值，是因为整型的最小值没有对应的绝对值，得到的依旧是负值(Spring Cloud #1074)
加权轮询负载均衡算法有很多主流的实现，并且各自都有各自的优点。虽然加权负载均衡产生任意符合全总分配比例分布的选择序列都是合适的，但在短时间窗口内是否能够选择尽可能多的节点提供服务仍是评价加权负载均衡实现的质量的关键指标。
数组展开实现方式是一种适用空间换时间的策略，适用于较小的服务器集群或专用型负载均衡设备。它的优点是速度非常快，与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，这个时候可以使用最大公约数来减少展开后的数组大小。因为最大公约数的诸多限制，例如任意自然数N与N+1互质，任意自然数N与1互质，所以很容易出现优化失败的情况，因此本示例并未给出，感兴趣的可以去看Spring Cloud相关PR（Spring Cloud #1140）
在实例按权重展开成数组后，需要对得到的数组进行洗牌，以保证流量尽可能均匀，避免连续请求相同实例（Java中实现的洗牌算法是Fisher-Yates算法，其他语言可以自行实现）
因为是在构建负载均衡器的时候按权重展开成数组的，所以在负载均衡器构建完成后无法再改变实例的权值，对于频繁动态变更权重的场景不适用
上界收敛选择方式提前计算出所有权重的最大值，并将初始上界设置为所有权重的最大值，接下来我们一轮一轮地去遍历所有实例，并找到权重大于等于上界的实例。当前轮遍历结束后，所有大于等于上界的元素都被选取到了，接下来开始尝试权重更低的节点，直到最后上界为0时，将其重新置为最大值。目前openresty （有人在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的话，中间这些轮会反复请求权重最高的那些实例，导致负载不均衡。
虽然最大公约数可以减少下降次数，但是如果权重相差非常多，并且所有元素都是互质的（n与n+1互质，任意自然数n与1互质，在实践中非常容易出现），那么在上界下降的过程中将会带来很多空转。这个可以参考广度优先遍历的思想，使用先入先出的队列来减少空转。
与数组展开方式遇到的问题相同，因为是在构建负载均衡器的时候计算最大公约数的值，所以对于频繁动态变更权重的场景依旧会有很大的性能开销，但是相较于数组展开方式可以避免频繁动态分配数组导致的性能与内存碎片问题
权重轮转算法中将会存储两个权重的值，一个是不会变化的原始权重，一个是会随着每次选择变化的当前权重。权重轮转实现中维护了一个循环不变量——所有节点的当前权重的和为0。每轮遍历过程中所有实例的有效权重都会增加它的原始权重，并选择出当前权重最高的节点。选择出权重最高的节点后将它的当前权重减去所有实例权重的总和，以避免它再次被选择。NGINX中加权轮询负载均衡算法使用此实现（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; } }
这里面有三个需要注意的点：
权重轮转非常适合实例变化频率非常高的集合，因为它不需要提前构建数据结构
权重轮转实现的效率与实例数量相关，时间复杂度是O(n)，当集群服务器数量非常大时需要限制每次参与选择的服务器数量（Spring Cloud #1111）
权重轮转实现需要修改服务器实例的数据结构，当服务实例是由其他机构提供时无法使用此实现
EDF算法最早被用在CPU调度上，EDF是抢占式单处理器调度的最佳调度算法。EDF实现与权重轮转实现相似，引入了名为deadline的额外变量，可以认为权重越高的服务器实例完成任务的时间越快，那么在假设所有请求的成本相同时，所需要花费的时间是权重的倒数，所以可以很自然地选择可以最早空闲出来提供服务的服务器实例，并将任务分配给它。
实现EDF算法只需要将每个下游服务器实例与deadline绑定，然后以deadline为优先级维护到优先队列中，并不断取出队首元素，调整它的deadline，并将它重新提交到优先队列中。知名Service Mesh代理envoy使用了此方法实现加权负载均衡（envoy），以及蚂蚁开源网络代理mosn中也实现了此方法（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)，不会造成很大的内存开销。
最简单的实现方式，遍历所有实例，并找出当前连接数最少的实例
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; } }
加权最少连接负载均衡算法的实现方式与最少连接负载均衡算法相同，只是在计算时增加了权重相关的参数
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; } }
加权响应时间负载均衡算法使用统计学的方法，通过历史的响应时间来得到预测值，使用这个预测值来选择相对更优的服务器实例。得到预测值的方法有很多，包括时间窗口内的平均值、时间窗口内的TP99、历史所有响应时间的指数移动加权平均数（EWMA）等等。其中Linkerd与APISIX使用了EWMA算法（Linkerd和APISIX）。
通过历史的响应时间来得到预测值这个操作通常是CPU开销很大的，实际使用时可以不用遍历所有元素，而是使用K-临近元素或直接随机选择两个元素进行比较即可，这种启发式方法办法无法保证全局最优但是可以保证不至于全局最差。
源地址哈希负载均衡以任意算法将请求地址映射成整型数，并将这个整型数映射到实例列表的下标
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(); } } }
这里有一个需要注意的点：
面向公网提供服务的负载均衡器前面可能会经过任意多层反向代理服务器，为了获取到真实的源地址，需要先获取X-Forwarded-For头部，如果该头部不存在再去获取TCP连接的源地址
在维护大型服务器集群时，服务器实例随时都有可能被创建或移除，当服务器被创建或移除时，集群管理员需要到各个负载均衡设备上去更新服务器实例列表。
服务注册表会在内部维护服务对应的服务器实例列表。在服务器实例被创建并成功运行服务后，服务器实例会去服务注册表中注册自身，包括网络地址（IPv4/IPv6）、服务端口号、服务协议（TCP/TLS/HTTP/HTTPS）以及自身提供的服务名称等等，有的服务注册表本身也会提供主动健康检查的能力（如Eureka与Consul）。在服务器实例正常退出时会在服务注册表执行反注册逻辑，这个时候服务注册表就会将这个服务器实例从服务器实例列表中移除。即使服务器实例异常退出导致无法执行反注册逻辑，服务注册表也会通过主动健康检查机制将这个异常的服务器实例从服务器实例列表中移除。
在拥有服务注册表后，负载均衡设备不需要再手动维护服务器实例列表，而是当请求到来时从服务注册表中拉取对应的服务器实例列表，并在这个服务器实例列表中进行负载均衡。为了提高服务的可用性，负载均衡设备会在本地（内存或本地文件注册表）缓存这些服务器实例列表，以避免由于负载均衡设备与服务注册表无法连接而导致服务不可用。
缓存及重新获取服务器列表的策略根据不同业务场景有不同的实现，在Spring Cloud Loadbalancer中是通过缓存过期而触发重新获取的逻辑（Spring Cloud），当服务注册表不可用时，因为负载均衡设备中无可用的服务器备份而导致服务完全不可用；在大部分的负载均衡设备中将缓存获取与更新逻辑改为定时器主动刷新的机制，这样当服务注册表不可用时可以主动决定是否将旧数据标记为过期。尽管本地缓存可以提高服务的可用性，但是要注意负载均衡设备在使用的仍旧是旧的服务提供方列表，当长时间无法获取到新的服务提供方列表时，负载均衡设备应当舍弃旧的服务提供方列表，并将服务不可用的问题暴露出来，通过基础设施提供的监控与告警能力通知集群管理员来进行处理。
健康检查本质是一个预定规则，它向负载均衡器背后的服务器集群中的所有成员发送相同的请求，以确定每个成员服务器是否可以接受客户端请求。
对于某些类型的健康检查，通过评估来自服务器的响应以及收到服务器响应所需的时间以确定每个成员服务器的运行状态。通常情况下，当成员服务器的状态变为不健康时，负载均衡器应该快速地将其从服务器实例列表中移除，并在成员服务器状态恢复正常时将其重新添加回服务器实例列表中。
对于网络层负载均衡器（也叫做NLB或L4LB），通过建立TCP连接，根据是否能够成功建立连接以及建立连接所需要的时间来确定成员服务器的状态。
对于应用层负载均衡器（也叫做ALB或L7LB），通过发送应用层协议（不只是HTTP协议）定义的用于健康检查的请求报文，并根据响应报文内容以及整个请求从建立连接到完整收到所有响应所花费的时间来确定成员服务器的状态。
应用负载均衡器没有固定的模式。例如，对于提供HTTP协议服务的应用，可以提供用于健康检查的URL，设置通过健康检查的HTTP状态码（或状态码集），并验证响应报文中用于表示服务器状态的字段（通过JSONPath或XMLPath等提取）是否是预期值等方式来确认成员服务器状态；对于RPC协议，可以提供专门的ping-pong服务，负载均衡器根据RPC协议组装请求报文，并发送ping请求到成员服务器上，并根据成员服务器返回的内容是否为pong响应来确认成员服务器的状态，具体设计可以参考websocket的ping-pong机制（RFC 6455）。
负载均衡器中的慢启动思想来自于TCP的拥塞控制理论，其核心也是为了避免大量请求涌入刚刚启动完成的应用程序，导致大量请求阻塞、超时或异常的情况。 众所周知，Java是半编译半解释型语言，包括Java语言在内，现代解释型语言的解释器都带有即时编译器（Just In Time，JIT），JIT编译器会跟踪每个方法的执行点，对那些热点路径（Hotspot）进行更高效的优化，这也是Hotspot JVM名字的由来。而JIT对热点路径的优化全都来自于自应用程序启动以来的所有方法调用，也就是说应用程序的系统承载能力是随着程序的运行而不断得到强化的，经过JIT优化的Java代码甚至可以得到近似GCC中O3（最高级别）优化的性能。跟多关于JIT编译器的细节可以看Oracle的Java开发者指南（Java Developer Guide）。
同时，现代应用程序都不可避免的会使用本地缓存，当应用程序刚刚启动时内存中的缓存是空的，随着应用程序的运行，不断地访问外部系统获取数据并将数据写入到内存缓存中，应用程序与外部系统的交互会不断减少，应用程序的系统承载能力也会逐渐达到峰值。
上面是应用程序在启动后性能不断提升的因素中最常见的，初次之外还有很多的因素。所以为了避免大量请求涌入刚刚启动完成的应用程序的现象发生，负载均衡器会通过慢启动的方式，随着服务器运行不断增加这些服务器实例的权重，最终达到服务器的实际权重，从而达到动态调整分配给这些服务器实例的流量的效果。
服务器权重变化算法有很多，包括随时间线性增长、随时间对数增长、随时间指数增长、随时间变幂增长、与随时间按Logistic增长等。目前京东服务框架（JSF）实现的是随时间线性增长；envoy实现了随时间变幂增长，并引入了渐进因子来调整变化速率（envoy slow start）。
负载均衡技术是网络代理与网关组件最核心的组成部分，本文简单介绍了什么是负载均衡技术、常见的负载均衡算法以及常见负载均衡算法的实现，并给出了负载均衡技术的扩展，为将来更深入学习网络代理相关技术打下基础。
因本人才学疏浅经验能力有限，文中难免会有疏忽和遗漏，以及不连贯的地方，欢迎大家与我沟通交流给出建议。
作者：纪卓志