..

Google Dapper

1-Abstract

现代互联网服务通常是用复杂的，大规模的分布式集群来实现的。这些服务通常由不同的软件模块组成，而这些模块可能由不同的团队开发，使用不同的编程语言，也有可能分布在数千台机器上，横跨多个数据中心。因此，需要一些可以帮助理解系统行为，用于分析性能问题的工具。

Dapper 是 Google 生产环境下分布式跟踪系统，满足了低消耗（low overhead），应用层透明（application-level transparency），大范围部署（ubiquitous deployment on a very large scale system）三个需求。

2-Introduction

构建 Dapper 的目的是为了给开发者提供更多关于复杂分布式系统的行为信息。这类系统特别受关注，因为那些大规模的低端服务器，作为互联网服务的载体，是一个特殊的经济划算的平台。为了在上下文中理解分布式系统的行为，就需要监控那些横跨了不同的应用、不同服务器之间的操作。

网络搜索的例子将会说明此类监控系统需要解决的一些挑战。

  • 一个前端服务可能会将一次网络查询分发给数百个查询服务器，每一个查询都有自己的 Index。查询请求也可能被发送到多个子系统中，这些子系统也许用来处理广告，拼写检查，或者查询图片，视频，新闻等特殊结果。对这些服务的返回结果选择性地组合到结果页面；这种搜索模型被称为全局搜索（universal search）。

总的来说，一次全局搜索查询可能需要数千台机器，多个不同的服务参与处理。同时，用户对搜索延迟是比较敏感的，任何子系统的低性能都可能会导致延迟增大。

只看整体的延迟，工程师可能会知道全局搜索流程存在问题，但是可能无法判断哪个服务存在问题，或者为什么性能较差。原因可能有：

  • 无法准确知道此次全局搜索涉及哪些服务
  • 工程师对涉及的服务并不总是很了解
  • 涉及的服务或者机器可能同时被其他客户端访问，所以性能问题可能是由于其他应用的影响

上述描述的案例给出了 Dapper 的两个基本要求：1. 无处不在的部署；2. 持续的监控。

  • 无处不在的特性是很重要的，因为如果某个系统的很小一部分没有被监控到，那么追踪系统的可用性就会被严重影响
  • 另外，监控需要一直开启，因为经常会遇到很难或不可能重现异常或值得注意的系统行为

这些要求产生了三个具体的设计目标：

  1. 低消耗（low overhead）：追踪系统应该对正在运行的服务产生可以忽略不计的性能影响。对于某些高度优化后的服务来说，即使很小的监控负载也能被察觉到，有可能会迫使业务团队将监控系统关闭。
  2. 应用层透明（application-level transparency）：开发人员不需要感知到追踪系统的存在；一个依赖应用层开发人员积极合作才能有序运行的追踪系统会变得很脆弱（不可靠），可能会由于机器的问题或者代码的疏忽导致整个系统中断，从而违反普遍存在的要求。在像我们这样的快节奏开发环境中，这一点尤其重要。
  3. 可扩展性（scalability）：该系统必须能够处理 Google 接下来几年的服务和集群的规模。

一个额外的设计目标是，对于用于分析的数据，在其生成之后需要尽可能快地可以得到，理想的时间是一分钟内。

尽管基于数小时数据的追踪分析系统也是有一定的价值，但是最新数据的可用性能够使得对产生的异常有更快的反应。

真正的应用级透明设计目标也许是最大的挑战：通过把核心跟踪代码做的很轻巧，然后把它植入到那些无所不在的公共组件中，比如线程调用、控制流以及 RPC 库来实现该目标。通过使用自适应采样来使系统更具可扩展性，同时降低性能开销。结果展示的相关系统也包含一些用来收集跟踪数据的代码，用来图形化的工具，以及用来分析大规模跟踪数据的库和 API。

3-Distributed Tracing in Dapper

分布式服务的追踪系统需要记录一次特定请求后系统中所有完成的工作信息。

