WWW 2021丨MicroRank：微服务环境下基于谱分析的延迟时间故障定位系统

论文标题 ｜ MicroRank: End-to-End Latency Issue Localization with Extended Spectrum Analysis in Microservice Environments
论文来源 ｜ WWW 2021
论文链接 ｜ https://www2021.thewebconf.org/program/papers-program/links/
源码链接 ｜ 未公布

TL;DR

论文中针对微服务 trace 调用链延迟故障问题提出了一种新颖的定位系统 MicroRank，同时考虑分析正常 trace 和异常 trace ，但基于 PageRank 方法对不同的 trace 计算出不同的权重以此来进行根因定位。实验在开源的系统数据集中证明了 MicroRank 方法的召回率比当前 baselines 高出 6% - 22%，尤其是在于多个故障同时发生的情况下。

Problem Definition

• Trace：对于微服务架构下 trace 数据的结构如下，包含多个 spans。

• Coverage tree：基于 spans 间的依赖关系可以构造一个 coverage tree，即每个节点代表一个服务的操作 (Service instance operation)，树结构如下图所示

• Call graph：合并 converage tree 得到 converage graph 后，去除 coverage graph 中重复的边就是服务间的调用图。

基于以上定义，微服务系统中根因定位问题可以形式化表达成以下格式：

给定时间窗口中所有的 traces$T=\{T_1,\cdots, T_n\}$，其中$T_i= \{O_1^i,\cdots,O_m^j\}$ 表示$T_i$ 由$m$ 个操作组成，所有 trace 对应的延迟时间表示为$L=\{L_1,\cdots,L_n\}$ 及其对应的 Coverage graph$G=(V,E)$，需要解决的问题是找出正常的 trace 集合$T^n=\{T_1^n,\cdots,T_k^k\}$ 和异常的 trace 集合$T^a=\{T_1^a,\cdots,T_k^a\}$，然后基于$T^n,T^a$ 和$G$ 定位到根因服务操作$O_j^i$。

Algorithm/Model

论文中提出的模型主要基于软件工程领域的程序测试方法 Spectrum-based fault localization (SBFL)，主要假设是：较少的正常请求经过同时较多的异常请求经过的实例是根因。SBFL 方法的主要思想：给定故障程序$P$ 和一系列测试案例, 假设程序中一个单元$O\in P$，那么谱方法首先需要统计四个指标$(O_{ef},O_{ep},O_{nf},O_{np})$，其中$O_{ef}$ 表示包含单元$O$ 的失败测试案例，$O_{ep}$ 表示包含单元$O$ 的成功测试案例，$O_{nf}$ 表示不包含单元$O$ 的失败测试案例，$O_{np}$ 表示不包含单元$O$ 的成功测试案例。

文中发现如果直接将基于谱分析的方法用于微服务根因定位会存在以下两个问题：

• 基于谱的方法未考虑不同请求的权重，如果每个请求权重相同可能定位错误。

  

  如上图所示，如果是这种调用情况使用简单的 SBFL 方法计算四个指标会导致定位失败，而使用 MicroRank 可以正确定位根因。

  

• 微服务架构下服务调用的次数不平衡，即有些服务调用次数非常频繁但其它服务调用次数较少，但是软件工程中的测试案例设计不会如此不均衡。

  

针对以上问题，论文中提出的根因定位框架如下图所示：

主要包含四个模块：

• Anomaly Detector：用于 trace 异常检测来触发服务根因定位。
• Data Preparator：判断时间窗口内的 trace 是否异常并构造 call graph 和 operation-trace graph。
• PageRank Scorer：基于正常 trace 和异常 trace 生成每个服务的正常分数和异常分数。
• Weighted Spectrum Ranker：基于谱方法和服务的正常分数、异常分数对每个服务进行排序，以此来给管理员推荐根因。

Anomaly Detector

