清華AIOps新作：蒙特卡洛樹搜索定位多維指標異常

最新 08-15

作者｜孫永謙

編輯｜Vicky

導讀

在互聯網運維中，有一類多維度KPI指標體系，其指標數目繁多、之間具有複雜的相互影響關係，通常只對KPI總量進行實時的異常檢測演算法，檢測出異常後，再對體系查找定位導致該總量異常的細粒度指標集合。本篇文章介紹一種對這種多維度指標體系中準確、高效地進行異常定位的方法HotSpot，採用了蒙特卡洛樹搜索（MCTS）方法。該工作是清華大學NetMan實驗室和百度公司IOP部門共同完成，文章《HotSpot: Anomaly Localization for Additive KPIs with Multi-Dimensional Attributes》於2018年3月發表在IEEE Access期刊上。

簡介

對於網路運維中多數的關鍵性能指標（KPI，CPU利用率、某頁面點擊量等），對其應用實時的異常檢測演算法，即可快速發現異常狀況、進而及時止損，然而，有一類可加和的多維度KPI體系（如網頁訪問量PV、收入指標、錯誤計數等），其指標元素數目繁多、之間具有複雜的相互影響關係。如圖 1表示一個4維的PV指標體系（由一系列3維的結構來表示），維度是Province,ISP,DC和Channel（簡記為P,I,D,C），其中每個cell表示一個最細粒度的指標元素對應的PV值，例如v(Beijing, ChinaNet, DC1,Channel1)，相應的也有較粗粒度的元素，例如v(Beijing, ChinaNet, DC1,*)、v(Beijing, ChinaNet, *,*)、v(Beijing, *, DC1,*)、v(*, *, *,Channel1)、v(*,*,*,*)，分別對應一排cell、一個平面的cell、一個立方體的cell、總PV。這種數據結構稱為data cube，其中的子cube稱為cuboid （用Bi表示），圖 1 中的4維data cube，其中包含若干cuboid，結構可如圖 2所示。

圖 1 多維度指標體系示例

圖 2 一個4維data cube中的cuboid結構（維度:P,I,D,C）

對這類多維度指標體系的運維，通常只對KPI總量應用實時的異常檢測演算法，檢測出異常後，再對體系進行查找，定位出根因元素集合，這個查找、定位出根因集合的過程即為異常定位。需要說明的是，本文異常定位的集合，指的是在同一個cuboid中的若干元素組成的集合。

問題分析

本文問題需求是儘可能準確的找到根因集合，即使集合中的元素指標值比較小或者佔比比較小，也不宜採用暴力剪枝的方法將這些元素剪枝掉（上一篇文章中的iDice演算法就是這樣做的，但其場景有所差異）。例如某一元素(*,location1,*,*)的PV值雖然很小（表示來自location1的訪問量較少），對於我們的運維也是非常重要的，若它是根因的一部分，需要儘可能的找出它並儘快恢復。