下图给出了一个示例，一个与五台服务器相关的服务，包括一个前端（A），两个中间层（B，C），两个后端（D，E）。

  • 当一个用户请求到达前端时，发送两个 RPC 请求到 B，C。B 可以立即响应，但是 C 需要与后端的 D，E 交互之后再响应 A，最后由 A 来相应最初的请求。

对这样的请求，一个简单实用的分布式追踪系统的实现，就是为服务器上每一次发送和接收动作收集信息标识符（message identifier）和事件时间戳（timestamped event）。

为了将所有记录条目与特定的请求发起者关联起来并记录所有信息，有两种解决方案：

  1. 黑盒（black-box）模型
    • 假设除了上述消息记录外没有其他额外信息，使用统计回归技术推断两者之间的关系
    • 缺点：由于依赖统计推断，为了获得更高的准确性，就需要更多的数据
    • 优点：比基于标注的模型更加轻便
  2. 基于标注（annotation-based）的模型
    • 依赖应用或者中间件明确标记一个全局 ID，从而将每条消息记录与原始请求连接起来
    • 缺点：需要代码植入

在 Google 的开发环境中，所有的应用程序都是用同一种线程模型，控制流与 RPC 系统，因此可以把代码植入限制在一个很小的通用组件库中，实现一套对开发人员有效透明的监控系统。

我们倾向于将 Dapper 追踪系统看作类似嵌套在 RPC 调用的树形结构。 然而，我们的核心数据模型并不局限于特定的 RPC 框架，还需要追踪其他活动，如 Gmail 中的 SMTP 会话、来自外部的 HTTP 请求以及 SQL 查询。 形式上，我们使用 Trees, Spans & Annotations 对 Dapper 追踪系统进行建模。

3-1 Trace trees and spans

在 Dapper 追踪树中，树节点是 Span 的基本工作单元。节点之间的连线表示一个 Span 与其父 Span 之间的因果关系。不过，Span 在更大的树形结构中是相对独立的，一个 Span 就是简单的时间戳日志，记录了 Span 的开始时间与结束时间。

下图说明了多个 Span 如何组成更大的追踪树。

Dapper 记录了每个 Span 的 Name，ID，Parent ID，以便在单个分布式追踪链路中重建各个 Span 的因果关系。

  • 没有 Parent ID 的 Span 被称为 Root Span
  • 一个追踪链路上的所有 Span 共享一个公共 Trace ID（全局唯一的 64 位整数；图中并未展示）

在一个典型的 Dapper 追踪链路中，期望将每一个 RPC 调用对应一个单一的 Span，每一个额外的组件层都对应一个额外的树形结构的层级。

补充，即每个 Span 看作一次 RPC 调用；每一层看作一个额外的组件

下图给出了典型 Dapper Trace Span 中记录事件（log event）更详细的视图。

该图描述了图 2 中两个 RPC（Helper.Call）调用中跨度较长 Span

Span 的开始时间（start time），结束时间（end time）以及任何 RPC 调用中的计时信息（timing information）都是由 Dapper 的 RPC 组件库记录的。

如果应用程序开发者想要在 Trace 中添加自定义的注释（annotation, 如图中的 “foo”）以记录业务信息，这些信息也会和其他 Span 数据一样被记录下来。

值得注意的是，一个 Span 可以包含来自多个主机（host）的信息。事实上，每个 RPC Span 都包含来自客户端与服务端进程的信息，这使得链接两个主机（two-host）的 Span 成为最常见的类型。

由于客户端进程与服务端进程的时间戳（timestamp）来自不同的主机，因此我们必须要注意时钟漂移（clock skew）。在我们的分析工具中，我们利用了这样一个事实，即 RPC 客户端总是在服务端接收请求之前发送请求，反过来对服务端响应流程也是一样。 这样，我们可以得出 RPC 服务器端 Span 时间戳的下限和上限。

3-2 Instrumentation points

