21 | March | 2020 | ZHANG RONG

就在今天（2020 年 3 月 21 日），新加坡首次出现两起由于新冠病毒（COVID-19）引起的死亡病例。

从 MOH（Ministry of Health）的官网上可以看到，今天已经有两位感染新冠病毒（Coronavirus Disease 2019，简称为 COVID-19）的病人在新加坡离世。

第一名病人是一位 75 岁的女性新加坡公民，于 2020 年 2 月 23 日送入 NCID，并且当天确诊感染了 COVID-19。

第二名病人是一位 64 岁的男性印度尼西亚公民，于 2020 年 3 月 13 日送入 NCID，并且于 2020 年 3 月 14 日确诊感染了 COVID-19。

从新加坡政府的官网上可以看到：截止时间至 2020 年 3 月 21 日 12 点，现存确诊为 252 例（238 例稳定，14 例严重），死亡 2 例，治愈 131 例。

疾病爆发相应等级为橙色（orange）。

而新加坡政府也在其主页上呼吁大家注意卫生：

勤洗手，多用肥皂；
每天测量两次体温；
咳嗽或者打喷嚏的时候用纸巾遮住口鼻；
及时处理垃圾和食物，保持桌面整洁；
注意室内通风，保持厕所干净。

一旦发现自己生病，请带上口罩去医院，并且保证后续在家隔离。

而近三天，新加坡也有不少新增的病例。2020 年 3 月 20 日有 40 个病例，其中 30 位有欧洲，北美，亚洲的旅游史，7 位联系上了以前的病例，3 位没有找到传染病联系。

除此之外，从丁香医生的小程序可以看出，亚洲很多国家的疫情其实不容乐观。

最后，无论在国内还是国外，大家都要注意安全。抗击疫情，人人有责。

口号_1

在运维领域，服务侧的异常会由多方面的原因造成，有的时候是因为网络的抖动，有的时候是因为机器的故障，有的时候甚至是因为人为的变更。本篇博客会介绍一种机器异常定位的方法，论文是来自于清华 Netman 实验室的《FluxRank：A Widely-Deployable Framework to Automatically Localizting Root Cause Machines for Software Service Failure Mitigation》。本篇论文主要介绍了如何从服务的故障定位到局部异常的机器，也就是说在发现服务故障的同时，进一步推断出是由哪些机器出现问题而导致的。

通常来说，在服务异常（例如服务的耗时长，失败数上涨）的时候，需要运维人员通过历史上的经验迅速定位到是哪个业务，哪个模块，甚至哪台服务器出现了故障。而人工定位的速度总是会出现瓶颈的，无论对模块的判断，还是机器的判断，都依赖于人工所积累的经验。而每个人的经验却各不相同，并且经验的传承也需要一定的时间成本。那么如何基于人工运维的经验来构建模型，进一步地提升异常定位的速度就是智能运维的关键之处之一。

对于一条业务指标（时间序列）而言，大多数情况下是处于正常的状态（normal）。但是如果出现了错误的变更，发布了错误的程序，或者服务器突然出现了故障，都会导致业务指标出现变化，就从正常（normal）变成异常（abnormal）。这个时候就会出现一个故障的开始时间，也就是 failure start time $T_{f}$ ，这个时间戳是运维领域非常重要的时间戳，它由异常检测（anomaly detection）产生，无论在告警收敛（alarm convergence）还是根因分析（root cause analysis）都非常依赖这个时间戳。而另外一个时间戳虽然没有故障开始时间那么重要，但是也有着其实用价值，那就是缓和开始时间（mitigation start time），它表示故障虽然还没有恢复，但是出于稍微平稳的走势，并没有持续恶化。在出现了故障之后，通常都会发送相应的告警给运维人员，那么在发送告警的时候，如果将异常定位的结果随之带出，则会大大减少运维人员排障的时间。在故障缓和的时间内，运维人员通常需要进行必要的操作来排查故障，例如切换流量（switch Traffic），回滚版本（Rollback Version），重启实例（Restart Instances），下线机器等操作。除此之外，为了定位问题（Root Cause Analysis），运维人员需要分析源码（Code Analysis），查看日志（Log Analysis）等一系列操作。如果能够将这一系列操作融入相应的机器学习模块中，将会节省运维人员大量的排障时间。

贝叶斯网络

