start

  理论上，负载均衡就是指 将请求发送到最合适的节点上处理，最合适就需要分业务场景进行判断了；

  经典场景如:偏向需要更多内存的大数据处理，又或者是CPU密集型需要CPU性能和空闲与否的复杂计算处理，再或者两者兼具的图相关的处理；

代理(服务器端)、客户端、外部负载均衡

  首先在 代理 做负载均衡（集中式LB）时，客户端向负载均衡器发送RPC，由负载均衡器分发请求到可用的服务端上；在L3/4/7层做，如nginx、F5等；

  而在 客户端 做负载均衡（进程内LB）时，客户端需要获取多个服务端，并选其中之一发送RPC请求，可在返回响应时附带负载相关信息，或者从可观测性的平台直接拉取节点负载信息，以此更新客户端的内部状态；即胖客户端，没有额外开销，性能较好；

  、外部负载均衡器上（独立进程LB），原理和客户端类似，额外将LB和服务发现功能从进程内剥离，不会有单点问题，在性能没有明显下降的前提下，简化了客户端的逻辑；

代理层：

  • 优点：
    • 客户端逻辑简单；
    • 不需要客户端感知服务端；
    • 充当安全边界，一定程度上方便处理不信任的客户端；
  • 缺点：
    • 延迟较高；
    • 吞吐量会限制服务端的发挥；
    • 作为流量集中处，容易成瓶颈，挂了就完蛋（需要额外的机制保护）；

客户端层

  • 优点：
    • 性能相对高，因为是直连；
    • 去中心化；
  • 缺点：
    • 客户端可能需要维护服务端的负载等状态；
    • 客户端均需要实现自己的负载均衡算法，在不同语言or逻辑下，可能需要重复部分代码；

架构

分布式策略

  由节点间判断负载并作出决策；

  基本策略如近邻法，节点（处理器）和临近的节点交换负载，通过局部的负载均衡间接做到全局负载均衡；

具体策略如：扩散法、维交换法、梯度法；

扩散法（一维）：

  在每一次迭代中，处理器会根据自身与相邻处理器之间的负载差异，计算出需要传递的负载量，并将其传递给负载较轻的相邻处理器。这个过程反复进行，直到负载差异收敛到一个足够小的范围（范围过大导致全局负载均衡效果不佳，过小会导致过慢均衡负载）；

DEM:

  相比于扩散法，处理器通过在多维空间的坐标和其他处理器形成更多的邻接关系；思想也类似，都是局部间接达成全局均衡，只不过交换负载是在各个维度上分别进行的；

GM：

  基于梯度下降思想计算负载差异，通过梯度确定传递量和方向；注意可能陷入局部最优，且每次计算的开销也比前两种方法要大；

集中式策略

  由一个 Schedule 接收并分析各节点的负载情况，并作出决策；

层次策略

  由一个层次化的拓扑结构来最小化负载均衡的开销；核心思想是将分布式系统中的处理节点组织成一个层次树，并在这个层次树的各个层次上逐级进行负载均衡；

层次树的构建方法：

  分布式系统中的处理节点被划分为多个组，也被称为“均衡域”。每个均衡域包含一组相邻的处理器，这些域根据网络的拓扑结构组织成一个层次树。层次树中的节点代表均衡域，而树的层次结构对应不同级别的均衡；

多级负载均衡：

  • 局部负载均衡（低层）: 在层次树的每一层，首先在相邻的均衡域之间进行负载均衡。这个过程是局部的，只在域的范围内进行，目的是在相邻节点之间均衡负载； 合并域: 从树的底层逐级向上推进。在每一层完成局部负载均衡后，继续向上层推进，将较大范围的均衡域组合在一起进行新的负载均衡操作；
  • 全局负载均衡（根节点）: 最后，当负载均衡达到层次树的根节点时，根节点执行全局的负载均衡，确保整个系统的负载尽可能均衡；
  1. 优点
    • 通常可以减少通信开销，通过分层的方式，只在相邻的均衡域之间进行通信，即虽然通信总量变多，但是大部分通信都是相邻节点通信，影响的平均时间大概率不会变差；
    • 可扩展性良好，层次化的结构使得负载均衡过程可以扩展到非常大的系统，因为每一层次的均衡只需考虑相对较小的均衡域；
    • 每个均衡域可以独立处理其内部的负载均衡，这使得整个系统更易于管理和维护；
  2. 缺点：
    • 实现较为复杂；
    • 逐层传递的过程中，存在一定的延迟；

负载均衡策略

  大致可分为静、动态两种；

  静态（默认节点同质化，且请求需求同质化）如：

  1. 轮询(RoundRobin)
  2. 随机(Random)
  3. 一致性哈希算法(Consistent Hashing)，如 Ketama 算法，用于解决 cache 失效导致的缓存穿透的问题的；进一步优化如有界一致性哈希；

  动态（实时调整分流策略）如：

  1. 最小连接数(LeastConnections)
  2. 最低时延(Minimum latency)
  3. 加权轮询(Weight-RoundRobin),加权随机(Weight-Random)，解决异质化节点处理能力不同的问题；
  5. 自适应算法（P2C）：即从可用节点列表中随机选择两个节点，计算它们的负载率，选择负载率较低的进行请求；

注：任何加权算法，都需要注意是否需要平滑处理，即连续请求不打向同一节点，防止打挂；

注：最小链接数有一个关于多路复用的缺陷，即一个链接可能同时被多个请求复用，此时即使链接数少，但负载可能也很高；

gRPC 没提供返回链接数的方法，只能间接通过连接信息计算；

最低时延也可被称为最快响应时间，一般可以取平均响应时间或者99线；