ISSTA 2021 | 基于众包思想从用户空间诊断微服务内核故障

论文标题｜ Faster, Deeper, Easier: Crowdsourcing Diagnosis of Microservice Kernel Failure from User Space
论文来源｜ ISSTA(A) 2021
论文链接｜ https://dl.acm.org/doi/10.1145/3460319.3464805
源码链接｜ https://github.com/PanYicheng/dycause_rca

TL;DR

论文提出了基于用户空间和众包策略的微服务内核故障诊断方案 DyCause，以此来解决诊断信息不对称问题。DyCause 以分布式方式部署在应用端，通过轻量级 API 日志共享，程序可以协同收集内核服务的运行状态来按需启动诊断，DyCause 部署非常简单而且轻量级不依赖于内核的架构和功能。为了从不对称诊断信息中挖掘服务间的关系，论文中还设计了一种基于统计的算法来挖掘服务间随时间变化的因果关系，可以有助于了解异常传播的时序关系。实验部分在 testbed 和真实云系统中测试 DyCause，证明它在性能上优于当前的 baselines，尤其是在更少指标的情况下。

Backgrounds

首先先了解下上述提到的名词：

用户空间：特指普通用户而不是管理员用户，没有权限查看底层服务的监控指标；
内核空间：用户空间不能直接获取指标的服务为 kernel services。kernel diagnosis 指利用全部监控指标的诊断方法；
众包策略：通过大量应用 Apps 共享数据从而获得更全面服务指标数据的策略；
内核故障：在用户空间观察不到的服务故障；
诊断信息不对称问题：在用户空间中每个 App 应用只能获得其直接请求的 kernel service 状态，缺少全局监控指标的情况下不能利用全部的指标信息进行诊断 ⁉️

📢 Insights from practice，论文中提出的想法为 SREs 经验总结： 👍🏻

结合所有 cloud application 的信息进行诊断；
Troubleshoot the microservice kernel failure from user space is like blind men touching an elephant。看样子是裴老师粉丝！
微服务架构下服务间的关联是动态的。故障传播模式取决于系统架构、动态负载均衡、保护机制(重启)。

Model/Algorithm

论文中提出的 DyCause 框架如下图所示

主要包括五个模块：

Crowdsourcing Metric Collection 基于众包收集指标
Anomaly Interval Detection 服务指标异常检测得到异常区间
Temporal Dynamic Causality Discovery 时序因果挖掘
Crowdsourcing Graph Fusing 结合多个图的 correlation graph
Backtrace Root Cause Analysis 通过回溯搜索构建异常传播路径并定位根因

指标收集

通过共享请求的 logs，每个应用程序都可以获得任何其他应用程序曾经请求的内核服务的性能指标，logs 格式如下所示

论文中只用到了响应时间作为指标。如果服务的请求日志比较少，那么使用线性差值的方法来得到服务的指标 $M_i(t)$

总结下这步就是使用其它 Apps 监控的日志得到当前 App 未监控到的服务指标，写的太高大上了…

异常检测

使用 SPOT 算法检测每个服务的异常，SPOT 算法可以参考另一篇文章 SPOT：基于极值优化理论的流式单变量时间序列异常检测模型

检测每个服务异常后，统计异常服务的数量。如果数量超过 $\theta_{ab}N, \theta_{ab}\in (0,1)$ 那么开始根因诊断。

选择的异常区间为两个参数 $L_{pre}$ 和 $L_{post}$ ，实验中验证其影响。

因果挖掘

DyCause 分析异常区间对应的指标 $M^{ab}(t)$ ，通过滑动窗口测试没两个 services 间 Granger causal intervals 来生成动态因果曲线 $C_{i,j}(t)$ ，表示服务 $v_i$ 和服务 $v_j$ 间关联强度随时间的变化。

由于实际场景中变量间的因果可以可能仅在短期中存在而长期并不存在，以此需要使用一个有效且随时间变化的动态因果挖掘算法。

假设分析服务 $v_a$ 和 $v_b$ 间的因果，首先收集指标某一测试区间的数据为 $X,Y$ 。首先构建两个线性回归模型来预测 $Y(t)$ ，然后使用最小二乘法来估计模型参数，

$\begin{array}{ll} \mathbb{H}_{\text {partial }} & \hat{Y}(t)=\sum_{i=1}^{L_{\text {lag }}} \alpha_{i}^{\text {part }} Y(t-i)+b^{\text {part }} \\ \mathbb{H}_{\text {full }} & \hat{Y}(t)=\sum_{i=1}^{L_{\text {lag }}}\left(\alpha_{i}^{\text {full }} Y(t-i)+\beta_{i}^{\text {full }} X(t-i)\right)+b^{\text {full }} . \end{array}$

零假设：如果变量 $X$ 和 $Y$ 间如果不存在因果那么增加 $X$ 的特征也不会提高预测效果。

那么统计计算证明