通常来说，故障定位也称为根因分析或者根源分析（Root Cause Analysis），都是为了排查产生这次故障的原因。在机器学习领域，为了进行因果分析（Causal Analysis），则需要使用相应的模型来进行建模。其中较为经典的统计分析方法则是贝叶斯分析法，其中的贝叶斯网络（Bayesian Network）则是经典模型之一。下面来看一个简单的例子。

假设降雨（Rain）的概率是 0.2，不降雨的概率是 0.8；而洒水器（Sprinkler）是否开启会受到降雨的影响，其条件概率与下图所示。而降雨或者洒水器都会导致草湿润（Grass Wet），其概率分布如下图所示。那么可以问如下问题：

如果草已经湿润，求降雨的概率是多少？
如果草已经湿润，求没有降雨且洒水器开启的概率是多少？

而这一类的问题可以通过贝叶斯公式来进行解答。从表格来看：

从 Rain 的表格可得： $P(R=T)=0.2, P(R=F)=0.8$ 。

从 Rain 和 Sprinkler 的表格可得： $P(S=T|R=F)=0.4, P(S=F|R=F)=0.6$ ， $P(S=T|R=T)=0.01, P(S=F|R=T)=0.99$ 。

针对问题 1，需要计算条件概率 $P(R=T|W=T)$ 。从 Bayes 公式可以得到： $P(R=T|W=T) = P(R=T,W=T)/P(W=T)$ 。分别计算分子分母即可：

$P(R=T,W=T)=P(R=T,S=T,W=T)+P(R=T,S=F,W=T)$

$= P(W=T|R=T,S=T)P(S=T|R=T)P(R=T) + P(W=T|R=T,S=F)P(S=F|R=T)P(R=T)$

$= 0.99*0.01*0.2+0.8*0.99*0.2=0.16038$ ，

$P(W=T)=P(W=T,S=T,R=T)+P(W=T,S=F,R=T)+P(W=T,S=T,R=F)+P(W=T,S=F,R=F)$

$= 0.99*0.01*0.2+0.8*0.99*0.2+0.9*0.4*0.8+0.0*0.6*0.8=0.44838,$

那么如果草已经湿润，求降雨的概率是 $P(R=T|W=T)=P(R=T,W=T)/P(W=T)=0.16038/0.44838=0.3577.$

另外一个题目可以用类似的方法进行求解，在此不再赘述。

虽然贝叶斯算法能够计算出条件概率，例如本次故障是由哪些原因导致的，但是这个需要长期收集数据，需要对历史数据进行积累，才能通过人工或者统计的方法得到以上表格的条件概率。但是在实际的环境中是较难获取这些数据的，需要大数据平台的支持，因此需要探索其他的解决方案。

FluxRank

在本论文中，为了克服贝叶斯网络模型中的一些问题，针对子机异常定位的场景，设计了一套技术方案，作者们称之为 FluxRank。

FluxRank 这一模块的触发需要服务指标（Service KPI）的异常，因此需要对服务指标（Service KPI）进行异常检测。这里的服务指标通常指的是业务指标，包括某块 APP 的在线人数，某个接口的成功率，某个视频网站的卡顿数等指标。当服务指标出现了异常的时候，就启动 FluxRank 模块进行异常机器定位。

如果按照人工处理的流程来看，分成几个步骤：

异常检测部分：通过设定阈值或者某个简单的规则来进行异常检测，包括服务的 KPI（Service KPI）和机器的 KPI（machine KPIs）；
手工检查异常的时间段，并且查看在异常的时间段内发生了什么情况；
运维人员根据自身的业务经验来对机器的故障程度做人工排序；
运维人员根据自身的业务经验来对故障进行处理，并且人工给出处理方案。

那么 FluxRank 所面临的挑战就有以下几点：

如何衡量海量 KPIs 的变化程度？在这里不仅有服务的 KPIs，还有机器的 KPIs。而机器的 KPIs 包括内存，硬盘，IO，CPU等诸多固定的指标，那么如何对这些海量的 KPI 曲线进行变化程度的衡量，为后续的指标排序做准备就成为了一个难点；
如何对 KPIs 进行异常性或者重要性的聚类，让运维人员能够一眼看出每个聚簇的差异或者异常程度？
如何对 KPIs 聚类的结果进行排序？

为了解决以上的问题，FluxRank 的框架有以下几个贡献点：

