IWQoS 2021丨ModelCoder：基于故障模型的微服务系统自动根因定位框架

论文标题｜ ModelCoder: A Fault Model based Automatic Root Cause Localization Framework for Microservice Systems
论文来源｜ IWQoS(B) 2021
论文链接｜未公布
源码链接｜未公布

TL;DR

论文中提出了一种基于故障模型的自动根因定位框架 ModelCoder，首先介绍了部署图和服务依赖图的概念来描述服务节点的部署状态和调用关系，然后基于这些定义的图进行根因定位。其定义的故障模型主要用来捕获故障根因的特征，可以通过和预先定义的故障模型进行特征匹配来定位未知故障的根因。实验部分使用 AIOps 2020 挑战赛的数据来验证 ModelCoder 的有效性，可以达到约 93% 的定位准确性且平均耗时仅 80s，比现有的 baselines 准确率提升 12%。

Problem Description

论文中定义了非常多的概念，在阐述方法前先进行解释：

Deployment graph：部署图 $G_D=<V, E>$ ，其中 $V$ 包含服务节点和物理机节点，有向边 $<v_i, v_j>$ 表示服务节点 $v_i$ 部署在物理机 $v_j$ 上。
Service dependency graph：服务依赖图 $G_S=<N,L>$ ，其中 $N$ 表示服务节点集合，有向边 $<v_i, v_j>$ 表示服务 $v_i$ 调用服务 $v_j$ ，如下图所示

在图中定义了三种类型的节点：

Bidirectional nodes：双向节点 $v_i, v_j$ , 在部署图 $G_D$ 中存在边 $<v_i, v_k>$ 和边 $<v_j, v_k>$ 表示节点 $v_i$ 和 $v_j$ 部署在同一台机器 $v_k$ 上。
Parent node 和 child node：父子节点 $v_m,v_n$ ，在服务依赖图 $G_S$ 中存在边 $<v_m, v_n>$ 且 $v_m \neq v_n$ ，那么 $v_m$ 是 $v_n$ 的父节点且 $v_n$ 是 $v_m$ 的子节点。
Abnormal call：异常调用，基于历史数据监测出的异常调用边，如图 Fig. 1. 中的虚线箭头所示。
Abnormal service node：异常服务节点，在服务依赖图 $G_S$ 中异常调用包含的节点都被定义为异常服务节点，异常服务节点分为两类：explicit node 和 implicit node ，如图 Fig. 1. 中所示。服务依赖图中存在异常调用边 $<v_i, v_j>$ 那么 $v_i, v_j$ 都是异常服务节点，如果不存在异常调用 $<v_j, v_m>$ 那么 $v_j$ 是 implicit node。Nomal nodes、explicit nodes 和 implicit nodes 集合分别使用 $V^{nor}, V^{ex}, V^{im}$ 进行表示。

根据以上定义，可以将微服务系统中的根因定位问题描述成以下形式：

当故障发生时，可以得到部署图 $G_D$ 和服务依赖图 $G_S$ ，节点集合可以划分为不同类型 $V^{nor}, V^{ex}, V^{im}$ 和已知故障 $F_K=\{f_1, f_2, ..., f_{N_k}\}$ 。对于已知故障 $f_j\in F_K$ 的特征表示为 $f_j=<x_1, x_2, ..., x_m>$ ，其中 $m$ 表示向量维度且 $x_i \in \{-1, 0, 1\}$ 。

需要解决的问题是对于未知的故障 $F_U=\{f_1, f_2, ..., f_{N_U}\}$ 定位到根因。对于未知故障 $f_i \in F_U$ , 存在候选根因集合 $C^{i}=\left\{v_{1}^{i}, v_{2}^{i}, \ldots, v_{N_{i}}^{i}\right\}$ 。对于候选故障根因节点 $v_k^i \in C^i$ 使用特征向量 $v_k^i=<x_1, x_2, ..., x_m>$ 进行表示。

