ADSketch：基于模式側寫的在云服務性能異常檢測

本文發(fā)表在ICSE2022（CCF-A）會議，作者陳壯彬（香港中文大學博士研究生），論文內容為華為-港中文云系統(tǒng)與可靠性聯(lián)合實驗室研究工作產出。原文鏈接Adaptive Performance Anomaly Detection for Online Service Systems via Pattern Sketching

隨著云計算的發(fā)展，傳統(tǒng)桌面軟件逐漸遷移到云上，以云服務（在線服務）的形態(tài)提供給用戶。云服務質量于用戶體驗而言至關重要。為了保證服務性能，云服務通過各種指標（比如CPU使用率，服務響應延遲，吞吐量）進行7×24小時的密切監(jiān)控。指標異常檢測旨在找到指標序列（一種時序數(shù)據）中預期之外的或者罕見的模式，從而及時發(fā)現(xiàn)服務中的性能問題。為了應對復雜多樣的時序異常模式以及幫助運維人員進行快速故障理解與根因定位，華為云計算與網絡Lab聯(lián)合香港中文大學提出ADSketch，一種準確、高效，且具有可解釋性與在線學習能力的異常檢測算法。

傳統(tǒng)時序異常檢測的問題

時序異常檢測是一個經典的問題，然而云服務場景對算法提出了更高的要求。現(xiàn)有算法通常難以滿足以下兩個關鍵需求：

• 算法結果可解釋：現(xiàn)有工作大多是為指標序列的每個節(jié)點計算一個異常概率，并通過設置閾值的方式判斷異常是否發(fā)生。然而這樣的結果對運維人員的作用十分有限。由于算法無法進一步提供異常是由哪些故障/問題導致的，運維人員難以相信算法結果，需要手工排查大量指標進行問題定位。因此，可解釋性對于故障分析與服務恢復具有重要作用。
• 異常模式在線更新：實際場景中，在線服務頻繁變更（比如系統(tǒng)架構發(fā)生變化，新功能上線），異常模式也可能隨之改變?，F(xiàn)有工作大多通過歷史離線數(shù)據訓練學習異常檢測模式，難以適應頻繁變化的異常模式。因此現(xiàn)有工作部署在實際系統(tǒng)時，隨著時間的推移將產生較多誤報。

本論文方法：ADSketch

為解決上述問題，本論文提出ADSketch，一種基于模式側寫的在云服務性能異常檢測算法。軟件系統(tǒng)的不同組件（比如微服務、函數(shù)服務）提供特定的功能，并且用戶的行為具有一定規(guī)律，因此當同類型的性能問題發(fā)生時，指標通常表現(xiàn)出類似的模式，如圖1所示?；诖擞^察，ADSketch提出從指標時序序列中識別出具有判別性的子序列，作為指標模式（metric pattern）用以標識不同類型的服務性能問題。比如服務性能瓶頸通常表現(xiàn)為吞吐量下降及CPU利用率上升。通過將故障問題和指標模式進行關聯(lián)，可以為結果提供更好的可解釋性（類似于故障指紋/故障側寫）。當相似的時序異常模式出現(xiàn)時，算法便可快速識別異常并提供可能發(fā)生的故障/問題。

圖1：性能異常模式案例

整體框架

ADSketch的整體框架如圖2所示。共分為兩個階段：離線異常檢測（offline phase）及在線異常檢測（online phase）。在離線階段，輸入為一對指標序列，一個是不包含異常的指標序列（anomaly-free metric），用來作為正常指標的參考基準；另一個輸入為需要進行異常檢測的指標序列（metric for anomaly detection）。這個階段將學習到兩種指標模式，即正常模式（normal patterns）和異常模式（abnormal patterns）。特別地，指標模式為一組相似的子序列通過求平均獲得。運維人員在日常故障處理過程中把服務性能問題與學習到的異常模式進行關聯(lián)，以實現(xiàn)知識的積累。在線階段則利用離線階段捕獲的模式進行快速的異常檢測，同時對已習得的模式進行更新（adaptive pattern learning）。

圖2：ADSketch整體框架圖

算法細節(jié)

離線指標模式學習

離線階段的一個重要目標是發(fā)現(xiàn)指標模式。主要思想為，如果一個子序列顯著偏離正常時期的子序列，那么它是一種異常模式。偏移程度用兩個子序列的距離來度量，如果距離越大，說明越可能異常。對于一個長度為l的指標序列，假設子序列的長度為m，那該指標序列有l(wèi)-m+1條子序列。通過暴力計算這些子序列兩兩之間的距離，我們可以得到每一條子序列距離其他子序列最小的值，我們稱為the smallest pair-wise distance（簡稱SPW距離）。SPW越大，則表明該子序列越偏離整體指標序列（與其他所有子序列的相似度較低），因此也越可能是異常。從圖3可以看出，異常區(qū)間的SPW距離顯著高于正常區(qū)間的。

圖3：指標序列不同子序列的SPW距離

