避免无法克服的队列积压

自从大学开设第一门计算机科学课程以来，我就一直对算法在现实世界中的应用充满了好奇。我们在思考现实世界中发生的某些事情时，可以模仿这些事情得出算法。尤其是在排队（比如在杂货店、路上或者在机场）的时候，我经常会这样做。我发现排队无聊的时候可以思考排队论。

十多年前，我在 Amazon 物流中心忙完了一天的工作。我在算法的引导下，从架子上取下商品，将商品从一个箱子搬到另一个箱子里，然后把箱子搬走。我发现，和很多人一起工作，最美妙的事情就是工作本质上是精心编排的物理合并排序，而且自己能参与其中。

在排队论中，队列较短时的行为是相对无趣的。毕竟，队列较短时，大家都很高兴。只有当队列积压，参加活动的队伍从门外绕到拐角时，人们才开始考虑吞吐量和优先级。

在本文中，我将探讨 Amazon 用以处理队列积压情况的策略 – 我们采用的设计方法可快速释放队列并确定工作负载的优先级。首先，我将介绍最重要的内容，如何防止队列积压。在前半部分我会介绍哪些情况会导致队列积压，然后，我会介绍 Amazon 用以避免积压或巧妙处理积压的诸多方法。

为了在本文中更好地阐述基于队列的系统，我将介绍两项 AWS 服务的后台工作原理：一项服务是 AWS Lambda，它通过执行代码响应事件，无需担心它运行的基础设施；另一项是 AWS IoT Core，这是一项托管服务，可让连接的设备轻松、安全地与云应用程序和其他设备交互。

通过 AWS Lambda，您可以上传函数代码，然后通过以下两种方法中的一种调用函数：

• 同步：函数输出在 HTTP 响应中返回
• 异步：HTTP 响应立即返回，且函数在后台执行并重试

Lambda 确保即使在服务器出现故障时也可以运行函数，因此它需要持久的队列来存储请求。使用持久队列，如果您的函数第一次运行失败，则可以重新发送请求。

借助 AWS IoT Core，设备可以与应用程序连接并可以订阅 PubSub 消息主题。当设备或应用程序发布消息时，具有匹配订阅的应用程序会收到自己的消息副本。由于受限的 IoT 设备不想消耗有限的资源，等待确保所有订阅的设备、应用程序和系统都收到副本，因此大部分 PubSub 消息传递都是异步进行的。这一点特别重要，因为当另一台设备发布其感兴趣的消息时，订阅的设备可能会处于离线状态。离线设备重新连接时，它希望先恢复速度，然后再将消息传输给它（如需了解如何在重新连接后对系统进行编码以管理消息传输，请参阅《AWS IoT 开发人员指南》中的 MQTT 持久性会话）。为了实现这一目的，我们在后台进行了多种持久性和异步处理。

像这样的基于队列的系统通常使用持久队列来实施。SQS 可提供持久、可扩展、至少一次的消息传递语义，因此包括 Lambda 和 IoT 在内的 Amazon 团队在构建可扩展异步系统时通常都会选择 SQS。在基于队列的系统中，一个组件通过将消息放入队列中来生产数据，而另一个组件通过定期请求消息、处理消息并在完成后最终将其删除来消耗该数据。

在 AWS Lambda 中，如果函数调用比正常慢（例如，由于依存项），或者如果它暂时发生了故障，那么任何数据都不会丢失，而且 Lambda 会重新尝试调用函数。Lambda 将调用进行排队，当函数再次开始工作时，Lambda 会处理函数的积压事务。但是，我们来看一下处理积压事务并恢复正常所需的时间。

假设某个系统在处理消息时出现了历时一小时的中断。无论给定的速率和处理能力如何，从中断中恢复都需要在恢复后的一小时内将系统容量增加一倍。实际上，系统的可用容量可能会超出所需容量（尤其是在使用 Lambda 等弹性服务时），因此恢复速度可能会更快。另一方面，在您处理积压事务时，您的函数所交互的其他系统可能还没有做好处理大量增加的积压事务的准备。发生这种情况时，可能需要更长的时间才能赶上进度。异步服务会在中断期间累积积压事务，从而导致恢复时间较长。而同步服务与异步服务不同，它在中断期间会舍弃请求，因而恢复速度更快。

多年来，在论及排队时，我们有时候会认为延迟对于异步系统来说并不重要。异步系统通常是为实现持久性而构建的，或者是为了避免直接调用方延迟而构建的。但实际上，我们已经发现处理时间其实很重要，而且我们通常甚至希望异步系统的延迟能够达到亚秒级或更短。当为提高持久性而引入队列时，面对积压时很容易忽略由此带来的如此高的处理延迟。异步系统的隐性风险在于处理大量积压事务。

