论文主要提出的是request-flow comparison，也就是比较两个不同时期的流特征。论文主要提出两种异常：执行时间异常和执行路径异常。

值得注意的是，request-flow comparison和anomaly detection不一样。前者主要比较两个不同period的distribution changes，后者主要比较一个period内表现明显不同的flow。

Spectroscope

Categorizing request flows

Spectroscope利用一个普遍的期望，即采取相同路径的请求应该产生类似的成本，将结构相同的请求分为独特的类别，并使用它们作为比较请求流的基本单位。

对于每一个类别，Spectroscope都会识别总体统计数据，包括请求数、平均响应时间和差异。为了确定时间花在哪里，它还计算了平均edge延迟和相应的variance。

类别太多，可能需要聚类。但是我觉得这里他没讲清楚。

Comparing request flows

当比较请求流时，Spectroscope把两个活动时期的请求流图作为输入，我们称之为非问题时期和问题时期。通过运行统计测试和启发式方法来进行比较。方法在下面介绍。

Algorithms for comparing request flows

Identifying response-time mutations

要判断执行时间异常，使用Kolmogorov-Smirnov two-sample, non-parametric假设检验。

Identifying structural mutations

为了识别结构突变，Spectroscope假设在非问题期和问题期都运行了类似的工作负载。因此，可以合理地推断，在问题时期，通过分布式系统的一个路径的请求数量的增加应该对应于通过其他路径的请求数量的减少。

Categories that contain SM_THRESHOLD more requests from the problem period than from the non-problem period are labeled as containing mutations and those that contain SM_THRESHOLD fewer are labeled as containing precursors.

相当于就是precursor类别的request被执行成了mutations的情况。

Mapping mutations to precursors

基于三个启发：

通过删除root node不一样的，减少需要检查的precursor种类。
其余的precursor类，如果其请求数的增加小于mutation的请求数的增加，也将从考虑中删除。这种1:N的启发式方法反映了一种常见的情况，即一个precursor类可能会向N个mutation类捐赠请求。
第三，剩下的precursor类根据它们有捐赠请求的可能性进行排序，这是由它们和mutation类之间的字符串编辑距离决定的

Ranking

对mutation进行排序是必要的，原因有二。

首先，性能问题可能有多个根本原因，每个原因都会导致其自身的突变集。
其次，即使只有一个问题的根源（例如，错误的配置），也会经常观察到许多突变。

在这两种情况下，确定对性能影响最大的突变是有用的，以便将诊断工作集中在能产生最大利益的地方。

Spectroscope将包含突变的类别按其对性能变化的预期贡献降序排列。

执行路径异常的贡献被计算为它所包含的突变数量，这是它的问题期和非问题期计数之间的差异，乘以它和它的precursor类别之间问题期平均响应时间的差异。
- 如果确定了一个以上的候选precursor类别，则使用其平均响应时间的加权平均数；加权的依据是与突变的结构相似度。
执行时间异常的贡献被计算为它所包含的突变数量，也就是非问题期的计数，乘以该类别在不同时期的平均响应时间的变化。

如果一个类别同时包含执行时间异常和执行路径异常，它将被分成两个虚拟类别，并分别进行排名。

Identifying low-level differences

发现异常还不算结束，开发者可能希望知道low-level的一些区别，论文采用的是一个regression tree。

缺点

缺点很明显：不能够识别contention带来的问题；不能够识别workload变化的情况。