本文主要介绍智能运维中多维指标根因定位问题及其解决方案，以下内容主要源于我们组内一位同学对该问题的概述 传送门~，笔者为清华大学博三在读研究生，主要研究领域为智能运维中的根因定位问题。
关于智能运维领域另一个关键问题 【调用链根因定位】可以参考另一篇文章 智能运维 AIOps 系列丨调用链根因定位算法综述

智能运维领域 AIOps 平台调研，结果来自于 G2 统计： https://www.g2.com/categories/aiops-platforms

AIOps 平台

问题定义

多维度指标的异常定位是 AIOps 领域的一个典型且有挑战的问题。在互联网服务运维中，当某个总指标（如总流量）发生异常时，需要快速准确地定位到是哪个交叉维度的细粒度指标（如“省份=北京 & 运营商=联通”的流量）的异常导致的，以便尽快做进一步的修复止损操作。由于运维中的指标维度多、每个维度取值范围大，导致异常定位时的搜索空间非常大，因此需要一个高效的算法解决该问题。

举 🌰 说明：一个 KPI 指标根据多种属性分别监控，例如 Page Views（PV），分别统计来自不同 ISP 和不同省份的 PV。如 Fig.1 所示：

Fig.1 多维示例

上表中的ff 和vv 分别表示 PV 的期望的正常值和观测值，我们看到红色的部分观测值和正常值不符，这些 PV 就是发生了异常。

多维根因定位算法解决的是定位发生异常时哪些维度的属性取值导致了异常，比如 Fig.1 中的根因维度是 (Province=Beijing&Shanghai, ISP=*)

更详细的问题描述可以参考第二届智能运维挑战赛 传送门~，赛题为 多维监测指标的异常定位。

对于这个问题的解决方案可以参考获奖选手的答辩材料 传送门~

主流算法

主流的算法可以分为两类：

  • 一类是将这个问题看作是关联规则挖掘（挖掘和异常关联的属性集合，即关联规则）。
  • 另一类是设定一个判别根因的目标函数然后进行启发式搜索。

也有一些其他的方法，比如用神经网络去做多分类，但是方法我感觉不是很实用，也没有发在很好的会议上，就略去了。

关联规则挖掘

主要有 INFOCOM’16[1]，SIGMETRICS’20[2] 和 FSE’17[3]

其中前两者都是首先对所有属性组合进行异常检测，然后用 Apriori 算法去搜索 support 超过阈值的属性组合，再根据 confidence 去筛选。

FSE’17 可能原本目标的问题和这里的问题不太一致，但是比较类似。它使用的 Contrast set mining 可以看为一种特殊的关联规则挖掘。contrast set mining 是挖掘在不同的类中分布（support）差别很大的属性组合，而前两者挖掘的是和某个特定的类（即异常）关联的属性组合。

就我个人的经验，关联规则挖掘在参数（support 和 confidence 的阈值，异常检测的阈值）合适的情况下，可以取得非常好的效果。但是显然这些参数随着数据集和故障案例的不同会有不同的最佳取值，因此实际上这一类方法的效果可能不太稳定。

启发式搜索

剩下的算法都是各种各样的启发式搜索。这些方法首先需要定义自己关注的根因是什么样的，并据此定义一个目标函数f:attribute combinations→Rf: attribute~combinations \rightarrow \mathbb{R} ，即给定一个（或者一组）属性组合评估起根因分数。之后就是在整个搜索空间中搜索使得目标函数最大化的属性组合作为根因。由于搜索空间往往十分巨大，所以还需要各种各样的启发式方法或者剪枝方法。

以下按时间顺序简要总结现有的方法：

1. Adtributor[4][NSDI’14]

假设根因只可能是一个属性出了问题，例如只有可能是某一个省份或者某一运营商的问题，而不会是某个省份的某个运营商的问题。即 (Province=Beijing, ISP=*) 和 (Province=*, ISP=China Mobile) 都是合法的根因，而 (Province=Beijing, ISP=China Mobile) 是不会出现的。这个假设大大简化了问题，但是明显是不能覆盖实际的需求的。

Adtributor 提出了两个指标用来评估属性组合。一个是解释力，指的是该属性组合对应的指标变化和整体的指标变化的比例。另一个是 surprise， 一个属性下面的各个指标的取值的分布是否有变化，根因属性的话应该有明显变化。

