2022年3月29日
第20卷，第1期

通过关键路径追踪实现分布式延迟分析

CPT 可以提供可操作且精确的延迟分析。

Brian Eaton、Jeff Stewart、Jon Tedesco 和 N. Cihan Tas

对于包含功能和数据不断演变的服务的复杂分布式系统，将总体延迟保持在最低水平是一项具有挑战性的任务。关键路径追踪 (CPT) 是一种新的应用机制，用于收集大规模分布式应用程序中的关键路径延迟概况。它目前已在数百个 Google 服务中启用，为延迟分析提供有价值的日常数据。

快速的周转时间是在线服务的基本特征。对于不断支持不断增长的数据和功能的服务，将总体延迟保持在最低水平是一个持续存在的问题。确定分布式系统中高延迟的根本原因具有挑战性。目标是回答一个关键的优化问题：给定一个分布式系统和工作负载，可以优化哪些子组件来减少延迟？

低延迟是许多 Google 应用程序（如搜索⁴）的重要特征，延迟分析工具在维持大规模低延迟方面发挥着关键作用。系统不断变化，原因是代码和部署变更以及不断变化的流量模式。并行执行至关重要，无论是在服务边界之间还是在单个服务内部。不同的流量切片具有不同的延迟特性。延迟分析工具在实践中难以理解系统。

CPT 提供了关于大型复杂分布式系统中哪些子组件正在导致总体延迟的详细且可操作的信息。本文介绍了在特定应用程序 Google 搜索中使用 CPT 观察到的结果和经验。

关键路径追踪的需求

关键路径描述了直接导致通过分布式系统进行请求处理的最慢路径的有序步骤列表，优化这些步骤可以减少总体延迟。单个服务有许多子组件，CPT 依赖于软件框架¹⁵来识别哪些子组件在关键路径上。当一个服务调用另一个服务时，关键路径信息通过远程过程调用 (RPC) 元数据从被调用者传播回调用者。然后，调用者将其依赖项的关键路径合并到整个请求的统一关键路径中。

统一的关键路径与其他请求元数据一起记录。日志分析用于选择感兴趣的请求，然后聚合这些请求的关键路径以创建关键路径概况。跟踪过程是高效的，允许对大量请求进行抽样。生成的概况提供了关于分布式系统中延迟根本原因的详细而精确的信息。

总体目标是分布式系统的延迟分析。开发人员如何获得关于延迟根本原因的可操作信息？

示例系统

考虑图 1 中的分布式系统，该系统由三个服务组成，每个服务都有两个子组件。系统的目的是接收来自用户的请求，执行一些处理，然后返回响应。箭头显示请求的方向，响应以相反的方向发送回去。

Distributed Latency Profiling through Critical Path Tracing

系统在许多子组件之间分配工作。请求首先到达服务 A，服务 A 将请求处理移交给子组件 A1。A1 依次依赖于子组件 B1 和 A2，它们有自己的依赖项。某些子组件可以在请求处理期间多次调用（例如，A2、B2 和 C2 都调用 C1）。

即使系统架构从图中显而易见，系统的实际延迟特性也很难预测。例如，A1 是否能够并行调用 A2 和 B1，或者是否存在数据依赖性，使得对 B1 的调用必须在对 A2 的调用可以继续之前完成？A2 在调用 B2 之前执行多少内部处理？从 B2 收到响应后呢？这些请求中是否有任何重复的？每个处理步骤的延迟分布是多少？所有这些问题的答案如何随传入请求而变化？

如果没有这些问题的良好答案，改进整体系统延迟的努力将缺乏针对性，并可能付诸东流。例如，在图 1 中，为了减少 A1 及其下游子组件的总体延迟，您必须知道这些子组件中的哪些实际上影响了端到端系统延迟。在决定优化之前，您需要知道 𝐴1 → 𝐴2 是否真的重要。

使用 RPC 遥测进行分析

RPC 遥测通常用于延迟分析。服务导出关于 RPC 调用次数以及这些 RPC 的延迟特性的粗粒度信息。监控服务收集此信息并创建显示系统性能的仪表板。粗粒度切片（例如，时间范围、源和目标信息）通常用于增强基于 RPC 遥测的分析。^1,9,14

当只有少数几个 RPC 服务始终对延迟很重要时，RPC 遥测效果良好。监控这些服务可以快速识别哪些服务正在导致问题。可以识别服务所有者，他们可以努力提高性能。

然而，RPC 遥测在并行性方面存在困难。参考图，假设 A2 在等待来自 B2、C1 和 C2 的响应时执行 CPU 密集型工作。改进 B2、C1 和 C2 的延迟不会提高整体性能，因为 A2 在等待它们的响应时实际上并没有被阻塞。

重复的 RPC 也可能使监控变得混乱。也许 A2 正在向 C1 发出数百个请求。RPC 遥测可能显示平均延迟非常快，但数百个请求中的一个慢速 RPC 可能是整个系统速度缓慢的根本原因。⁷ RPC 遥测也无法判断这数百个请求是并行发生还是串行发生。这是理解这些请求如何影响延迟的重要信息。

异构工作负载也是 RPC 遥测的一个挑战，因为来自不同工作负载的数据点通常混合在一起。关于低容量但重要请求的信息丢失了。随着重要切片维度的数量增加，多样化工作负载的问题也随之增加。如果 A/B 实验显示延迟回归，则应分析实验的每个分支的延迟以识别根本原因。如果延迟问题出现在第 99 个百分位（即，在花费时间最多的前 1% 的请求中），则应仅分析那些非常慢的请求。

这种类型的工作负载切片对于 RPC 遥测来说很困难。大多数 RPC 遥测系统出于效率原因依赖于沿几个维度聚合数据。例如，每个进程可能按调用者聚合 RPC 数据，然后数据收集进一步聚合跨进程的数据。跨大量维度（例如，为每个 A/B 实验单独）收集数据通常是不可行的。延迟分析的感兴趣维度也需要在所有服务中提前定义和共享。例如，假设调用者想要根据客户端设备型号分析延迟。如果下游服务不知道设备型号信息，它们就无法提供按该维度切片的 RPC 遥测。

