SIGMETRICS 2013丨MonitorRank：微服务架构中的根因定位方法

论文标题 ｜ Root Cause Detection in a Service-Oriented Architecture
论文来源 ｜ SIGMETRICS 2013
论文链接 ｜ https://dl.acm.org/doi/10.1145/2465529.2465753
源码链接 ｜ 未公布

背景

MonitorRank 是最早使用随机游走的策略定位故障根因服务的方法，MonitorRank 把系统的服务分成三类：

1. 前端服务：负责接收用户的请求以及进一步调用下游请求以完成用户的请求。
2. 应用服务：负责真正处理用户请求的逻辑。
3. 数据服务：负责提供经过包装的数据。

应用服务和数据服务又统称为后端服务。

在每个服务上，配置有传感器，会定时给出指标数据。通过服务之间的调用关系，可以形成一个调用拓扑图。
图上的节点就是服务，边就是节点之间的调用关系。

基于这样的数据，MonitorRank 把根因服务定位问题定义为，给定告警指标$m$，告警前端节点$v_{fe}$和时间$t$，根据剩下其他节点的指标$m$的值，对所有节点进行排序。
MonitorRank 和我们研究的其他很多文献一样，只聚焦在异常发生之后的故障定位，和大量的异常检测的相关工作区分开来了。

故障定位

现在假设我们有了服务之间的调用图（稍后再来看 MonitorRank 是如何获取调用图的），MonitorRank 是如何定位根因（即排序所有节点）的呢？

MonitorRank 基本思想是，一个节点的指标$m$ 和异常前端节点$v_{fe}$ 的指标$m$ 的相关性表示了该节点是根因的可能性。
由于非根因节点也可能有很高的相关性，所以相关性高只是一个必要条件，相关性高的节点作为候选，后续再进行进一步的分析。
我们如果从任何一个怀疑的节点开始入手，根据调用关系图，我们查看它是不是依赖其他高相关性的节点，如果是，那么我们的怀疑就转移到它的邻居去，以此类推。
即，依次选择一系列节点，每次都根据转移概率（目标节点和异常的相关性）从上一个节点的邻居中选择下一个节点。
MonitorRank 假设在许多次随机游走过程中，被访问越多的节点越可能是根因，即被访问的概率就是根因排序依据的分数。
这样的随机游走过程其实就是 Weighted PageRank 的过程，鉴于我们完全不怀疑相关性低的节点，MonitorRank 采用了 Personalized PageRank，对每个节点的偏好程度（personalization）就是它的相关性。

我们形式化地描述 MonitorRank 的具体算法，给定图$G=<V, E>$。$V$是服务的集合，如果服务$v_i$ 调用了$v_j$，那么$e_{ij}\in E$，否则$e_{ij}\notin E$。$\mathbf{A}$ 是$G$ 的邻接矩阵。
向量$\mathbf{S}$ 定义了每个节点和异常前端节点指标$m$的相关性，即$S_i=\text{similarity}_{m}(v_i, v_{fe})$。
那么转移概率矩阵可以定义为$Q_{ij}=\frac{A_{ij}S_j}{\sum_{k}A_{ik}S_k}$，即节点$v_i$转移到节点$v_j$的概率和$S_j$成正比，且仅当$v_i$调用了$v_j$时才转移。

根据以上定义，每个节点都必须转移到它的一个邻居（因为$A_{ii}=0$），但是实际上可能一个节点本身就是根因，不需要转移到其他邻居节点去了。这会导致随机游走不得不游走到相关性很低的节点上。
因此 MonitorRank 在$Q$的基础上额外定义了自环，自环的概率代表的就是一个节点本身就是根因的概率。
所以如果一个节点所有依赖的节点相关性都不高（比自己还低就是不高），那么这个节点的自环概率就应该相应更高。
所以自环的转移概率（未归一化）定义为：$S_i-\max_{j:e_{ij}\in E}S_j$

因为相关关系并不代表真正的因果关系，所以以上定义的转移概率可能是有错误的，然而，一旦随机游走时因为错误的概率定义游走到了错误的分支上，就再也没有机会纠正了。
因此 MonitorRank 给每一条边都引入了反向边，反向边的权重就代表了转移概率错误的概率：$\rho S_i$（未归一化），其中$\rho$是一个超参数。

因此，完整的转移概率矩阵$P$定义为

$$P_{ij}=\frac{A'_{ij}}{\sum_{k}A'_{ik}},\\\\ A'_{ij}=\begin{cases} A_{ij}S_{j}+A_{ji}S_{i} & i\neq j \\\\ \max(0, S_i - \max_{k:e_{jk}\in E}S_k) & i = j \neq fe \end{cases}$$

Personalized PageRank Vector$\pi_{PPV}$ 就是每个节点是故障根因的概率，可以通过解如下方程得到

$$\pi_{PPV}=\alpha\pi_{PPV}\mathbf{P}+(1-\alpha)\mathbf{S}$$

其中$\alpha$ 是 Personalized PageRank Vector 算法的参数。

故障图提取和外部因素

上述的故障定位流程是在异常发生后触发的。
而 MonitorRank 方法还会周期性地运行对所有指标数据调用关系的分析，得到调用图。
当触发故障定位时，直接使用最新的调用关系图。

另外，服务之间的依赖关系并不只有调用关系，比如两个服务竞争同一个外部资源。

在外部因素的具体化中， 我们会介绍其他一些工作是如何考虑更具体的外部因素的影响的。这种情况下，即使两个节点之间没有调用关系，它们之间的转移概率也应该更大。
MonitorRank 周期性地基于每一个前端节点对剩下的所有节点进行条件聚类。
当触发故障定位之后，MonitorRank 首先选择一个最合适的类，然后把类中每一个节点的相似度$S_i$ 都再额外加上此类的平均相似度，以此表达类内的所有节点都和异常前端节点受同一个外部因素的影响。

联系作者