文|纪卓志（GitHub ID：jizhuozhi)
京东高级开发工程师
MOSN 我的项目 Committer
专一于云原生网关研发的相干工作，长期投入在负载平衡和流量管制畛域
前言
这篇文章次要是介绍 MOSN 在 v1.5.0 中新引入的基于提早的负载平衡算法 #2253。首先会对分布式系统中提早呈现的起因进行分析，之后介绍 MOSN 都通过哪些办法来升高提早，最初构建与生产环境性能散布相近的测试用例来对算法进行验证。
在开始聊基于提早的负载平衡算法之前，咱们先介绍下什么是负载平衡。
什么是负载平衡
Wikipedia 中 Load Balancing (Computing)) 词条是这样介绍负载平衡的：
负载平衡是将一组任务分配到一组资源（计算单元）上的过程，目标是使它们的整体解决更有效率。负载平衡能够优化响应工夫，防止负载不平均导致一些计算节点过载而其余计算节点处于闲暇状态
负载平衡在大型分布式系统中是要害的组成部分。负载平衡解决了分布式系统中最重要的两个问题：可伸缩性 （Scalability） 和韧性 （Resilience）。
- 可伸缩性 ：应用程序部署在多个雷同的正本中。当计算资源有余时能够通过部署额定的副原本减少计算资源，而当计算资源大量冗余时能够通过缩小副原本节省成本。通过负载平衡能够将申请负载散布到不同的正本中。
- 韧性 ：分布式系统的故障是局部的。应用程序通过冗余正本的形式，保障在局部组件故障时仍能失常地提供服务。负载平衡通过感知节点的故障，调整流量的调配，将流量更多的调配到那些可能失常提供服务的节点上。
走得更快
负载平衡使得古代软件系统具备了可扩展性和韧性。但在分布式系统中还存在不容忽视的问题： 提早 。
提早来自哪里
古代软件系统通常是多层级构造大型分布式系统，即便是只服务单个终端用户的申请，它背地也有可能通过了上百次的数据拜访，这种状况在微服务架构中更是尤为广泛。
微服务架构 （援用自 Microservices Pattern）
单台性能稳固的服务器中提早通常由以下几个方面造成：
- 计算工作自身的复杂度
- 内容的传输过程中的提早
- 申请排队期待的提早
- 后台任务流动所导的资源竞争
这些服务器之间的提早将会叠加，任何显著的提早减少都会影响终端用户的体验。此外，任何来自单个节点的提早峰值也会间接影响到终端用户体验。同时越来越多地应用私有云部署应用程序也进一步加剧了响应工夫的不可预测性。因为在这些环境中存在共享资源 （CPU、内存和 IO） 的争用，应用程序机简直不可避免地遇到性能影响，而这种影响是随时产生的。
如何缩小提早
有钻研表明，在大型互联网利用中，提早往往具备长尾特点，P99 比中位数高出几个数量级。如果在利用架构的每层都可能缩小这些尾部提早，那么对终端用户整体的尾部提早将会显著升高。
在服务网格中，所有接管和发送的流量都会通过边车代理，通过边车代理能够轻松地管制网格的流量，而无需对服务进行任何批改。如果边车代理在对应用层流量进行转发时，总是通过负载平衡时选择响应工夫较短的服务器，那么将会显著升高对终端用户的尾部提早。
基于此，咱们筹备开始为 MOSN 引入基于提早的负载平衡算法，并进行适当调整来保障可能在大多数应用场景下显著缩小提早。
性能问题是部分的
后面提到了，每个节点的性能受到多种因素的影响，这些影响因素是动静的，难以精确预测每个节点的性能，因而咱们无奈准确地抉择最好的节点，然而能够防止较差的节点。
在云环境中，服务器的性能经常是难以预测的，然而咱们能够通过对大量的数据进行剖析，发现服务器性能的散布大多数状况下是合乎正态分布的。因而，只管有一部分的服务器在性能方面体现比拟差，它们的数量通常都是多数的 （3Sigma），而绝大部分服务器节点的体现是失常的。
除了服务器之间的差别，还存在由基础设施导致的动静提早，这种提早可能是因为网络拥塞、故障或一直增长的流量所导致。这种提早通常具备持续性和局部性：持续性则示意提早会长工夫存在，不会在短时间内隐没；而局部性指的是提早往往只呈现在某些特定服务器上，而不会在全局产生。
PeakEWMA
面对这些问题，咱们应用 Peak EWMA （Peak Exponentially Weighted Moving Average） 计算响应工夫指标，并依据这个指标来对节点进行负载平衡。
EWMA 是一种动静权重调整算法，各数值的加权影响力随工夫而指数式消退，越近期的数据加权影响力越重，但较旧的数据也给予肯定的加权值。
它以绝对较高的权重思考了最近响应工夫的影响，因而更具备针对性和时效性。加权的水平以常数 𝛼 决定，𝛼 数值介于 0 至 1，它用来控制数据加权影响力消退的速率。
作为一种统计学指标，EWMA 的计算过程不须要大量的采样点以及工夫窗口的设定，无效地防止了计算资源的节约，更适宜在 MOSN 这样的边车代理中应用。
因为响应工夫是历史指标，当服务器呈现性能问题导致长时间未返回时，负载平衡算法会谬误地认为这台服务器仍是最优的，而一直地向其发送申请而导致长尾提早增高。咱们应用沉闷连接数作为实时变动的指标对响应工夫进行加权，示意期待所有沉闷的连贯都返回所须要的最大工夫。
P2C（Power of Two Choice）
在大规模集群中，如果应用遍历所有服务器抉择最好的服务器的办法，尽管能够找到最轻负载的服务器来解决申请，但这种办法通常须要大量的计算资源和工夫，因而无奈解决大规模的申请。因而，咱们应用 P2C 来抉择最优节点。相比之下，P2C 算法能够在常数工夫内抉择两个服务器进行比拟，并抉择其中负载更轻的服务器来解决申请。P2C 基于概率调配，即不间接基于权重调配，而是依据每个服务器优于其余服务器的概率值来决定申请的调配。
此外，在多个负载均衡器的状况下，不同负载均衡器可能会有不同的节点视图，这可能导致某些负载均衡器抉择的最优节点总是最差的节点。这是因为负载均衡器抉择最优节点时基于本人的视图信息，而节点视图随着工夫的变动可能会发生变化，因而不同的负载均衡器抉择的最优节点也可能不同。P2C 算法通过对随机抉择的两个节点进行比拟，能够使节点间的负载平衡更加平均，即便节点视图发生变化，也能提供稳固的负载平衡成果。
在 MOSN 的 v1.5.0 版本中，只有节点权重雷同时会应用 P2C，当权重不同时会应用 EDF 进行加权抉择。后续会提供可配置的选项。
模仿流量验证
咱们构建了与生产环境性能散布相近的测试用例来对算法进行验证。
首先咱们应用正态分布生成了 10 台服务器的基准性能，其中数学冀望为 50ms，标准差为 10ms。接下来，咱们将这些基准性能作为数学冀望，并以标准差为 5ms 的正态分布随机生成了申请提早，以模仿真实世界的状况。此外，咱们还在其中一台服务器注入了概率为 0.1 的故障，故障产生时会产生 1000ms 的提早，以测试零碎的容错性。
为了模仿申请歪斜时申请排队期待的提早，咱们限度了每台服务器的最大并发数为 8，当同时解决的最大申请数超过了最大并发数时，将会排队期待。这样可能更加实在地模拟出零碎的运行状况。
最初，咱们应用了 Round Robin、Least Request 和 Peak EWMA 三种算法，别离以 16 并发同时发送申请，失去的 P99 如下：
Round Robin 算法尽管均衡，然而始终会抉择到注入了故障的服务器，导致 P99 始终在 1000ms 高低稳定；Least Request 算法尽管避开了故障服务器，然而其 P99 值仍然体现出较大的稳定。
与此相比，Peak EWMA 算法在保持稳定的同时，P99 值始终低于 Round Robin 和 Least Request 算法。这失当地体现了 MOSN 在性能优化方面的胜利，MOSN 的确做到了走得更快。
期待走得更稳
尽管 MOSN 在服务网格中解决了让利用跑得更快的问题，然而分布式系统中的故障却时刻存在。咱们冀望通过 MOSN 的负载平衡算法，能够让咱们的服务走得更稳。
疾速失败的挑战
依据教训，故障时的响应工夫往往远小于正常值，比方网络分区导致的连贯超时，而没有理论解决申请。咱们称这种故障时的响应工夫远远小于正常值的状况为疾速失败。
在服务器呈现疾速失败时，从负载平衡的角度看，就会谬误地认为该服务器是最优的抉择。只管能够通过断路器来防止向该服务器发送长期申请，但断路器自身也是一种疾速失败，谬误的视图仍然会流传。此外，断路器的阈值设置也存在挑战。此外，断路器须要足够的谬误样本能力触发，而咱们冀望尽可能防止谬误的产生。
因而，咱们在后续版本中将会对负载平衡算法进行调整，让负载平衡算法可能感知谬误的产生，并在触发断路器前就防止将申请转发到故障的服务器中。
MOSN Star 一下✨： https://github.com/mosn/mosn