从排队论到过载保护算法

Posted 2023-04-12 10:38 +0800 by ZhangJie ‐ 1 min read

排队论简介 ##

排队论的精髓是通过数学模型和分析方法来研究排队系统的性能和行为。排队系统是指由一些服务设施和一些顾客组成的系统，顾客需要排队等待服务。排队论的目标是研究如何优化排队系统的性能，以提高服务质量和效率。

排队论的核心是建立数学模型来描述排队系统的行为。这些模型通常基于随机过程和概率论，用于描述顾客到达的随机性、服务时间的随机性以及服务设施的数量和性能等因素。通过分析这些模型，可以得出排队系统的性能指标，如平均等待时间、平均逗留时间、系统利用率等等。

排队论的应用非常广泛，涉及到许多领域，如交通运输、通信网络、制造业、医疗保健等等。在这些领域中，排队论可以用来优化资源利用、提高服务质量、降低成本等等。

总之，排队论的精髓是通过数学模型和分析方法来研究排队系统的性能和行为，以优化系统的性能和效率。

公式及应用 ##

排队论是一个非常广泛的领域，其中涉及到许多不同的理论公式和应用。以下是一些常见的排队论理论公式和计算机系统中的应用：

1. Little’s Law：L = λW，其中L表示系统中平均顾客数，λ表示到达率，W表示平均逗留时间。这个公式表明，系统中平均顾客数等于到达率乘以平均逗留时间。在计算机系统中，这个公式可以用来计算系统中的平均并发请求数，以及系统的响应时间和吞吐量。
2. Kendall’s Notation：A/B/C/K/N，其中A表示到达过程的类型，B表示服务时间的分布类型，C表示服务设施的数量，K表示服务设施的排队规则，N表示系统容量。这个符号表示了排队系统的基本特征，可以用来描述和比较不同的排队系统。
3. M/M/1队列：这是一个经典的排队模型，其中到达过程和服务时间都是指数分布，服务设施数量为1。这个模型可以用来计算系统的平均等待时间、平均逗留时间、系统利用率等指标。在计算机系统中，这个模型可以用来分析单个服务器的性能。
4. M/M/m队列：这是一个扩展的M/M/1队列模型，其中服务设施数量为m。这个模型可以用来计算系统的平均等待时间、平均逗留时间、系统利用率等指标。在计算机系统中，这个模型可以用来分析多个服务器的性能。
5. 网络队列模型：这是一个用于分析计算机网络性能的排队模型，其中网络节点被建模为队列，数据包被建模为顾客。这个模型可以用来计算网络的吞吐量、延迟、丢包率等指标。
6. 负载均衡算法：这是一种用于优化计算机系统性能的算法，通过将负载均衡地分配到多个服务器上，以提高系统的吞吐量和可靠性。排队论可以用来分析负载均衡算法的性能和效率。

这些理论公式和应用只是排队论中的一部分，排队论还涉及到许多其他的理论和应用，如排队网络、排队模拟、排队优化等等。

浅谈Little’s Law ##

简要说明 ##

Little’s Law是一个基本的排队论原理，它描述了在一个稳定的系统中，平均顾客数、平均等待时间和平均服务率之间的关系。该原理最初由美国数学家John Little在1961年提出，被广泛应用于各种排队系统的性能分析和优化。

Little’s Law的问题背景是排队系统，例如银行、超市、餐厅等等。在这些系统中，顾客到达、等待和离开的过程构成了一个排队模型。Little’s Law的目的是通过分析这个模型，来解决如何优化排队系统的问题。

Little’s Law的核心公式是：L = λW，其中L表示平均顾客数，λ表示平均到达率，W表示平均等待时间。这个公式告诉我们，如果我们知道了平均到达速率和平均等待时间，就可以计算出平均顾客数。反之亦然，如果我们知道了平均顾客数和平均等待时间，就可以计算出平均到达速率。这个公式可以帮助我们更好地理解排队系统的性能，并且指导我们如何优化排队系统。

应用案例 ##

以下是一些应用Little’s Law的案例：

1. 在一个银行分行，平均每小时有100名顾客到达，平均等待时间为10分钟，那么该分行的平均顾客数是多少？根据Little’s Law，L = λW = 100 * 10 / 60 = 16.67，因此该分行的平均顾客数为16.67人。
2. 一家餐厅想要提高服务质量，他们决定增加服务员的数量。根据Little’s Law，如果他们想要减少平均等待时间，他们需要增加服务员的数量，以提高服务率。如果他们想要减少平均顾客数，他们需要减少到达率，例如通过减少广告宣传或者提高价格等方式。

在线服务领域 ##