由于不同长短的 trace 会有不同的处理时间，因此不能将所有请求混合在一起考虑。论文中提出一种轻量级的 trace 异常检测方法来同时考虑服务处理时间和 trace 中包含的服务数量。

首先离线计算每个服务 Operation 的历史响应时间的均值$\mu_o$ 和标准差$\sigma_o$，然后一条 trace 预计的延迟时间为

$$L_{\text {excepted }}=\sum \operatorname{count}_{o} *\left(\mu_{o}+n * \sigma_{o}\right)$$

其中$\operatorname{count}_{o}$ 表示 trace 中包含服务操作$o$ 的数量，$n$ 是超参数用来调整值的上界，论文中一般设为 1.5。应该是$L_{\text {excepted }}$ 小于真实 trace 响应时间即为异常 trace，论文中应该是写错了。

Data Preparator

以上异常检测方法仅考虑了 trace 的时间维度异常却没有考虑 trace 中 operation 间的空间关系。

Data Preparator 模块首先将时间窗口内的 trace 分为异常集合和正常集合，根据 trace id 查询 trace 的 spans 来构造每个 trace 的 coverage tree。如果 trace 的 coverage tree 相同那么被视为同种类型的 trace，Data Preparator 模块也记录每种类型 trace 出现的次数。

论文中还将所有正常或者异常的 coverage tree 合并在一起得到 coverage graph，根据 coverage graph 同时将每个请求视为节点可以得到 operation-trace graph。例如上图 3 异常的 operation-trace graph 如下图所示：

这一节作者引入了些名词来说明构造的图结构，怕理解出现歧义说明下逻辑关系：coverage tree 如图 2 所示指一条请求所包含的 trace operations；coverage graph 是多个 trace 合并之后得到的图，如图 3 所示； operation-trace graph 中有两类节点，请求ID和服务，如图 6 所示，个人简单理解为一个二部图，边的意义为请求包含的所有服务。

PageRank Scorer

这一节介绍下如何使用 PageRank Scorer 来得到不同 trace 的权重。

PageRank Scorer 分为两种：Normal Scorer 和 Anomalous Scorer，主要是为下文的 Weighted Spectrum Ranker 计算得到加权的谱信息。主要想法是基于 operation-trace graph 和 PageRank 计算得到每个 operation 的权重，trace 的重要性是根据 trace 能找到根因的可能性来判断的。

计算权重时基于了三个假设：

• 如果 operation 被更多的异常 trace 包含那么这个 operation 更可能是根因。
• 如果异常的 trace 包含更少的 operation 那么这个 trace 更加重要，因为检测根因范围更小。
• 如果一种类型 trace 出现的次数较少那么重要性更大，因为容易被其它出现次数非常多的 trace 所忽略。

Personalised PageRank Algorithm

由于 operation-trace graph 是一个异质图，因此论文中使用 PPR 排序算法。

PPR排序的基本计算公式如下所示：

