WWW 2020 | 多维时间序列间的异常关联与因果推断

关注微信公众号“时序人”获取更好的阅读体验

时间序列学术前沿

1. NeurIPS 2020 | 时间序列相关论文一览
2. ICML 2020 | 时间序列相关论文一览
3. KDD 2020 | 时间序列相关论文一览
4. 智能运维 | 故障诊断与根因分析论文一览
5. WWW 2020 | 通过多源时间序列诊断微服务故障根因
6. WWW 2020 | 多源时序数据驱动用于窃电行为识别
7. AAAI 2020 | 时序转化为图用于可解释可推理的异常检测

写在前面

故障诊断是服务稳定性的重要一环，在工业界有非常丰富的应用场景。过去运维人员诊断根因常常需要人工浏览多种监控指标找关联关系，构建服务拓扑以分析故障传播等工作，非常耗费人力。是否有模型可以自动的分析多维时间序列之间的关联关系，推导根因呢？来自北京大学、中山大学的研究者们所带来的工作：《AutoMAP: Diagnose Your Microservice-based Web Applications Automatically》就这个问题给出了他们的一个方案。

微服务架构的高度复杂性和动态性使得故障诊断十分困难。首先，获取固定的服务拓扑关系比较困难，同时这种静态的故障排除方法无法适用于服务调用频繁变化的情况；即时我们知道了服务之间的拓扑关系，由于存在故障的间接传播，我们也缺乏有效的动态诊断机制来判断根因。此外，基于单一指标的时间序列异常检测算法通常无法识别到故障的根本原因，因为单一指标不足以表征各种服务中所发生的异常。

有鉴于此，该工作设计了一种名为AutoMAP的模型，其利用多种类型的时序指标来动态生成服务关联，诊断根因。针对多维时间序列，该工作分析时序之间的异常关联，生成****异常行为图来描述不同服务之间的相关性。根据行为图，该工作使用正向、自向和反向随机游走算法设计启发式模型，用以识别服务故障的根本原因。

AutoMAP可以快速部署在各种基于微服务的系统中，无需专家经验知识启动。 同时，它也支持引入专家知识以提高诊断的准确性。

其研究成果被世界万维网顶级会议 WWW-20 论文收录。

会议简介

万维网国际会议(The World Wide Web International Conference，简称WWW)起源于1994年，是计算机与互联网领域的顶级学术会议，被列为《中国计算机学会推荐国际学术会议和期刊目录》(CCF) 中的A类学术会议，录用率常年维持在14%～17%。

大会汇集了国际著名大学、研究机构、跨国企业和国际标准化组织的一流学者和产业界精英，持续推动着互联网技术的发展，尤其是为各国信息化建设提供了重要的技术标准。

论文标题 | AutoMAP: Diagnose Your Microservice-based Web Applications Automatically
论文来源 | WWW 2020
论文链接 | https://dl.acm.org/doi/10.1145/3366423.3380111
场景模拟 | https://github.com/rshriram/pymicro

背景

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

上图是一个基于微服务的Web应用程序，其中六边形代表服务，Web应用程序通过API网关调用在不同主机和容器上运行的服务。图中展示了一个异常传播的简单示例：红色代表根本原因，黄色代表受影响的服务，箭头代表同步（实线）或异步请求（虚线）。这里可见，未调用的微服务发生了异常，它可能影响同一主机或容器中的其他服务，并导致异常传播。 因此，即使我们知道服务的调用拓扑，由于存在间接故障传播，我们也不能直接定位出原因。

运维人员通常会配置一系列监控指标以持续监视每个微服务的性能。这些指标包括用户可感知的指标（KPI），包括响应时间（RT）、每秒查询量（QPS），中间件的RT，CPU与内存等。当KPI异常时，通常表示微服务故障，而这往往是由基础组件的异常导致的。探寻故障的根本原因往往需要下探所调用服务的多个指标。

因此，给定一个微服务故障实例下的N个指标，我们如何找到引发故障的Top N个根因，及其异常关联关系，是该研究主要研究的问题。

方法

该文提出的AutoMap模型，主要分为如下6步进行：

1. 确定多种类型指标的时序数据采样间隔；
2. 对多种类型指标进行关联分析，构建异常行为图（anomaly behavior graph）；
3. 根据异常信息对图进行“增加”或“删减”操作；
4. 使用启发****根因分析算法（heuristic root cause detection）对所构建的图建模，输出候选根因；
5. 验证根因结果的有效性，计算准确度；
6. 更新指标权重。如果有新的异常发生，重复 1-6 的过程。

