根因分析RCA

简介

综合转载于：

• 智能运维 | 故障诊断与根因分析论文一览
• 异常检测中‘根因定位’（root cause analysis）有什么常用的算法？ - 旅行者的回答 - 知乎
• 应用实时监控服务ARMS链路追踪

近些年来，在需要支持多平台的互联网应用中，微服务架构越来越受欢迎。与此同时，对于互联网公司来说，微服务的性能质量至关重要，因为微服务故障会降低用户体验并带来经济损失。有效的定位故障的根本原因对于快速恢复服务并减轻损失来说至关重要。

随着5G与云计算的⼤⼒发展，如何进行更自动化的运维以管理⼤规模的服务设备，是当今云⼚商⾮常关心的问题。针对这⼀问题，全球权威的IT研究与顾问咨询公司 Gartner于2016年提出了AIOps(Artificial Intelligence for IT Operations)概念，即智能运维。

AIOps涉及时间序列异常检测、关联分析、语义分析等多学科领域，旨在将⼈⼯智能的能⼒与⼯业运维相结合，通过机器学习的⽅法来解决复杂场景下的故障处理、变更管理、容量管理、服务资源调度等问题，帮助⼈们或代替⼈更好地做出决策，提⾼运维的效率。

其中最为困难的问题是诊断微服务架构的故障原因。

首先，服务侧的异常会由多方面的原因造成，有的时候是因为网络的抖动，有的时候是因为机器的故障，有的时候甚至是因为人为的变更，有效的根因定位需要整合非常多的数据（Log/Metric/Trace）以及丰富的专家经验；

其次，捕捉服务调用关系可以帮助我们追溯异常，但获取固定的服务拓扑关系比较困难，不同厂家有不同的微服务设计很难规范化，同时当服务调用频繁变化时，基于规则的静态故障定位方法便会失效；

再者，即使我们构建了服务之间的拓扑关系，由于存在故障的间接传播，使得当故障发生时，系统中的各项服务指标都会发生抖动，大量噪音使得模型难以“在万军之中取上将首级”，找到致使故障发生的问题机器和问题指标。

因此，在智能运维（AIOps）领域，故障诊断（根因分析）这是一个极具研究意义的系统性的难题。

当前针对微服务系统的故障根因问题，学术界已有一些成熟的工作，包括层次化定位故障的实体，捕捉服务指标之间的关联关系，分析故障在微服务之间传播等，涵盖亚马逊/微软/阿里/谷歌/Ebay/IBM/华为/腾讯/…等诸多大厂的云服务实践。

本文梳理近年来KDD/WWW/AAAI/VLDB/IWQOS/IEEE Access等国际顶会发表的有关论文，将根因分析场景大致抽象为几大方向：

• 搜索定位
• 指标关联
• 调用异常
• 组合分析

搜索定位

• 问题概述：该类根因分析旨在对指标总量进行实时的异常检测，再对检测出的异常查找定位导致该总量异常的细粒度指标集合

• 适用场景：业务KPI（集群请求错误数/网络整体延时/…)

• 问题定义：一个KPI指标根据多种属性分别监控。比如Page Views（PV），分别统计来自不同ISP和不同省份的PV。如Fig 所示：

  

  表中的f和v分别表示PV的期望的正常值和观测值，我们看到红色的部分观测值和正常值不符，这些PV就是发生了异常。根因定位问题希望的是定位发生异常时哪些属性取值导致了异常，比如Fig中的根因就应该是(Province=Beijing&Shanghai, ISP=*)。

主要算法

主要的算法我理解有两类，一类是将这个问题看作是关联规则挖掘（挖掘和异常关联的属性集合，即关联规则），另一类是设定一个判别根因的目标函数然后进行启发式搜索。也有一些其他的方法，比如用神经网络去做多分类，但是方法我感觉不是很实用，也没有发在很好的会议上，就略去了。

关联规则挖掘

• INFOCOM：首先对所有属性组合进行异常检测，在有异常的结果里面，然后用Apriori/FP-growth去搜索support超过阈值的属性组合，再根据confidence去筛选
• SIGMETRICS：用Apriori/FP-growth去搜索support超过阈值的属性组合，结合support+lift设计filter
• FSE：可能原本目标的问题和这里的问题不太一致，但是比较类似。它使用的Contrast set mining可以看为一种特殊的关联规则挖掘。contrast set mining是挖掘在不同的类中分布（support）差别很大的属性组合，而前两者挖掘的是和某个特定的类（即异常）关联的属性组合。

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

剪枝/启发式搜索

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

