TL;DR 目前生产环境中的监控数据主要包括两种类型:指标的时间序列数据 (time series),例如 CPU 利用率指标,和事件序列数据 (events),例如 out of memory 时间,论文中提出一种事件和时间序列关联分析的方法来提升故障诊断的效率。主要考虑了事件序列与时间序列间三个方面的问题:事件和时间序列 ① 是否存在关联关系 ② 时间先后顺序 ③ 单调性影响。论文实验部分在仿真数据集和真实数据集中验证了算法的有效性。
Problem Statement 下图展示了事件与时间序列的关系,例如 CPU 密集型的程序会导致 CPU 使用率上升,但是磁盘密集型的程序将对 CPU 使用率没有什么影响,因此 CPU 密集型事件与 CPU 使用率上升事件间存在关联但是磁盘密集型的程序与 CPU 使用率上升没有关联。 当故障发生时,考虑这种事件与时间序列的关联有助于提高故障诊断的效率。
event-timeseries
故障诊断时需要考虑事件与时间序列间三个方面的问题:
是否存在依赖关系 :首先需要根据统计关系方法判断事件与时间序列间是否存在关系,虽然不能代表因果关系但是可以两者是关联的。依赖关系的时间顺序 :判断事件和时间序列发生的顺序,例如事件E E E 先发生,时间序列S S S 也随之改变,那么可以说明事件E E E 导致时间序列S S S 波动,或者反之序列S S S 波动导致了事件E E E 。这样可以确认因果方向。依赖的单调性影响 :通过判断时间序列上升或者降低导致了事件的发生。给定事件序列或时间类型E E E ,对应的时间戳表示T E = ( t 1 , t 2 , ⋯ , t n ) T_E=(t_1, t_2,\cdots,t_n) T E = ( t 1 , t 2 , ⋯ , t n ) ,n n n 表示发生事件的数量;时间序列S = ( s 1 , s 2 , ⋯ , s m ) S=(s_1, s_2, \cdots,s_m) S = ( s 1 , s 2 , ⋯ , s m ) ,其中m m m 表示数据点数量,时间序列的时间戳表示为T S = ( t ( s 1 ) , t ( s 2 ) , ⋯ , t ( s n ) ) T_S=(t(s_1), t(s_2),\cdots,t(s_n)) T S = ( t ( s 1 ) , t ( s 2 ) , ⋯ , t ( s n ) ) ,时间戳存在关系t ( s i ) = t ( s i − 1 ) + τ t(s_i)=t(s_{i-1})+\tau t ( s i ) = t ( s i − 1 ) + τ ,τ \tau τ 表示采样时间间隔。
sub-series
如上图所示,如果事件e i ∈ E e_i\in E e i ∈ E 与时间序列S S S 间存在联系那么必然发生事件e i e_i e i 发生后时间序列S S S 会随之改变。
假设ℓ k r e a r ( S , e i ) \ell_k^{rear}(S, e_i) ℓ k r e a r ( S , e i ) 表示事件e i e_i e i 发生后长度为k k k 的子序列,ℓ k f r o n t ( S , e i ) \ell_k^{front}(S, e_i) ℓ k f r o n t ( S , e i ) 表示发生前的子序列。如果事件E E E 与时间序列S S S 无关,那么子序列集合Γ front = { ℓ k front ( S , e i ) , i = 1 ⋯ n } \Gamma^{\text {front }}=\{\ell_{k}^{\text {front }}(S, e_{i}),i=1 \cdots n\} Γ front = { ℓ k front ( S , e i ) , i = 1 ⋯ n } 或者Γ rear = { ℓ k rear ( S , e i ) , i = 1 ⋯ n } \Gamma^{\text {rear }}=\left\{\ell_{k}^{\text {rear }}\left(S, e_{i}\right), i=1 \cdots n\right\} Γ rear = { ℓ k rear ( S , e i ) , i = 1 ⋯ n } 将不会与S S S 中随机采样长度为k k k 序列Θ \Theta Θ 统计概率分布相同,如果概率分布相同那么事件E E E 和S S S 存在关联。因此,论文中将关联分析问题转为多变量的二样本假设检验问题。
Algorithm/Model 论文中主要基于最近邻的方法来分析三个方面的关联关系。
最近邻方法 以Γ front \Gamma^{\text {front }} Γ front 为例,给定样本Γ front = { ℓ k front ( S , e i ) , i = 1 ⋯ n } ) \left.\Gamma^{\text {front }}=\left\{\ell_{k}^{\text {front }}\left(S, e_{i}\right), i=1 \cdots n\right\}\right) Γ front = { ℓ k front ( S , e i ) , i = 1 ⋯ n } ) 和Θ = { θ 1 , θ 2 , ⋯ , θ n ~ } \Theta=\left\{\theta_{1}, \theta_{2}, \cdots, \theta_{\tilde{n}}\right\} Θ = { θ 1 , θ 2 , ⋯ , θ n ~ } ,样本合集Z = Γ ∪ Θ = { Z 1 , ⋯ , Z p } Z=\Gamma \cup \Theta = \{Z_1,\cdots,Z_p\} Z = Γ ∪ Θ = { Z 1 , ⋯ , Z p } ,p = n + n ~ p=n+\tilde{n} p = n + n ~
Z i = { ℓ k front ( S , e i ) , if i = 1 , ⋯ , n θ i − n , if i = n + 1 , ⋯ , p Z_{i}=\left\{\begin{array}{ll} \ell_{k}^{\text {front }}\left(S, e_{i}\right), & \text { if } i=1, \cdots, n \\ \theta_{i-n}, & \text { if } i=n+1, \cdots, p \end{array}\right. Z i = { ℓ k front ( S , e i ) , θ i − n , if i = 1 , ⋯ , n if i = n + 1 , ⋯ , p 定义N N r ( x , A ) NN_r(x, A) N N r ( x , A ) 表示集合{ A \ x } \{A\backslash x\} { A \ x } 中x x x 的最近邻样本;
定义两个子集合A 1 , A 2 A_1,A_2 A 1 , A 2 并且x ∈ A x\in A x ∈ A 指示函数的值为
I r ( x , A 1 , A 2 ) = { 1 , if x ∈ A i & & N N r ( x , A ) ∈ A i , 0 , otherwise I_{r}\left(x, A_{1}, A_{2}\right)=\left\{\begin{array}{ll} 1, & \text { if } x \in A_{i} \& \& N N_{r}(x, A) \in A_{i}, \\ 0, & \text { otherwise } \end{array}\right. I r ( x , A 1 , A 2 ) = { 1 , 0 , if x ∈ A i & & N N r ( x , A ) ∈ A i , otherwise 基于最近邻的假设检验量化形式如下
T r , p = 1 p r ∑ i = 1 p ∑ j = 1 r I j ( x , A 1 , A 2 ) T_{r, p}=\frac{1}{p r} \sum_{i=1}^{p} \sum_{j=1}^{r} I_{j}\left(x, A_{1}, A_{2}\right) T r , p = p r 1 i = 1 ∑ p j = 1 ∑ r I j ( x , A 1 , A 2 ) 当p p p 足够大时,( p r ) 1 / 2 ( T r , p − μ r ) / σ r (pr)^{1/2}(T_{r,p}-\mu_r)/\sigma_r ( p r ) 1 / 2 ( T r , p − μ r ) / σ r 符合高斯分布,其中
μ r = ( λ 1 ) 2 + ( λ 2 ) 2 , σ r 2 = λ 1 λ 2 + 4 λ 1 2 λ 2 2 λ 1 = n / p , λ 2 = n ~ / p \mu_{r}=\left(\lambda_{1}\right)^{2}+\left(\lambda_{2}\right)^{2},\quad \sigma_{r}^{2}=\lambda_{1} \lambda_{2}+4 \lambda_{1}^{2} \lambda_{2}^{2}\\ \lambda_1=n/p,\quad \lambda_2=\tilde{n}/p μ r = ( λ 1 ) 2 + ( λ 2 ) 2 , σ r 2 = λ 1 λ 2 + 4 λ 1 2 λ 2 2 λ 1 = n / p , λ 2 = n ~ / p 高斯分布的假设检验如下,
( p r ) 1 / 2 ( T r , p − μ r ) / σ r > α (pr)^{1/2}(T_{r,p}-\mu_r)/\sigma_r > \alpha ( p r ) 1 / 2 ( T r , p − μ r ) / σ r > α :α = 1.96 , P = 0.025 \alpha=1.96,P=0.025 α = 1 . 9 6 , P = 0 . 0 2 5 ;α = 2.58 , P = 0.001 \alpha =2.58,P=0.001 α = 2 . 5 8 , P = 0 . 0 0 1 ;
判断关联存在及其时序 根据最近邻的假设检验方法,如果Γ front \Gamma^{\text {front }} Γ front 和Θ \Theta Θ 是统计独立的,那么S → E S\rightarrow E S → E ,如果Γ rear \Gamma^{\text {rear}} Γ rear 和Θ \Theta Θ 是统计独立的,那么E → S E\rightarrow S E → S 。
判断单调性影响 主要是判断事件E E E 导致序列上升还是下降:E → + S E \stackrel{+}{\rightarrow} S E → + S 或者E → − S E \stackrel{-}{\rightarrow} S E → − S 。论文中使用t t t 检验进行判断,Γ f r o n t \Gamma ^{front} Γ f r o n t 和Γ r e a r \Gamma ^{rear} Γ r e a r 间的t t t 分数计算公式如下
t s c o r e = μ Γ f r o n t − μ Γ r e a r ( n 1 − 1 ) σ Γ f r o n t 2 + ( n 2 − 1 ) σ Γ r e a r 2 n 1 + n 2 − 2 ( 1 n 1 − 1 n 2 ) t_{s c o r e}=\frac{\mu_{\Gamma^{f r o n t}}-\mu_{\Gamma^{r e a r}}}{\sqrt{\frac{\left(n_{1}-1\right) \sigma_{\Gamma^{f r o n t}}^{2} +\left(n_{2}-1\right) \sigma_{\Gamma^{r e a r}}^{2}}{n_{1}+n_{2}-2}{\left(\frac{1}{n_{1}}-\frac{1}{n_{2}}\right)}}} t s c o r e = n 1 + n 2 − 2 ( n 1 − 1 ) σ Γ f r o n t 2 + ( n 2 − 1 ) σ Γ r e a r 2 ( n 1 1 − n 2 1 ) μ Γ f r o n t − μ Γ r e a r 其中μ Γ f r o n t \mu_{\Gamma^{front}} μ Γ f r o n t μ Γ f r o n t \mu_{\Gamma^{front}} μ Γ f r o n t 分别表示序列均值,σ Γ f r o n t \sigma_{\Gamma^{front}} σ Γ f r o n t σ Γ f r o n t \sigma_{\Gamma^{front}} σ Γ f r o n t 表示标准差。由于n 1 = n 2 = n n_1 =n_2=n n 1 = n 2 = n ,n n n 表示E E E 中事件数量,因此上式可以简化为
t s c o r e = μ Γ f r o n t − μ Γ r e a r σ Γ f r o n t 2 + σ Γ r e a r 2 n t_{s c o r e}=\frac{\mu_{\Gamma^{f r o n t}}-\mu_{\Gamma^{r e a r}}}{\sqrt{\frac{\sigma_{\Gamma^{f r o n t}}^{2} + \sigma_{\Gamma^{r e a r}}^{2}}{n}}} t s c o r e = n σ Γ f r o n t 2 + σ Γ r e a r 2 μ Γ f r o n t − μ Γ r e a r 如果t s c o r e > α t_{s c o r e}>\alpha t s c o r e > α 那么表示负影响E → − S E \stackrel{-}{\rightarrow} S E → − S ,如果t s c o r e < − α t_{s c o r e}<-\alpha t s c o r e < − α 那么表示正影响E → + S E \stackrel{+}{\rightarrow} S E → + S ,α = 1.96 , P = 0.025 ; α = 2.58 , P = 0.001 \alpha = 1.96, P = 0.025 ; α = 2.58 , P = 0.001 α = 1 . 9 6 , P = 0 . 0 2 5 ; α = 2 . 5 8 , P = 0 . 0 0 1
整体的算法流程如下图所示:
algorithm
Experiments 论文中采用的数据集如下所示
dataset
实验参数参考论文,实验效果如下:
experiments1
考虑了计算最近邻时的时间序列相似度指标,整体而言 DTW 效果较好。
experiments2
Thoughts