The Mystery Machine：大规模互联网服务的端到端性能分析

论文地址：The Mystery Machine：大规模互联网服务的端到端性能分析

谷歌的Dapper论文非常有名，但Facebook的The Mystery Machine似乎鲜为人知——这很可惜，因为我有预感，这种方法可能与很多人都非常相关。

当前的调试和优化方法在处理现代Internet服务的复杂性方面规模很小，其中单个请求触发在一组分布式计算机上并行执行大量异构软件组件。当前方法的致命弱点是需要一个被观察系统的完整和精确的模型：生成这样的模型是一个挑战，因为它需要吸收负责单个组件的数百名程序员的集体知识，或者限制组件交互的方式。

Facebook的神秘机器可以测量端到端的性能，从在web浏览器中启动页面加载，一直到服务器端基础设施，再回到页面完成呈现的位置。这样做需要一个组件之间关系的因果模型（以前发生过）。你怎么知道的？尤其是，如果你不能假设一个统一的仪器环境，你怎么得到这个结果呢？

许多以前的系统都假设可以通过对所有中间件进行全面的通信、调度和/或同步检测来记录组件交互来生成这样的模型。如果软件架构是同质的，这是一个合理的假设；例如，Dapper为一组在Google中广泛使用的中间件组件提供了工具。

Facebook不是这样的。其他许多公司也没有内部系统…。

……许多系统就像我们研究的Facebook系统；它们随着时间的推移在一种有利于创新而非标准化的文化中有机地成长（例如，“快速行动，打破僵局”是Facebook的一个著名口号）。编程语言、通信中间件、执行环境和调度机制有着广泛的多样性。向这样一个基础设施中追溯地添加工具是一项艰巨的任务。此外，端到端管道包括客户端软件（如Web浏览器），向所有此类软件添加详细的工具是不可行的。

因此，Facebook从应用程序组件生成的常规日志中推断出因果关系：

我们的主要观察结果是，现代服务处理的请求量之大，使我们能够收集对大量请求中记录消息的顺序的观察结果。然后我们可以假设并确认这些信息之间的关系。我们通过一个分析超过130万个Facebook请求以生成端到端请求处理的综合模型的实现来证明这一技术的有效性。

这非常方便，因为几乎所有的东西都已经生成了日志。Facebook的日志消息依赖于最少的公共内容：请求标识符、主机标识符、主机本地时间戳和唯一的事件标签。所有日志的输出都聚合到UberTrace服务中。

为了将现有日志消息映射到UberTrace模式，我们对现有日志系统进行了最小的更改。我们修改了日志消息以使用相同的全局标识符，并使事件或任务名称更具可读性。我们没有添加其他日志消息。因为我们重用了现有的组件日志记录，并且只需要一个最小的模式，所以这些日志记录更改大约需要一个人一个月的努力。

UberTrace始终对一小部分请求进行端到端跟踪采样。跟踪数据被写入Facebook的分布式日志服务Scribe，日志存储在名为Hive的数据仓库基础设施的表中。神秘机器对数据运行批处理Hadoop作业以推断因果关系。

The Mystery Machine使用UberTrace生成的跟踪来创建一个因果模型，说明在端到端处理Facebook请求期间软件组件是如何交互的。然后，它使用因果模型执行几种类型的分布式系统性能分析：找到关键路径，量化不在关键路径上的段的松弛度，以及识别与性能异常相关的段。神秘机器通过关系数据库和图形查询工具导出结果，从而实现更具针对性的分析。

The Mystery Machine


The Mystery Machine（TMM）对日志记录进行预处理，将它们转换成段—同一任务的两个单独日志记录之间的执行间隔。然后TMM开始识别因果关系的过程。它首先假设一切都是由事物引起的，然后为各部分之间的卡索关系生成所有可能的假设。然后它通过追踪语料库工作，如果在任何追踪中发现反例，它就会拒绝一个假设。

TMM推断出三种类型的关系：

• 之前发生–如果在所有请求中，段B的开始时间都在段A的开始时间之后。（也就是说，当我们看到一对重叠的跟踪片段时，我们可以拒绝假设之前发生的事件）。
• 互斥-A段和B段从不重叠。（与之前只允许排序[A，B]的情况相反，互斥同时允许[A，B]和[B，A]）。
• 管道-两个任务t1和t2具有管道依赖性，因此如果t1按d1、d2、d3的顺序处理数据元素，那么t2也具有管道依赖性，并且对于每对任务，t1中的数据项的处理在t2中的相同数据项的处理之前发生。

当然，这都依赖于对时间的一些全局理解，而日志记录将使用本地时间编写：

由于所有日志时间戳都与本地时钟相关，UberTrace通过补偿时钟偏差将它们转换为估计的全局时钟值。UberTrace寻找通用的RPC通信模式，在这种模式下，单个任务中的控制线程从一台计算机（称为客户端以简化此说明）传递到另一台计算机，在第二台计算机（称为服务器）上执行，然后返回客户端。UberTrace通过减去嵌套在客户端RPC中的最新和最早服务器时间戳（根据服务器的本地时钟）来计算服务器执行时间。然后，它通过减去立即成功并位于RPC之前的客户端时间戳来计算客户端观察到的执行时间。客户端和服务器间隔之间的差异是客户端和服务器之间估计的网络往返时间（RTT）。通过假设请求和响应延迟是对称的，UberTrace计算时钟偏差，以便在时钟偏差调整之后，模式中的第一个服务器时间戳正好是任务的前一个客户端时间戳之后的1/2 RTT。