RPC 遥测在识别服务内的重要子组件方面存在困难。例如，A1 和 A2（服务 A 内的子组件）都向 B2 发出请求。服务 A 和服务 B 的遥测通常会将这些请求混合在一起，即使它们可能具有不同的延迟特性。这可能使得难以判断哪些请求需要优化。

RPC 遥测的最后一个主要问题是路灯效应：RPC 遥测照亮了系统的特定区域，因此您花费时间优化系统的该部分。与此同时，非 RPC 引起的延迟问题在黑暗中丢失了。

使用 CPU 性能分析器进行分析

CPU 性能分析很好地补充了 RPC 遥测。一旦 RPC 遥测识别出有问题的服务，CPU 性能分析可以帮助找出如何使该服务更快。收集并聚合带有函数调用堆栈的 CPU 样本，从而深入了解昂贵的代码路径。通常一次为一个服务收集概况，并且可能包括正在运行的请求类型和硬件概况计数器。^2,10,13

CPU 性能分析擅长识别服务内的特定昂贵子组件。在 CPU 时间导致总体延迟的情况下，CPU 性能分析可以帮助识别优化的位置。然而，许多影响 RPC 遥测的相同问题也导致了 CPU 概况的问题。缺乏关于并行性的信息意味着您无法判断 CPU 密集型工作是与 RPC 并行发生，还是与其他 CPU 密集型工作并行发生，还是实际上阻止了请求进度。异构工作负载也会导致问题：少量但重要的流量切片会淹没在噪声中。将 CPU 概况与来自分布式跟踪的关于并行性和请求元数据的信息结合起来可以解决这些限制，但是该技术的部署并不广泛。³

路灯效应也影响 CPU 性能分析：它更有可能让您专注于使用大量 CPU 的代码，即使该代码没有导致总体系统延迟。

使用分布式跟踪进行分析

延迟分析工具包中的最后一个常用工具是分布式跟踪。这种方法跟踪通过系统的各个请求，收集定时点和附加数据，因为这些请求被处理。聚合和分析跟踪以产生应用程序见解。^5,16,17

与 RPC 遥测和 CPU 性能分析不同，分布式跟踪可以很好地处理并行性和异构工作负载。收集关于所有跨服务请求的信息，包括定时点。可视化显示每个服务的工作何时开始和结束，以及哪些服务是并行运行的，哪些是串行运行的。

大多数分布式跟踪默认包括 RPC 边界的跟踪，但省略了服务子组件信息。开发人员可以根据需要添加子组件的跟踪。

工作负载切片以查找特别重要请求的跟踪也是可能的，尽管同样，开发人员需要手动标记重要的跟踪。分布式跟踪甚至允许自动分析以识别哪些服务导致总延迟。^5,18

使用分布式跟踪进行详细延迟分析的主要障碍是成本。在 Google 搜索中，单个服务可能只有几个或几十个 RPC 依赖项，但很容易有 100 倍于此数量的重要子组件。默认情况下对子组件进行检测会使跟踪的大小增加几个数量级。

分布式跟踪系统的采样率是另一个问题。系统运营商需要在他们使用分布式跟踪收集的数据量与他们这样做带来的开销之间做出权衡。随着跟踪变得更加详细，它变得更加昂贵。自适应采样技术^16,17有时用于提高有趣请求的采样率。如果任务是调查 1% 实验的第 99 个百分位延迟，则找到一个相关的例子需要 10,000 个跟踪请求。正如本文后面所示，可能需要 10,000 到 100,000 个例子才能获得关于回归发生位置的统计信心。总之，这意味着可能需要收集 10⁸ 到 10⁹ 个请求的完整跟踪，每个跟踪都比分布式跟踪系统默认预期的要大 100 倍。

关键路径追踪

CPT 旨在填补这些系统中的一些空白。项目管理¹²中的术语关键路径指的是完成项目必须完成的许多相互依赖的步骤。在本文中，关键路径描述了直接导致通过分布式系统进行请求处理的最慢路径的有序步骤列表。将这些跟踪聚合到关键路径概况中可以识别整个系统中的延迟瓶颈。

这种方法如今已广泛用于数百个 Google 服务（包括搜索）中的延迟分析，并具有以下几个优点。

软件框架用于自动检测服务子组件。¹⁵ 支持已添加到 Google 搜索中最常用的框架中，使用这些框架的开发人员无需额外的编码工作即可获得细粒度的 CPT。（稍后将讨论自动检测对总体关键路径精度的影响。）

框架检测代码自动识别请求执行的关键路径。仅保留关键路径用于分析；其他跟踪信息被丢弃。这使跟踪成本降低了几个数量级。

关键路径跟踪与其他请求和响应元数据（例如 A/B 实验信息以及搜索结果页面上出现的功能）一起记录。这允许标准日志分析技术使用业务标准来查找来自感兴趣请求的跟踪。集中日志记录提供了额外的成本节省。其他分布式跟踪系统为请求中涉及的每台机器单独记录跟踪。重建完整请求需要连接来自数百台机器的跟踪。将所有关键路径子组件一起记录避免了连接跟踪的开销。

总之，这些成本降低允许使用高采样率进行详细跟踪。

跟踪请求

本节介绍收集单个请求的细粒度关键路径跟踪所需的工作。

关键路径定义

对于延迟分析，使用的关键输入是关键路径：阻止生成响应的步骤集。当多个步骤并行进行时，最慢的步骤是关键路径上的唯一步骤。

请求的执行可以建模为命名节点（例如，子组件名称）的有向图。图中的每个节点都执行一些自己的计算。图中的每条边都是依赖关系，其中一个节点必须等待其一个依赖项完成才能继续计算。关键路径是通过节点的最长持续时间路径，从请求入口点开始，到计算响应的节点结束。关键路径的长度是处理请求的总延迟。