对如何权衡可用性与延迟的讨论提出了一个有趣的问题：我们如何衡量异步服务的延迟和可用性并设定相关目标？ 从生产方的角度衡量错误率可让我们对可用性有一定的认识，但所知较少。生产方可用性与我们正在使用的系统的队列可用性成正比。因此，当我们基于 SQS 构建时，我们的生产方可用性与 SQS 可用性相当。

另一方面，如果我们在消耗方端衡量可用性，则可能会使系统的可用性看起来比实际情况要差，因为可能会重试故障，然后在下一次尝试中成功。

我们还可以通过死信队列 (DLQ) 衡量可用性。如果消息没有重试，则系统会将其舍弃或放入 DLQ 中。DLQ 只是一个单独的队列，用于存储无法处理的消息，以便后期进行调查和干预。舍弃的消息或 DLQ 消息的比率是一个很好的可用性衡量标准，但是发现问题时为时已晚。虽然可以设置 DLQ 卷警报，但是 DLQ 信息到达得太晚，我们无法完全依赖它来检测问题。

如何衡量延迟？ 同样，生产方观察到的延迟反映了我们队列服务本身的延迟。因此，我们将更多的精力放在衡量队列中消息的生命时长上。这样可以迅速发现系统落后或频繁出错以及导致重试的情况。每当消息到达队列时，SQS 等服务就会提供时间戳。根据时间戳信息，每当我们从队列中提取出一条消息时，我们就可以记录并生成系统落后程度的指标。

不过，延迟问题可能更微妙一些。毕竟，积压是可以预计的，而且事实上对某些消息来说是可以接受的。例如，在 AWS IoT 中，有时设备可能会离线或读取消息的速度较慢。这是因为许多 IoT 设备功率低且互联网连接不稳定。作为 AWS IoT Core 的运营商，我们需要能够区分由于设备离线或选择缓慢读取消息而导致的预期少量积压与系统范围内出现意外积压之间的区别。

在 AWS IoT 中，我们使用另一个指标对服务进行检测：AgeOfFirstAttempt。此衡量记录现在减去消息排入队列的时间，但前提是这是 AWS IoT 首次尝试将消息传递到设备。这样一来，在备份设备时，我们得到了一个纯粹的指标，该指标不会因设备重新尝试处理消息或排队而受到影响。为了使指标更加纯粹，我们发出了第二个指标 – AgeOfFirstSubscriberFirstAttempt。在 AWS IoT 等 PubSub 系统中，对于可以订阅特定主题的设备或应用程序的数量没有实际限制，因此，将消息发送给一百万个设备时，其延迟要比发送给单个设备时高。为了得到一个稳定的指标，我们会在第一次尝试向该主题的第一个订阅者发布消息时发出计时器指标。此外，我们还有一些其他标准，用以衡量系统发布剩余消息的进度。

AgeOfFirstAttempt 指标可作为系统范围内发生问题的早期警报，很大程度上是因为它可以筛选掉那些选择更慢地读取消息的设备的噪音。值得一提的是，像 AWS IoT 这样的系统，检测的指标远多于此。但是，在所有与延迟相关的指标均可用的情况下，Amazon 上通常使用的策略是将首次尝试的延迟与重试尝试的延迟分开进行分类。

由于请求在服务器之间来回跳转而且可能在各系统之外的地方发生延迟，因此衡量异步系统的延迟和可用性面临着不小的挑战，调试也并非易事。为了帮助进行分布式跟踪，我们在排队的消息中传播了一个请求 ID，以便可以将它们拼合在一起。我们通常也使用 X-Ray 等系统来帮助解决此问题。

许多异步系统都是多租户的，代表许多不同的客户来处理工作。这增加了管理延迟和可用性的复杂维度。多租户的优势在于，它节省了我们必须单独操作多个队列的运营开销，而且在运行组合工作负载时提升了资源利用率。但是，客户希望无论其他客户的工作负载如何，它都能够像自己的单租户系统一样，可以预计延迟并且可用性高。

在将消息放入队列时，AWS 服务不会直接向调用方公开其内部队列。而是实施轻量级 API 来对调用方进行身份验证，并将调用方信息附加到每个消息，然后再将消息排入队列。这类似于之前介绍的 Lambda 架构：异步调用函数时，Lambda 会将消息放入 Lambda 的队列并立即返回，而不是直接向您公开 Lambda 的内部队列。

