ADSketch：基于模式側(cè)寫的在云服務(wù)性能異常檢測

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

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

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

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

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

本論文方法：ADSketch

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

圖1：性能異常模式案例

整體框架

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

圖2：ADSketch整體框架圖

算法細節(jié)

離線指標(biāo)模式學(xué)習(xí)

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

圖3：指標(biāo)序列不同子序列的SPW距離

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

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

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

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

在線異常檢測

異常檢測

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

圖6：在線異常檢測

指標(biāo)模式自適應(yīng)學(xué)習(xí)

由于云服務(wù)經(jīng)常需要更新或新功能上線，指標(biāo)模式也隨之發(fā)生變化。本論文提出在線更新離線過程中學(xué)習(xí)到的指標(biāo)模式，如圖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加入到距離最近的簇并更新相關(guān)的變量$S_c$，$R_c$以及${\mu }_c$。
• 算法第18-21行：如果d大于目前所有聚類簇的半徑，則以t為中心新建一個簇。并認為該簇構(gòu)成的指標(biāo)模式為異常模式。
• 算法第11-13行：新出現(xiàn)的模式總被認為是異常，此設(shè)定將產(chǎn)生大量誤報，因此需要識別新的正常模式。隨著時間的累計，可以對新形成的（異常的）簇設(shè)置閾值，如果一個異常簇的樣本數(shù)超過閾值，則表明該模式是一種常見現(xiàn)象，因此需要將其調(diào)整為正常模式。此閾值設(shè)置為最大的異常簇的子序列數(shù)。

圖7：指標(biāo)模式在線更新算法

實驗結(jié)果

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

圖8：離線異常檢測實驗結(jié)果

圖9：在線異常檢測實驗結(jié)果

圖10：指標(biāo)模式在線更新異常檢測實驗結(jié)果