考虑图 1 中的分布式系统，并假设子组件根据图 2 中总结的场景并行执行。图 2a 显示了一个示例关键路径计算，其中对 B1 和 A2 的请求按顺序发生：A1 执行一些计算，然后阻塞，等待 B1 完成。然后 A1 继续进行额外的计算，然后等待 A2 完成。此示例的关键路径为 {A1=5 毫秒, B1=20 毫秒, A1=8 毫秒, A2=2 毫秒}，总关键路径为 35 毫秒。

图 2b 显示了当 B1 和 A2 并行执行时，这种情况如何变化。新的关键路径变为 {A1=5 毫秒, B1=20 毫秒, A1=8 毫秒}，总关键路径为 33 毫秒。A2 已从关键路径中移除。在这种情况下，优化工作应集中在 A1 和 B1 上。

当父节点与子节点重叠时，并行执行也适用，如图 2c 所示。在本例中，A1 向 B1 发送 RPC，但不会立即阻塞以等待响应。相反，A1 继续并行进行其他计算。对于这种情况，将分配给关键路径的节点是最后完成的节点：{A1=3 毫秒, B1=14 毫秒, A1=10 毫秒}

识别服务子组件

基础设施优先的分布式跟踪系统通常默认收集 RPC 边界的数据，并允许开发人员添加跟踪注释以进行更详细的跟踪。^16,17 使用 CPT，您可以利用软件框架提供的标准化来默认收集更详细的信息。¹⁵

例如，Dagger 框架鼓励作者将代码编写为 ProducerModules。（Dagger 是一个完全静态的编译时依赖注入框架，适用于 Java、Kotlin 和 Android。它是 Square 创建的早期版本的改编版，现在由 Google 维护；https://dagger.dev。）每个 ProducerModule 声明它需要哪些输入，以及它产生哪些输出。然后 Dagger 协调 ProducerModules 的执行以处理请求。回顾图 1，以下代码片段显示了子组件 A1 的 Dagger 实现

@ProducerModule public abstract class A1ProducerModule { @Produces @A1Output static A1Output runA1(@A2Output a2, @B1Output b1, @B2Output b2) { ... 代码从 a2、b1 和 b2 读取信息，并计算 A1Output... } }

ProducerModules 的集合创建了框架执行以处理请求的子组件图。对于此示例，框架知道 A2、B1 和 B2 中哪个是最后一个阻塞执行以产生 A1 输出的。由于框架知道子组件依赖关系，因此它可以记录关键路径。

对于 Google 搜索，子组件级别的跟踪是从多种编程语言的多个软件框架收集的。框架级别的实现对于可扩展性至关重要，因为它允许相对较小的开发团队为数千人编写的代码提供详细的关键路径跟踪。由于每个框架都自动检测和报告关键路径，因此大多数开发人员都不知道正在发生关键路径跟踪。一些未使用框架实现的服务也实现了特定于服务的 CPT。来自这些服务的跟踪粒度较粗。当向不提供任何跟踪的服务发出请求时，系统会优雅地降级。关键路径中盲点的大小被正确报告，并包括哪个服务负责关键路径的该部分。

有关显示 Google 搜索关键路径跟踪总体精度的指标，请参阅后面的“采用”部分。

传播和合并

将子节点路径传播到父节点允许更详细地查看请求关键路径。

在图 2b 中，初始关键路径为 {A1=5 毫秒, B1=20 毫秒, A1=8 毫秒}。B1 子节点占用了大部分执行时间；但是，缺少 B1 的内部执行细节。为了添加此细节，B1 首先计算自己的关键路径（例如，{B1=4 毫秒, B2=12 毫秒}），并将该关键路径返回给 A1。

然后 A1 将来自 B1 的关键路径合并到总体关键路径中。请注意，从 B1 返回的总关键路径仅为 16 毫秒，但 A1 观察到 B1 中的执行时间为 20 毫秒。这是正常的，可能是由于网络延迟、排队延迟或根本没有检测到返回关键路径信息的执行路径而发生的。为了解释这种差异，A1 向关键路径添加了一个 4 毫秒的“未说明”节点。类似地，每个子组件都向关键路径添加一个“self”节点，以表示内部发生的延迟，而不是由其他子组件引起的延迟。符号 𝑆1/𝑆2 表示 𝑆2 作为 𝑆1 的子组件而产生的延迟。

请求的合并关键路径为 {A1=5 毫秒, B1/self=4 毫秒, B1/B2=12 毫秒, B1/unaccounted=4 毫秒, A1=8 毫秒}。

此过程递归发生。如果 B2 返回更详细的路径，则总体路径中的 B2 条目也会变得更详细。

传播和合并发生在单个服务内部和跨 RPC 服务边界。RPC 传输支持 RPC 请求和响应元数据通道，用于传递水平关注点，例如 Dapper 中的跟踪标识符。¹⁷ 参与关键路径协议的服务使用响应元数据中的标准字段将其关键路径传播给调用者。然后，框架级别的代码将来自 RPC 的关键路径合并到每个服务的关键路径中。

传播需要纠错。测量误差在大规模分布式系统中是不可避免的：网络需要时间，程序停顿，错误存在或会随着时间的推移而添加，有时您无法确切地确定发生了什么。目标是使测量误差足够小，以便您仍然可以从延迟概况中得出良好的结论。

过度计数是最容易检测到的问题。当关键路径元素的总和超过请求的观察到的挂钟时间超过指定的误差范围时，就会发生这种情况。这通常表明生成关键路径的框架中存在错误（例如，由于将多个操作报告为串行发生，而它们实际上是并行发生的）。Google 的实现通过允许将过度计数合并到总体关键路径中来处理它。这允许发现哪些服务正在过度计数，以便可以修复它们。有关示例，请参阅本文后面的“幻影盲点案例”。

低估是预期的。RPC 的报告关键路径将小于观察到的挂钟时间，原因是序列化成本、网络传输时间和调度延迟。“未说明”子节点反映了差异。

盲点也是一个常见问题，尤其是在分析最近才出现在关键路径上的新代码路径时。盲点看起来像是关键路径上大块的时间，这些时间都归因于单个子组件。盲点的一个常见原因是向尚未实现 CPT 的慢速服务发出 RPC。

触发

