华为云计算与网络创新Lab

ADSketch：基于模式侧写的在云服务性能异常检测

本文发表在ICSE2022（CCF-A）会议，作者陈壮彬（香港中文大学博士研究生），论文内容为华为-港中文云系统与可靠性联合实验室研究工作产出。原文链接Adaptive Performance Anomaly Detection for Online Service Systems via Pattern Sketching

随着云计算的发展，传统桌面软件逐渐迁移到云上，以云服务（在线服务）的形态提供给用户。云服务质量于用户体验而言至关重要。为了保证服务性能，云服务通过各种指标（比如CPU使用率，服务响应延迟，吞吐量）进行7×24小时的密切监控。指标异常检测旨在找到指标序列（一种时序数据）中预期之外的或者罕见的模式，从而及时发现服务中的性能问题。为了应对复杂多样的时序异常模式以及帮助运维人员进行快速故障理解与根因定位，华为云计算与网络Lab联合香港中文大学提出ADSketch，一种准确、高效，且具有可解释性与在线学习能力的异常检测算法。

传统时序异常检测的问题

时序异常检测是一个经典的问题，然而云服务场景对算法提出了更高的要求。现有算法通常难以满足以下两个关键需求：

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

本论文方法：ADSketch

为解决上述问题，本论文提出ADSketch，一种基于模式侧写的在云服务性能异常检测算法。软件系统的不同组件（比如微服务、函数服务）提供特定的功能，并且用户的行为具有一定规律，因此当同类型的性能问题发生时，指标通常表现出类似的模式，如图1所示。基于此观察，ADSketch提出从指标时序序列中识别出具有判别性的子序列，作为指标模式（metric pattern）用以标识不同类型的服务性能问题。比如服务性能瓶颈通常表现为吞吐量下降及CPU利用率上升。通过将故障问题和指标模式进行关联，可以为结果提供更好的可解释性（类似于故障指纹/故障侧写）。当相似的时序异常模式出现时，算法便可快速识别异常并提供可能发生的故障/问题。

图1：性能异常模式案例

整体框架

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

图2：ADSketch整体框架图

算法细节

离线指标模式学习

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

图3：指标序列不同子序列的SPW距离

由于暴力算法的时间复杂度太高，本文采用STAMP算法进行快速的SPW距离计算。特别地，原算法的归一化方法为z-normalization，而本论文发现min-max normalization产生的结果更有意义。

本论文提出的指标模式发现算法如图4和图5所示， $T_{n}$ 为输入的正常指标序列， $T_{a}$ 为需要进行异常检测的序列，m为子序列长度，p为分位数阈值（用来划定异常子序列，为了降低漏报率，该参数设置的比较宽松），I和S为子序列的索引以及子序列的SPW距离。算法流程如下：

算法第1行：在 $T_{n}$ 内部计算SPW距离（self-join），即进行距离计算的子序列均取自 $T_{n}$ ，见图5第1部分。
算法第2行：对于 $T_{a}$ 的子序列，从 $T_{n}$ 找与其最相似的子序列（cross-join），即进行距离计算的子序列分别来自 $T_{a}$ 和 $T_{n}$ 。由于 $T_{n}$ 为正常序列，因此SPW距离较大的 $T_{a}$ 的子序列有可能为异常，由分位数阈值p划定正常与异常子序列，见图5第1部分。
算法第3-4行：构建连通图G，图中的节点为来自 $T_{n}$ 和 $T_{a}$ 的所有子序列，两个节点有连线则表明它们在self-join和cross-join中取得SPW距离，即最相似。接着按照p划定的距离阈值将大于p的边剪断，这将产生孤立节点，孤立节点可以认为是候选的异常子序列 $N_{i}$ ，见图5第2部分。这里连接子图里的序列不能代表相似的指标模式，主要有两个原因：一是图的构造条件比较严格，只考虑了最近邻连接，不同子图之间也可能比较相似；二是由于百分位阈值p设置得比较宽松，可能会产生误报。
算法5-6行：对每个子图里的子序列计算均值 $μ_{G}$ ，并采用Affinity Propagation算法对均值向量做进一步聚类C。由此将所有相似的子序列尽可能地聚合在一起。
算法第7-15行：对进一步聚类得到的子序列簇C再次计算均值 $μ_{C}$ ，得到的均值向量作为指标模式。如果这个簇中所有的子序列均来自前面的候选异常子序列，则判定该指标模式为异常模式 $P_{a}$ ，否则为正常模式 $P_{n}$ ，见图5第3部分。

图4：指标模式发现算法

图5：指标模式发现算法（图示）

在线异常检测

异常检测

利用离线学习到的异常模式，我们能快速进行异常检测。输入一个长度为m的子序列t，计算t到上一步中学习到的所有模式的距离，找到最近的模式。如果这个最近的模式是异常模式，那么t判断为异常；否则为正常。算法如图6所示。

图6：在线异常检测

指标模式自适应学习

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

算法第1-2行：给定一个新的子序列t，计算则t和所有聚类簇中心的距离d，找到距离最小的簇。
算法第3-10行：如果d小于目前所有聚类簇的半径，则将t加入到距离最近的簇并更新相关的变量 $S_{c}$ ， $R_{c}$ 以及 $μ_{c}$ 。
算法第18-21行：如果d大于目前所有聚类簇的半径，则以t为中心新建一个簇。并认为该簇构成的指标模式为异常模式。
算法第11-13行：新出现的模式总被认为是异常，此设定将产生大量误报，因此需要识别新的正常模式。随着时间的累计，可以对新形成的（异常的）簇设置阈值，如果一个异常簇的样本数超过阈值，则表明该模式是一种常见现象，因此需要将其调整为正常模式。此阈值设置为最大的异常簇的子序列数。

图7：指标模式在线更新算法

实验结果

实验部分对算法的离线异常检测，在线异常检测以及指标模式的在线更新能力均进行了检验。使用了三个数据集：Yahoo公开的指标数据集，2018年AIOps算法比赛数据集以及华为云的实际数据集。对比了一些主流的单指标异常检测方法LSTM, Donut, LSTM-VAE, LODA, iForest, DAGMM, SR-CNN。实验结果如图8-10所示，均表明了ADSketch较现有算法的优越性。

图8：离线异常检测实验结果

图9：在线异常检测实验结果

图10：指标模式在线更新异常检测实验结果

下一代计算与网络