Paper｜ADSketch

研究背景

研究问题

随着云计算的出现，许多传统的软件系统被迁移到云计算平台上作为在线服务。云服务质量于用户体验而言至关重要。由于在线服务需要服务全球数以百万计的客户，短时间的性能下降可能导致经济损失和用户不满。因此，主动甚至自适应的系统排故成为在线服务提供商的核心能力。

云服务通过各种指标来监控逻辑资源(例如,一个虚拟机)和物理资源(例如,一个计算服务器)的各个方面。我们观察到当相似类型的性能异常发生时，它们往往会在指标时间序列上触发类似的反应/症状，我们称之为指标模式（metric pattern）。 比如服务性能瓶颈通常表现为吞吐量下降及CPU利用率上升，如图1所示。每个指标时间序列记录了一周左右的监测数据，其异常表现由红色表示。

指标异常检测旨在找到指标序列（一种时序数据）中预期之外的或者罕见的模式，从而及时发现服务中的性能问题。

传统解决方案的问题

在对指标值进行异常检测时，现有方法往往缺乏可解释性，这对于工程师和分析人员采取补救措施至关重要。而且，它们无法有效地以在线方式适应不断变化的服务。

• 算法结果可解释：现有工作大多是为指标序列的每个节点计算一个异常概率，并通过设置阈值的方式判断异常是否发生。然而这样的结果对运维人员的作用十分有限。由于算法无法进一步提供异常是由哪些故障/问题导致的，运维人员难以相信算法结果，需要手工排查大量指标进行问题定位。因此，可解释性对于故障分析与服务恢复具有重要作用。
• 异常模式在线更新：实际场景中，在线服务频繁变更（比如系统架构发生变化，新功能上线），异常模式也可能随之改变。现有工作大多通过历史离线数据训练学习异常检测模式，难以适应频繁变化的异常模式。因此现有工作部署在实际系统时，随着时间的推移将产生较多误报。

本文方案

针对以上局限性，作者提出了一种基于模式草图的在线服务系统性能异常检测方法ADSketch，该方法具有可解释性和自适应性。 其主要思想是从度量时间序列中识别出能够表示服务性能问题类别的判别性子序列。 ADSketch通过识别代表特定类型性能问题的一组异常度量模式来实现可解释性。如果类似的模式再次出现，潜在的问题就可以立即被认识到。此外，还设计了自适应学习算法，以适应由服务更新或用户行为变化引起的前所未有的模式。

整体框架

共分为两个阶段：离线异常检测（offline phase）及在线异常检测（online phase）。在离线阶段，输入为一对指标序列，一个是不包含异常的指标序列（anomaly-free metric），用来作为正常指标的参考基准；另一个输入为需要进行异常检测的指标序列（metric for anomaly detection）。这个阶段将学习到两种指标模式，即正常模式（normal patterns）和异常模式（abnormal patterns）。特别地，指标模式为一组相似的子序列通过求平均获得。运维人员在日常故障处理过程中把服务性能问题与学习到的异常模式进行关联，以实现知识的积累。在线阶段则利用离线阶段捕获的模式进行快速的异常检测，同时对已习得的模式进行更新（adaptive pattern learning）。

离线异常检测

离线阶段的一个重要目标是发现指标模式。主要思想为，如果一个子序列显著偏离正常时期的子序列，那么它是一种异常模式。偏移程度用两个子序列的距离来度量，如果距离越大，说明越可能异常。对于一个长度为$l$的指标序列，假设子序列的长度为$m$，那该指标序列有$l-m+1$条子序列。通过计算这些子序列两两之间的距离，我们可以得到每一条子序列距离其他子序列最小的值，我们称为the smallest pair-wise distance（简称SPW距离）。SPW越大，则表明该子序列越偏离整体指标序列（与其他所有子序列的相似度较低），因此也越可能是异常。从图3可以看出，异常区间的SPW距离显著高于正常区间的，作者采用欧氏距离作为距离度量函数，并且采用STAMP算法进行快速的SPW距离计算。

具体算法

$\mathcal{T}_n$为输入的正常指标序列，$\mathcal{T}_a$为需要进行异常检测的序列，$m$为子序列长度，$p$为分位数阈值（用来划定异常子序列，为了降低漏报率，该参数设置的比较宽松），$I$和$S$为子序列的索引以及子序列的SPW距离。算法流程如下：

1：在$\mathcal{T}_n$内部计算SPW距离（self-join），即进行距离计算的子序列均取自$\mathcal{T}_n$，见图5第1部分。