根据框架实现，CPT 可能会产生显着的开销。实际上，并非每个请求都必须被跟踪，因此使用抽样来分摊成本。（稍后在本文中讨论开销和精度之间的权衡。）抽样需要跨服务协调，以避免在跟踪中创建不必要的盲点。

每个服务都可以做出独立的抽样决定，然后在请求元数据中传递其出站 RPC 的决定。与 Facebook 的 Mystery Machine⁵一样，当下游服务看到调用者已选择加入 CPT 时，下游服务也会启用跟踪。即使调用者未选择加入抽样，下游服务也可以自由跟踪和记录自己的关键路径。未请求抽样的调用者将忽略生成的跟踪。

Google 搜索还实现了一种一致的抽样机制，该机制极大地增加了分布式方式下多个服务之间的 CPT 抽样重叠。当服务器本地决定是否应为特定请求启用 CPT 时，会使用此系统，并且当存在断开的调用流（例如 CPT 功能服务器位于不具备 CPT 功能的服务器之后）时，此系统可最大限度地减少盲点。此机制使用 Dapper¹⁷ 跟踪标识符作为分布式协议的来源，并将此标识符转换为多个抽样桶。然后，每个服务通过检查请求是否属于其抽样策略的相应桶来做出抽样决定。

系统运营商可以选择加入特定请求的跟踪，而不是依赖随机抽样。这对于人工操作员需要收集跟踪以进行调试的情况很有用。当识别出一种特别慢的请求类型时，操作员会收集该请求的许多样本以获取概况数据。由于这些请求不是随机样本，因此默认情况下，它们会从稍后描述的聚合分析中排除。

CPT 的局限性

此处定义的关键路径对于解决查找罪魁祸首的问题很有用，但有一些局限性。

一般来说，任何延迟优化工作都应集中在关键路径上的子组件上。然而，与非关键路径子组件的资源争用也可能减慢关键路径的执行速度。

再次考虑图 2b，想象一下 A2 正在持有互斥锁或正在运行密集的计算，并导致关键路径代码中出现 CPU 饥饿。关键路径将显示部分资源饥饿问题：等待被阻塞资源的节点将出现在关键路径上。然而，罪魁祸首节点 (A2) 不会出现在关键路径上。专注于 CPU 和锁争用的性能分析器非常适合识别这些瓶颈。

关键路径也缺乏对总体执行的拖累和松弛¹²的可见性。拖累和松弛是基于优化单个步骤的关键路径潜在变化的度量。阻塞所有其他子组件的单个子组件具有较大的拖累：改进该子组件很可能提高总体执行时间。

当多个子组件并行运行时，它们具有很大的松弛：即使一个子组件变慢，它也可能不会影响总体时间。因果性能分析⁶ 使用实验驱动的方法，通过自动将延迟注入到不同的子组件中来识别余量，以确定它们的拖累和松弛。Quartz³ 旨在通过 CPU 性能分析识别具有高拖累的子组件。Mystery Machine⁵ 通过日志分析重建系统依赖关系图来识别子组件松弛。

流式传输是提高延迟的重要技术，但不幸的是，流式 API 的 CPT 尚不明确。服务可以返回结果流，允许在稍后结果准备就绪之前开始处理早期结果。双向流式传输（客户端和服务器来回发送多条消息）是一种更复杂的编程模型，但在某些情况下也对延迟有用。必须为这些操作仔细定义关键路径：段应在返回第一条消息时结束，还是在最后一条消息时结束？如果 API 的调用者也在流式传输怎么办？Google 搜索当前的 CPT 实现通过将关键路径段定义为在收到流的最后一条消息时结束来应对此挑战，但在早期消息对于延迟更重要的情况下，此定义具有误导性。

与大多数数据收集系统一样，CPT 收集和聚合的数据越多，提供的信息就越精确。聚合数据也可能隐藏关键细节。“聚合和可视化”部分讨论了聚合关键路径跟踪时发生的权衡。

即使存在这些警告，CPT 也有助于将精力集中在最有可能产生影响的领域。

采用

在采用 CPT 之前，Google 搜索中的延迟分析主要基于日志分析和 RPC 遥测。采用成本很低，因为默认情况下启用了 RPC 监控，但测量的粒度不足。日志分析可以正确识别延迟的微小变化；例如，可以通过 A/B 测试轻松检测到几毫秒的回归。识别哪个服务导致了回归具有挑战性，因为许多服务并行运行。识别服务内的哪个子组件导致了回归几乎是不可能的，因为没有系统地收集子组件对端到端延迟的贡献。

在整个 Google 搜索中广泛部署 CPT 已经大大提高了延迟根本原因的可见性。

图 3 通过比较各个关键路径元素的粒度与总体请求延迟，显示了 Google 搜索中 CPT 的粒度。

约 50% 的请求延迟归因于延迟低于 10 毫秒的子组件。曲线的这一部分显示了在支持细粒度跟踪的框架中编写的软件。当这些子组件中发生延迟回归时，通常不需要 CPU 性能分析器等辅助工具。仅 CPT 就足够精确以标记回归的根本原因。

粒度曲线的右侧表示盲点中产生的延迟：CPT 的粒度太粗，无法立即标记根本原因。在某些情况下，延迟回归发生在使用了尚未实现细粒度 CPT 的框架的 RPC 服务中。CPT 足以证明根本原因在于给定的 RPC 服务中的某个地方，但它无法自动识别罪魁祸首子组件。在其他情况下，CPT 已正确识别出关键路径上的慢速子组件。对这些子组件进行 CPU 性能分析通常可以找到减少延迟的机会。

运营成本

CPT 的运营开销非常低，以至于在许多应用程序（包括 Google 搜索）中，默认情况下启用了性能数据收集。对于搜索，会在 0.1% 的请求上持续收集跟踪。被跟踪的请求的平均延迟增加了 1.7%，从而使总体平均请求延迟增加了 0.002%。尾部开销仍然很低，被跟踪请求的第 99 个百分位延迟开销为 2.0%。

CPU 开销更难计算。框架被重写以在运行时集成 CPT。这些更改通常产生的 CPU 成本不到总体 CPU 成本的 0.1%，但框架开销取决于工作负载。与延迟性能分析的价值相比，CPU 开销被认为是可接受的。