Dapper 可以通过几乎零侵入成本来实现对分布式路径的追踪（基本完全依赖于少量组件库的改造）常见的植入点有：

  • 当一个线程处理一个被追踪的路径时，Dapper 会将追踪上下文（context）附加到线程本地（thread local）存储。追踪上下文是一个轻量且易于复制的 Span 属性容器，这些属性包括 Span ID, Trace ID
  • 当计算过程是延迟调用或是异步的，大多数 Google 开发者通过线程池或其他执行器，使用一个通用的控制流库来回调。Dapper 确保所有这样的回调可以存储这次跟踪的上下文，而当回调函数被触发时，这次跟踪的上下文会与适当的线程关联上。在这种方式下，Dapper 可以使用 Trace ID 和 Span ID 来辅助构建异步调用的路径
  • 几乎所有的 Google 进程间通信都是建立在一个 RPC 调用框架上，支持 C++ 与 Java。我们已经使用该框架来定义所有 RPC Span。对于被追踪的 RPC，Span ID 与 Trace ID 会从客户端发送到服务端。像这样在 Google 内部被广泛使用的，以 RPC 通信为基础的系统，这是一个重要的植入点。我们计划在非 RPC 通信框架中找到用户群并对其进行植入

Dapper 的追踪数据是语言无关的（language-independent），许多追踪数据同时包含了来自 C++ 与 Java 编写的进程。

3-3 Annotations

上述植入点足以推导出复杂分布式系统的追踪细节，使得 Dapper 核心功能可以应用于未经改造的 Google 应用。然而，Dapper 还允许用户添加额外的信息来丰富 Dapper 追踪数据，这些被添加的信息可以用来监控更高级别的系统行为或者用于问题调试。

我们允许用户通过简单的 API 定义带时间戳的 Annotation（timestamped annotations），核心用法如下：

Annotation 中可以包含任意内容

为了避免用户过度添加 Annotation 记录，每个 Dapper Span 都有一个可配置的 Annotation 总量上限。

需要注意，不管应用程序行为如何，应用层面的 Annotation 都不能代替用于表示 Span 结构的信息或者 RPC 信息

除了简单的文本 Annotation，Dapper 还支持 Key-Value 型 Annotation，可以为用户提供更多的追踪能力，如维护计数器，记录二进制信息，在进程内传输任意用户定义数据以及跟踪请求。

  • Key-Value 型 Annotation 用来在分布式追踪的上下文中定义某个特定应用程序的相关类型。

3-4 Sampling

低负载（low overhead）是 Dapper 的一个关键设计目标。

  • 如果对服务性能有重大影响，那么用户是不愿意部署使用的。
  • 我们希望允许用户使用 Annotation API 而不用担心额外的性能开销。
  • 我们也发现有些 Web 服务确实对植入带来的性能开销比较敏感。

因此，除了使 Dapper 收集的基本植入性能开销尽可能小之外，我们还通过仅记录所有追踪的一小部分来进一步控制性能开销。

3-5 Trace Collection

Dapper 追踪记录和收集是三阶段（three-stage）处理流程。

  1. Span 数据被写入本地日志文件
  2. Dapper 守护进程及收集组件把这些数据从所有主机中拉取出来
  3. 收集到的数据被写入 BigTable 仓库中

一次 Trace 被设计成 Bigtable 中的一行，每一列相当于一个 Span。Bigtable 支持稀疏表格的布局正适合这种情况，因为每一次跟踪可以有任意多个 Span。

Trace 数据收集（即从应用中的二进制数据传输到中央仓库所花费的时间）的延迟中位数少于 15 秒。TP98 延迟往往随着时间的推移呈现双峰型；大约 75% 的时间，TP98 延迟时间小于 2 分钟，但是另外大约 25% 的时间，可以增涨到几个小时。

Dapper 还提供了一个 API 来简化访问 BigTable 仓库中的 Trace 数据。 用户通过该 API，可以构建通用和特定应用程序的分析工具。

3-5-1 Out-of-band trace collection