Adtributor

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

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

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

Recursive Adtributor

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

iDice

通常情况下，一个软件系统下用户上报问题（issue report）的数量是相对稳定的，但是有时会发生issue report的数量突变（通常是骤增）的情况，往往由个别属性组合（如“Country=India; TenantType=Home; DataCenter=DC1”）对应的issue report数量突变引起的。该文要解决的问题就是如何快速找出导致issue report数量突变的问题组合。

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

iDice的目标函数如下：

$$R=p_a * \ln \frac{p_a}{p_b}$$

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

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

• 首先，issue report数量本身太小的属性组合会被剪枝。这个剪枝策略显然就无法用在例如响应时间等指标上。
• 其次，issue report数量随时间没有突变的会被剪枝。
• 最后，根因属性组合需要把在故障时刻前后issue report数量有没有发生突变的细粒度属性组合分开。即有变化的应该是根因属性组合的细粒度属性组合，而没有变化的应该不是。

HotSpot

• 场景：在互联网运维中，有一类多维度KPI指标体系（如网页访问量PV、收入指标、错误计数等），其指标数目繁多、之间具有复杂的相互影响关系，通常只对KPI总量进行实时的异常检测算法，检测出异常后，再对体系查找定位导致该总量异常的细粒度指标集合。

• 示例：例如有可能是某一个省份(Province)或者某一运营商(ISP)的问题，也有可能是某个省份的某个运营商的问题。即(Province=Beijing, ISP=*)和(Province=*, ISP=China Mobile)、(Province=Beijing, ISP=China Mobile)都是合法的根因。

• 该文介绍一种对这种多维度指标体系中准确、高效地进行异常定位的方法，HotSpot，其构建多维时序指标的数据立方（Data Cube）并采用蒙特卡洛树搜索（MCTS）方法定位出根因元素集合。

• HotSpot首先的出发点是Ripple effect。假设两个属性的指标取值是相关的，那么它们两一定是由第三个属性（可能和它们两之一重合）共同导致的。所以如果一个属性组合是根因，那么他和别的属性都是独立的。也就是说根因属性组合的更细粒度属性组合的指标变化，和根因指标本身的指标变化，一定是成比例的。
• 基于这个假设，Hotspot设计了一个目标函数叫potential score。这个分数评估两方面的内容：对于待评估属性组合的更细粒度属性组合，它们的指标应该是异常的并且服从ripple effect；另一方遍，对于其他的属性组合，它们的指标应该是正常的。
• HotSpot和其他工作例如iDice很不一样的一点就是，它显式地考虑了有多个根因同时作用的情况。因此搜索空间直接变成了属性组合数目的幂，搜索空间的极大地增加了。为了解决这个问题，HotSpot采用了MCTS算法（蒙特卡洛树搜索，AlphaGo用过的）来进行启发式搜索。

Squeeze

• Squeeze依然是基于ripple effect，但是相比HotSpot额外证明了ripple effect对于衍生指标（例如响应时间等，具体定义参见论文）也成立。
• Squeeze的目标函数也基本还是potential score，只是做了一些改进，使得对于根因的属性数量比较大，根因的指标变化相比整体不够显著的时候，算法效果稳健了很多。
• 最大的变化是搜索过程。Squeeze没有采用暴力搜索加MCTS优化。而是采用了一套启发式策略来大大加速搜索，同时避免性能损失。
  • 首先，根据ripple effect，我们发现同一个根因所影响的细粒度属性组合的指标变化比例是相同的。因此我们利用这种先对细粒度属性组合进行聚类。
  • 之后，我们在每一类中再去搜索根因。因为此时已经不用考虑多根因同时作用的影响，所以问题简化了很多。此时，我们又采用了一个启发式策论。基本的思路是，根因属性组合对应的细粒度属性组合的指标应该都是异常的。

MID

• 和iDice针对的是同样的问题，采用了iDice相同的目标函数。不同之处在于搜索策略不同。
• MID采用了Meta-heuristic Searching的策略，它定义了四个操作，每个可以把一个属性组合更新为一个新的。然后定义了一个meta-heuristic 函数，用来评测一个属性取值是不是更有可能在根因中。具体的做法是评估其熵。
• 最后在搜索过程中，在每一步中MID评测当前属性组合的目标函数值，然后随机选择一个操作，根据meta-heuristic 函数选择操作要增删改的属性和取值，最后得到一个新的属性组合，进去下一轮循环。这个方法看起来很简单，但是有个巨大的问题就是每次随机选择的操作有可能重复出现已经搜索过的节点。但是如果简单禁止重复，那么就无法在搜索路径上进行回溯。因此这里需要一个合适的策略，我不太清楚怎么做能达到最好的效果。可惜原论文没有提及方法的细节。