网络开销非常显著，主要是因为线格式过于冗长。对于具有 𝑁 个元素且每个元素平均具有 𝑀 个子组件的关键路径，线格式使用 𝑂(𝑁 ∗ 𝑀) 内存。图形表示将以更低的成本编码相同的信息。实际上，网络开销通过仅采样 0.1% 的请求和通过压缩来缓解。

聚合和可视化

单个关键路径跟踪很有趣，但可能无法呈现系统整体性能的真实视图。单个请求可能是异常值。合并多个性能分析可以创建系统性能的具有统计意义的视图。

单个关键路径与关于请求的其他元数据一起记录。标准日志分析技术用于选择感兴趣的任何标准的随机请求样本。例如，Google 搜索的关键路径分析通常包括按 A/B 实验组进行切片、筛选以选择在搜索结果页面上显示某些 UI 元素的请求，以及筛选以选择来自特定时间范围和地理区域的请求。一种有效的方法是仅选择非常慢的请求。分析这些请求通常会揭示系统性问题，这些问题相当于重要的优化机会。

请注意，与分布式跟踪系统¹⁷不同，单个日志条目包含跨多个服务的关键路径。这对于正确性原因很重要：后端服务可以记录自己的关键路径，但他们无法先验地知道他们的工作是否会在其调用者的关键路径上。CPT 实现了关键路径合并机制，其中调用者将来自其后端的关键路径合并到他们自己的关键路径中。与从后端日志中连接信息的替代方法相比，这是一种更简单、更快速的方法。

聚合算法

Google 搜索用于聚合关键路径信息的技术与 CPU 性能分析中通常使用的机制类似。该过程通过将来自采样请求的关键路径合并到单个“平均关键路径”中来创建用于可视化和分析的性能分析，类似于 Mystery Machine。⁵ Google 搜索使用 pprof⁸ 进行可视化，但 CPT 是灵活的，可以与其他可视化工具结合使用。

以图 1 为例系统，其中接收到两个请求。表 1 显示了如何合并这两个请求以创建平均关键路径。在请求 1 中，A1 并行调用 A2 和 B1，并且只有 A2 在关键路径上。在请求 2 中，再次并行调用 A2 和 B1，但 B1 较慢且在关键路径上。通过合并具有相同路径的子组件，然后除以样本数量以保持度量相对于平均请求延迟，将这些聚合到单个性能分析中。

这种聚合可以被认为是整个系统的平均关键路径。对平均关键路径的解释需要记住，子组件不是顺序的，并且平均值可能无法反映系统可能采取的任何真实关键路径。如果并行调用两个子组件，则两者不可能在单个请求的关键路径上。但两者仍可能出现在平均关键路径上。

平均关键路径上的子组件时间反映了子组件在关键路径上的频率以及存在时的时长。在考虑通常很快但偶尔会变慢的系统子组件时，这种差异变得很重要。始终在关键路径上花费 5 毫秒的系统子组件将在聚合性能分析中显示为花费 5 毫秒。仅在 1% 的时间内在关键路径上，但在出现时花费 500 毫秒的系统子组件也将在聚合性能分析中显示为花费 5 毫秒。

与其他统计分析一样，查看样本池中数据的分布可能很有帮助。除了 pprof 格式的性能分析之外，聚合工具还收集关键路径段的延迟直方图。在 Google，我们在调查延迟问题时会尽早查阅这些数据。优化很少发生但速度非常慢的事情与优化频繁发生的事情是不同的问题。在特定子组件的延迟分布高度倾斜的情况下，额外的采样会有所帮助，以关注子组件速度较慢的情况。本文后面的“案例研究”部分讨论了几个事件，在这些事件中，重点分析使根本原因更加明显。

总关键路径的精度

我们需要多少个样本才能确信，一定大小的关键路径变化不是请求延迟随机变化的结果？中心极限定理可以计算各种样本大小的置信区间。表 2 显示了 Google 搜索性能分析的第 95 个百分位置信区间宽度的估计值。

实际上，当样本中包含数百万个请求时，性能分析可视化会变得非常慢。我们默认查看 100,000 个请求的样本，作为精度和性能分析工具可用性之间的折衷，并根据需要将采样增加到超过 100,000 个请求。

单个子组件精度

聚合的性能分析包含数千个子组件。这会造成一种情况，即使是第 95 个百分位置信区间也可能产生大量误报——即子组件似乎发生了统计上显著的延迟变化，但差异实际上是由随机变化引起的。误报会浪费工程时间，因为调查延迟变化不会找到根本原因。

衡量误报率的一种方法是使用相同的采样标准创建两个性能分析，然后使用 pprof 的差异基准视图比较生成的性能分析。差异基准视图突出显示性能分析之间的较大差异。当您事先知道性能分析应该是相同时，任何大于给定阈值的差异都是误报。

为了量化 Google 搜索的延迟性能分析误报率，我们对各种样本大小和各种阈值（用于考虑值得调查的足够重要的性能分析差异）重复了 100 次成对比较实验。表 3 显示了预期误报数量的第 95 个百分位置信区间。例如，如果性能分析比较基于每个性能分析 1,000 个请求，则您可以 95% 确信误报大于 5 毫秒的组件的平均数量在 0.2 到 0.4 之间。

在 Google 搜索中，由于随机变化，性能分析显示单个子组件出现较大差异的情况非常罕见。分析的另一个发现是，并非所有子组件都同样可能显示随机差异。具有较大平均时间和较大标准偏差的组件也具有较大的误报率。（中心极限定理预测了这一结果。即使子组件具有非正态延迟分布，但随着标准偏差的缩小和样本大小的增长，平均延迟的估计值也会变得更加精确。）

这一发现对搜索中的延迟调查具有重要的意义。识别 A/B 实验中延迟差异的根本原因非常简单，因为可以比较具有相同采样标准的两个性能分析。任何高于 1 毫秒的子组件级差异都可能是由实验引起的，而不是由随机变化引起的。当比较在不同工作负载上采集的性能分析时，根本原因分析要困难得多。在这些情况下，更大的样本大小不会使性能分析差异更清晰。性能分析之间的任何较大差异都可能是由不同的采样标准引起的，而不是随机变化。