本論文提出的指標模式發(fā)現(xiàn)算法如圖4和圖5所示，$T_n$為輸入的正常指標序列，$T_a$為需要進行異常檢測的序列，m為子序列長度，p為分位數(shù)閾值（用來劃定異常子序列，為了降低漏報率，該參數(shù)設置的比較寬松），I和S為子序列的索引以及子序列的SPW距離。算法流程如下：

• 算法第1行：在$T_n$內部計算SPW距離（self-join），即進行距離計算的子序列均取自$T_n$，見圖5第1部分。
• 算法第2行：對于$T_a$的子序列，從$T_n$找與其最相似的子序列（cross-join），即進行距離計算的子序列分別來自$T_a$和$T_n$。由于$T_n$為正常序列，因此SPW距離較大的$T_a$的子序列有可能為異常，由分位數(shù)閾值p劃定正常與異常子序列，見圖5第1部分。
• 算法第3-4行：構建連通圖G，圖中的節(jié)點為來自$T_n$和$T_a$的所有子序列，兩個節(jié)點有連線則表明它們在self-join和cross-join中取得SPW距離，即最相似。接著按照p劃定的距離閾值將大于p的邊剪斷，這將產生孤立節(jié)點，孤立節(jié)點可以認為是候選的異常子序列$N_i$，見圖5第2部分。這里連接子圖里的序列不能代表相似的指標模式，主要有兩個原因：一是圖的構造條件比較嚴格，只考慮了最近鄰連接，不同子圖之間也可能比較相似；二是由于百分位閾值p設置得比較寬松，可能會產生誤報。
• 算法5-6行：對每個子圖里的子序列計算均值${\mu }_G$，并采用Affinity Propagation算法對均值向量做進一步聚類C。由此將所有相似的子序列盡可能地聚合在一起。
• 算法第7-15行：對進一步聚類得到的子序列簇C再次計算均值${\mu }_C$，得到的均值向量作為指標模式。如果這個簇中所有的子序列均來自前面的候選異常子序列，則判定該指標模式為異常模式$P_a$，否則為正常模式$P_n$，見圖5第3部分。

圖4：指標模式發(fā)現(xiàn)算法

圖5：指標模式發(fā)現(xiàn)算法（圖示）

在線異常檢測

異常檢測

利用離線學習到的異常模式，我們能快速進行異常檢測。輸入一個長度為m的子序列t，計算t到上一步中學習到的所有模式的距離，找到最近的模式。如果這個最近的模式是異常模式，那么t判斷為異常；否則為正常。算法如圖6所示。

圖6：在線異常檢測

指標模式自適應學習

由于云服務經常需要更新或新功能上線，指標模式也隨之發(fā)生變化。本論文提出在線更新離線過程中學習到的指標模式，如圖7所示。算法的核心思想為，如果一個新的子序列t距離現(xiàn)有的模式（由相似子序列組成的簇計算均值得到）較近，則t將被吸收進現(xiàn)有的簇中并更新該簇，否則t將作為新的模式自組成一個新的簇。記$S_c$為聚類簇的大小（即該簇包含的子序列數(shù)量），$R_c$為聚類簇的半徑（簇中心到所包含的子序列的最大距離），${\mu }_c$為聚類簇中心（即簇所包含子序列的均值）。算法的具體細節(jié)如下：

• 算法第1-2行：給定一個新的子序列t，計算則t和所有聚類簇中心的距離d，找到距離最小的簇。
• 算法第3-10行：如果d小于目前所有聚類簇的半徑，則將t加入到距離最近的簇并更新相關的變量$S_c$，$R_c$以及${\mu }_c$。
• 算法第18-21行：如果d大于目前所有聚類簇的半徑，則以t為中心新建一個簇。并認為該簇構成的指標模式為異常模式。
• 算法第11-13行：新出現(xiàn)的模式總被認為是異常，此設定將產生大量誤報，因此需要識別新的正常模式。隨著時間的累計，可以對新形成的（異常的）簇設置閾值，如果一個異常簇的樣本數(shù)超過閾值，則表明該模式是一種常見現(xiàn)象，因此需要將其調整為正常模式。此閾值設置為最大的異常簇的子序列數(shù)。

圖7：指標模式在線更新算法

實驗結果

實驗部分對算法的離線異常檢測，在線異常檢測以及指標模式的在線更新能力均進行了檢驗。使用了三個數(shù)據集：Yahoo公開的指標數(shù)據集，2018年AIOps算法比賽數(shù)據集以及華為云的實際數(shù)據集。對比了一些主流的單指標異常檢測方法LSTM, Donut, LSTM-VAE, LODA, iForest, DAGMM, SR-CNN。實驗結果如圖8-10所示，均表明了ADSketch較現(xiàn)有算法的優(yōu)越性。

圖8：離線異常檢測實驗結果

圖9：在線異常檢測實驗結果

圖10：指標模式在線更新異常檢測實驗結果