UberTrace以这种方式进行多次估计，并使用产生最低观测RTT的估计。

本文中的图2展示了TMM在工作中的一个很好的例子。它本质上是一种基于筛子的算法。

The Mysery Machine假设，在大量追踪上出现的时间的自然变化足以揭露不正确关系的反例。

30天内收集的130万个请求证实了这一假设：“随着分析追踪数量的增加，对新反例的观察减少，只留下真实的关系。请注意，总关系数随着时间的推移而变化，因为开发人员不断向管道添加新的段。”

为了验证神秘机器产生的因果模型，我们确认了神秘机器识别出的几个具体关系。尽管由于模型的大小，我们无法验证整个模型，但我们对两个更复杂的组件进行了实质性验证：客户端上的JavaScript执行与向客户端传递数据所涉及的依赖项之间的相互作用。这些成分分别有42和84个片段，以及2583和10458个确定的偶然关系。

在Hadoop集群上花了大约2个小时来分析30天内抽样的130万个请求。该计算被并行化，使得每晚都可以作为批处理作业运行。这使得推断出的因果依赖关系可以随着部署的系统而发展：

神秘机器的一个关键特征是它自动发现依赖关系，这一点至关重要，因为Facebook的请求处理一直在不断发展。如前所述，神秘机器假设两段之间的关系，直到找到反例。随着时间的推移，随着网站的发展和新功能的添加，新的部分也会随之添加。神秘机器通过假设新的可能关系和移除发现反例的关系，自动发现新片段引入的依赖关系……以解释被删除的片段和添加的不变量，可以简单地运行一个新的Hadoop作业，在不同的跟踪时间窗口上生成模型。

给定推断的因果模型，TMM执行三种不同类型的性能分析：关键路径、松弛和异常检测。

关键路径
关键路径被定义为一组段，段执行时间的差异增加将导致端到端延迟的相同差异增加。神秘机器根据每个请求计算关键路径。它将请求中的所有段表示为一个有向无环图，其中的段是具有等于段持续时间的权重的顶点。它在所有顶点之间添加一条边，相应的线段具有因果关系。然后，它执行一个传递归约，如果存在一个由a→B和B→C组成的链接两个节点的路径，则递归地移除所有边a→C。最后，神秘机器执行最长路径分析，以找到从请求中的第一个事件（请求的启动）到最后一个事件（通常是某些JavaScript执行的终止）的关键路径。关键路径的长度是整个请求的端到端延迟。如果存在等长的关键路径，则选择第一个发现的路径。

在正常操作中，TMM被要求计算大量记录道的关键路径并汇总结果。“例如，我们可能会询问给定的段落在关键路径上的频率或每个段表示的关键路径的平均百分比。”

Slack
Slack是当你不在关键的道路上时得到的…

我们将slack定义为在不增加请求端到端延迟的情况下，段的持续时间可以增加的量，假设所有其他段的持续时间保持不变。根据此定义，关键路径上的段没有松弛，因为增加它们的延迟将增加请求的端到端延迟。

slack结果通常在大量跟踪上聚合。

异常检测
The Mystery Machine支持的一种特殊的聚集形式是异常分析。为了执行此分析，它首先根据端到端延迟对请求进行分类，以识别一组异常请求。目前，异常值被定义为端到端延迟的前5%的请求。然后，它对分类器标识的每组请求执行关键路径或空闲数据的单独聚合。最后，它执行一个差异比较，以确定在请求的离群值集中比在非离群值集中具有更大比例表示的段。例如，我们使用此分析来确定与高延迟请求相关的一组段。检查显示，这些段实际上是在调试响应某些用户请求而返回的组件

运行中的The Mystery Machine
文章最后给出了两个扩展的例子，利用TMM的分析来提高对Facebook系统的理解。首先是对Facebook主页进行关键路径分析，其次是减少延迟。

TMM提供的全局视图有助于将精力集中在正确的地方：

总延迟和关键路径条的比较通过只检查总延迟故障（例如，如果工程师只分析一个系统组件），揭示了神秘机器的重要性，人们可能高估了网络延迟和JavaScript处理对端到端性能的重要性。事实上，服务器和其他客户机处理段通常是关键的，并且整个关键路径在服务器、客户机和网络之间是相对平衡的。

第二个案例研究很有趣，因为它使用神秘机器对潜在的性能优化差异化服务进行早期探索，而不承担实现优化的费用。

直观地说，较小的延迟意味着服务器延迟与端到端延迟密切相关；实际上，如果延迟为零，我们预计服务器延迟的任何增加都会延迟相同数量的端到端延迟。相反，当slack很大时，我们期望服务器延迟和端到端延迟之间的相关性很小；服务器延迟的增加很大程度上被其他并发延迟所隐藏。通过直接测量服务器和端到端延迟的相关性，我们验证了slack的概念。

以前请求中报告的Slack是未来请求中Slack的一个很好的预测器（这一假设也通过TMM得到了验证）。根据这种预测，可以提高平均延迟：

利用预测Slack时间作为调度截止期，我们可以以类似于最早截止期优先的实时调度算法的方式提高平均响应时间。在不影响端到端延迟的情况下，可以为具有相当松弛的连接分配较低的优先级。但是，松弛度很小的连接应该可以看到端到端延迟的改善，因为它们被赋予了调度优先级。因此，平均延迟应该提高。我们还表明，先前的松弛值是未来松弛的一个很好的预测因子。当接收到新连接时，可以检索历史值并将其用于调度决策。由于计算slack比服务于Facebook的实际请求要简单得多，因此每个用户大约每月重新计算一次slack应该是可行的。