这些轻量级 API 还使我们能够增加公平性限制。在多租户系统中，公平性很重要，可以确保任何客户的工作负载都不会影响其他客户。AWS 实现公平性的一种常见方式是对每个客户的速率进行限制，并灵活处理消息突增。在我们的许多系统中，例如在 SQS 中，随着客户逐渐增多，我们会提高每个客户的限制。这些限制可以在出现意外峰值时起到保护作用，让我们有时间在后台进行预置调整。

从某些方面来讲，异步系统中的公平性与同步系统中的限制有着异曲同工之道。但是，我们认为在异步系统中考虑这一点更为重要，因为大量的积压事务会很快堆积起来。

为了说明这一点，请想象一下，如果异步系统内置的“吵闹的坏邻居”保护不足，会发生什么情况。如果系统的一位客户流量突增，无法控制，并在系统内产生积压，操作员可能需要 30 分钟时间才能参与进来，了解发生的情况并缓解问题。在这 30 分钟内，系统的生产方端可能扩展良好并将所有消息排队。但是，如果排队消息的数量达到了消耗方所扩展容量的 10 倍，则意味着系统需要 300 分钟才能完成处理完积压并恢复。即使短时的峰值负载也可能导致数小时的恢复时间，从而导致数小时的中断。

实际上，AWS 中的系统具有许多补偿因素，可以最大程度地减少或防止队列积压带来的负面影响。例如自动扩展，它有助于减轻负载增加时带来的问题。但是，如果不考虑补偿因素而只看排队的影响也是具有积极作用的，因为这有助于设计在多个层面可靠的系统。 我们发现一些设计模式可以帮助避免队列大量积压和恢复时间过长：

• 在异步系统中，每一层的保护都很重要。 由于同步系统不希望出现积压，因此我们通过前门限制和准入控制来保护它们。而在异步系统中，系统的每个组件都需要保护自己免于过载，并防止一个工作负载消耗超出其资源的合理份额。总会有一些工作负载绕过前门准入控制，因此我们需要一个保护装置，以防止服务超载。
• 使用多个队列帮助调整流量。 在某些方面，单个队列和多租户彼此矛盾。当工作在共享队列中排队时，很难将一个工作负载与其他工作负载隔离。
• 实时系统通常使用类似 FIFO 的队列来实施，但更喜欢类似 LIFO 的行为。 据客户反映，当队列出现积压时，他们更倾向于立即处理新数据。有容量可用时，可以处理中断或激增期间堆积的任何数据。

Amazon 的系统使用多种模式，以确保多租户异步系统能够适应工作负载的变化。涉及的技术很多，但是整个 Amazon 中使用的系统也很多，每个系统都有自己的一系列活动性和持久性要求。在下一部分，我将介绍一些我们使用的模式，以及 AWS 客户在系统中使用的模式。

在某些系统中，我们不是让所有客户共享一个队列，而是为每个客户提供自己的队列。为每个客户或工作负载添加队列并不总是最划算的，因为服务轮询所有队列需要消耗资源。但是在客户较少的系统或相邻系统中，这种简单的解决方案可能会比较实用。另一方面，如果系统有数十甚至数百个客户，单独的队列就会显得比较臃肿。例如，AWS IoT 并不会对环境中的每个 IoT 设备使用单独的队列。在这种情况下，轮询成本无法很好地扩展。

在一个系统中，为每个 Lambda 客户轮询一个单独的队列成本高昂，AWS Lambda 就是一个很好的例子。但是，使用一个队列可能会导致本文中描述的某些问题。因此，AWS Lambda 不会使用一个队列，而是会预置固定数量的队列，并将每个客户哈希到少量队列。消息排入队列之前，它会检查哪些目标队列包含的消息最少，然后加入到该目标队列中。当某个客户的工作负载增加时，它将在其映射的队列中引发积压，但其他工作负载将自动从这些队列中路由出去。构建一些高效的资源隔离并不需要大量队列。这只是 Lambda 内置的诸多保护措施之一，但这项技术也应用于 Amazon 的其他服务。

从某些方面来说，队列出现积压后再为流量确定优先级为时已晚。但是，如果处理消息相对来说比较昂贵或费时，将消息移至单独的溢出队列中仍然是有必要的。在 Amazon 的某些系统中，消耗方服务会实施分布式限制，当它们将已超过配置速率的客户的消息排出队列时，会将这些多余的消息排入单独的溢出队列中，并从主队列中将其删除。一旦有资源可用，系统仍然可以处理溢出队列中的消息。本质上，这近似于优先级队列。有时在生产方端实施类似的逻辑。这样，如果系统从一个工作负载接收大量请求，则该工作负载不会将热路径队列中的其他工作负载挤出。

