该论文是Universidad Politécnica de Madrid（马德里技术大学）和CA科技公司（现被思科收购）合作于2020年发表在Journal of Systems and Software上的一篇论文。题目是《Graph-based Root Cause Analysis for Service-Oriented and Microservice Architectures》/ 《面向服务及微服务架构基于图论的根因分析》
整体架构
论文首先定义一个普遍的网络服务场景，在这个场景中包含负载均衡（load bancer），比如HAproxy，包含数个web服务，比如WordPress，包含中间件存储，比如MySQL。每个element运行在各自集群独立的容器中，容器之间能够相互通信。每个element都是一个节点，节点会包含一些属性（attr），这些属性可能是一些数值型的指标信息，比如cpu usage, DiskIO，或者是一些类别信息，比如说是一个标签信息用来指示当前节点是容器还是物理机，当前服务是前端还是后端服务等等。如下图所示
显然，上述拓扑图中，如果有某个节点发生异常会产生链式反应。比如若load balancer发生了异常，通常会导致某个服务的入口流量减少。论文提出了一种基于图论的根因定位系统，如下图所示：
系统图生成模块（System graph module)
该模块的职责是将系统中所有指标、网络活动，日志和异常情况等在给定的时间窗口（例如15s）用结构化的图形表示，相当于给某个系统的当前状态作了一个快照（snapshot）。这个时间窗口是可以调整的，可以根据系统的变更率、监控频率进行调整。时间窗口不宜设置得过大或过小，较大的时间窗口会导致指标信息粗略，无法检测到某些异常；窗口设置得过小则会导致收集到大量噪音数据，无法得到有用的信息。
图的构建过程，论文在第五部分会详细介绍，这里先给出了图元素的组成部分：
- 节点（Nodes）
节点可以用来表示任意一个容器，主机或者和系统交互的任意元素。每个节点会包含多个属性。
- 边（Edges)
边表示系统中各个元素之间的网络通信，例如tcp连接或http请求。还可以用来表示逻辑连接，例如容器与托管该容器之间的关系。与节点相同，边具备不同类型的多个属性。
- 属性（Attr）
属性从收集的指标、日志和异常中获得，包含以下几种类型：
- 数值型：可以包含离散或者连续时间范围内的指标值，比如一段时间内的cpu usage。
- 类别型：特定类别的标签信息。比如特定容器内的Docker镜像（比如HAproxy v1.8，WordPress V4.9)
- 本体类型（Ontological): 此类型用来表示概念的层级结构，如下图所示，该类型的属性用来描述语义上相同但是涉及不同元素的问题。比如，在负载均衡场景中，Nginx实例和WordPress实例是等同的，因为他们都是前端服务器。
- 异常等级：可以视为一种特殊的属性，表示给定的节点或者边正在发生异常。可以用任意的异常检测方法来识别是否异常并在图中作标记。之后，异常区域提取器将使用它在系统图之外构建异常子图。
异常区域提取模块（Anomalous region module）
该模块能够对2.1中输出的系统图进行异常区域提取，该模块由两部分组成。
- 异常检测系统：检测并标记系统图中的异常节点
- 异常区域提取器
其中，1可以使用任何有效的异常检测技术，论文假设存在此模块，不关心这一块如何实现，因为论文专注于检测到的异常而非如何检测异常。
论文基于异常发生时会影响其相关节点这样的直觉，用异常区域提取器对检测到并被标记的异常节点生成异常子图。考虑到计算资源有限以及出于可伸缩性目的，异常区域提取器仅对异常周边有限节点进行提取。这样做有一个明显的缺点是，可能根因节点不在该子图范围之内，但是，该提取器提取范围是可以根据需要设置。提取出的异常子图仍然包含节点、边以及各自的属性信息。异常区域中的节点、边和属性可以单独设置权重，以表示该异常区域中给定元素的重要性。例如，机器中cpu usage消耗过多产生的异常，cpu对应属性的权重可能会相应增加，后续图相似性模块会用到这些权重。
提取到的异常区域会发送到相似性模块，和已经定位过的异常进行相似性匹配。
下图是异常区域提取示意图：
异常模式库（The pattern library module)
异常模式库是一系列经专家标注过的异常区域的集合，这些异常区域可以和系统中正在发生的异常情况进行匹配。如果新的异常区域与库中存在的异常区域图都无法匹配（相似度达不到阈值），则将该模式添加到库中。在系统设计之初，可以手动扩充这个库，使得系统拥有一组最常见的异常模式。随着系统运行，该库将越来越丰富，尽管这可能会增加搜索时间。用户能够访问到这个库中的内容（可视化的形式），浏览并进行如下操作：
- 权重调整：用户可以对异常区域中的节点、边的权重进行设置，对一些重要的节点设置更大的权重将有助于根因定位过程。
- 根因标注：对异常区域图进行根因节点的标注，主要由专家对异常结构图进行分析并确定根因节点。
论文尚未实现上述提到的可视化操作，更多地关注于图相似比较方法上。
图相似性度量模块
图相似性度量模块依赖模糊匹配函数，该函数考虑了两个多属性加权图之间的相似度距离。该模块接收两个输入：由异常区域提取模块生成的异常区域和来自异常模式库标记过的异常区域图。输出由两个元素组成：相似性得分和节点从图A到图B的映射。前者从0到1，得分为1表示两个图是完全相同的，而0表示两个图完全不同。后者描述了来自第一个图的那些图元素与来自第二图的元素匹配以实现相似性得分。下图是输出的示意图：
图相似性可以使用任何图匹配方法，在第四部分论文详细介绍了本文使用的方法。
每当新的异常区域产生时，模块会尝试将其与异常模式库中的一个或多个图进行匹配。当两个图之间的相似度高于设定的阈值时，认为两个图存在匹配。如果没有任何匹配项，则将该新的异常区域添加到异常模式库中，等待专家进行根因节点标记。如果存在一个或多个，则可以将这些匹配的模式图以及可能的根因节点按相似度排名生成一个列表显示给用户。
相似度阈值的设定需要在精确率和搜索时间之间进行权衡。降低阈值将导致产生多个可能的根因节点，需要进行更多次数的比较来提高准确性。论文认为将阈值设置在0.8到0.9之间会有比较好的精确率。论文指出，对图中的节点正确地设置权重能有效提升匹配的准确率。
图相似性度量计算引擎
图相似性度量是论文所提出方法中关键的一环，论文详细介绍了其实现。
问题定义
DEF1.一个图由一个5元组构成，用\(G\)表示一个图结构
\[G=(V, E, a t t, C, w)\]
其中，\(V\)是节点的集合，\(E \subseteq V \space \times \space V\)是边的集合，\(att\)是一个函数，\(attr(V \vee E) = A\)，\(A\)是由一系列\(a = \{ val, weight, c \subset C \}\)这样的元素组成的列表，其中\(val\)是具体值，\(weight\)是该节点或边的权重，\(c\)是上下文属性。\(C\)表示图形上下文，用来结石图形中包含的属性，并提供一个用于比较其值的上下文，后面会提到。\(w\)是一个函数，\(w(x)\)用来生成图内节点、边或属性的权重。
DEF2.图相似性度量定义，给定两个图
\[G_{1}=\left(V_{1}, E_{1}, a t t, C, w\right), G_{2}=\left(V_{2}, E_{2}, a t t, C, w\right)\]
以及两个单射函数，\(m_{n}: V_{1} \rightarrow V_{2}\)和\(m_{e} = E_{1} \rightarrow E_{2}\)，前者返回\(G_{1}\)中和\(G_{2}\)匹配的节点，后者返回两个图相同的边，这里我们遇到一个优化问题：找到一个使得两个图之间相似性最大化的映射，公式如下：
\[\begin{aligned} &\frac{\sum_{v \in V_{1}}\left(w(v)+w\left(m_{n}(v)\right)\right) \cdot \operatorname{sim}\left(v, m_{n}(v)\right)+\sum_{e \in E_{1}}\left(w(e)+w\left(m_{e}(e)\right)\right) \cdot \operatorname{sim}\left(e, m_{e}(e)\right)}{\sum_{v \in V_{1}} w(v)+\sum_{v \in V_{2}} w(v)+\sum_{e \in E_{1}} w(e)+\sum_{e \in E_{2}} w(e)} \\ &\underset{m_{n}, m_{e}}{\arg \max } \end{aligned}\]
其中，\(sim(x_{1}, x_{2})\)是一个能得到一个0到1之间的相似性度量函数。上面公式表示，相似性度量是通过 \(m_{n}\)和\(m_{e}\)两个函数确定的最佳匹配点和边决定的，匹配点和边的权重将会影响相似性得分。最小化问题可以用任何优化手段求解，论文使用的是Hill climbing （爬山算法），使用该算法能够减少搜索时间但是是以找到局部最优而不是全局最优为代价的。
\(sim(v, m_{n}(v))\)和\(sim(e, m_{e}(e))\)后文会介绍其实现，下表列出了所有相关的定义：
节点和边的相似性计算方法
节点或边的相似性由如下公式给出：
\[\frac{\sum_{a \in a t t(v) \cup a t t(u)}\left(w\left(a_{1}\right)+w\left(a_{2}\right)\right) \cdot \operatorname{sim}\left(a_{1}, a_{2}\right)}{\sum_{a \in a t t(v) \cup a t t(u)}\left(w\left(a_{1}\right)+w\left(a_{2}\right)\right)}\]
其中，\(sim(a_{1}, a_{2})\)用来衡量两个元素间属性的相似性。和DEF 2 中公式相似，这个公式表示，两个元素之间的相似性由他们之间共同属性的加权平均值确定。同样的，属性的权重会影响相似性计算结果。增加属性的权重意味着如果两个节点或两个边的属性值相似，则它们的相似性将进一步增加，下图是一个示例，对属性（如节点的形状）赋予更大的权重，则形状的相似度优先于结构相似度，可以看到右侧匹配的节点既没有两条边也没有连接到一个圆圈，但是仍将两个图视为匹配。
举个例子，假如某个异常是由磁盘异常产生的，那么该异常模式中，关于磁盘相关的属性值的权重应该适当增加。
属性相似性计算
本节介绍\(sim(a_{1},a_{2})\)实现方式。进行属性比较时，上下文可以帮我们衡量不同属性间的相似性。上下文\(C\)将用于不同的相似度计算中，如果属性没有有效的上下文，那么在相似度计算中将忽略该属性。论文考虑了三种上下文：
- 明确类别的上下文（Categorical Context）：具备该上下文的属性一般有明确的标签值，比较此类属性时，直接用精确的相等函数，如下所示，仅当两个属性值相等，相似度为1，否则为0。
\[\operatorname{sim}\left(a_{1}, a_{2}\right)=\left\{\begin{array}{ll} 1 & \text { if } a_{1}=a_{2} \\ 0 & \text { otherwise } \end{array}\right.\]
数值类型的上下文(Numerical Context): 具备该上下文的属性有特定的范围，上下文可以表示为\(c_{numerical} = \{min, max\}\),比如cpu usage 的范围应该设置为从0 到100。当比较具备此类型上下文的属性时，用如下公式：
\[\operatorname{sim}\left(a_{1}, a_{2}\right)=1-\frac{\left|a_{1}-a_{2}\right|}{\max -m i n}\]
本体上下文（Ontological Context): 此类上下文一般表示为树结构，在该上下文中，每个节点表示层级结构中的一种概念。这种类型的上下文目的是使本质相同的两种属性（比如负载均衡和分布式数据库主数据库：它们的作用比较相似，都是将请求重定向到后端执行单元池）。此上下文中，论文使用 Wu 和Palmer相似性度量的一种变体：令c1和c2作为本体中的两种概念，C作为它们共同的最近的祖先，那么相似性按下式进行计算
\[\operatorname{sim}(C 1, C 2)=\frac{2 \cdot d(C)}{d(C 1)+d(C 2)}\]
其中，\(d(x)\)是从根节点遍历到节点x的节点数，要求树结构中必须包含\(x\)，因此\(d(x) >= 1\)。
图结构生成
节点添加
首先添加构成图的节点，即系统中存在的元素（容器和主机）。由于需要提取容器级别和主机级别两种不同的指标，论文在每台机器上运行了两个容器：node exporter 和cadvisor。前者会监控主机，后者监控容器。收集指标的后端使用了Prometheus，它是一个监控和报警系统。 node export和cadvisor通过http请求将指标上报到prometheus，指标遵循多维时间序列数据模型进行存储，即每个指标都有一系列格式为(ts, id, value, labels) 的元组，其中，ts是毫秒级别的时间戳，id指示指标属于哪个容器或主机，value是指标具体值，标签是一个可选的键值对，用来指示指标特定的维度。 举例说明，可能有一个数据点，如\((ts = 1518537794351, id = 10.136.1.9, value = 98.1, cpu = cpu3, mode = user)\)，它表示 节点为10.136.1.9的cpu3在用户模式下时间戳为1518537794351时，值为98.1。 每个不同的id将作为一个节点添加到图中，并且其信息（label包含的键值对，如mode=user）会作为节点的属性。
边添加
添加了各个节点之后，可以通过边对它们进行连接，为此，需要监控它们的内部通信。论文通过使用Sysdig捕获容器或主机间的任何TCP通信。对于每个TCP请求，会有一个元组
\[（ts，id，cip，sip，io dir, bytes）\]
其中，ts是该请求发生的时间戳，id是发生通信的容器或主机，cip是客户端ip，sip是服务器ip，io dir是正则读取或写入的TCP套接字，字节是发送或读取的信息量。对一段时间内的通信进行监控，将该时间内的所有通信信息按（cip，sip）分组，构建起所有节点的边节点。下面是一个例子示意图：
参考资料
1.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.