理解little’s law ##

将其应用到我们熟悉的在线服务领域的话，可以达到稳态的前提下，调整下相关参数：

• 队列平均长度可视为同时被服务的请求个数，即服务并发度Concurrency，
• 队列人数到达(速)率可视为服务吞吐Throughput，
• 平均服务时间可视为服务平均处理延迟Latency（可细分为等待延迟+处理延迟），

这样可以得到另一个版本的Little’s Law，Concurrency=Throughput * Latency。

简单理解下这里的公式。假设请求都是单线程处理，每个请求只会占用一个cpu core，则服务并发度Concurrency就是cpu core的个数；每个请求的处理平均时间为Latency（单位为秒），则1秒内一个cpu core可以处理的请求数为 1/Latency；因此，1秒内可处理的总请求个数也就可以确定：Throughput = Concurrency * (1/ Latency)，进一步就可以得到公式：Concurrency = Throughput * Latency……所以，还是好理解的。

利用这个公式，我们可以进一步去分析计算机系统处理请求时的吞吐量、处理时延、并发处理能力之间的关系。

有时候我们队计算机进行系统性能优化，也会对某任务的某一部分进行改善，如何评估改善后任务的整体性能极限呢？可以通过Amdahl’s Law来分析，详见 Wikipedia Amdahl’s Law，不展开了。

那我们如何具体来使用它来评估系统处理请求时的吞吐量、处理时延、并发处理能力之间的关系呢？有没有什么实际案例可供借鉴下。

工程应关注什么 ##

首先，工程上我们往往会通过调整服务配置，对服务进行不同测试，比如性能测试、负载测试、压力测试、稳定性测试等。

• 性能测试，以系统设计初期规划的性能指标为预期目标，对系统不断施加压力，验证系 统在资源可接受范围内，是否能达到性能预期。

• 负载测试，对系统不断地增加并发请求，以增加系统压力，直到系统的某项或多项性能 指标达到安全临界值。当并发请求数量超过安全临界值之后，系统吞吐量不升反降。

• 压力测试，超过安全负载的情况下，对系统继续施加压力，直到系统崩溃或不能再处理 任何请求，以此获得系统最大压力承受能力。

• 稳定性测试，被测试系统在特定硬件、软件、网络环境条件下，给系统加载一定业务压力， 运行一段较长时间，以此检测系统是否稳定。

通过这些测试，来确定不同负载下（cpu、内存、IO等）服务能够支持的吞吐量Throughput（QPS）、处理延迟Latency（p90、p95、p99耗时、平均处理耗时）。

真实的测试场景下涉及到软硬件、网络、其他组件影响等等比较复杂的因素，用Little’s Law、Amdahl’s Law很难进行精准的分析，但是可以用来推断下理论值、极限值。

尽管真实环境中，不能直接用它来直接预测服务的负载、吞吐量、平均耗时等指标值，但是仍然可以使用它来指导具体的过载保护算法的设计。

负载的评估 ##

这里思考下，负载与RPS、处理时长之间的关系。根据排队论模型：Little’s Law L = λW，类比到计算机系统，L表示系统中任意时刻需要处理的请求数，λ表示每秒到达的请求数量，W表示请求的平均处理时长。

随着λ从0逐渐增大：

• 当λ较小时，平均处理时长不会随着每秒请求量的增长有明显增加；
• 随着λ继续增大，系统中资源竞争逐渐加剧，比如抢锁、内存分配、协程调度、GC等问题开始表现出来，平均处理时长会略有增加，系统中任意时刻的处理请求数也会增加；
  • 这个很好理解，但是难以精确的建模，比如针对内存负载、cpu负载、调度开销、GC开销做一个复杂的公式，模型训练也存在过拟合的问题，我们设计的公式可能也会
  • 可能设计出的公式对某种workload比较合适，但是换一种就不一定行，如果只考虑我们后台微服务场景，也可以设计一套这样的负载计算公式（类似trpc-overload-control）
  • 或者我们把问题简化下，把服务本身当做一个黑盒，管你内部发生了什么呢，只从外部观测角度来衡量负载高还是低，那就是Little’s Law指导下的做法，比如：Netflix自适应限流过载保护、微信基于排队时延的过载保护
• λ继续增大，导致L超过了系统规划的容量，这个时候，就处理不了了
  • 请求可能会有请求队列放不下的问题，这个就会丢弃请求，
  • 或者处理超时，排队时延+处理时延，排队明显更久了，竞争也会加剧处理时延

对于过载保护，更适合基于一些能反映系统负载、服务负载情况的指标来评估负载信息：