确定采样间隔

采样间隔的选择取决于系统的特性。具体来说，合理的选择是对所有微服务统计平均呼叫间隔。 换句话说，在此间隔内，服务平均被调用一次。 公式如下：

∑ i = 1 n T h e   n u m b e r   o f   c a l l i n g   v i T h e   n u m b e r   o f   t o t a l   s e r v i c e   c a l l i n g × ( i n t e r v a l   o f   c a l l i n g   v i ) \sum_{i=1}^n\frac{The~number~of~calling~v_i}{The~number~of~total~service~calling} \times (interval~of~calling~v_i) i=1∑n​The number of total service callingThe number of calling vi​​×(interval of calling vi​)

构建异常行为图

该文提到，因为微服务架构中的调用依赖关系是复杂且动态的，应用程序的服务调用拓扑需要花费大量时间进行分析与构建。该文提出直接分析多种服务的指标，捕捉异常，构建指标之间的关系，从而推导出异常行为图进行根因分析。一个异常行为图定义为： G ( V , E , W ) G(V, E, W) G(V,E,W)， v i ∈ V v_i \in V vi​∈V为顶点， e i , j ∈ E e_{i, j} \in E ei,j​∈E为边。这里 W i , j , k ∈ [ 0 , 1 ] W_{i, j, k}\in[0,1] Wi,j,k​∈[0,1]是一个边的权重矩阵，表示点 v i v_i vi​受点KaTeX parse error: Expected group after ‘_’ at position 2: v_̲上的第k个指标的影响程度。图的构建分为下面几步：

1. 根据微服务个数，构建一个全连接图，边的权重全部为1
2. 对于每一个指标 k，测试点 v i , v j v_i, v_j vi​,vj​之间的条件独立性，如果独立， W i , j , k = 0 W_{i,j,k} = 0 Wi,j,k​=0
3. 如果在m个指标中，存在一个指标k，使得** W i , j , k = 0 W_{i,j,k} = 0 Wi,j,k​=0**，则移除边 e i , j e_{i,j} ei,j​
4. 对无向图抽取三元组 ( v i , v j , v l ) (v_i, v_j, v_l) (vi​,vj​,vl​)，采用同样的独立检验探寻满足 v i → v j ← v l v_i \rightarrow v_j \leftarrow v_l vi​→vj​←vl​条件的V结构

加法运算与服务归档

真实云服务场景中，在没有任何先验知识的情况下，模型需要对上百种或上千种微服务进行分析，根据其特征对各种服务进行分类是一项艰巨的任务。直接的方法是使用正常状态下指标的多个历史观察，构建多个行为图，并将它们汇总以显示服务的链路关系。 因此，该文在行为图上定义了加法运算：

G ( V , E , W ) = G a ( v a , E a , W a ) + G b ( V b , E b , W b ) , V = V a ∪ V b , E = E a ∪ E b G(V,E,W) = G_a(v_a,E_a,W_a) + G_b(V_b, E_b, W_b), V=V_a\cup V_b, E=E_a\cup E_b G(V,E,W)=Ga​(va​,Ea​,Wa​)+Gb​(Vb​,Eb​,Wb​),V=Va​∪Vb​,E=Ea​∪Eb​

[ W ] i , j , k = ∣ ∣ [ W a ] i , j ∣ ∣ × [ W a ] i , j , k + ∣ ∣ [ W b ] i , j ∣ ∣ × [ W b ] i , j , k ∣ ∣ [ W a ] i , j ∣ ∣ + ∣ ∣ [ W b ] i , j ∣ ∣ , i , j ∈ [ 1 , n ] , k ∈ [ 1 , m ] [W]_{i,j,k}=\frac{||[W_a]_{i,j}|| \times [W_a]_{i,j,k} + ||[W_b]_{i,j}|| \times [W_b]_{i,j,k}}{||[W_a]_{i,j}|| + ||[W_b]_{i,j}||}, i, j \in [1, n], k \in [1, m] [W]i,j,k​=∣∣[Wa​]i,j​∣∣+∣∣[Wb​]i,j​∣∣∣∣[Wa​]i,j​∣∣×[Wa​]i,j,k​+∣∣[Wb​]i,j​∣∣×[Wb​]i,j,k​​,i,j∈[1,n],k∈[1,m]

