27 | June | 2019 | ZHANG RONG

背景介绍

在互联网公司里面，通常都会监控成千上万的时间序列，用于保障整个系统或者平台的稳定性。在这种情况下，如果能够对多条时间序列之间判断其是否相关，则对于监控而言是非常有效的。基于以上的实际情况，清华大学与 Alibaba 集团在2019年一起合作了论文《CoFlux: Robustly Correlating KPIs by Fluctuations for Service Troubleshooting》，并且发表在 IWQos 2019 上。CoFlux 这个方法可以对多条时间序列来做分析，并且主要用途包括以下几点：

告警压缩和收敛；
推荐与已知告警相关的 Top N 的告警；
在已有的业务范围内（例如数据库的实例）构建异常波动传播链；

CoFlux 的整体介绍

从论文的介绍中来看，CoFlux 的输入和输出分别是：

输入：两条时间序列

输出：这两条时间序列的以下信息

波动相关性：两条时间序列是否存在波动相关性？
前后顺序：如果两条时间序列相关，那么它们的前后波动顺序是什么？是同时发生异常还是存在固定的前后顺序？
方向性：如果两条时间序列是波动相关的，那么它们的波动方向是什么？是一致还是相反？

Remark. CoFlux 的关键点就是并没有对时间序列做异常检测算法，而是直接从时间序列的历史数据（历史半个月或者一个月）出发，判断两条时间序列之间的波动相关性，并且进一步的分析先后顺序与波动方向。

从论文的介绍中来看，CoFlux 的流程图如下图所示：

coflux流程图1

如果两条时间序列 $X$ 和 $Y$ 存在波动相关性，则需要输出这两条时间序列的波动先后顺序和是否同向波动。如果两条时间序列 $X$ 和 $Y$ 并不存在波动相关性的话，则不需要判断波动先后顺序和是否同向波动。

coflux流程图2

CoFlux 的细节阐述

已知一个长度是 $n$ 的时间序列 $S=\{s_{1},\cdots,s_{n}\}$ ，对于任意一个 detector，可以得到一条关于 $S$ 的预测值曲线 $P=\{p_{1},\cdots,p_{n}\}$ 。于是针对某个 detector 可以得到一个波动特征序列 $E=\{\epsilon_{1},\cdots,\epsilon_{n}\}$ ，其中 $\epsilon_{i} = s_{i} - p_{i}$ ， $1\leq i\leq n$ 。因此，一个detector 可以对应一个波动序列特征，也是一个时间序列。因此，对于 $m$ 个 detector，可以对应 $m$ 条波动特征序列，并且它们的长度都是 $n$ 。

在 CoFlux 算法的内部，根据不同的参数使用了总共 86 个 detector，大致列举如下：

Difference：根据昨天，七天前的数据来做差分；
Holt-Winters： $\{\alpha,\beta,\gamma\} \in \{0.2,0.4,0.6,0.8\}$ ；
历史上的均值 & 历史上的中位数：1，2，3，4 周；
TSD & TSD 中位数：1，2，3，4 周；
Wavelet：1，3，5，7 天；
移动平均算法：MA，WMA，EWMA。PS：根据作者们的说法，在这里，MA等方法并不适用。

detectors

根据直觉来看，

对于任何一条时间序列 kpi，总有一个 detector 可以相对准确地提炼到其波动特征；
如果两条时间序列 $X$ 和 $Y$ 波动相关，那么 $X$ 的一个波动特征序列与 $Y$ 的一个波动特征序列应该也是相关的；

Remark. 两条时间序列的波动特征可以对齐同一个 detector，也可以不做对齐工作。如果是前者的话，时间复杂度低；后者的话，时间复杂度高。

下图是从时间序列中提取波动特征曲线的案例：

提炼时间序列的波动曲线特征只是第一步，后续 CoFlux 还有几个关键的步骤：

特征工程的扩大（amplify）：对波动序列特征进行放大，让某些波动序列特征更加明显；
Correlation Measurement：用于解决时间序列存在时间前后的漂移，两条时间序列之间存在 lag 的情况，因此需要对其中一条时间序列做平移操作；
CoFlux 考虑了历史数据（历史半个月或者一个月）作为参考，并且一个范围内的 kpi 数量不超过 60 条；

