在運維領域，服務側的異常會由多方面的原因造成，有的時候是因為網絡的抖動，有的時候是因為機器的故障，有的時候甚至是因為人為的變更。本篇博客會介紹一種機器異常定位的方法，論文是來自于清華 Netman 實驗室的《FluxRank：A Widely-Deployable Framework to Automatically Localizting Root Cause Machines for Software Service Failure Mitigation》。本篇論文主要介紹了如何從服務的故障定位到局部異常的機器，也就是說在發現服務故障的同時，進一步推斷出是由哪些機器出現問題而導致的。

通常來說，在服務異常（例如服務的耗時長，失敗數上漲）的時候，需要運維人員通過歷史上的經驗迅速定位到是哪個業務，哪個模塊，甚至哪臺服務器出現了故障。而人工定位的速度總是會出現瓶頸的，無論對模塊的判斷，還是機器的判斷，都依賴于人工所積累的經驗。而每個人的經驗卻各不相同，并且經驗的傳承也需要一定的時間成本。那么如何基于人工運維的經驗來構建模型，進一步地提升異常定位的速度就是智能運維的關鍵之處之一。

對于一條業務指標（時間序列）而言，大多數情況下是處于正常的狀態（normal）。但是如果出現了錯誤的變更，發布了錯誤的程序，或者服務器突然出現了故障，都會導致業務指標出現變化，就從正常（normal）變成異常（abnormal）。這個時候就會出現一個故障的開始時間，也就是 failure start time  ，這個時間戳是運維領域非常重要的時間戳，它由異常檢測（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），其概率分布如下圖所示。那么可以問如下問題：

1. 如果草已經濕潤，求降雨的概率是多少？
2. 如果草已經濕潤，求沒有降雨且灑水器開啟的概率是多少？

而這一類的問題可以通過貝葉斯公式來進行解答。從表格來看：

從 Rain 的表格可得：  。

從 Rain 和 Sprinkler 的表格可得：  ，  。

從 Grass Wet 和 Sprinkler，Rain 的表格可得：  ，  ，  ， 

針對問題 1，需要計算條件概率  。從 Bayes 公式可以得到：  。分別計算分子分母即可：

 ，

那么如果草已經濕潤，求降雨的概率是 

另外一個題目可以用類似的方法進行求解，在此不再贅述。

雖然貝葉斯算法能夠計算出條件概率，例如本次故障是由哪些原因導致的，但是這個需要長期收集數據，需要對歷史數據進行積累，才能通過人工或者統計的方法得到以上表格的條件概率。但是在實際的環境中是較難獲取這些數據的，需要大數據平臺的支持，因此需要探索其他的解決方案。

FluxRank

在本論文中，為了克服貝葉斯網絡模型中的一些問題，針對子機異常定位的場景，設計了一套技術方案，作者們稱之為 FluxRank。

FluxRank 這一模塊的觸發需要服務指標（Service KPI）的異常，因此需要對服務指標（Service KPI）進行異常檢測。這里的服務指標通常指的是業務指標，包括某塊 APP 的在線人數，某個接口的成功率，某個視頻網站的卡頓數等指標。當服務指標出現了異常的時候，就啟動 FluxRank 模塊進行異常機器定位。

如果按照人工處理的流程來看，分成幾個步驟：

1. 異常檢測部分：通過設定閾值或者某個簡單的規則來進行異常檢測，包括服務的 KPI（Service KPI）和機器的 KPI（machine KPIs）；
2. 手工檢查異常的時間段，并且查看在異常的時間段內發生了什么情況；
3. 運維人員根據自身的業務經驗來對機器的故障程度做人工排序；
4. 運維人員根據自身的業務經驗來對故障進行處理，并且人工給出處理方案。

那么 FluxRank 所面臨的挑戰就有以下幾點：

1. 如何衡量海量 KPIs 的變化程度？在這里不僅有服務的 KPIs，還有機器的 KPIs。而機器的 KPIs 包括內存，硬盤，IO，CPU等諸多固定的指標，那么如何對這些海量的 KPI 曲線進行變化程度的衡量，為后續的指標排序做準備就成為了一個難點；
2. 如何對 KPIs 進行異常性或者重要性的聚類，讓運維人員能夠一眼看出每個聚簇的差異或者異常程度？
3. 如何對 KPIs 聚類的結果進行排序？

為了解決以上的問題，FluxRank 的框架有以下幾個貢獻點：

1. 基于 Kenel Density Estimation 用于衡量海量 KPIs 在某一個時間段的變化程度和異常程度；
2. 基于上一步生成的異常程度，對諸多機器所形成的特征使用距離公式或者相似度公式，然后使用 DBSCAN 聚類算法來對機器進行聚類；
3. 在排序部分，對上一步的機器聚類結果進行排序；

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）  和緩和開始時間（Mitigation Start Time）  。在失敗開始時間  之前，可能有的機器已經出現了故障，因此變化開始時間（Change Start Time）  小于或者等于  。通常情況下，一個或者多個機器故障會在半小時（30 mins）甚至更短的時間內引發服務故障，因此，只需要假設  即可。關鍵時間點的排序為  。

對于服務 KPIs 的異常檢測，FluxRank 中提到了兩種方法：分別是 absolute derivative 和 CUSUM 方法。