因为是只考虑一个属性，所以搜索空间并不大，基本上就是搜索解释力和 surprise 最大的属性。

2. iDice[5] [ICSE’16]

首先 iDice 处理的问题是我们讨论问题的一个子集，它只专注处理 issue report 数量增加的根因。即考虑的指标只有 issue report 的数量。

iDice 的目标函数如下

R=pa∗ln⁡papbR=p_{a} * \ln \frac{p_{a}}{p_{b}}

其中pp 指的是属性组合对应的 issue report 占所有 issue 的比例。aa 和bb 分别指的是异常时刻后（after）和前（before）。整个公式就是两个比例的 fisher distance。

为了加速搜索，iDice 提出了三个剪枝策略。

  • issue report 数量本身太小的属性组合会被剪枝。这个剪枝策略显然就无法用在例如响应时间等指标上。

  • issue report 数量随时间没有突变的会被剪枝。

  • 根因属性组合需要把在故障时刻前后 issue report 数量有没有发生突变的细粒度属性组合分开。即有变化的应该是根因属性组合的细粒度属性组合，而没有变化的应该不是。

3 Recursive Adtributor[6]

这是一篇学位论文中提到的。Recursive Adtributor 主要是为了解决 Adtributor 的不合理的假设的问题。基本的思路是递归调用 Adtributor。Adtributor 会返回一个根因属性和对应的取值，Recursive Adtributor 就会在选出来的切片 3. 上递归调用 Adtributor，得到下一个根因属性和对应的取值。

img

4. HotSpot[7][IEEE Access’18]

我们实验室之前的工作。

HotSpot 首先的出发点是 Ripple effect。假设两个属性的指标取值是相关的，那么它们两一定是由第三个属性（可能和它们两之一重合）共同导致的。所以如果一个属性组合是根因，那么他和别的属性都是独立的。也就是说根因属性组合的更细粒度属性组合的指标变化，和根因指标本身的指标变化，一定是成比例的。

基于这个假设，Hotspot 设计了一个目标函数叫 potential score。这个分数评估两方面的内容：对于待评估属性组合的更细粒度属性组合，它们的指标应该是异常的并且服从 ripple effect；另一方遍，对于其他的属性组合，它们的指标应该是正常的。

HotSpot 和其他工作例如 iDice 很不一样的一点就是，它显式地考虑了有多个根因同时作用的情况。因此搜索空间直接变成了属性组合数目的幂，搜索空间的极大地增加了。

为了解决这个问题，HotSpot 采用了 MCTS 算法（蒙特卡洛树搜索，AlphaGo 用过的）来进行启发式搜索。

5. Squeeze[8][ISSRE’19]

我本人的工作。

Squeeze 依然是基于 ripple effect，但是相比 HotSpot 额外证明了 ripple effect 对于衍生指标（例如响应时间等，具体定义参见论文）也成立。

Squeeze 的目标函数也基本还是 potential score，只是做了一些改进，使得对于根因的属性数量比较大，根因的指标变化相比整体不够显著的时候，算法效果稳健了很多。

最大的变化是搜索过程。Squeeze 没有采用暴力搜索加 MCTS 优化。而是采用了一套启发式策略来大大加速搜索，同时避免性能损失。

首先，根据 ripple effect，我们发现同一个根因所影响的细粒度属性组合的指标变化比例是相同的。因此我们利用这种先对细粒度属性组合进行聚类。

之后，我们在每一类中再去搜索根因。因为此时已经不用考虑多根因同时作用的影响，所以问题简化了很多。

此时，我们又采用了一个启发式策论。基本的思路是，根因属性组合对应的细粒度属性组合的指标应该都是异常的。

6. MID[9][FSE’20]

和 iDice 针对的是同样的问题，采用了 iDice 相同的目标函数。不同之处在于搜索策略不同。

MID 采用了 Meta-heuristic Searching 的策略，它定义了四个操作，每个可以把一个属性组合更新为一个新的。然后定义了一个 meta-heuristic 函数，用来评测一个属性取值是不是更有可能在根因中。具体的做法是评估其熵。

最后在搜索过程中，在每一步中 MID 评测当前属性组合的目标函数值，然后随机选择一个操作，根据 meta-heuristic 函数选择操作要增删改的属性和取值，最后得到一个新的属性组合，进去下一轮循环。