下面来一一讲解这些技术方案，对于每一条波动特征曲线（Flux-Features），按照以下几个步骤来进行操作：

Step 1：对波动特征曲线 $E=\{\epsilon_{1},\cdots,\epsilon_{n}\}$ 做 z-score 的归一化，i.e.

$\mu = \frac{\sum_{i=1}^{n}\epsilon_{i}}{n},$
$\delta = \sqrt{\frac{\sum_{i=1}^{n}(\epsilon_{i}-\mu)^{2}}{n}}.$

Step 2：对归一化之后的波动特征曲线做特征放大（feature amplification）：定义函数 $f_{\alpha,\beta}(x)$ 如下：

$f_{\alpha,\beta}(x)= \begin{cases} e^{\alpha\min(x,\beta)} - 1, \text{ when } x\geq 0,\\ -e^{\alpha\min(|x|,\beta)} + 1, \text{ when } x< 0. \end{cases}$

则 $E=\{\epsilon_{1},\cdots,\epsilon_{n}\}$ 放大之后的波动特征曲线（amplified flux feature）就是： $\hat{E}=\{f(\epsilon_{1}),\cdots,f(\epsilon_{n})\}.$

Step 3：对于两条放大之后的波动特征曲线（amplified flux features） $G=\{g_{1},\cdots,g_{\ell}\}$ 和 $H=\{h_{1},\cdots,h_{\ell}\}$ ，可以计算它们之间的相关性，先后顺序，是否同向。
令
$G_{s}= \begin{cases} \{0,\cdots,0,g_{1},\cdots, g_{\ell-s}\}, \text{ when } s\geq 0, \\ \{g_{1-s},\cdots,g_{\ell},0,\cdots,0\}, \text{ when } s< 0. \end{cases}$

这里的 0 的个数是 $|s|$ 个。其中， $-\ell<s<\ell$ 。特别地，当 $s=0$ 时， $G_{0}=\{g_{1},\cdots,g_{s}\}=G$ ，那么我们可以定义 $G_{s}$ 与 $H$ 的内积是： $R(G_{s},H) = G_{s}\cdot H,$

这里的 $\cdot$ 指的是向量之间的内积（inner product）。同时可以定义相关性（Cross Correlation）为： $CC(G_{s},H) = \frac{R(G_{s},H)}{\sqrt{R(G_{s},G_{s})\cdot R(H,H)}}.$

由于波动有可能是反向的，那么在这里我们不仅要考虑相关性是大于零的情况，也需要考虑小于零的情况。于是，

$minCC = \min_{-\ell<s<\ell}CC(G_{s},H),$
$maxCC = \max_{-\ell<s<\ell}CC(G_{s},H).$

则最小值或者最大值的指标分别是

$s_{1}=argmin_{-\ell<s<\ell}CC(G_{s},H),$
$s_{2}=argmax_{-\ell<s<\ell}CC(G_{s},H).$

令
$FCC(G,H) = \begin{cases} (minCC, s_{1}), \text{ when } |maxCC|<|minCC|, \\ (maxCC, s_{2}), \text{ when } |maxCC|\geq|minCC|. \end{cases}$

从定义中可以看出， $FCC(G,H)$ 是一个元组，里面蕴含着三个信息，分别是相关性，波动方向，前后顺序。 $FCC(G,H) \in [-1,1]$ ，越接近 1 或者 -1 就表示放大之后的波动特征曲线 $G$ 和 $H$ 越相关。正值的 $FCC(G,H)$ 表示 $G$ 与 $H$ 的波动方向相同，是正相关；负值的 $FCC(G,H)$ 表示 $G$ 与 $H$ 的波动方向想法，是负相关。通过对 $s<0$ 或者 $s\geq 0$ 的分析就可以判断先后顺序。因此，CoFlux 方法的是通过对 $FCC(G,H)$ 的分析来得到最终结果的。