Dapper 通过请求树实现 Trace 数据（in-band）及带外数据（out-of-band）收集。这么做是出于两个不相关的原因：

  1. 带内数据（in-band）收集方案会影响应用程序的网络动态：Trace 数据会在 RPC 响应头中携带。在 Google 的许多大型系统中，一次 Trace 中包含数千个 Span 是很常见的。然而，RPC 响应仍可能相对比较小，经常小于 10KB。这样， Dapper 带内的 Trace 数据会让应用程序数据和倾向于使用后续分析结果的数据量相形见绌，并使后续分析的结果产生偏差。
  2. 带内数据收集方案假设所有 RPC 调用都是完美嵌套的。我们发现，在所有后端系统返回最终结果之前，有许多中间件会把结果返回给他们的调用者。带内收集系统是无法解释这种非嵌套的分布式执行模式的。

带外数据：传输层协议使用带外数据(out-of-band，OOB)来发送一些重要的数据,如果通信一方有重要的数据需要通知对方时,协议能够将这些数据快速地发送到对方。为了发送这些数据，协议一般不使用与普通数据相同的通道,而是使用另外的通道。

这里指的 in-band 策略是把跟踪数据随着调用链进行传送，out-of-band 是通过其他的链路进行跟踪数据的收集，Dapper 的写日志然后进行日志采集的方式就属于 out-of-band 策略

4-Managing Tracing Overhead

追踪系统的成本被认为包含：

  1. 由于追踪数据生成和收集开销而导致的被监视系统的性能下降
  2. 存储和分析跟踪数据所需的资源量

尽管有人会说有价值的追踪系统值得性能损耗，但是我们仍相信如果基线开销可以忽略不计，那么将会极大的促进业务使用率

接下来将主要介绍 Dapper 植入操作的开销，Trace 数据收集的开销，以及 Dapper 对业务负载的影响。同时，还会介绍 Dapper 自适应采样机制如何平衡低性能损耗的需求与对代表性 Trace 追踪的需求。

4-1 Trace generation overhead

Trace 生成开销是 Dapper 性能损耗中最关键的部份，因为 Trace 数据收集及分析可以在紧急情况下被关掉。

Trace 生成开销主要来源有以下几点：

  • Span 的创建及销毁
  • 将 Span 信息记录到本地磁盘，以便后续收集

Root Span 创建及销毁平均需要 204 ns，非 Root Span 创建及销毁需要 176 ns；差别的原因是 需要给 Root Span 分配一个全局唯一的 Trace ID

如果不对 Span 进行追踪采样，那么额外的 Span Annotation 成本几乎可以忽略不计，包括 Dapper 运行时线程本地查找（平均耗时 9ns）。如果对 Span 进行追踪采样，那么会用字符串文本进行注释追踪 ???。

If it is sampled, annotating the trace with a string literal

将 Span 数据写入本地磁盘时 Dapper 运行时库最昂贵的操作，但是这部分损耗被大大减少，因为日志写入操作相对于被追踪的应用程序时异步执行的。然而，日志写入操作会对高吞吐量应用程序性能产生明显影响，尤其是在所有请求都被追踪的情况下。

4-2 Trace collection overhead

读取本地 Trace 数据也会对被追踪的前台应用负载有影响。下表展示了压力测试情况下 Dapper 守护进程的 CPU 使用率。

Dapper 守护进程在数据收集期间 CPU 使用率不超过 0.3%，并且内存占用非常小。同时我们也会将 Dapper 守护进程的内核调度优先级设置的尽可能低，以防止在高负载的主机中出现 CPU 争用的情况

Dapper 也是一个轻量级的带宽资源消费者，每个 Span 平均为 426 Byte；Dapper 数据收集流量仅占 Google 生产环境网络流量的不到 0.01%。

4-3 Effect on production workloads