这个方法看起来很简单，但是有个巨大的问题就是每次随机选择的操作有可能重复出现已经搜索过的节点。但是如果简单禁止重复，那么就无法在搜索路径上进行回溯。因此这里需要一个合适的策略，我不太清楚怎么做能达到最好的效果。可惜原论文没有提及方法的细节。

7. ImpAPTr[10][ISSRE’20]

ImpAPTr 只处理成功率下降的异常。

ImpAPTr 提出了两个目标函数，和 Adtributor 用过的解释力和 surprise 基本思路一致。但是 ImpAPTr 并没有假设单属性组合。它还是会搜索多个属性的组合，然后用这两个目标函数分别排序。再用排序得到的排名的均值作为最后的排序依据。

这个方法在根因的属性数量不多以及单根因的时候效果很好。

8. AutoRoot[11]

改进了 Squeeze。

首先是提出一种对聚类方法的修改，主要是在聚类之前会用 KDE 对 density 做一遍平滑。应该是比较有作用的。

其次是把 generalized potential score 中的绝对误差改成了相对误差。这在指标的时序预测误差较大的时候会受很大影响。

最后使用了在类内搜索的时候采用了一种新的启发式策略，比 Squeeze 多考虑了一些。

联系作者

  1. F. Ahmed, J. Erman, Z. Ge, A. X. Liu, J. Wang, and H. Yan, “Detecting and localizing end-to-end performance degradation for cellular data services based on tcp loss ratio and round trip time,” IEEE/ACM Transactions on Networking (TON), vol. 25, no. 6, pp. 3709–3722, 2017. ↩︎

  2. Fred Lin, Keyur Muzumdar, Nikolay Pavlovich Laptev, Mihai-Valentin Curelea, Seunghak Lee, and Sriram Sankar. 2020. Fast Dimensional Analysis for Root Cause Investigation in a Large-Scale Service Environment. Proc. ACM Meas. Anal. Comput. Syst. 4, 2 (June 2020), 31:1-31:23. ↩︎

  3. Marco Castelluccio, Carlo Sansone, Luisa Verdoliva, and Giovanni Poggi. 2017. Automatically analyzing groups of crashes for finding correlations. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ACM, Paderborn Germany, 717–726. ↩︎

  4. R. Bhagwan, R. Kumar, R. Ramjee, G. Varghese, S. Mohapatra, H. Manoharan, and P. Shah, “Adtributor: Revenue debugging in advertising systems,” in 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14), 2014, pp. 43–55. ↩︎

  5. Q. Lin, J.-G. Lou, H. Zhang, and D. Zhang, “idice: problem identification for emerging issues,” in 2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE). ↩︎

  6. M. Persson and L. Rudenius, “Anomaly detection and fault localization an automated process for advertising systems,” Master’s thesis, 2018, g¨oteborg : Chalmers University of Technology. ↩︎

  7. HotSpot: Anomaly Localization for Additive KPIs with Multi-Dimensional Attributes Yongqian Sun, Youjian Zhao, Ya Su, Dapeng Liu, Xiaohui Nie, Yuan Meng, Shiwen Cheng, Dan Pei, Shenglin Zhang, Xianping Qu, Xuanyou Guo. IEEE Access2018. ↩︎

  8. Generic and Robust Localization of Multi-Dimensional Root Causes Zeyan Li, Chengyang Luo, Yiwei Zhao, Yongqian Sun, Kaixin Sui, Xiping Wang, Dapeng Liu, Xing Jin, Qi Wang and Dan Pei. ISSRE 2019 ↩︎

  9. Jiazhen Gu, Chuan Luo, Si Qin, Bo Qiao, Qingwei Lin, Hongyu Zhang, Ze Li, Yingnong Dang, Shaowei Cai, Wei Wu, Yangfan Zhou, Murali Chintalapati, and Dongmei Zhang. 2020. Efficient incident identification from multi-dimensional issue reports via meta-heuristic search. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ACM, Virtual Event USA, 292–303. ↩︎

  10. G. Rong, H. Wang, Y. You, H. Zhang, J. Sun, D. Shao, and Y. Xu. 2020. Locating the Clues of Declining Success Rate of Service Calls. In 2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE), 335–345. ↩︎

  11. Pengkun Jing, Yanni Han, Jiyan Sun, Tao Lin, and Yanjie Hu. 2021. AutoRoot: A Novel Fault Localization Schema of Multi-dimensional Root Causes. In 2021 IEEE Wireless Communications and Networking Conference (WCNC), 1–7. ↩︎