减法运算与异常归档

实际上，只有少数服务才会导致故障传播。 由于服务的大部分与异常无关，因此最初构造的行为图可能包含冗余的服务和相关性。因此，该文定义了另一种减法运算：

G ( V , E , W ) = G a ( v a , E a , W a ) − G b ( V b , E b , W b ) , V = V a ∩ V b , E = E a ∩ E b G(V,E,W) = G_a(v_a,E_a,W_a) – G_b(V_b, E_b, W_b), V=V_a\cap V_b, E=E_a\cap E_b G(V,E,W)=Ga​(va​,Ea​,Wa​)−Gb​(Vb​,Eb​,Wb​),V=Va​∩Vb​,E=Ea​∩Eb​

指标权重学习

AutoMAP通过人工经验选择合适的诊断指标。也就是说，如果历史事件中已确认的根本原因在某些指标上显示与前段应用有高度相关性，则在类似情况下，使用相同指标进行根因探寻。为此，AutoMAP引入了基于经验信息与相关性的指标权重学习机制：

服务关联性
根据构建出的行为图，计算服务 v i , v j v_i, v_j vi​,vj​之间的相关性 C k = [ C k ] n × n \mathbf{C}_k = [C_k]_{n\times n} Ck​=[Ck​]n×n​:

**
结果准确性
为了量化指标k所能提供的故障关联置信度，该文引入了一种度量来评估结果的精度，表示为 P ( G ) P(G) P(G)，其中G是构建的异常行为图。越高的结果准确度表明该算法可以更准确地识别根本原因，从而减少了要调查的错误候选指标对象。

上图展示了AutoMAP中相似度权重学习的过程。 给定异常行为图 G A G_A GA​，AutoMap在历史记录中搜索与 G A G_A GA​相似的top-k个候选图，并将结果表示为 { G 1 , G 2 , . . . , G k } \{G_1,G_2,…,G_k\} { G1​,G2​,...,Gk​}。 因此， G A G_A GA​上各指标的权重是通过历史的故障根因与前端应用的相关性分数来计算的。

根因分析

AutoMAP采用动态启发式算法来确定根本原因，它模拟了传统故障排除中的操作。 更具体地说，从前端应用开始，遵循服务调用拓扑，并根据其与异常的指标的相关性逐步排查每个服务。有更多调查路径作为目标的节点更有可能是根本原因。基于此，该文提出了一种具有三种转移类型的随机游走算法，即正向，自向和反向转移。

正向转移（Forward Transition）
一般的。对于异常行为图的一个访问按照概率 p i , j p_{i,j} pi,j​走。根据根本原因诊断的基本概念，从 v i v_i vi​访问 v f e v_{fe} vfe​按照其相关性作为概率进行游走。

自向转移（Self Transition）
自身转移会鼓励访问者在其当前访问的服务上停留更长的时间，以防止访问者中没有一个与邻居的相关性很高。

反向转移（Backward Transition）
另一种情况，当访问者正在访问相关分数较低的特定服务时，如果其所有邻近服务与给定异常的相关性都较低，则可能找不到任何离开的途径。因此使用反向转移跳出。

给定一个异常行为图，根因的探寻通过随机游走算法，从前段应用节点 v f e v_{fe} vfe​开始，计算正向，反向自身的转移概率，并随机选择其中之一。 访问者按顺序访问服务，即从访问者当前访问的节点及其邻居中随机选择下一个目标。 AutoMap记录每个服务被访问了多少次，并输出结果降序的列表，以此作为可能根因的排序。

实验

该文的实验在IBM Cloud 的真实数据集上进行。总共从1732个微服务API中收集了大约1500万个指标。

总结

• 该文提出了一种基于多维时序数据关联分析的根因分析方法，不依赖先验知识推导调用拓扑，可以适合大多数应用程序场景；
• 该方法的归档设计可以很容易将专家经验引入，提升整体模型的准确度；
• 该方法通过指标关联生成出服务关联图，不仅可以诊断系统故障，还可以发现设计缺陷和潜在问题（发现间接传播）。

更多原创内容与系列分享，欢迎关注微信公众号“时序人”获取。

本文地址：https://blog.csdn.net/weixin_53741275/article/details/111973738