1. absolute derivative 方法：個人理解就是對時間序列進行一階差分操作，然后對一階差分來做時間序列異常檢測，例如 3-sigma 等方法，一旦有明顯的變化，就說明當前的時間點出現了突增或者突降；與該方法比較類似的一種方法是：MAD（Median Absolute Deviation）。對于一條時間序列  而言，MAD 定義為  ，而每個點的異常程度可以定義為：  當  較大或者較小的時候，表示上漲或者下降的異常程度。通過設置相應的閾值，同樣可以獲得時間序列的異常開始時間。
2. CUSUM 算法也是用于時間序列異常檢測的。對于一條時間序列  ，可以預估它的目標值（target value）  ，通?？梢杂镁祦砉烙?，也需要計算出這條時間序列的標準差  。通常設定  ，  。而 Tabular CUSUM 指的是迭代公式  ，  ，初始值是  。當累計偏差  或者  大于  的時候，表示  出現了異常，也就是 out of control。通過這個值，可以獲得時間序列開始異常的時間。

從論文的描述來看，作者是使用 absolute derivative 來做異常檢測的，并且定位其異常開始時間的準確率較高。

Change Degree

其次，我們來看一下變化程度（Change Degree）是怎么計算出來的，通過之前的計算，我們已經可以獲得一些關鍵的時間戳，例如  等時間戳。根據變化開始時間（change start time）  ，同樣需要設置一個窗口值  ，例如 60 分鐘（1 小時）?？梢詮膬蓚€時間段獲取數據，正常時間段  ，異常時間段  ，分別獲取到數據  和  ，前者是在變化開始時間之前的數據點，后者是在變化開始之后的數據點。于是，作者們通過概率值來計算變化程度  ，意思就是計算一個條件概率，在觀察到  之后，得到  的概率值。

為了計算以上概率值，需要簡化模型，因此這里需要假設  是獨立同分布（iid）的，于是  ，在這里  表示集合  的元素個數。 為了分別得到其上漲和下降到概率，則需要計算：

 ,

 ,

其中  表示上漲的程度，  表示下降的程度。如果不想處理連乘的話，則需要處理連加：

 ,

 .

在這里，作者們使用了三種概率分布函數，分別是 Beta 分布（Beta distribution），泊松分布（Poisson distribution），高斯分布（Gaussian distribution）。

Beta 分布的概率密度函數（probabilisty density function）是  ，其中  。在機器 KPIs 中，CPU 等指標可以用 Beta 分布；

泊松分布的概率密度函數是  ，在機器 KPIs 中，SYS_OOM 用于衡量超出內存的頻率，可以用泊松分布來做。

高斯分布的概率密度函數  。

根據論文中的陳述，機器 KPIs 分別適用于以下概率分布：

通過以上公式，可以計算出每一個機器的每一個指標的  和  兩個值。

Digest Distillation

再來看一下 Digest Distillation 部分，在此部分需要對機器的 KPIs 進行聚類操作；那么就需要構造特征向量和距離函數，再加上聚類算法即可獲得結果。

每一個機器的特征向量是由之前計算的 Change Degree 形成的，由于每臺機器的 KPIs 都是一樣的，因此可以對它們的 KPIs 的 change degree 進行排列。假設每臺機器有  個 KPIs，那么這臺機器所對應的向量就是  。

在描述向量的相似性方面，可以使用相關性的系數，包括 Pearson 系數，Kendall tau 系數，Spearman 系數。對于兩條時間序列而言，  和  ，

Pearson 系數指的是：  其中  ，  。

Kendall tau 系數指的是：如果 (  且  ) 或者 (  且  )，那么稱之為 concordant；如果 (  且  ) 或者 ( 且  )，稱之為 discordant；如果  或者  ，則既不是 concordant，也不是 discordant。那么 Kendall tau 定義為 

Spearman 系數指的是：通過原始序列變成秩次變量（rank）（從大到小降序排列即可），  將會對應到  ，后者表示  在從大到小排序之后的序列  的位置，稱之為秩次（rank），得到序列  。對原始序列  作同樣的操作，得到  。一個相同的值在一列數據中必須有相同的秩次，那么在計算中采用的秩次就是數值在按從大到小排列時所在位置的平均值。如果沒有相同的 rank，那么使用公式  進行計算，其中  ；如果存在相同的秩次，則對  和  來做 Pearson 系數即可，也就是  。

通過作者們的實驗，說明 Pearson 系數在這個數據集上效果最佳。在聚類算法的場景下，作者們同樣對比了 KMeans，Gaussian Mixture，Hierarchical Clustering，DBSCAN 算法的效果，最后使用了 DBSCAN 的聚類算法。每一個聚類的結果，作者稱之為一個 digest，也就是下圖的 M1，M2 等聚類結果。

Digest Ranking

最后，就是對聚類結果的排序工作。通過觀察會發現：

1. 變化開始時間（change start time）  會在失敗發生時間  之前；
2. 不同的故障機器 KPIs 的 change start time 是非常接近的；
3. 故障機器的一些 KPIs 的 change degree 是非常大的；
4. 故障機器的占比是與故障原因相關的，故障機器越多說明故障越大；

在同一個模塊下，如果出現故障機器的占比較大，那么故障將集中于這個模塊下，可以通過 ratio 這個指標進行排序工作。

實驗數據

在 FluxRank 論文中，作者們收集了 70 個真實的案例，然后根據實驗效果獲得了結果。

在標記的時候，除了標記異常機器（Root Cause Machines，簡稱為 RCM）之外，也需要標記相關的指標（Relevant KPI，簡稱為 RK）。Root Cause Digest（簡稱為 RCD）把包括兩個部分，不僅包括 RCM 的一個聚類結果，還包括聚類結果中的 top-five KPIs。

通過對 FluxRank 進行實驗，可以得到如下實驗數據：

其中 Recall@K 指的是： 或者 

參考資料

1. 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。
2. Introduction to Statistical Quality Control，6th edition，Douglas C.Montgomery。
3. Bayesian Network：https://en.wikipedia.org/wiki/Bayesian_network