与分流过量流量类似，我们也可以分流时间久的流量。当我们将一条消息排出队列时，我们可以查看它的存在时间。除了记录存在时间之外，我们还可以利用这些信息来决定是否将消息移至堆积队列中。只有在处理完实时队列后，我们才会处理堆积队列。如我们需要在某个负载高峰摄取大量数据，但进度落后了，那么我们可以迅速将流量的波峰分流到另一队列中，速度如我们将流量排出队列再重新排入队列一样。与我们简单地按顺序处理积压队列相比，这可以释放消耗方资源，使其更快地处理新消息。这是一种近似 LIFO 的排序方法。

一些系统可以舍弃时间比较久的消息。例如，某些系统快速处理系统的增量，但也会定期执行完全同步。我们通常将这些周期性同步系统称为反熵清理工具。在这些情况下，如果消息是在最近一次清理前进入的，我们可以较低成本将其舍弃，而不用分流时间较久的排队流量。

就像在同步服务中一样，我们设计异步系统的目的是防止一个工作负载使用超出其合理份额的线程。对于 AWS IoT，我们还有一个方面未尚未讨论，那就是规则引擎。客户可以对 AWS IoT 进行配置：将消息从设备路由到客户的 Amazon Elasticsearch 集群、Kinesis Stream 等。如果这些客户资源延迟变慢，但是传入消息速率保持不变，则系统中的并发量将会增加。由于系统任何时候处理的并发量都是有限的，因此规则引擎可以防止任何一个工作负载消耗超出其合理份额的与并发相关的资源。

利特尔法则中是这样描述工作中的影响的：系统中的并发等于到达率乘以每个请求的平均延迟。例如，如果服务器以平均 100 毫秒的速度每秒处理 100 条消息，则平均将消耗 10 个线程。如果延迟突然增加到 10 秒，它将突然使用 1000 个线程（平均数，实际可能更多），这很容易耗尽线程池。

规则引擎运用多种技术来防止这种情况的发生。它使用非阻塞 I/O 来避免线程耗尽，虽然给定服务器的工作量还有其他限制（例如，内存、客户端通过连接时以及依存项超时时的文件描述符）。可以使用的第二个并发防护是信号量，它可以测量和限制可随时用于任何单个工作负载的并发量。规则引擎还使用基于速率的公平性限制。但是，由于工作负载随时间变化是完全正常的，因此规则引擎还可以随时间自动扩展限制，以适应工作负载的变化。此外，由于规则引擎是基于队列的，因此它充当了 IoT 设备与后台资源和安全限制自动扩展之间的缓冲。

在 Amazon 的所有服务中，我们为每个工作负载使用单独的线程池，以避免一个工作负载消耗所有可用线程。我们还使用 AtomicInteger 来限制每个工作负载允许的并发，并使用基于速率的限制方法来隔离基于速率的资源。

如果有工作负载导致了不合理的积压，消耗方的处理速度跟不上，我们的许多系统会自动开始更积极地拒绝生产方的工作。工作负载很容易堆积一整天的积压。即使隔离了该工作负载，它也可能出现意外，而且处理成本较高。这种方法的实施很简单，简单到偶尔测量工作负载的队列深度（假设工作负载在自己的队列上）并根据积压大小按比例调整入站限制（反向）即可。

如果多个工作负载共享一个 SQS 队列，这种方法实施起来就没有那么容易了。虽然有一个 SQS API 可以返回队列中的消息数量，但没有 API 可以返回具有特定属性的队列中的消息数量。我们仍然可以测量队列深度并相应地施加背压，但是这会对恰好共享同一队列的无辜工作负载施加背压，显然不公平。Amazon MQ 等其他系统的积压可见性更加精细。

并不是 Amazon 的所有系统都适用背压。例如，在为 amazon.com 执行订单处理的系统中，即使积压已久，我们也倾向于接受订单，而不是阻止接受新订单。当然，与之相随的是后台优先排序，因此最紧急的订单会优先处理。

当系统意识到需要减少特定工作负载的吞吐量时，我们会尝试对该工作负载使用回退策略。我们通常使用 SQS 功能实施这一策略，该功能会将消息的传递推后。当我们处理一条消息并决定将其保存以备稍后使用时，有时会将该消息重新排队到单独的激增队列中，但会设置延迟参数，以使该消息在延迟队列中保持几分钟隐藏状态。这样，系统就可以处理更新的数据了。