此外，你可能會有疑問，為什麼不對體系中的每一個指標做實時的異常檢測呢？主要是因為元素間存在複雜的互相影響關係，常常是根因只有兩三個元素，但會發現大量的指標都發生了較大的變化，例如表1中的簡單案例中，(Beijing,*）是根因，但你會發現(Beijng,Mobile)、(Beijing,Unicom)、(*,Mobile)、(*,Unicom)的值都會發生變化。因此，我們認為，在這種可加和的多維度指標體系中，通過對每一個元素進行異常檢測來判斷根因的方法不合理。

表 1 簡單二維指標體系案例（表格中的數字，前者為預測值，後者為真實值）

我們提出的思路為：多維度指標體系中的異常定位問題，實際上是尋找導致總量突變的根因元素集合。因此可以歸結為一個搜索問題，即如果任意給定一個元素集合都可以判定其有多大可能是根因，則只需遍歷搜索可能的集合併計算是根因的可能性，最後挑選出可能性最大集合即可。

挑戰

基於以上思路，本文的主要挑戰有以下兩個方面，其中最主要是挑戰二，搜索空間太大。

挑戰一：準確衡量一個元素或集合是根因的可能性非常困難。不同元素的值是相互依賴和影響的，首先父元素和子元素間具有加和關係，此外如表 1 所示，元素間還有更為複雜的關係，這導致變化量、變化率等常用指標不足以準確描述元素或集合是根因的可能性，例如表 1 中，兩個集合 S1={(Beijing,*)}、S2={(*,Mobile), (*,Unicom)}變化量都是18，都佔總量的18%，無法區分誰的可能性更大。因此，需要提出更為本質的評價一個元素/集合是根因的可能性程度。

本文中定義了Potential Score (ps) 來解決這個問題。提前交代一下，ps不具可加和性，也就是如果S』=，那麼ps(S』)≠ps(e1)+ps(e2)。

挑戰二：要遍歷搜索所有可能的集合是不可能做到的。由於可加和的KPI擁有多維度的屬性，隨著維度的增加或粒度的細化，元素數目呈指數級爆炸式增長。更糟糕的是，我們想要搜索的不是單個元素（ps不具可加和性），而是元素集合，理論上一個cuboid中如果有n個元素，那麼對應所有集合的數目是2?n-1（除去空集），也就是若n=100，則集合數目約是2?100個，要遍歷這個天文數字數目的集合，並分別求ps值，顯然在有限時間內是不可能實現的。

為了克服這個困難，本文將採用兩個策略：一是應用MCTS演算法，對於每個cuboid中的元素進行遍歷；二是採用分層剪枝的策略，逐層搜索、利用前一層的結果對該層先做剪枝。

HotSpot演算法設計

如前所述，本文將多維度指標體系中的異常定位問題轉化為搜索問題，其中主要挑戰是搜索空間太大。而一些圍棋程序，如AlphaGo，要解決的主要問題之一也是搜索空間太大，他們常用的是MCTS的方法。受此啟發，本文也採用了MCTS搜索的方法。基本原理簡述如下，圍棋程序中需要決策下一步的落子位置，對於一個待測位置要判斷其落子勝率，可以通過模擬儘可能多的結果來評估，最後選擇一個勝率最大的位置落子；類似地，本文中需要決策根因集合中是否添加下一個元素，與勝率相對應，本文也提出了判斷一個集合是根因可能性的分數Potential Score （也是對挑戰一的解決方案）。

HotSpot概覽見圖 2，它將問題轉化為在一個巨大空間的搜索問題後，應用 MCTS 作為基礎搜索演算法，並且提出了一個根因可能性評分指標，作為每個集合的度量和 MCTS 中的價值函數; 此外，HotSpot還採用分層剪枝的方法以進一步降低搜索複雜度（逐層搜索，利用前一層的結果對該層先做剪枝）。

圖 3 HotSpot 概覽

下面介紹其中HotSpot中的主要環節。

1.Ripple effect:

本文從實際案例中總結出一個元素之間互相影響的規則，Ripple effect。該規則旨在說明，任何一個元素值變化時，最細粒度層次中它的後代節點值將按照一定比例（通常是相同比例）進行變化；因體系的可加和性，有了最細粒度元素值，即可推導出其他所有元素值。例如表 1中箭頭所示，(Beijing,*)是根因，其最細粒度子節點 (Beijing,Mobile)和(Beijing,Unicom)會等比例降低（這裡是理想情況，實際中存在雜訊等影響），進而可推導出其他相關的值。

令x表示非最細粒度元素，x』i表示其最細粒度層中x的後代元素。當x的值改變了h(x)時:

其中v和f分別代表真實值和預測值。

2.Potential score:

由Ripple effect知，任何一個元素值變化時最細粒度元素會等比例變化，而最細粒度變化元素又可將這些變化「傳導給」其他所有元素。因此，可用最細粒度所有元素來表徵任何一個元素或集合的變化。那麼，最細粒度所有元素的真實值、預測值構成的向量分別記為v(→),f(→)。。任給定一集合S，假設其為根因則可推導出其對應最細粒度元素值，對應的向量記為a(→，d(x,y)表示距離（本文採用歐氏距離），則Potential score如下：

3.MCTS演算法：

MCTS解決一個Cuboid中的空間過大、搜索太慢的問題。它是一種啟發式演算法，理論上給的時間越長結果越準確，實際中常通過設定閾值（準確性閾值、時間閾值等）的方法，當找到滿足閾值的結果即可停止搜索。其中一次迭代搜索過程包括以下四步：

4.分層剪枝：

隨著cuboid中元素數目的增加，在相同時間內其準確性會下降。因此，為了進一步降低搜索的複雜度，本文在層間採用分層剪枝的策略。基本思想是，HotSpot逐層搜索cuboid，即從第1層到第L層；對於前一層中ps過小的元素，將其在本層中的子元素剪枝去掉。

實驗驗證