有些请求都会涉及到大量高吞吐量的线上服务，这是对有效追踪最主要的需求之一；这些请求往往会生成大量的追踪数据，同时它们对性能干扰也最敏感。在下表中，我们使用网络搜索集群作为这类服务的一个示例，当我们改变 Trace 采样率时，评估 Dapper 对平均延迟与吞吐量的影响。

可以看到，虽然对吞吐量的影响不是很明显，但是为了避免明显的延迟增加，Trace 采样确实很有必要。在实践中我们发现，即使使用 1/1024 的采样率，对于请求量大的服务仍然能够产生足够的 Trace 数据。

将 Dapper 的基线开销降低很重要，因为用户可以使用全部范围的 Annotation API，而不必担心性能损耗。使用低采样率还有一个额外的好处，Trace 数据可以在主机被回收之前在磁盘上保存更长的时间，这为数据 Trace 数据收集设施提供了更大的灵活性。

4-4 Adaptive sampling

Dapper 进程开销与单位时间处理 Trace 数据量成正比。Dapper 第一版对 Google 内所有进程使用统一的采样率 (1/1024)，这个简单的方案对高吞吐量的在线服务很有效，因为绝大多数我们感兴趣的事件可能经常会出现，足以被捕获。

然而，有些低吞吐量（低负载）的服务可能会在低采样率的情况下错过一些重要的事件；同时，这类服务可以容忍高采样率带来的性能损耗。对于这类系统，解决方案是覆盖默认的采样率；对于这种需要手动干预的情况是我们在 Dapper 中力求避免的。

我们正在部署一种自适应采样模型，该方案不是采用统一的采样率参数，而是使用一个采样期望率来标识单位时间内的采样。这样，低流量的服务会自动提高采样率，而高流量的服务会自动降低采样率，从而使采样开销保持在可控的范围内。

4-5 Coping with aggressive sampling

新的 Dapper 用户经常想知道低采样率是否会干扰他们的分析（在高吞吐量的服务下经常低至 0.01％）。Google 的经验让我们相信，激进的采样（aggressive sampling）并不会妨碍重要的分析：如果一个值得注意的时间在一个系统中出现一次，那么它将会出现很多次。对于流量比较小的服务（每秒处理几十个请求，而不是几万个请求），可以接受对每个请求进行监控。这就是我们决定采用自适应采样率的原因。

5-Experiences

Dapper 在 Google 内部被广泛应用，一部分直接通过 Dapper 的用户界面，另一部分间接地通过对 Dapper API 的二次开发或者建立在基于 API 的应用上。在本节中，我们并不打算罗列出每一种已知的 Dapper 使用方式，而是试图覆盖 Dapper 使用方式的“基本向量”，并努力来说明什么样的应用是最成功的。

5-1 Using Dapper during development

Google AdWords 系统是围绕一个关键词定位准则和相关文字广告的大型数据库搭建的。当新的关键字或广告被插入或修改时，它们必须通过服务策略术语的检查（如检查不恰当的语言）；这个过程如果使用自动复查系统来做的话会更加有效。

当设计一个 Ads Review 服务时，这个团队迭代的从第一个系统原型开始使用 Dapper，并且最终用 Dapper 一直维护着他们的系统。Dapper 帮助他们从以下几个方面改进了他们的服务：

  • 性能（performance）：开发人员针对请求延迟的目标进行跟踪，并对容易优化的地方进行定位。Dapper 也被用来确定在关键路径上不必要的串行请求（通常来源于不是开发者自己开发的子系统）并促使相关团队持续修复。
  • 正确性（correctness）：Ads Review 服务围绕大型数据库系统搭建。系统同时具有只读副本（访问成本低）和读写主节点（访问成本高）两种方式。Dapper 用于识别一些不必要地向主节点而不是副本发出查询的情况。
  • 理解性（understanding）：Ads Review 查询跨越了各种类型的系统，包括 BigTable，以及其他各种 C++，Java 后端服务。Dapper 数据追踪可以用来评估总查询成本，促进重新对业务的设计，从而减少系统依赖性负载。
  • 测试（testing）：新代码发布通过 Dapper 跟踪 QA 流程，验证系统行为的正确性和性能，在这个过程中发现了许多问题，包括 Ads Review 服务代码本身和依赖库中的问题。