ImpAPTr

• ImpAPTr只处理成功率下降的异常。
• ImpAPTr提出了两个目标函数，和Adtributor用过的解释力和surprise基本思路一致。但是ImpAPTr并没有假设单属性组合。它还是会搜索多个属性的组合，然后用这两个目标函数分别排序。再用排序得到的排名的均值作为最后的排序依据。
• 这个方法在根因的属性数量不多以及单根因的时候效果很好。

AutoRoot

• 改进了Squeeze。
• 首先是提出一种对聚类方法的修改，主要是在聚类之前会用KDE对density做一遍平滑。应该是比较有作用的。
• 其次是把generalized potential score中的绝对误差改成了相对误差。这在指标的时序预测误差较大的时候会受很大影响。
• 最后使用了在类内搜索的时候采用了一种新的启发式策略，比Squeeze多考虑了一些。

HALO

• 思想比较直观，考虑到多维属性中，某些属性之间其实存在包含关系（即有层次结构），首先提取这种层次结构，搜索时按照层次结构去搜索，减少了搜索范围
• 属性层次图+维度搜索，减少了搜索空间

参考文献

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. https://doi.org/10.1145/3392149
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. DOI:https://doi.org/10.1145/3106237.3106306 https://doi.org/10.1145/3106237.3106306
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. DOI:https://doi.org/10.1145/3368089.3409741 https://doi.org/10.1145/3368089.3409741
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. DOI:https://doi.org/10.1109/ISSRE5003.2020.00039 https://doi.org/10.1109/ISSRE5003.2020.00039
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. DOI:https://doi.org/10.1109/WCNC49053.2021.9417302 https://doi.org/10.1109/WCNC49053.2021.9417302
12. Zhang X, Du C, Li Y, et al. Halo: Hierarchy-aware fault localization for cloud systems[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021: 3948-3958.

调用异常

• 问题概述：该类根因分析一般具有明确的服务调用拓扑关系，旨在捕捉服务链路上的异常，定位异常实体
• 使用场景：中间件（微服务之间的调用异常）

trace调用链数据

在广义上，一个调用链代表一个事务或者流程在（分布式）系统中的执行过程。在OpenTracing标准中，调用链是多个Span组成的一个有向无环图（Directed Acyclic Graph，简称DAG），每一个Span代表调用链中被命名并计时的连续性执行片段。

下图是一个分布式调用的例子：客户端发起请求，请求首先到达负载均衡器，接着经过认证服务、计费服务，然后请求资源，最后返回结果。

数据被采集存储后，分布式追踪系统一般会选择使用包含时间轴的时序图来呈现这个调用链。

主要算法

因为近两年出现了一些针对网络路由调用和其他虚拟资源调用的论文，所以这些归在其他中。

trace调用链

trace特征构造

MEPFL

• 定位异常微服务+具体节点+故障类型
• 2个公开数据：Sock Shop和TrainTicket，https://fudanselab.github.io/Research-ESEC-FSE2019-AIOPS
• 用了专业领域知识来构建特征
• 多层预测，4个分类模型，细化故障定位，能获得微服务->具体instance节点->不同故障类型的定位

Seer

• 定位异常微服务+具体节点+具体metric
• 比较完整的系统设计，包括trace数据的采集+分布式存储+处理+故障预测+定位
• 两步走，先根据trace看具体微服务哪里出问题，根据trace数据+深度学习进行微服务的故障预测，然后深入具体微服务的节点node，根据更底层的metrics看哪里出问题

TraceAnomaly

• 定位异常微服务

• 微服务调用跟踪的异常通常表明基于微服务的大型软件服务的质量受到了损害。但是，由于以下原因，及时准确地检测trace异常非常具有挑战性：

  • 大量底层为服务
  • 它们之间的复杂调用关系
  • 响应时间于调用路径之间的相互依赖性

  我们的核心思想是使用机器学习在定期的离线培训期间自动学习trace的总体正常模式。

• 构造service trace vector（STV）

TraceRCA

• 定位异常微服务
• 先要知道异常发生，然后根据异常发生去检测trace里面的链路哪些有异常，哪些指标可能相关，得到异常set+features，然后排序
• 核心思想：a microservice with more abnormal and less normal traces passing through it is more likely to be the root cause

trace->有向图

Graph-based RCA

• 定位异常微服务
• 考虑到要检查的众多服务和连接，识别应用程序中检测到的异常的根本原因可能是一项困难且耗时的任务。基于这些体系结构的图表现形式，提出了根因分析框架。这些图可用于将系统中发生的任何异常情况与异常图库进行比较，该库可作为用户对这些异常进行故障排除的知识库。
• 构造调用图（点是容器+host，边是调用）->异常检测，子异常图->经验达标沉淀异常库，计算相似性

Trace RCA

• 定位异常微服务
• trace log->graph
• 根据历史情况聚类，沉淀trace的图库，并抽取正常的图模式
• 异常检测获得异常trace->匹配图库找对应的cluster->比较对应的normal pattern->计算

trace->无向图

invariance network

• 定位异常微服务
• 基于不变网络理论，没有调用关系，无向网络，自己构造图
• 检测系统异常在许多领域（例如安全性，故障管理和工业优化）引起了极大的兴趣。最近，不变网络已被证明是表征复杂系统行为的有效方法。在不变网络中，节点表示系统组件，边缘表示两个组件之间的稳定，重要的交互作用。不变性网络的结构和演化，尤其是消失的相关性，可以为定位因果异常和执行诊断提供重要的启示。然而，现有的利用不变网络检测因果异常的方法通常使用消失的相关性百分比来对可能的偶然分量进行排名，这有几个局限性：1）网络中的故障传播被忽略；2）根源偶然异常可能并不总是那些消失率很高的节点；3）消失的相关性的时间模式未用于鲁棒检测。为了解决这些局限性，在本文中，我们提出了一个基于网络扩散的框架，以识别重大的因果异常并对它们进行排名。我们的方法可以有效地对整个不变网络上的故障传播建模，并且可以对结构和随时间变化的破碎不变模式进行联合推断。

其他

NetBouncer

• IDC网络中的主动设备和链路故障定位，总共分为3步：
  1. 根据网络生成一个探测计划，保证在每个交换机都至少有一条健康路径的时候，在Clos网络中可连接识别
  2. 基于IP in IP的高效路径探测，通过交换机中的硬件功能来低成本明确探测路径
  3. 源于路径测量的故障推理，将故障定位的领域知识编码成专门的二次正则化项。此外，还开发了基于坐标下降的高效算法，利用了所有路径中的链路的稀疏特性，比SGD快一个数量级
• NetBouncer针对的是非瞬态（不短于两个探测间隔），分组丢失网络事件。虽然它擅长检测系统会忽略的灰色故障，但其他与丢包相关的事件也在其范围中

Deepview

• 针对的是VHD故障（虚拟硬盘）
• 在数据中心中，每当VHD访问速度太慢而无法响应时，客户系统会崩溃。为了保护数据完整性，当VHD不响应时，必须暂停客用操作系统。但是不能永久暂停，过慢VM可能导致客户无法通过自己的应用程序级SLAs。经过一些等待后，一个合理的选择是通过崩溃的客用操作系统来向客户暴露潜在的VHD访问失败。简称此VHD故障由计算存储分离或VHD故障引起

• 以全局视角将该问题建模成二部图，然后采用两种推理算法：

  • Lasso regression来选择组件的小部分子集作为候选集
  • 假设检验作为处理强信号和弱信号并给组件打标记的一种原则性和可解释的方式

• 同样利用了clos网络的性质

参考文献

1. Zhou X, Peng X, Xie T, et al. Latent error prediction and fault localization for microservice applications by learning from system trace logs[C]//Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2019: 683-694.
2. Gan Y, Zhang Y, Hu K, et al. Seer: Leveraging big data to navigate the complexity of performance debugging in cloud microservices[C]//Proceedings of the twenty-fourth international conference on architectural support for programming languages and operating systems. 2019: 19-33.
3. Liu P, Xu H, Ouyang Q, et al. Unsupervised detection of microservice trace anomalies through service-level deep bayesian networks[C]//2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE). IEEE, 2020: 48-58.
4. Li Z, Chen J, Jiao R, et al. Practical root cause localization for microservice systems via trace analysis[C]//2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS). IEEE, 2021: 1-10.
5. Brandón Á, Solé M, Huélamo A, et al. Graph-based root cause analysis for service-oriented and microservice architectures[J]. Journal of Systems and Software, 2020, 159: 110432.
6. Cai Z, Li W, Zhu W, et al. A real-time trace-level root-cause diagnosis system in alibaba datacenters[J]. IEEE Access, 2019, 7: 142692-142702.
7. Cheng W, Zhang K, Chen H, et al. Ranking causal anomalies via temporal and dynamical analysis on vanishing correlations[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016: 805-814.
8. Tan C, Jin Z, Guo C, et al. NetBouncer: Active Device and Link Failure Localization in Data Center Networks[C]//NSDI. 2019: 599-614.
9. Zhang Q, Yu G, Guo C, et al. Deepview: Virtual disk failure diagnosis and pattern detection for azure[C]//15th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 18). 2018: 519-532.

指标关联

问题概述：该类根因分析旨在分析海量的多维时间序列，找到故障时不同指标之间的关联关系（因果关系）

适用场景：机器多维指标分析（disk&load/net&load/cpu&mem/…)

主要算法

时序相关性分析

ε-diagnosis

• 基于这样的假设：服务异常前后变化大的为根因
• 具体做法就是对于每个metric，对异常前和异常后的序列对做假设检验

Log AD RCA

• 基于假设是：和从日志中检测出的异常得分序列相关性高的metric最有可能是根因

拓扑图分析

• 拓扑图一般指的是服务依赖关系图
• 该类方法首先通过微服务之间的关系或者微服务和host之间的关系来构建拓扑图，然后针对因果图照出根因KPI或者service，主要方法有BFS、随机游走和计算图性质等

Sieve

1. 服务依赖图构建
2. 对metrics聚类，每个簇选取有代表性的metric：metric包括系统级别（如CPU、memory和IO等）的和应用级别的（如RT）
3. 找根因 基于服务依赖图+Granger Causality构建图

MicroRCA

已知整体故障，定位到具体微服务，总体思路比较简单：

1. 构建图：根据ms和host的依赖关系，以及ms之间的交互关系来构建属性图
2. 提取异常子图
3. 计算有权图权重
4. 通过personalized pagerank 计算中心性得分作为排序

因果图分析

年份期刊	论文方法	metrics关联	根因诊断	优缺点
2016TSC	CauseInfer	微服务之间因果关系：基于traffic lag KPI之间因果关系：PC算法	DFS：从frontend出发，进行DFS，若当前节点异常，则继续访问其孩子节点，直到最后一个无孩子的异常节点为止；若当前节点正常，则访问其兄弟节点。当一个异常节点没有孩子节点	假设了数据不遗漏，要求因果图的每一层都要有异常表现；不适用于数据遗漏的场景
2018ICST	LOUD	Granger causality test（因果图构建后之后，只看异常KPI相关的子图）	eigenvector centrality non-backtracking centrality HITS PageRank 实验中PageRank效果最好	根据某次故障的异常KPI子图进行PageRank等多种方式，得到分数最高的根因，给不出异常传播链路
2018CCGRID	CloudRanger	PC算法	随机游走（计算转移矩阵时考虑了上次访问节点的权重）设计三种策略	构图的方式借用了贝叶斯网络的d-分离 随机游走的策略可以参考
2019ICWS王平	MS-Rank	PC-stable算法	随机游走（带metrics权重，权重还会根据反馈结果进行调整）	基本上是基于CloudRanger，不过是在service的metric增加了一些设计
2019WWW微软	AirAlert	FCI based on the causal Markov assumption pearson correlation	没有诊断环节 构建因果图的目的时提取后面预测模型所需要的特征	构造因果图的方法可以参考
2020WWW王平	AutoMAP	PC算法+图的相加相减操作	随机游走（带metrics权重，权重还会根据反馈结果进行调整）	构造因果图阶段，根据不同metrics分别构建图，获得边权重；根据异常和正常情况也分别构建图；最后也会有图的融合或者相减的操作 和MS-Rank类似，有反馈机制，用于调整metrics权重 随机游走阶段没啥特别创新
2020IWQoS裴丹阿里	MicroCause	KPI之间因果算法：PCMCI算法/PCTS算法	随机游走（计算转移矩阵时用偏相关）+异常程度+人工经验 确定排序	因果推断策略模块的作用，从结果来看，效果一般 随机游走策略的作用，这部分改进效果明显，但是未分开比较偏相关、异常程度、先验这三部分的作用，没法说明各个子模块分别带来多大提升 有源码
2020AS	O&M Graph	PC算法+领域知识图谱	BFS，找出所有路径再基于规则排序： 路径权重之和越大，排序越靠前；路径长度越短，排序越靠前	领域知识图谱，其实是物理设备设施的拓扑，从而得到这些设备设施上KPI的连接 在构造因果图时，如果符合这些连接，直接保留 路径长度越短，排序越靠前，如果有遗漏数据等情况，不是越短越好
2021SIGSOFT王平	DyCause	Granger causality test->时间动态因果图+多图融合	BFS	动态因果关系只能用在时间序列中，不适用于事件
2021CIKM阿里	CloudRCA	PC算法+CMDB	贝叶斯网络
2021ASE	Groot	以事件作为节点，通过专家规则得到因果边，构造出因果图	PageRank改造过后的GrootRank	全依靠专家只是得到事件因果边，忽略了专家覆盖不了的情况 给不出故障传播链路

参考文献

1. Nguyen H, Tan Y, Gu X. Pal: P ropagation-aware a nomaly l ocalization for cloud hosted distributed applications[M]//Managing Large-scale Systems via the Analysis of System Logs and the Application of Machine Learning Techniques. 2011: 1-8.
2. Nguyen H, Shen Z, Tan Y, et al. FChain: Toward black-box online fault localization for cloud systems[C]//2013 IEEE 33rd International Conference on Distributed Computing Systems. IEEE, 2013: 21-30.
3. Shan H, Chen Y, Liu H, et al. ε-diagnosis: Unsupervised and real-time diagnosis of small-window long-tail latency in large-scale microservice platforms[C]//The World Wide Web Conference. 2019: 3215-3222.
4. Wang L, Zhao N, Chen J, et al. Root-cause metric location for microservice systems via log anomaly detection[C]//2020 IEEE International Conference on Web Services (ICWS). IEEE, 2020: 142-150.
5. Thalheim J, Rodrigues A, Akkus I E, et al. Sieve: Actionable insights from monitored metrics in distributed systems[C]//Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference. 2017: 14-27.
6. Samir A, Pahl C. Dla: Detecting and localizing anomalies in containerized microservice architectures using markov models[C]//2019 7th International Conference on Future Internet of Things and Cloud (FiCloud). IEEE, 2019: 205-213.
7. Wu L, Tordsson J, Elmroth E, et al. Microrca: Root cause localization of performance issues in microservices[C]//NOMS 2020-2020 IEEE/IFIP Network Operations and Management Symposium. IEEE, 2020: 1-9.
8. Wu L, Bogatinovski J, Nedelkoski S, et al. Performance diagnosis in cloud microservices using deep learning[C]//Service-Oriented Computing–ICSOC 2020 Workshops: AIOps, CFTIC, STRAPS, AI-PA, AI-IOTS, and Satellite Events, Dubai, United Arab Emirates, December 14–17, 2020, Proceedings. Cham: Springer International Publishing, 2021: 85-96.
9. Wu L, Bogatinovski J, Nedelkoski S, et al. Performance diagnosis in cloud microservices using deep learning[C]//Service-Oriented Computing–ICSOC 2020 Workshops: AIOps, CFTIC, STRAPS, AI-PA, AI-IOTS, and Satellite Events, Dubai, United Arab Emirates, December 14–17, 2020, Proceedings. Cham: Springer International Publishing, 2021: 85-96.
10. Chen P, Qi Y, Zheng P, et al. Causeinfer: Automatic and distributed performance diagnosis with hierarchical causality graph in large distributed systems[C]//IEEE INFOCOM 2014-IEEE Conference on Computer Communications. IEEE, 2014: 1887-1895.
11. Mariani L, Monni C, Pezzé M, et al. Localizing faults in cloud systems[C]//2018 IEEE 11th International Conference on Software Testing, Verification and Validation (ICST). IEEE, 2018: 262-273.
12. Wang P, Xu J, Ma M, et al. Cloudranger: Root cause identification for cloud native systems[C]//2018 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID). IEEE, 2018: 492-502.
13. Ma M, Lin W, Pan D, et al. Ms-rank: Multi-metric and self-adaptive root cause diagnosis for microservice applications[C]//2019 IEEE International Conference on Web Services (ICWS). IEEE, 2019: 60-67.
14. Chen Y, Yang X, Lin Q, et al. Outage prediction and diagnosis for cloud service systems[C]//The world wide web conference. 2019: 2659-2665.
15. Ma M, Xu J, Wang Y, et al. Automap: Diagnose your microservice-based web applications automatically[C]//Proceedings of The Web Conference 2020. 2020: 246-258.
16. Meng Y, Zhang S, Sun Y, et al. Localizing failure root causes in a microservice through causality inference[C]//2020 IEEE/ACM 28th International Symposium on Quality of Service (IWQoS). IEEE, 2020: 1-10.
17. Qiu J, Du Q, Yin K, et al. A causality mining and knowledge graph based method of root cause diagnosis for performance anomaly in cloud applications[J]. Applied Sciences, 2020, 10(6): 2166.
18. Pan Y, Ma M, Jiang X, et al. DyCause: Crowdsourcing to Diagnose Microservice Kernel Failure[J]. IEEE Transactions on Dependable and Secure Computing, 2023.
19. Zhang Y, Guan Z, Qian H, et al. CloudRCA: a root cause analysis framework for cloud computing platforms[C]//Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021: 4373-4382.
20. Wang H, Wu Z, Jiang H, et al. Groot: An event-graph-based approach for root cause analysis in industrial settings[C]//2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2021: 419-429.

组合分析

方法概述：该类根因分析旨在组合更多的数据进行分析，包括事件分析、调用与指标（Trace&Metric）、调用与日志（Trace&Log）

适用场景：构建AIOps系统

主要算法

Correlating Events with Time Series

• evaluate the correlation between time series data and event data
  • 是否相关
  • 是否有延时
  • 正相关/负相关
• 互联网产品在日常运行提供服务时，运维人员会对机器、进程和服务层面的日志、事件和性能数据等进行自动测量，这些数据主要分为事件（Event）和时间序列（Time Series）两大类数据。时序数据指的是实值-时间序列（通常有固定的时间间隔），例如CPU使用率等；而事件数据指的是记录了特定事件发生的序列，例如内存溢出事件等。为了保证产品的服务质量、减少服务宕机时间，从而避免更大的经济损失，对关键的服务事件的诊断显得尤为重要。实际的运维工作中，对服务事件进行诊断时，运维人员可以通过分析与服务事件相关的时序数据，来对事件发生的原因进行分析。虽然这个相关关系不能完全准确的反映真实的因果关系，但是仍然可以为诊断提供一些很好的线索和启示。

COT

• COT的思路是，对于历史上的每一个 Outage，研究员们都挖掘与该 Outage 相关的故障之间的关联信息，并以服务为单位，将故障之间的关联信息进行聚合，然后，以 Outage 中服务之间的故障关联为特征，以 Outage 的根因服务为标签，训练机器学习模型。在新的 Outage 发生后，研究员们可以通过历史故障的关联信息，快速找到与该 Outage 相关的故障，并用相同的方法对这些故障进行聚合与特征提取，再利用先前训练好的机器学习模型来预测其根因服务。

Roots

• PaaS的应用异常检测+根因定位（负载变化、云服务）
• Roots不需要应用程序及检测，它结合使用元数据注入和平台级工具来跟踪PaaS云中由应用程序请求触发的事件
• 针对应用的请求，在全链路打标，PaaS内部继续打标跟踪，并收集分析，让用户不再看黑盒

Multitier Service RCA

• 公有云租户应用根因定位，VM级别定位，自己或者别人的VM都可以
  • 采集trace+VM metrics，计算调用时间
  • 基于VM Communication Graph VCG构造anomaly propagation graph(APG)，边是调用关系以及同物理机的协同关系
  • 随机游走，概率是相似度-VM的metric与调用响应时间的Pearson相关系数

FluxRank

• 在运维领域，服务侧的异常会由多方面的原因造成，有的时候是因为网络的抖动，有的时候是因为机器的故障，有的时候甚至是因为人为的变更。该论文主要介绍了如何从服务的故障定位到局部异常的机器，也就是说在发现服务故障的同时，进一步推断出是由哪些机器出现问题而导致的。该文介绍了FluxRank，它是一种可广泛部署的框架，可以自动，准确地定位根本原因机器，以便可以触发某些操作来减轻服务故障。

• 从服务故障（service KPI）定位到局部异常的机器及KPI（类似MicroCause）

• 三个步骤：

  1. Change Quantification，找出服务异常时间段内每台机器各个KPI的变化时间和变化程度

  2. Digest Distillation，以各台机器的KPI变化程度作为特征，进行机器级别的聚类，将KPI变化相似的机器聚类到一个簇

  3. Digest Ranking，建立逻辑回归模型，对2中形成的簇进行排序，将最可能引发故障的机器簇排序靠前，并根据KPI变化程度对簇内KPI排序

• 领域总结：

  • 引起故障的机器的某些KPI的change start time在服务故障点之前
  • 引起故障机器的哥哥KPI的change start time比较接近，而其他机器的各个KPI的change start time一般相差大一些。（可以解释为异常从引起故障的机器传递到其他机器和模块需要的时间各不相同，受一些随机因素影响）
  • 引起故障的机器的某些KPI的变化程度比较大

Gandalf

• Gandalf没有采用单独的组件日志分别分析每个部署的方法，而是采用自顶向下的方法来全面评估部署的影响。 Gandalf持续监视来自基础设施的监控数据，包括服务级别日志、性能计数器和流程级别事件。 当检测到系统异常时，Gandalf会分析它是否由部署引起。 如果发现部署不正确，Gandalf会将其停止。
• Gandalf的核心决策逻辑是由异常检测、相关分析和影响评估组成的。 该模型首先从原始数据中检测异常。 然后，它通过时间和空间相关性以及整体排序算法（ensemble ranking algorithm），判断部署是否与检测到的故障高度相关。 最后，使用高斯判别器（ Gaussian discriminant classifier）来确定可疑部署所造成的影响是否足以阻止部署。
• Gandalf系统是lambda架构，将实时决策引擎与批处理决策引擎结合在一起。 实时引擎监测部署前后一个小时的时间窗口，以检测紧急问题。 批处理引擎分析系统30天的状况，以检测更复杂、潜在的问题。 当Gandalf识别出不良的部署时，它会自动通知部署引擎停止部署，并向相关团队发出通知。

GRANO

• 通过提供系统组件拓扑，警报和应用程序事件的整体视图，该文介绍了Grano模型，这是用于云原生分布式数据平台的端到端异常检测和根因分析系统。Grano提供：一个检测层，用于处理大量时间序列监视数据，以检测逻辑和物理系统组件的异常；具有新颖图形模型和算法的异常图形层，可利用系统拓扑数据和检测结果在系统组件级别识别根本原因；应用层自动通知待命人员，并通过交互式图形界面提供实时和按需的RCA支持。该系统使用eBay的生产数据进行部署和评估，以帮助值班人员将根本原因的识别时间从数小时缩短至数分钟。
• 云原生数据库异常检测+根因定位（软件节点+硬件节点）
  1. 采集metrics+各种alarm+event
  2. 异常检测之后形成event+各种事件
  3. 构造异常图anomaly graph
  4. edge+node score
  5. score propagation
  6. root cause， the alarm types，alarm frequency， and topology for the suspected incidents

GMTA

• 微服务调用异常定位系统，trace
• 完整系统：包括数据采集、存储、流式处理、不同level的数据访问、异常trace/path展示与对比、系统展示等
• 多层数据消费：将trace提炼成graph聚类成为path，结合领域知识提炼业务流

Groot

• metrics异常检测之后形成event+各种事件，trace
• 针对微服务系统根因定位（具体事件+节点）
• 整体流程
  1. 构造通用节点、服务依赖图（基于trace、拓扑等）
  2. 构造事件因果图（整合SRE的经验）
  3. 异常子图进行优化的PageRank排序打分
  4. root event

参考文献

1. Luo C, Lou J G, Lin Q, et al. Correlating events with time series for incident diagnosis[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014: 1583-1592.
2. Wang Y, Li G, Wang Z, et al. Fast outage analysis of large-scale production clouds with service correlation mining[C]//2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE). IEEE, 2021: 885-896.
3. Jayathilaka H, Krintz C, Wolski R. Performance monitoring and root cause analysis for cloud-hosted web applications[C]//Proceedings of the 26th International Conference on World Wide Web. 2017: 469-478.
4. Weng J, Wang J H, Yang J, et al. Root cause analysis of anomalies of multitier services in public clouds[J]. IEEE/ACM Transactions on Networking, 2018, 26(4): 1646-1659.
5. Liu P, Chen Y, Nie X, et al. Fluxrank: A widely-deployable framework to automatically localizing root cause machines for software service failure mitigation[C]//2019 IEEE 30th International Symposium on Software Reliability Engineering (ISSRE). IEEE, 2019: 35-46.
6. Li Z, Cheng Q, Hsieh K, et al. Gandalf: An Intelligent, End-To-End Analytics Service for Safe Deployment in Large-Scale Cloud Infrastructure[C]//NSDI. 2020, 20: 389-402.
7. Wang H, Nguyen P, Li J, et al. Grano: Interactive graph-based root cause analysis for cloud-native distributed data platform[J]. Proceedings of the VLDB Endowment, 2019, 12(12): 1942-1945.
8. Guo X, Peng X, Wang H, et al. Graph-based trace analysis for microservice architecture understanding and problem diagnosis[C]//Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2020: 1387-1397.
9. Wang H, Wu Z, Jiang H, et al. Groot: An event-graph-based approach for root cause analysis in industrial settings[C]//2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2021: 419-429.