2：对于$\mathcal{T}_a$​的子序列，从$\mathcal{T}_n$找与其最相似的子序列（cross-join），即进行距离计算的子序列分别来自$\mathcal{T}_a$​和$\mathcal{T}_n$。由于$\mathcal{T}_n$​为正常序列，因此SPW距离较大的$\mathcal{T}_a$​的子序列有可能为异常，由分位数阈值$p$划定正常与异常子序列，见图5第1部分。

3-4：构建连通图$G$，图中的节点为来自$\mathcal{T}_n$​和$\mathcal{T}_a$的所有子序列，两个节点有连线则表明它们在self-join和cross-join中取得SPW距离，即最相似。接着按照$p$划定的距离阈值将大于$p$的边剪断，这将产生孤立节点，孤立节点可以认为是候选的异常子序列$N_i$​，见图5第2部分。这里连接子图里的序列不能代表相似的指标模式，主要有两个原因：一是图的构造条件比较严格，只考虑了最近邻连接，不同子图之间也可能比较相似；二是由于百分位阈值$p$设置得比较宽松，可能会产生误报。

5-6：对每个子图里的子序列计算均值$\mu_G$​，并采用Affinity Propagation算法对均值向量做进一步聚类$C$。由此将所有相似的子序列尽可能地聚合在一起。

7-15：对进一步聚类得到的子序列簇$C$再次计算均值$\mu_C$​​，得到的均值向量作为指标模式。如果这个簇中所有的子序列均来自前面的候选异常子序列，则判定该指标模式为异常模式$P_a$​，否则为正常模式$P_n$​，见图5第3部分。

指标模式的可解释性

对于每个度量模式，域工程师将标注触发它的性能问题的类型。特别地，一个模式可以同时具有多个标签。具有重叠的度量模式将共享同一组性能问题标签。

在线异常检测

利用离线学习到的异常模式，我们能快速进行异常检测。输入一个长度为$m$的子序列$t$，计算$t$到上一步中学习到的所有模式的距离，我们搜索其最相似的度量模式，并检查它来自哪个模式池。

具体算法

1-2：给定一个新的长度为$m$的度量子序列$t$，搜索其最相似的度量模式。

3-7：如果$t$与异常模式更相似，则预测为异常；否则为正常。

指标模式自适应学习

由于云服务经常需要更新或新功能上线，指标模式也随之发生变化。作者提出在线更新离线过程中学习到的指标模式，如图7所示。算法的核心思想为，如果一个新的子序列$t$距离现有的模式（由相似子序列组成的簇计算均值得到）较近，则$t$将被吸收进现有的簇中并更新该簇，否则$t$将作为新的模式自组成一个新的簇。记$S_C​$为聚类簇的大小（即该簇包含的子序列数量），$R_C​$为聚类簇的半径（簇中心到所包含的子序列的最大距离），$\mu_C$为聚类簇中心（即簇所包含子序列的均值）。

具体算法

1-2：首先寻找$t$最接近的模式。

3：均值向量$\mu_C$更新方程。

4-6：半径$R_C[idx]$的更新值。

7：考虑到正常团簇和异常团簇之间的高度不平衡性，我们为它们保持两个最大半径，分别记为$d_n$和$d_a$

8：一旦一个簇改变了它的半径，我们重置了它的类的最大半径。

9-16：集群接受一个新成员，需要更新其均值向量$\mu_C[idx]$(即度量模式，通过第3行的公式更新)、大小$S_C[idx]$（加一）和半径$R_C[idx]$。

11：对新形成的异常团簇的大小设置阈值来减轻假阳性。
12-13：当集群的规模超过阈值时，集群的角色将从异常切换到正常。

18-21：另一方面，如果簇拒绝$t$，我们通过适当地设置它的性质，形成一个新的只包含$t$的反常簇。

半径$R_C[idx]$的更新有点问题。由于原始子序列不可得，我们无法直接计算新的半径。为了解决这个问题，我们使用最坏情况距离进行近似。如图5所示，当$t$位于产生半径(记为$t_r$)的杆件处切空间的(向内指)法线时，新半径达到最大值。

实验评估

通过从华为云中具有代表性的在线服务系统收集的公共数据和工业数据对所提方法进行评估。实验结果表明，ADSketch算法的性能明显优于现有的方法，证明了在线算法在新模式发现中的有效性。

复现结果

时间&资源

个人总结