5-2 Addressing long tail latency

由于移动部件（moving parts）的数量，代码库的大小，部署的范围，使得调试类似通用搜索这样的服务具有非常大的挑战性。接下来，我们将描述为了降低通用搜索延迟分布的长尾效应所做出的努力。

Dapper 能够验证关于端到端延迟的假设，更具体来说，能够验证通用搜索请求的关键路径。当系统不仅涉及数十个子系统，而且涉及数十个开发团队时，即使最优秀，最有经验的工程师也不能准确判断导致端到端性能较差的根本原因。在这种情况下，Dapper 可以提供急需的数据，并且能够对许多重要的性能问题的出结论。

5-3 Inferring service dependencies

在任何给定的时间内，Google 内部的一个典型的计算集群是一个汇集了成千上万个逻辑“任务”的主机，一套的处理器在执行一个通用的方法。Google 维护着许多这样的集群，事实上，我们发现在一个集群上计算着的这些任务通常依赖于其他的集群上的任务。由于任务之间的依赖是动态改变的，所以不可能仅从配置信息上推断出所有这些服务之间的依赖关系。同时，在公司内部的各个流程需要准确的服务依赖关系信息，以确定瓶颈所在，以及计划服务的迁移。

Google 内部被称为 “Service Dependencies” 的项目是通过使用 Trace Annotation 和 Dapper API MapReduce 接口来实现自动化确定服务依赖。

Dapper 核心组件与 Dapper Trace Annotation 一起使用的情况下，“Service Dependencies” 项目能够推算出任务各自之间的依赖，以及任务和其他组件之间的依赖。

5-4 Layered and Shared Storage Systems

Google 的许多存储系统是由多重独立复杂层级的分布式基础设备组成的。例如，Google 的 App Engine 就是搭建在一个可扩展的实体存储系统上的。该实体存储系统基于 BigTable 上公开某些RDBMS 功能。BigTable 同时使用Chubby 及 GFS。而且，像 BigTable 这样的系统简化了部署，并更好的利用了计算资源。

在这种分层的系统，并不总是很容易确定最终用户资源的消费模式。例如，来自给定 BigTable 单元的大量 GFS 流量可能主要来自一个用户或多个用户，而在 GFS 层面，这两种不同使用模式之间的差异是模糊的。而且，如果缺乏像 Dapper 这样的工具，对此类共享服务的竞争可能会同样难以调试。

Dapper 的用户界面可以聚合那些调用任意公共服务的多个客户端的跟踪的性能信息，这就很容易让提供这些服务的源从多个维度给他们的用户排名（例如，入站的网络负载，出站的网络负载，或服务请求的总时间）。

6-Conclusions

在本文中，我们介绍 Dapper 这个 Google 生产环境下的分布式系统跟踪平台，并汇报了我们开发和使用它的相关经验。

Dapper 几乎在部署在 Google 所有系统上，并可以在不需要应用级修改的情况下进行跟踪，而且没有明显的性能影响。Dapper 对于开发人员和运维团队带来的好处，可以从我们主要的跟踪用户界面的广泛使用上看出来，另外我们还列举了一些 Dapper 使用用例来说明 Dapper 的作用，这些用例有些甚至都没有 Dapper 开发团队参与，而是被应用的开发者开发出来的。

我们相信，Dapper 比以前基于 Annotation 的分布式跟踪达到更高的应用透明度，这一点已经通过只需要少量人工干预的工作量得以证明。虽然一定程度上得益于我们的系统的同质性，但它本身仍然是一个重大的挑战。最重要的是，我们的设计提出了一些实现应用级透明性的充分条件，对此我们希望能够对更错杂环境下的解决方案的开发有所帮助。

最后，通过开放 Dapper 仓库给内部开发者，促使了更多基于 Dapper 的分析工具的产生。