$F=\frac{\left(S S E_{\text {part }}-S S E_{\text {full }}\right) /\left(d_{\text {full }}-d_{\text {part }}\right)}{\operatorname{SSE}_{\text {full }} /\left(T-d_{\text {full }}-1\right)}$

$F_{d_{full}-d_{part}, T-d_{full}-1}$ 服从 F 分布。其中 $SSE_{part}， SSE_{full}$ 分别表示上述两个模型的平方误差和 $\sum_{t}(\hat{Y}(t)-Y(t))^{2}$ 。 $d_{part}$ 和 $d_{full}$ 分别表示两个模型的自由度为 $L_{lag}, 2L_{lag}$ 。 $T$ 表示时间序列中全部样本数量。

通过上式可以计算零假设 $F$ 的概率，如果概率低于某一阈值那么拒绝假设，说明 $X\rightarrow Y$ 存在因果。

给定一张图来验证下，如下图所示

从这个图里面可以看到，如果我们以整个周期 $T$ 来做因果关系挖掘那么可能无关，但是以 $[s_i:e_i]$ 范围内的数据那么是相关的。但个人感觉就这个图而言， $T$ 周期范围内可能是相关的，DTW 算出来也会非常相关。

整体的动态因果挖掘算法如下所示，迭代计算每个滑动窗口内是否存在因果关系。

其中函数 $c(\alpha, L_{lag}, e-s+1)$ 表示使用自由度 $L_{lag}, e-s-1$ 来计算 $F$ 分布的临界值。

迭代复杂度太高，因此用到了 “[2017 ICDM] Discovery of causal time intervals” 中的方法进行剪枝。细节不再细述，如需请参考原文。

通过上述方法得到的动态根因曲线值如下图所示

对于一个真实异常，其传播路径及其对应的因果曲线如下所示

上面图非常重要，可以从分数看出因果传播的时间顺序，每个曲线达到峰值的时间从左往右表示异常传播的先后顺序。

构建依赖图

令有向加权图 $G(V,E,W)$ 表示微服务系统依赖图， $W$ 表示微服务关联权重。

论文中提出了自适应阈值的方法来构建局部微服务依赖图，算法描述如下 [局部体现在？]

其中参数 $\theta_e$ 用来控制图的稀疏性。

Graph Fusing

单个应用进行定位可能效果有限，所以论文提出融合多个应用构造的局部图来优化。

假设 DyCause 运行在 $n$ 个应用上，每个应用构造得到的局部微服务依赖图为 $G_i(V^i,E^i, W^i)$ ，每个应用的前端服务为 $v_{fe}^1,\cdots, v_{fe}^n$ 。为了融合这 $n$ 个图，首先计算应用间相似度 $sim(v_{fe}^1, v_{fe}^j), j=2,...,n$ ，然后对于每条边 $e=(v_a, v_b)$ 优化边权重

$W_{e}^{1^{\prime}}=W_{e}^{1}+\lambda_{\text {fuse }} \sum_{j=2}^{n} \operatorname{sim}\left(v_{f e}^{1}, v_{f e}^{j}\right) W_{h(e, j)}^{j}$

其中 $\lambda_{fuse}$ 表示其它图中融合信息的权重，映射函数 $h(e,j)$ 将 local graph中的边映射到其它图 $G_j$ ，如果 $v_a$ 为 kernel service，那么 $h(e,j)=e$ ,如果 $v_a$ 是一个 front-end service 那么 $h(e,j)=(v_{fe}^j, v_b)$ 。调整后的图表示为 $G^{\prime}\left(V^{\prime}, E^{\prime}, W^{\prime}\right)$ 。

一个真实案例中的融合图如下所示

为什么要使用 Graph fusing 呢？

Although applications (app 1 to 4) have shared access to kernel services’ performance metrics, they still showed different behaviors during the anomaly. Thus, their local dependency graphs indicated different pathways on how the kernel services impact themselves.

但是从整个 local dependency graph 的构造过程而言，看不出来不同 app 构造的 graph 计算过程有什么区别！

回溯分析

异常是从根因节点通过依赖链传播至前端，因此 DyCause 通过 BFS 回溯的方法来进行根因定位。

主要考虑两部分：

从前端 $v_{fe}$ 的路径关联强度 $S_{path}(v_i)$
Pearson 相关系数 $S_{corr}(v_i)$

第一部分主要步骤入下：

从前端 $v_{fe}$ 通过 BFS 回溯找到所有路径 $P$ ，实验中采用 $n_{path}$ 条路径；
计算每条路径存在的概率，对于路径 $P_i=\{i_1 \rightarrow ...\rightarrow i_n=fe\}$ 计算调和平均
$\operatorname{Prob}\left(P_{i}\right)=\operatorname{Mean}\left(1 / W_{i_{1}, i_{2}}^{\prime}, \ldots, 1 / W_{i_{n-1}, i_{n}}^{\prime}\right)$
选择 $n_{topk}$ 路径来计算每个 service 出现次数 $S_{path}(v_i)$ ，并计算每条路径中 $n_{lead}$ services。