可视化

一旦聚合了性能分析，就可以使用各种可视化来帮助工程师理解系统延迟。自上而下、自下而上、调用图和火焰图¹¹都很有用。图 4 显示了作为火焰图的 CPT 可视化示例，其中延迟关键路径表示为框列，每个框代表一个子组件。（每个框的颜色无关紧要，并且为了易于查看而进行了优化。）性能分析比较对于诊断回归至关重要，因为它们仅显示具有较大变化的子组件。这对于分析 A/B 实验中的回归尤其有帮助。

案例研究

在以下示例中，CPT 性能分析用于调试延迟问题。

非阻塞 RPC 的案例

识别优化机会的一种常用策略是查找异常请求。将选择一些高延迟阈值（例如，速度慢到给最终用户带来非常糟糕的体验）。然后，针对超出该阈值的请求进行延迟性能分析。有时，生成的性能分析只是证明一系列不寻常的事件可能会导致高延迟。在这种情况下，异常请求并非异常值：它们是多年来未被发现的模式的一部分。

一项延迟分析发现，单个常用查询的延迟比正常情况长几百毫秒。延迟性能分析显示对很少在搜索中使用的 API 的阻塞调用。该性能分析还识别出正在进行此调用的子组件，这足以表明该行为是由特定类型的搜索功能引起的，该功能在不到 10% 的请求中发生。进行了额外的性能分析，这次包括关键路径上显示此 RPC 的所有请求。

最初识别出的请求实际上并没有最初想象的那么异常：几乎所有触发此搜索功能的请求都受到了很大的延迟惩罚。此 RPC 在 18 个月前触发了瞬时警报，但它并不严重到需要彻底调查。

联系拥有相关代码的团队很有帮助：使用此 API 的最初意图是用于报告目的，事实上，此代码从未打算阻止请求处理。重构代码以进行实际的非阻塞 RPC 解决了该问题，并显著减少了受影响的搜索流量切片的延迟。

结论：将事件置于上下文中是有帮助的。如前所述，由于缺乏对流量切片的支持，RPC 遥测技术未能充分发挥作用。CPT 的流量切片功能帮助识别和解决了问题。

未运行的代码案例

在调查平均搜索延迟时，在某个特定服务中出现了一种常见模式。数千个子组件偶尔会被在关键路径上标识为框架的子组件阻塞，这表明关键路径延迟发生在框架中，而不是应用程序代码中。即使这些被阻塞的子组件大多很快，但少数子组件很慢；累积起来，它们代表了减少延迟的重大机会。

初步调查未能识别根本原因。对框架代码进行 CPU 性能分析未显示明显的问題。调查框架代码中延迟较高的受影响子组件也没有显示明显的模式，只是它们似乎很慢。实施了一些 CPU 优化，但都没有对延迟产生重大影响。

最终，一位工程师突然想到，问题不是框架使用了过多的 CPU；问题是框架应该使用更多的 CPU。几年前，有人发现每个请求的锁争用导致了严重的延迟问题。数十个 CPU 可能并行处理同一请求，并且正在竞争获取保护每个请求状态的锁。实验测试了每个请求的不同并行级别，结果表明，将单个请求限制为最多同时使用两个 CPU 是最佳的。由于减少了锁争用，该配置使用的 CPU 更少，并且降低了搜索延迟。

新的发现是，双 CPU 请求规则仅作为默认值是最佳的。某些子组件有大量 CPU 密集型工作要执行，并且可以从额外的并行性中获益，而不会增加锁争用。添加了一个新的框架功能，允许子组件请求将额外的 CPU 分配给它们的工作。该优化奏效了，现在在子组件显示大量框架时间时会例行应用。

结论：在针对延迟进行优化时，应首选延迟性能分析。CPU 性能分析、RPC 遥测和分布式跟踪都无法检测到这个特定问题，而延迟性能分析成功地发现了意外的延迟模式，并促使了进一步的调查。

幽灵盲点案例

在研究 CPT 中的盲点时，出现了一种令人担忧的模式。标记为deferredwork的子组件存在很大的盲点，并且对关键路径时间做出了重大贡献。研究代码表明，deferredwork 子组件正在积极开发中。它的目的是生成应添加到搜索结果页面底部的信息。搜索中的一种常见优化是首先生成应显示在结果页面顶部的信息，然后将该信息流式传输到客户端。deferredwork 子组件实际上是否也在阻止页面顶部的内容？

这种解释与数据不符：deferredwork 子组件通常显示在关键路径上花费超过一秒的时间。例行在搜索延迟中增加一秒钟会导致警报触发。将总请求延迟与关键路径延迟的总和进行比较，显示了真正的问题：关键路径时间远大于实际请求延迟。维护出现问题的服务的框架团队进行了调查，并确认 deferredwork 代码正在触发关键路径跟踪错误。

结论：更好的框架对流行为的支持是未来发展的方向。

慢速主页案例

监控显示，非常慢的主页加载频率有所增加。调查显示，问题始于几天前，最初的评估是问题很严重但不严重。直接原因是配置更改的推出。每次推出都将数百个独立的更改批处理在一起，并通过金丝雀流程运行它们，以确保它们是安全的。金丝雀已通过，这些更改已上线数天而未引起重大问题，因此未执行回滚。

然而，随着问题的调查，担忧情绪增加。实际上，问题比监控显示的更严重，因为问题不是随机的。大多数用户根本没有受到影响，但是特定地理区域中某些类型的设备上的用户正在经历高延迟。调查的紧迫性增加了。

配置推出中包含的任何更改似乎都不太可能导致该问题，因此根本原因很难确定。通常，地理区域中的延迟回归是网络问题导致的。但是，捕获问题的 Dapper 跟踪显示了相反的情况。RPC 很快，但是涉及的一个服务在为这些请求提供服务时使用了过多的 CPU。Dapper 跟踪的粒度太粗，无法捕获哪些子组件正在消耗 CPU。CPU 性能分析也没有帮助：触发问题的请求非常罕见，以至于它们在噪声中丢失了。