基于 Kenel Density Estimation 用于衡量海量 KPIs 在某一个时间段的变化程度和异常程度；
基于上一步生成的异常程度，对诸多机器所形成的特征使用距离公式或者相似度公式，然后使用 DBSCAN 聚类算法来对机器进行聚类；
在排序部分，对上一步的机器聚类结果进行排序；

Change Quantification

首先，来看一下 Change Quantification 是怎么样做出来的。这里的 Change Quantification 使用与衡量机器 KPIs 的变化程度，称之为 change degree。Change degree 可以用于 CPU，内存，IO 等诸多机器指标。为了达到衡量变化程度，需要一个非常重要的信息，那就是变化的开始时间，change start time，也就是说在哪个时刻时间序列开始出现了变化。于是在 Change Quantification 部分，就分成两部分：（1）用 absolute derivative 或者 CUSUM 算法获得变化开始时间（change start time）；（2）用 Kernel Density Estimation（KDE）来计算变化程度（change degree）。

正如上图所示，针对服务 KPIs（ervice KPIs），存在两个关键的时间点，那就是失败开始时间（Failure Start Time） $T_{f}$ 和缓和开始时间（Mitigation Start Time） $T_{m}$ 。在失败开始时间 $T_{f}$ 之前，可能有的机器已经出现了故障，因此变化开始时间（Change Start Time） $T_{c}$ 小于或者等于 $T_{f}$ 。通常情况下，一个或者多个机器故障会在半小时（30 mins）甚至更短的时间内引发服务故障，因此，只需要假设 $w_{1}=30$ 即可。关键时间点的排序为 $T_{f}-w_{1}<T_{c}\leq T_{f}<T_{m}$ 。

对于服务 KPIs 的异常检测，FluxRank 中提到了两种方法：分别是 absolute derivative 和 CUSUM 方法。

absolute derivative 方法：个人理解就是对时间序列进行一阶差分操作，然后对一阶差分来做时间序列异常检测，例如 3-sigma 等方法，一旦有明显的变化，就说明当前的时间点出现了突增或者突降；与该方法比较类似的一种方法是：MAD（Median Absolute Deviation）。对于一条时间序列 $X=[x_{1},\cdots,x_{n}]$ 而言，MAD 定义为 $MAD = median_{1\leq i\leq n}(|x_{i}-median(X)|)$ ，而每个点的异常程度可以定义为： $s_{i}=(x_{i}-median(X))/MAD = (x_{i}-median(X))/median_{1\leq i\leq n}(|x_{i}-median(X)|).$ 当 $s_{i}$ 较大或者较小的时候，表示上涨或者下降的异常程度。通过设置相应的阈值，同样可以获得时间序列的异常开始时间。
CUSUM 算法也是用于时间序列异常检测的。对于一条时间序列 $X=[x_{1},x_{2},\cdots,x_{n}]$ ，可以预估它的目标值（target value） $\mu_{0}$ ，通常可以用均值来估计，也需要计算出这条时间序列的标准差 $\sigma$ 。通常设定 $\mu_{1}=\mu_{0}+\delta\sigma$ ， $K=\delta\sigma/2=|\mu_{1}-\mu_{0}|/2$ 。而 Tabular CUSUM 指的是迭代公式 $C_{i}^{+}=\max[0,x_{i}-(\mu_{0}+K)+C_{i-1}^{+}]$ ， $C_{i}^{-}=\max[0,(\mu_{0}-K)-x_{i}+C_{i-1}^{-}]$ ，初始值是 $C_{0}^{+}=C_{0}^{-}=0$ 。当累计偏差 $C_{i}^{+}$ 或者 $C_{i}^{-}$ 大于 $H=5\sigma$ 的时候，表示 $x_{i}$ 出现了异常，也就是 out of control。通过这个值，可以获得时间序列开始异常的时间。

从论文的描述来看，作者是使用 absolute derivative 来做异常检测的，并且定位其异常开始时间的准确率较高。

Change Degree

其次，我们来看一下变化程度（Change Degree）是怎么计算出来的，通过之前的计算，我们已经可以获得一些关键的时间戳，例如 $T_{f}, T_{c}, T_{m}$ 等时间戳。根据变化开始时间（change start time） $T_{c}$ ，同样需要设置一个窗口值 $w_{2}$ ，例如 60 分钟（1 小时）。可以从两个时间段获取数据，正常时间段 $[T_{c}-w_{2},T_{c})$ ，异常时间段 $[T_{c},T_{m}]$ ，分别获取到数据 $\{x_{i}\}$ 和 $\{x_{j}\}$ ，前者是在变化开始时间之前的数据点，后者是在变化开始之后的数据点。于是，作者们通过概率值来计算变化程度 $P(\{x_{j}\}|\{x_{i}\})$ ，意思就是计算一个条件概率，在观察到 $\{x_{i}\}$ 之后，得到 $\{x_{j}\}$ 的概率值。