• 系统负载，
  • cpu利用率高往往会被认为是负载高，确实是；但举个极端case如计算型负载，只要请求量不超过cpu cores很多就不能认为是过载；
  • ram利用率高往往会被认为是负载高，也确实是；但是ram利用率多高算高呢？实际观察系统可用内存+可用buff加起来确实不是很大，这个时候认为过载可能也不见得正确，而且GC的触发也依赖内存分配动作的触发（定时只是兜底）；
• 服务负载：
  • 由于机器可能会混部多个服务，这里用服务负载来特指某个服务的负载，用来和系统负载区分下
  • 服务负载准确说应该是服务资源的配额限制，如内存软限制，其负载信息也会通过GC导致的CPU开销反映到系统负载上
  • 协程调度的间隔、GC Pause耗时可能受系统负载影响，但也受服务本身影响，这些指标通过观测系统负载不一定能观测到，但是通过服务自身的运行时监控能观测到
• 当做黑盒
  • 观察系统的吞吐量变化、处理耗时变化（client端、server端），真实情况可能会受网络抖动影响，但是网络（拥塞等）也确实是需要考虑的

总的来说，为了更合理地评估服务的过载保护算法，我们不能单纯看系统负载，也不能单独看服务负载，也不能完全当做黑盒来看，需要综合来评估下。

这里提的是负载的评估，还没有提及过载保护算法，过载保护可以在客户端做，也可以在服务器做，也可以两边都做各有侧重点。

过载保护算法 ##

传统做法 ##

通常会将负载作为一个相对固定的值，比如CPU单核85%作为一个参考点，测试期间压力源发送的请求系统负载稳定在这个值，然后观察Throughtput、Latency的关系变化。注意此时85%的负载下，响应时间Latency不一定是最好的，但是吞吐量可能是更大的，要注意根据SLA（承诺的响应时间、QPS等）来为客户分配合理的资源。或者我们将其压测到过载，然后取此时QPS的一个75%左右作为一个相对合理的QPS值，并在客户端通过漏桶、令牌桶等算法来强制执行这个最大频率上限。

但是对于大型分布式系统，这个配置值很快就会过期，QPS可能偏小导致后端服务不能充分利用资源，或者QPS过大导致后端服务过载。

分布式限频 ##

为了解决这个问题，我们也会引入分布式限频，后端节点定期上报负载、可承载请求给频控服务，客户端定期从频控服务获取最新的配额（一般客户端请求量大，会通过先消费后上报，与频控服务来完成同步）。

但是这样需要额外引入一个频控服务，它设计实现的不好也容易成为系统瓶颈。

自适应过载保护 ##

我们应该考虑并发请求，而不是考虑RPS、CPU、内存、磁盘或网络等限制。Little’s Law 很好地涵盖了这种关系，其中 Limit = Average RPS * Average Latency。

Little’s Law，它其实可以指导我们简化过载保护算法的设计，我们可以不用围绕CPU、内存、磁盘或网络情况来设计华而不实、过度复杂、又不能充分覆盖不同负载场景的负载计算的算法，仅通过观察请求成功率、失败率、响应时间就可以预测出系统接下来大致能支持的一个负载。简单理解，latency增加还好，如果成功率下降了，适当调低rps，反之调高。

不需要引入其他分布式频控服务，也不需要设计复杂的负载计算的算法，借鉴最具有说服力的服务成功率、失败率、响应时间就可以动态调整接下来的请求速率，实现起来简单，部署时伸缩性、不同负载适应性更好。

相关的尝试：

1、netflix在自己的视频处理链路中引入了这种算法，我们在之前业务腾讯看点的内容处理链路中也有类似的实践，gRPC中也有类似tcp拥塞窗口控制的机制。netflix设计实现了一个基于Java的库 Netflix/concurrency-limits，2.9k stars，有开发者用go重写了一遍 platinummonkey/go-concurrency-limits, 91 stars。

2、微信在过载保护算法dagor中，将请求排队时长作为重点参考指标，参考文献Overload Control for Scaling WeChat Microservices，中文翻译见 微信过载保护的实现原理。

这里的几种案例都是基于Little’s Law出发的实践，都是大型项目中的真实实践，对于大规模分布式系统、动态扩缩容、链路动态变化场景下的适应性效果比较好。

本文总结 ##

本文简单是在实践过程中，对排队论、little’s Law、服务负载评估、过载保护算法的一点思考和认识，将相关的理论、实践简单总结下。我认为Little’s Law模型，以及以及在此基础之上的netflix、微信的过载保护实践，恰恰是抓住了问题的重点，所以能以更简洁优雅的做法来妥善的解决这个由来已久又被广泛讨论的问题。