在调试的这一点上，问题随着另一次配置推出而神秘地消失了。调查继续进行，现在使用延迟性能分析来尝试找出发生了什么。进行了两个延迟性能分析，一个捕获正常主页请求，另一个捕获极慢的主页请求。

比较性能分析找到了罪魁祸首：一个负责短期特定区域主页更改的自定义系统正在阻止请求处理。再次审查配置更改显示，触发问题的推出包括一个新的主页自定义，并且主页自定义的计划结束时间与延迟问题的结束时间相吻合。

负责主页自定义的团队查看了该问题，并迅速确定了根本原因：“简单”配置已被自动化系统扩展为一组出乎意料的复杂配置规则。处理这些规则在每个触发它们的请求上都需要几秒钟的 CPU 时间。

结论：关注受影响的流量是延迟性能分析的关键。来自特定地理区域中特定类别设备的首页请求在 CPU 性能分析的噪声中丢失了。Dapper 跟踪可以显示问题，但无法关注导致问题的子组件。收集关注于受影响请求的细粒度延迟性能分析的能力发挥了作用。

未来工作

此处概述的方法是实用的并且可很好地扩展，但具有局限性。未来工作的一个领域是增加细粒度跟踪的采用率并减少性能分析中的盲点大小。这可能需要增加基于框架的编程模型的采用率。

将关键路径跟踪与 CPU 性能分析相结合可能是一个强大的工具。这项工作将非常具有挑战性，因为采样 CPU 性能分析器必然会在请求处理完成之前进行采样。关键路径直到请求完成时才知道，这可能在采样收集之后很久。找到一种方法将来自这些系统的数据连接起来，将使 CPU 性能分析器能够将开发人员的注意力集中在已知在关键路径上的代码上。

在流协议中添加框架级别的 CPT 支持将很有帮助。本文中描述的方法仅针对请求/响应 RPC 协议定义，这些协议创建调用节点的有向图，并且仅当这些 RPC 的所有关键工作都在请求到达和响应传输之间完成时才定义。生成增量进度的流协议或会话中具有多个请求和响应的会话协议更难分析。避免在使用流协议的性能分析中的盲点将很有帮助。

CPT 专注于服务器端延迟分析。添加对客户端延迟组件的支持（如 Facebook 的 Mystery Machine⁵所做的那样）将提高理解哪些端到端延迟贡献者对最终用户体验影响最大的能力。

CPT 用于识别服务子组件的框架集成具有延迟之外的性能分析应用。我们在 Google 搜索中构建了概念验证分布式成本性能分析器，允许下游系统将昂贵的流量跟踪到调用者中的特定子组件。这些成本性能分析是详细且有用的，但尚未推广到搜索之外使用。

最后，向跟踪收集添加元数据似乎既可行又有帮助。例如，框架可以为每个关键路径节点收集松弛信息。在节点被阻塞的情况下，框架可以收集有关导致延迟的争用资源的信息。在该领域继续研究应产生更多技术，以帮助进行延迟性能分析。

结论

在大型、真实的分布式系统中，现有的工具（如 RPC 遥测、CPU 性能分析和分布式跟踪）对于理解整个系统的子组件很有价值，但在实践中不足以执行端到端延迟分析。诸如高度并行的执行流、异构工作负载和子系统内复杂的执行路径等问题使延迟分析变得困难。此外，这些系统和工作负载经常变化。

没有任何团队或个人能够详细了解整个系统。

CPT 在此类系统中应对这些挑战，以提供可操作、精确的延迟分析。在框架级别¹⁵的集成提供了应用程序代码的详细视图，而无需每个开发人员都实现自己的跟踪。通用线协议允许用于触发、聚合和可视化的一致机制。高效的实现允许高采样率，即使对于相对罕见的事件也能提供精确的性能分析。可扩展且准确的细粒度跟踪使 CPT 成为许多 Google 应用程序（包括 Google 搜索）的分布式延迟分析的标准方法。

致谢

如果没有来自 Google 的许多贡献者，本文将不可能实现。来自搜索的 Fabian Gura、David German 和许多其他人构建了在 Google 搜索中实际实现此方法的工具和工具。Steven Procter 设计、实现和启动了第一个基于框架的 CPT 算法，证明了大规模收集细粒度跟踪是可能的。几个框架团队合作扩展了工作，以支持数千名开发人员。Michael Levin 的工作指导了统计精度分析。

我们感谢 Jennifer Klein、Łukasz Milewski、Ali Sheikh、Paul Haahr 和 Brian Stoler 提供了关于文章可读性和内容的 критический 反馈。Salim Virji 协调了发布过程。没有他的支持，本文的发布关键路径将会长得多。

参考文献

1. 亚马逊网络服务。Amazon CloudWatch：AWS 资源以及 AWS 和本地应用程序的可观测性；https://aws.amazon.com/cloudwatch/。

2. 亚马逊网络服务。什么是 Amazon CodeGuru profiler？；https://docs.aws.amazon.com/codeguru/latest/profiler-ug/what-is-codeguru-profiler.html。

3. Anderson, T.E., Lazowska, E.D. 1990. Quartz：用于调整并行程序性能的工具。载于 SIGMETRICS 计算机系统测量和建模会议论文集，115–125；https://dl.acm.org/doi/10.1145/98457.98518。

4. Arapakis, I., Bai, X., Cambazoglu, B.B. 2014. 响应延迟对 Web 搜索中用户行为的影响。载于第 37 届 SIGIR 国际信息检索研究与开发会议论文集，103–112；https://dl.acm.org/doi/10.1145/2600428.2609627。

5. Chow, M., Meisner, D., Flinn, J., Peek, D., Wenisch, T.F. 2014. Mystery Machine：大规模互联网服务的端到端性能分析。载于第 11 届 Usenix 操作系统设计与实现研讨会论文集，217–231；https://dl.acm.org/doi/10.5555/2685048.2685066。

6. Curtsinger, C., Berger, E.D. 2015. Coz：使用因果性能分析查找计数代码。载于第 25 届操作系统原理研讨会论文集，184–197；https://dl.acm.org/doi/10.1145/2815400.2815409。