为了计算以上概率值，需要简化模型，因此这里需要假设 $\{x_{j}\}$ 是独立同分布（iid）的，于是 $P(\{x_{j}\}|\{x_{i}\})=\prod_{j=1}^{\ell}P(x_{j}|\{x_{i}\})$ ，在这里 $\ell$ 表示集合 $\{x_{j}\}$ 的元素个数。为了分别得到其上涨和下降到概率，则需要计算：

$P_{o}(\{x_{j}\}|\{x_{i}\}) = \prod_{j=1}^{\ell}P(X\geq x_{j}|\{x_{i}\})$ ,

$P_{u}(\{x_{j}\}|\{x_{i}\}) = \prod_{j=1}^{\ell}P(X\leq x_{j}|\{x_{i}\})$ ,

其中 $P_{o}(\{x_{j}\}|\{x_{i}\})$ 表示上涨的程度， $P_{u}(\{x_{j}\}|\{x_{i}\})$ 表示下降的程度。如果不想处理连乘的话，则需要处理连加：

$o=-\frac{1}{\ell}\sum_{j=1}^{\ell}\ln P(X\geq x_{j}|\{x_{i}\})$ ,

$u =-\frac{1}{\ell}\sum_{j=1}^{\ell}\ln P(X\leq x_{j}|\{x_{i}\})$ .

在这里，作者们使用了三种概率分布函数，分别是 Beta 分布（Beta distribution），泊松分布（Poisson distribution），高斯分布（Gaussian distribution）。

Beta 分布的概率密度函数（probabilisty density function）是 $f(x;\alpha,\beta) = x^{\alpha-1}(1-x)^{\beta-1}/B(\alpha,\beta)$ ，其中 $B(\alpha,\beta)=\Gamma(\alpha)\Gamma(\beta)/\Gamma(\alpha+\beta)$ 。在机器 KPIs 中，CPU 等指标可以用 Beta 分布；

泊松分布的概率密度函数是 $f(x;\lambda)=\lambda^{x}e^{-\lambda}/x!$ ，在机器 KPIs 中，SYS_OOM 用于衡量超出内存的频率，可以用泊松分布来做。

高斯分布的概率密度函数 $f(x;\mu,\sigma) = e^{-(x-\mu)^{2}/2\sigma^{2}}/(\sqrt{2\pi}\sigma)$ 。

根据论文中的陈述，机器 KPIs 分别适用于以下概率分布：

通过以上公式，可以计算出每一个机器的每一个指标的 $o$ 和 $u$ 两个值。

Digest Distillation

再来看一下 Digest Distillation 部分，在此部分需要对机器的 KPIs 进行聚类操作；那么就需要构造特征向量和距离函数，再加上聚类算法即可获得结果。

每一个机器的特征向量是由之前计算的 Change Degree 形成的，由于每台机器的 KPIs 都是一样的，因此可以对它们的 KPIs 的 change degree 进行排列。假设每台机器有 $k$ 个 KPIs，那么这台机器所对应的向量就是 $(o_{0},u_{0},\cdots,o_{k},u_{k})$ 。

在描述向量的相似性方面，可以使用相关性的系数，包括 Pearson 系数，Kendall tau 系数，Spearman 系数。对于两条时间序列而言， $X=[x_{1},\cdots,x_{n}]$ 和 $Y=[y_{1},\cdots,y_{n}]$ ，

Pearson 系数指的是： $\rho_{X,Y}=\sum_{i=1}^{n}(x_{i}-\overline{x})\cdot(y_{i}-\overline{y})/\sqrt{\sum_{i=1}^{n}(x_{i}-\overline{x})^{2}\cdot\sum_{i=1}^{n}(y_{i}-\overline{y})^{2}},$ 其中 $\overline{x}=\sum_{i=1}^{n}x_{i}/n$ ， $\overline{y}=\sum_{i=1}^{n}y_{i}/n$ 。