SQS 等队列服务对于可以向队列的消耗方传递多少动态消息，在数量上是有限制的。这与队列中可以存在的消息数（没有实际限制）不同，但是与消耗方队列一次处理的消息数相同。如果系统将消息排出队列，则该数字会增加，不过之后将无法删除这些消息。例如，我们已经看到了一些错误，这些错误使得代码在处理消息时无法捕获异常且忘记删除消息。在这些情况下，从 SQS 的角度来看，对于 VisibilityTimeout 的消息，消息仍然处于动态。在设计错误处理和过载策略时，请牢记这些限制，并倾向于将过量消息移至其他队列，而不是让它们保持可见状态。

SQS FIFO 队列具有相似的限制，但存在细微差别。使用 SQS FIFO，系统按顺序使用给定消息组的消息，但是其他组的消息并非按顺序处理。因此，如果在一个消息组中有少量的积压，我们将继续处理其他组中的消息。但是，SQS FIFO 仅轮询最近未处理的 20000 条消息。因此，如果消息组的子集中未处理的消息超过 20000 条，那么其他包含新消息的消息组就无法得到处理。

无法处理的消息会导致系统过载。如果系统将无法处理的消息排入队列（可能是因为它触发了输入验证边缘用例），则 SQS 可以通过将这些消息自动移至具有死信队列 (DLQ) 功能的单独队列来帮助解决这一问题。如果此队列中有任何消息，我们会发出警报，因为这意味着有错误需要我们修复。DLQ 的优势是，我们可以在修复错误后重新处理消息。

如果工作负载使足够的吞吐量达到以下状态：即使在稳定状态下，轮询线程也始终处于繁忙状态，则系统可能已经达到了一个没有缓冲区来吸收激增流量的状态。在这种状态下，传入流量的小幅峰值将导致持续的未处理积压，从而导致更高的延迟。我们计划在轮询线程中增加缓冲区，以解决此类突增问题。一种衡量标准是跟踪导致空响应的轮询尝试的次数。如果每次轮询尝试都检索不止一条消息，那么要么是轮询线程数量正合适，要么就是轮询线程不足，无法满足传入流量的需求。

当系统处理 SQS 消息时，SQS 给系统一定的时间来完成对消息的处理，然后假定系统崩溃，并将消息传递给另一个消耗方重试。如果代码继续运行并且忘记了此截止时间，则可能会多次并行发送同一条消息。当第一个处理器在超时后仍在处理消息时，第二个处理器将接收它并以类似的方式在超时后继续处理，然后是第三个处理器，依此类推。我们之所以实施消息处理逻辑以在消息过期时停止工作，或继续检测该消息以提醒 SQS 我们仍在处理它，就是因为这种级联断流的存在。这个概念类似于领导者选举中的租约。

这是一个隐患，因为我们发现系统的延迟可能会在过载期间增加，可能从查询到数据库所花费的时间更长，或者仅仅通过服务器承担超出其处理能力的工作。当系统延迟超过 VisibilityTimeout 阈值时，它将导致已经过载的服务本质上就是 fork 炸弹。

了解分布式系统中的故障确实很困难。包含检测内容的相关文章介绍了我们用于检测异步系统的几种方法，从定期记录队列深度到发布“跟踪 ID”以及与 X-Ray 集成。或者，当我们的系统具有超出普通 SQS 队列的复杂异步工作流程时，我们通常会使用 Step Functions 等其他异步工作流程服务，这类服务可以直观呈现工作流程并简化分布式调试。

在异步系统中，很容易忽略延迟的重要性。人们通常会认为异步系统有时候确实应该需要更长时间，因为它们前面有执行可靠重试的队列。但是，过载和故障情况可能会堆积大量难以解决的积压，导致服务无法在合理时间内恢复。导致积压的情况很多：可能源于意外以高速率排入队列的某个工作负载或客户，也可能因为处理工作负载变得比预期代价更高昂，或者源于依存项中的延迟或故障。

在构建异步系统时，我们需要关注并预测这些积压情况，并通过使用优先级划分、分流和背压等手段将积压降至最少。

• 排队论
• 利特尔法则
• 阿姆达尔定律
• Little A Proof for the Queuing Formula: L = λW, Case Western, 1961
• McKenney, Stochastic Fairness Queuing, IBM, 1990
• Nichols 和 Jacobson, Controlling Queue Delay, PARC, 2011