$$A_{s t}=\left\{\begin{array}{ll} \frac{1}{|O(s)|}, & t \in O(s) \\ 0, & \text { otherwise } \end{array}\right.$$

其中$A_{st}$ 表示概率转移值，$O(s)$ 表示节点$s$ 的出度。迭代公式如下所示：

$$v=(1-d) A v+d \cdot u$$

Transition Matrix

考虑到 operation-trace graph 的异质性，因此论文中使用的概率转移矩阵如下所示：

其中$A_{oo}$ 表示 call graph 中 operation 间的概率转移矩阵，主要作用是区分正常和异常 trace 同时包含 operation 的情况，$A_{ot}$ 和$A_{to}$ 表示 operation-trace graph 中的 operation 和 trace 的概率转移矩阵。

例如图 3 中异常转移矩阵如下图所示

由于在定位中 operation-trace graph 比 call graph 更加重要，因此添加一个参数$\omega$ 来调整权重。最终得到的概率转移矩阵为

$$A=\left[\begin{array}{c|c} \omega A_{o o} & A_{o t} \\ \hline A_{t o} & 0 \end{array}\right]$$

Preference Vector

MicroRank 使用个性化向量来考虑 trace 范围和种类的影响，包括两个部分$\boldsymbol{u}=\left[\boldsymbol{u}_{\boldsymbol{o}}^{T}, \boldsymbol{u}_{t}^{T}\right]^{T}$，其中$\boldsymbol{u}_{\boldsymbol{o}}^{T}$ 和$\boldsymbol{u}_{\boldsymbol{t}}^{T}$ 分别表示 operations 和 traces 个性化分数。论文中将$\boldsymbol{u}_{\boldsymbol{o}}^{T}$ 置为 0 因为不考虑个性化 operation 的影响。

对于 Anomalous Scorer ，$\boldsymbol{u}_{\boldsymbol{t}}^{T} = \left[\theta_{1}, \theta_{2}, \ldots, \theta_{m}\right]^{T}$ ,其中

$$\theta_{i}=\varphi \cdot \frac{n_{i}^{-1}}{\sum n_{j}^{-1}}+(1-\varphi) \cdot \frac{k_{i}^{-1}}{\sum k_{j}^{-1}}$$

其中$n_i$ 表示异常 trace i 中包含的 operations 数量；$k_i$ 表示第$i$ 类异常的 trace 数量；$\varphi$ 表示 trace 数量和种类的平衡参数，默认为 0.5。

对于 Normal Scorer，不考虑 trace 量级的影响，因为量级不能反映正常 trace 的重要性，

$$\theta_{i} = \frac{n_{i}^{-1}}{\sum n_{j}^{-1}}$$

例如图 3 异常 trace 的个性化向量为$\boldsymbol{u}=\left[0,0,0,0, \frac{8}{21}, \frac{13}{42}, \frac{13}{42}\right]$。

以上确定概率转移矩阵和个性化向量后就可以得到最终的重要性排序，例如图 3 中的异常 PPV 向量为

$$F[\text { front, recommend, checkout, product }]=[0.990,0.328,0.328,1] .$$

Weighted Spectrum Ranker

基于异常和异常的 trace 分数和数量，对于 operation$O$ 的谱信息可以通过下式进行计算

$$\begin{array}{ll} O_{e f}=F * N_{e f}, & O_{n f}=F *\left(N_{f}-N_{e f}\right) \\ O_{e p}=P * N_{e p}, & O_{n p}=P *\left(N_{p}-N_{e p}\right) \end{array}$$

其中$F$ 和$P$ 分别表示$O$ 的异常和正常 PageRank 分数，$N_{ef}$ 和$N_{ep}$ 表示包含$O$ 的异常和正常 trace 数量，$N_f$ 和$N_p$ 表示当前滑动窗口异常和正常 trace 数量。

对于以上四个统计值，最终每个 operation$O$ 的根因分数可以采用不同的组合来进行计算，如下表所示

Experiments

论文中采用的数据集包含以下两种

• Hipster-Shop Microservice System
• 2020 AIOps Challenge Event

在这个两个数据集中的实验效果如下图所示

同时考虑了论文中方法异常检测的准确率

方法的性能会受 trace 数量的影响，从这个图中说明了论文中提出的方法仅考虑了很小量级的 trace，而且 trace 数量增加还会影响方法的性能。

其它的参数实验就不再赘述，如有兴趣可以参考原文。

Thoughts

• 模型思路非常完整，但方法实用性貌似不高，而且整体思路类似论文 An Empirical Study of Boosting Spectrum-based Fault Localization via PageRank。
• 整体而言实验较为全面，但没有考虑实际环境中海量 trace 的情况，实验部分采用的两个数据集包含的 trace 和 operation 数量太小，例如某商业银行一分钟 40± 万 trace 如何计算 trace 的重要性。
• 不能应用在大规模生产环境中。

Contact