Kendall tau 系数指的是：如果 ( $x_{i}>x_{j}$ 且 $y_{i}>y_{j}$ ) 或者 ( $x_{i}<x_{j}$ 且 $y_{i}<y_{j}$ )，那么称之为 concordant；如果 ( $x_{i}<x_{j}$ 且 $y_{i}>y_{j}$ ) 或者 ( $x_{i}>x_{j}$ 且 $y_{i}<y_{j}$ )，称之为 discordant；如果 $x_{i}=x_{j}$ 或者 $y_{i}=y_{j}$ ，则既不是 concordant，也不是 discordant。那么 Kendall tau 定义为 $[\text{(number of concordant pairs)}-\text{(number of disordant paris)}] / [n(n-1)/2]$

Spearman 系数指的是：通过原始序列变成秩次变量（rank）（从大到小降序排列即可）， $x_{i}$ 将会对应到 $x_{i}'$ ，后者表示 $x_{i}$ 在从大到小排序之后的序列 $\{x_{i}\}_{1\leq i\leq n}$ 的位置，称之为秩次（rank），得到序列 $X'=[x_{1}',\cdots,x_{n}']$ 。对原始序列 $Y=[y_{1},\cdots,y_{n}]$ 作同样的操作，得到 $Y'=[y_{1}',\cdots,y_{n}']$ 。一个相同的值在一列数据中必须有相同的秩次，那么在计算中采用的秩次就是数值在按从大到小排列时所在位置的平均值。如果没有相同的 rank，那么使用公式 $r_{s} = 1-6\sum_{i=1}^{n}d_{i}^{2}/(n(n^{2}-1))$ 进行计算，其中 $d_{i}=x_{i}'-y_{i}'$ ；如果存在相同的秩次，则对 $X'=[x_{1}',\cdots,x_{n}']$ 和 $Y'=[y_{1}',\cdots,y_{n}']$ 来做 Pearson 系数即可，也就是 $\rho_{X',Y'}$ 。

通过作者们的实验，说明 Pearson 系数在这个数据集上效果最佳。在聚类算法的场景下，作者们同样对比了 KMeans，Gaussian Mixture，Hierarchical Clustering，DBSCAN 算法的效果，最后使用了 DBSCAN 的聚类算法。每一个聚类的结果，作者称之为一个 digest，也就是下图的 M1，M2 等聚类结果。

Digest Ranking

最后，就是对聚类结果的排序工作。通过观察会发现：

变化开始时间（change start time） $T_{c}$ 会在失败发生时间 $T_{f}$ 之前；
不同的故障机器 KPIs 的 change start time 是非常接近的；
故障机器的一些 KPIs 的 change degree 是非常大的；
故障机器的占比是与故障原因相关的，故障机器越多说明故障越大；

在同一个模块下，如果出现故障机器的占比较大，那么故障将集中于这个模块下，可以通过 ratio 这个指标进行排序工作。

实验数据

在 FluxRank 论文中，作者们收集了 70 个真实的案例，然后根据实验效果获得了结果。

在标记的时候，除了标记异常机器（Root Cause Machines，简称为 RCM）之外，也需要标记相关的指标（Relevant KPI，简称为 RK）。Root Cause Digest（简称为 RCD）把包括两个部分，不仅包括 RCM 的一个聚类结果，还包括聚类结果中的 top-five KPIs。

通过对 FluxRank 进行实验，可以得到如下实验数据：

其中 Recall@K 指的是： $Recall@K=\text{\# of cases whose top-k digests contain RCDs}/ \text{\# of all cases},$ 或者 $Recall@K=\text{\# of cases whose top-k machines contain RCMs}/\text{\# of all cases}.$

参考资料

FluxRank: A Widely-Deployable Framework to Automatically Localizing Root Cause Machines for Software Service Failure Mitigation，Ping Liu，Yu Chen，Xiaohui Nie，Jing Zhu，Shenglin Zhang，Kaixin Sui，Ming Zhang，Dan Pei，ISSRE 2019， Berlin, Germany, Oct 28-31, 2019。
Introduction to Statistical Quality Control，6th edition，Douglas C.Montgomery。
Bayesian Network：https://en.wikipedia.org/wiki/Bayesian_network

ZHANG RONG

Daily Archives: March 21, 2020

新加坡首次出现两起新冠病毒死亡病例！

FluxRank: 如何快速地进行机器故障定位