7. Dean, J., Barroso, L.A. 2013. 大规模尾部。通讯 56(2), 74–80；https://dl.acm.org/doi/10.1145/2408776.2408794。

8. GitHub。pprof；https://github.com/google/pprof。

9. 谷歌。云监控；https://cloud.google.com/monitoring。

10. 谷歌。云性能分析器；https://cloud.google.com/profiler。

11. Gregg, B. 2016. 火焰图。通讯 59(6), 48–57；https://dl.acm.org/doi/10.1145/2909476。

12. Kelley., J.E. 1961. 关键路径规划和调度：数学基础。运筹学 9(3), 296–435；https://www.jstor.org/stable/167563。

13. 微软。使用 Application Insights 在 Azure 中分析生产应用程序；https://docs.microsoft.com/en-us/azure/azure-monitor/app/profiler-overview。

14. 微软。Azure Monitor；https://azure.microsoft.com/en-au/services/monitor/。

15. Nokleberg, C., Hawkes, B. 2021. 最佳实践：应用程序框架。acmqueue 18(6), 52–77；https://queue.org.cn/detail.cfm?id=3447806。

16. Pandey, M., Lew, K., Arunachalam, N., Carretto, E., Haffner, D., Ushakov, A., Katz, S., Burrell, G., Vaithilingam, R., Smith, M. 2020. 构建 Netflix 的分布式跟踪基础设施。Netflix 技术博客；https://netflixtechblog.com/building-netflixs-distributed-tracing-infrastructure-bb856c319304。

17. Sigelman, B.H., Barroso, L.A., Burrows, M., Stephenson, P., Plakal, M., Beaver, D., Jaspan, S., Shanbhag, C. 2010. Dapper，大规模分布式系统跟踪基础设施。Google 技术报告；https://static.googleusercontent.com/media/research.google.com/en//archive/papers/dapper-2010-1.pdf。

18. Yang, C.-Q., Miller, B. 1988. 并行和分布式程序执行的关键路径分析。载于第 8 届国际分布式计算系统会议论文集。IEEE 计算机学会出版社，366–375。

Brian Eaton 于 2007 年加入 Google 信息安全团队，担任软件工程师，专注于可用安全性与身份验证。从 2014 年开始，他加入 Web 搜索部门，领导工程效率和性能团队，开发延迟性能分析和 Web 搜索中的首批微服务部署。他现在在搜索质量和用户信任方面工作，帮助用户了解他们在 Web 上找到的信息的来源和背景。他拥有加州大学圣克鲁斯分校的学士学位，并且是一名半职业足球运动员。

Jeff Stewart 在 Google 工作了超过 17 年。在超过 10 年的时间里，他改进了 Web 搜索，领导团队提高计算效率和最终用户延迟。他领导了默认在搜索流量上启用 https 的倡议。Jeff 帮助推出了 Gmail。他于 2021 年跳槽到一家新公司。他获得了位于宾夕法尼亚州匹兹堡的卡内基梅隆大学的电气与计算机工程学士学位和信息网络硕士学位。他拥有美式 Kenpo 空手道黑带。他住在波士顿附近。

Jon Tedesco 在 Google 的 Web 搜索基础设施部门工作了 9 年。在此期间，他领导了多个团队为搜索堆栈构建延迟和计算分析工具，并开发了专注于性能分析和优化的搜索基础设施新组件。他拥有伊利诺伊大学厄巴纳-香槟分校的计算机科学硕士和学士学位。

N. Cihan Tas 是 Google Stadia 团队的站点可靠性软件工程师，目前专注于数据中心网络的优化。在加入 Google 之前，他曾在西门子公司研究院从事无线网络领域的工作，范围广泛，从车辆到车辆网络到智能电网通信网络。他拥有比尔肯特大学的学士学位，以及马里兰大学帕克分校的硕士和博士学位，所有学位均为计算机科学专业。N. Cihan 是会员。

最初发表于 Queue vol. 20, no. 1—
在数字图书馆中评论本文

更多相关文章

David Collier-Brown - 你对带宽一窍不通
当您的员工或客户说他们的互联网性能很差时，带宽可能不是问题。一旦他们拥有大约 50 到 100 Mbps 的带宽，问题就是延迟，即 ISP 路由器处理他们的流量需要多长时间。如果您是一家 ISP 并且所有客户都讨厌您，请振作起来。这现在是一个可以解决的问题，这要归功于一群专门的人员，他们追捕、消灭了它，然后在家庭路由器中验证了他们的解决方案。

Geoffrey H. Cooper - 使用 FDO 和不受信任的安装程序模型进行设备入网
设备的自动入网是处理正在安装的越来越多的“边缘”和 IoT 设备的重要技术。设备的入网与大多数设备管理功能不同，因为设备的信任从工厂和供应链转移到目标应用程序。为了加快自动入网的速度，供应链中的信任关系必须在设备中形式化，以允许自动化过渡。

David Crawshaw - 一切 VPN 都焕然一新
VPN（虚拟专用网络）已有 24 年的历史。这个概念是为与我们今天所知的互联网截然不同的互联网创建的。随着互联网的增长和变化，VPN 用户和应用程序也在增长和变化。VPN 在 2000 年代的互联网中经历了尴尬的青春期，与其他广泛流行的抽象概念交互不良。在过去的十年中，互联网再次发生了变化，而这个新的互联网为 VPN 提供了新的用途。一种全新的协议 WireGuard 的开发，提供了一种构建这些新 VPN 的技术基础。

Yonatan Sompolinsky, Aviv Zohar - 比特币的潜在激励机制
激励机制对于比特币协议的安全性至关重要，并有效地驱动其日常运行。矿工们竭尽全力最大化他们的收入，并且经常找到创造性的方法来实现这一目标，这些方法有时与协议相悖。加密货币协议应建立在更强大的激励机制基础上。还有许多领域有待改进，从挖矿奖励的基本原理以及它们如何与共识机制互动，到矿池中的奖励，一直到交易费用市场本身。