定义特征向量间的距离：候选根因节点 $v_k^i$ 和已知故障 $f_j$ 特征向量间的距离计算定义如下：
$d\left(v_{k}^{i}, f_{j}\right)=\sum_{1 \leq n \leq m} \alpha_{n} \text { compare }\left(v_{k n}^{i}, f_{j n}\right) \\ \operatorname{compare}(a, b)=\left\{\begin{array}{ll} 1 & \text { if } a=b \\ 0 & \text { if } a \neq b \end{array}\right.$
其中 $\alpha_n$ 表示向量每一位的权重。
~~在分析未知故障 $f_i$ 时，论文将候选根因结合 $C^i$ 划分为不同的簇，簇中心为已知故障 $F_K$ 。其中聚类中心 $f_k$ 满足~~：
$f_{k}=\operatorname{argmin}\left\{d\left(v_{k}^{i}, f_{j}\right) \mid f_{j} \in F_{K}\right\}$
从下文来看这一项好像没用到…
定义候选故障根因节点分数： $v_k^i$ 和 $f_k$ 间的距离定义为 $v_k^i$ 的根因分数。

通过对候选根因集合 $C^i$ 中节点分数进行从小到大排序，可以获得未知故障 $f_i$ 分析结果 $A_{f_i}$ 。假设 $f_i$ 真实故障根因节点是 $r_{f_i}$ ，那么 $P\left(r_{f_{i}}, A_{f_{i}}\right)$ 定义为 $r_{f_i}$ 在 $A_{f_i}$ 中的位置。目标是根因排在前面。

$\text { Minimize } \sum_{f_{i} \in F_{U}} P\left(r_{f_{i}}, A_{f_{i}}\right)$

为了解决以上问题，还定义了几个名词：

Node feature group：节点特征组，包括目标节点本身，父节点，子节点和双向节点。
Node feature：节点特征，节点特征组中 explicit nodes 和 implicit nodes 分布。
Fault model：故障模型，故障根因节点的特征为故障模型。
对于挑战赛的数据集，论文中定义了四种故障模型：
- docker network fault
- CPU fault
- docker deployed host network fault
- user oriented host network fault
Node feature code：节点特征的形式化表示，包含四种故障模型特征。

Algorithm/Model

基于以上一堆定义，论文中提出的 ModelCoder 整体架构主要包括三部分：

Data preprocessing：3-sigma 响应时间异常检测、依赖图构建和节点分类等。
Known faults analysis：已知故障根因节点特征构建并存储在标准编码库中。
Unknown fault analysis：候选根因节点判定并根据节点特征去匹配标准编码库进行根因定位。

故障模型编码

数据预处理中的异常检测和节点分类简单不再细述。

节点特征编码格式

节点特征 ~~使用 8 位编码表示~~，按照下文的意思应该只用了 7 位。

按照论文的意思故障模型应该用的是根因节点。

第一位：表示节点自身类型。如果节点是 explicit node 那么为 1，否则为 0。
第二位：表示节点的子节点中 explicit nodes 分布。包含三种值 1，0，-1，分别对应所有子节点都是 explicit nodes，部分是 explicit nodes 和全部都不是 explicit nodes。
第三位：表示节点的子节点中 implicit nodes 分布。
第四位和第五位：表示节点的父节点类型。
第六位和第七位：表示节点的双向节点类型。

第四五六七位含义模糊。

特征存储格式

三元组包含故障根因节点，故障类型，故障模型编码：<cmdb_id, fault_type, code>，然后存储在标准编码库中。

PSO 定位优化

第一步：候选故障根因节点
由于故障通常是由服务依赖图的底层向上传播，因此选用底层 explicit nodes 和 implicit nodes 作为候选根因节点。如何判断是底层节点呢？
第二步：节点特征编码对比
通过下式计算节点特征的相似度，由于节点编码包含了四种类型的节点信息，因此定义了四个参数： $\alpha_1, \alpha_2, \alpha_3, \alpha_4$ .
$\begin{array}{r} S\left(\operatorname{code}_{1}, \text { code }_{2}\right)=\sum_{1 \leq i \leq 4,1 \leq j \leq 7} \alpha_{i} \operatorname{compare}\left(\operatorname{code}_{1 j}, \operatorname{code}_{2 j}\right) \\ \left\{\begin{array}{r} i=1 \text { if } j=1 \\ i=2 \text { if } j=2 \text { or } 3 \\ i=3 \text { if } j=4 \text { or } 5 \\ i=4 \text { if } j=6 \text { or } 7 \end{array}\right. \\ \\ \text { compare }(a, b)=\left\{\begin{array}{l} 1 \text { if } a=b \\ 0 \text { if } a \neq b \end{array}\right. \end{array}$
第三步：系数优化
使用粒子群优化算法求解系数 $\alpha$ ，主要是根据 ModelCoder 定位的准确率来优化适应度函数，计算细节论文中略过。实验中采用的是 [2, 7, 3, 3]。
第四步：编码分析
对于每个故障候选根因节点，经过上述步骤都已和标准编码库中的编码进行对比，取最大的相似性分数作为这个节点的根因分数。
$\operatorname{grade}_{n o d e_{i}}=\max \left\{S\left(\operatorname{code}_{n o d e_{i}}, \text { code }\right) \mid \text { code } \subseteq \text { codes }\right\}$
其中 $grade_{nodes_i}$ 表示节点 $node_i$ 的分数。
通过从大到小将所有候选根因的分数进行排列，就可以得到未知故障的分析结果。对于候选故障根因节点 $node_i$ ，从标准库中选出的三元组为 $<cmdb\_id^{'}, fault\_type^{'}, code^{'}>$
$\operatorname{code}^{\prime}=\operatorname{argmax}\left\{S\left(\operatorname{code}_{n o d e_{i}}, \text { code }\right) \mid \text { code } \subseteq \text { codes }\right\}$
其中 $fault\_type^{'}$ 即为对应的故障类型。