大型分布式信息系統故障檢測研究

尹 娟,葛 愿,王 炎,徐 旺,陳 鑫(安徽工程大學電氣工程學院,安徽蕪湖 241000)

大型分布式信息系統故障檢測研究

尹 娟,葛 愿?,王 炎,徐 旺,陳 鑫
(安徽工程大學電氣工程學院,安徽蕪湖 241000)

通過引入流強度并搜索全部流強度量測之間的不變關系,將大型分布式信息系統建模成一個不變網絡,其中節點代表流強度量測,邊代表不變關系.當系統發生故障時,會導致不變網絡中與故障點相關的邊發生中斷,且由于故障會在監測數據中進行傳播,從而導致多條邊發生中斷以及多個節點出現異常,加大了系統故障檢測的難度.為此,設計了gRank＋算法,根據節點測量的異常水平對不變網絡中的節點進行排序,從而實現系統故障的快速檢測.最后使用3組綜合數據集通過準確率、召回率和增益值3個指標來驗證g Rank＋算法的有效性和優越性.

大型分布式信息系統;不變網絡;故障檢測;g Rank＋算法

大型分布式信息系統的故障檢測是一項艱巨而有價值的任務,已經引起了廣泛關注.文獻[1]基于系統故障與癥狀之間預知的依賴關系,使用事件關聯法進行故障檢測.然而,在實際系統中很難精確地獲得這種故障與癥狀之間的依賴關系.文獻[2-3]分別使用貝葉斯網絡和神經網絡從標記樣本數據中學習故障癥狀,顯著改善了故障診斷效果.但對于大型分布式信息系統,想要預先得到這種故障知識是非常困難的.

事實上,從分布式系統組件中收集到的大量監測數據(如日志文件、系統審計事件、網絡流量統計等)可用于故障檢測.文獻[4-6]提出了用系統不變量分析技術(System Invariant Analysis Technique,SIAT)來模擬系統動力學及檢測系統故障.文獻[4]引入“流強度”概念來測量內部監測數據對用戶請求數量的反應強度,且首次提出“不變量”這樣一個新概念,并將其廣泛應用于大規模的系統管理中.在分布式信息系統中,文獻[4,7]用帶有外源輸入的自回歸模型(AutoRegressive model with eXogenous inputs,ARX)來模擬各個測量組件測量到的流強度量測之間的關系.

考慮到一個信息系統所有流強度量測,它可能生成一個不變網絡,如圖1所示.由圖1可知,虛線鏈接表示正常,實線鏈接表示異常.其中,每個節點代表一個流強度量測,而兩個節點之間的邊代表這兩個量測之間的一個不變量(不變關系).

文獻[8]利用搜索到的不變量生成不變網絡,在這個網絡中,一個節點代表一個監控數據,一個鏈接代表兩個監測數據之間的不變關系.由于故障一般會在監測數據中傳播,所以當系統發生故障時,會破壞不變網絡中的一些鏈接.文獻[8]提出m Rank算法和gRank算法來給異常量測進行排序,排序結果有助于系統專家檢測與定位故障.m Rank算法雖然考慮了節點本身以及鄰近節點的影響,但每個節點的異常水平是固定的,不具有可變性.而gRank算法是在假設一個節點的中斷不變量鄰近節點所有iScore都相對較低,即在假設這個節點的iScore是高度可靠的情況下進行更新迭代.由于節點本身和它的鄰近節點相互影響,即使一個節點的中斷不變量鄰近節點所有iScore很低,也會對這個節點產生影響.而本文設計的gRank＋算法將一個節點的中斷不變量鄰近節點對其斷開鏈接的影響考慮進節點的異常水平中,降低了算法的保守性.綜上所述,國內外學者從多個角度對大型分布式信息系統故障檢測問題進行了廣泛研究,為本文研究的開展奠定了堅實的基礎.首先針對從分布式系統組件中收集到的大量監測數據建立ARX模型,然后進行不變量搜索生成相應的不變網絡,最后利用改進的g Rank＋算法對節點異常水平進行排序,并基于準確率、召回率和增益值這3個指標來驗證算法的有效性和優越性.

1 問題描述

1.1 流強度與不變量

許多大型分布式信息系統(如Google、Amazon)每天收到數以百萬計的事務請求.在系統運行期間,大量監測數據在各種系統組件中被收集,用來記錄它們的運行狀態.通常情況下,很多內部監測數據直接或間接反應出用戶的請求量,因此,可以使用流強度來衡量內部監控數據響應用戶請求量的強度.流強度可以用從分布式系統的不同點收集到的監測數據進行計算.如果這些流強度隨著用戶負載無論如何變化,流強度的這種關系始終固定不變,就將這種不變關系認為是一個不變量.

1.2 不變量的建模和提取

文獻[4,7]中用帶有外源輸入的自回歸模型來獲知流強度量測間的關系.根據文獻[7]中的符號,在時間t,用x(t)和y(t)分別表示一個組件輸入端和輸出端測得的流強度.ARX模型用下面的式子來描述兩個流強度量測間的關系:

式中,[n,m,k]是模型的階,它決定前面有多少步驟影響當前輸出;ai和bj是系數參數,用來反映上一步是如何強烈地影響當前輸出的.表示為:

然后,式(1)可以被寫成:

假設在時間間隔1≤t≤N中有觀察到的輸入和輸出(即流強度),用下式表示這些觀察值:ON＝{x(1), y(1),…,x(N),y(N)}.

利用最小二乘法(Least Squares Method,LSM)可以找到一個^θ,使估計誤差EN(θ,ON)最小化.然后,歸一化的適配值F(θ)[9]用于評估已學到的模型擬合實際觀測值的程度.

1.3 不變網絡

考慮一個信息系統所有量測(流強度量測),不變量搜索在每個量測都有觀測值的成對量測之間進行.然后,可以為這個信息系統獲得一組不變量.假設在兩個量測之間將每個量測描繪成節點、每個不變量描繪成鏈接,就能夠生成如圖1所示的被稱為不變網絡的圖形.

1.4 不變網絡的在線跟蹤

在信息系統的不變網絡中,基于模型的故障檢測與隔離(Fault Detection and Isolation,FDI)[6,9-10]方法用來實時跟蹤不變量以實現故障檢測.具體地講,在未來的某一個時刻t,比較每個不變量的真實觀察值y(t)和其模擬值得到絕對差值在無故障正常情況下,應該有殘差Rt≤εM,其中εM為模型誤差的閾值.FDI不變量追蹤示例如圖2所示.由圖2可知,如果R＞εM,則x和y之間的鏈接斷開.需要注意的是εM對每個不變量來說是不同的.事實上,每一個不變量的εM是由與每個鏈接相關的殘差分布自動決定的.具體來說,閾值的選擇由下式決定:εM＝1.1·arg^R{prob(|R(t)|＜^R)＝0.995}.

2 故障檢測

2.1 兩種測量值

如果一個節點的大部分鏈接斷開,可能直覺地認為這個節點是異常的.然而,也有可能這些鏈接斷開是由其他節點引起的.因此,為了推斷一個節點異常的可能性,需要考慮與中斷不變量鄰近節點(Broken-Invariant-Neighboring-Nodes,BINNs)相連的鏈接.一個節點的中斷不變量鄰近節點是指與此節點用斷開鏈接相連的節點.因此,如果一個節點的大部分鏈接已斷開,而其中斷不變量鄰近節點的大多數鏈接未斷開,此節點很有可能異常.基于這一基本思想,定義了兩種測量值[8]以量化節點的異常.

iScoreVi＝A/B,其中,A表示節點Vi所有斷開鏈接的數目;B表示節點Vi所有鏈接的數目.x ScoreVi其中,C表示節點V i與BINNs相連的所有斷開鏈接的數目;D表示節點V i與BINNs相連的所有鏈接的數目.

需要注意的是,如果一個鏈接是連接到BINNs的多個節點,計算x Score時只計算該鏈接一次.將iScore和x Score合并在一起得到ix Score,即ix Score＝iScore＋x Score.這個ix Score用來測量不變網絡中每個節點的異常程度.從上面的定義可知ix Score是結合一個節點本身及其鄰近節點的狀態來推斷節點的異常程度.由于節點本身和它的鄰近節點是相互影響的,所以不能單獨地推斷某個節點的異常程度.

2.2 gRank算法

在此基礎上介紹g Rank算法,它有一個迭代過程,計算一個分數量化每個節點的異常程度.將權重iScore表示為wiScore.根據iScore的定義,可以為每個節點計算出iScore.然后,如果一個節點的BINNs所有iScore都相對較低,就假設這個節點的iScore是高度可靠的.基于此,wiScore的定義如下:

式中,Vk表示節點Vi的BINNs中的一個單獨節點.

g Rank算法的迭代過程表述如下:計算各節點的iScore,對于下面的幾輪計算根據式(7)和上一輪的結果更新wiScoreVi,直至達到最大迭代次數才停止更新.因此,在得到每個節點最初iScore后,作為第二輪可以計算出每個節點的wiScore.事實上,可以迭代地計算并更新每個節點的wiScore.對于下面的幾輪計算,當更新wiScore需要使用在上一輪中獲得的wiScore來代替iScore.需要注意的是,逐輪更新意味著當更新第r＋1輪的wiScore時只需使用第r輪的所有wiScore.

2.3 噪聲的影響

在上述迭代過程中,實際上由斷開鏈接連接的兩個節點的異常分數,在某一輪迭代結束時可能會縮小到相當小.這是因為在這些斷開鏈接中存在噪聲,意味著某些斷開鏈接是假的.為此,需要引入一個機制中斷上述迭代.具體來說,在每一輪迭代時,通過檢查由斷開鏈接連接的兩個節點的異常分數是否小于閾值τ來識別并過濾掉噪聲斷開鏈接.然后,當下一輪更新每個節點的wiScore時,將濾出的鏈接作為非斷開鏈接.

2.4 gRank＋算法

在原始g Rank算法中,是將權重iScore表示為wiScore,也就是考慮與該節點連接的所有鏈接以及斷開鏈接.而這些斷開鏈接也可能是由其他節點引起的.因此,為了推斷一個節點異常的可能性,需要考慮與中斷不變量鄰近節點有關的鏈接.基于這一觀點,將x Score考慮進g Rank算法中,形成g Rank＋算法.只量化一個節點的最鄰近節點對其本身的影響.其中,在計算與BINNs相關聯的斷開鏈接的數目時,不只是僅僅考慮有幾條斷開鏈接,而是用與BINNs相關聯的斷開鏈接的權數來更新公式x Score的分子.一個斷開鏈接與兩個節點相關聯,要確定哪個節點的異常導致了不變量的斷開.給定一個斷開鏈接和它的兩個節點,進一步引入rScore規范化iScore、x Score,并依此決定每個節點對不變量斷開貢獻值的大小.而且,最終使用rScore給不變網絡的所有節點排序.

在此,介紹基于ix Score的rScore,可以被直接應用到wiScore.先得到節點Vi和Vj的ix Scorei和 ix Scorej,接下來,可以得到如下兩種比率:

為每個斷開鏈接計算這些比率.因此,對于每個斷開鏈接的相關節點,假設一個節點Vi有K條斷開鏈接,將得到K比率riak(1≤k≤N),其中,ak是節點索引.這意味著該節點Vak是通過斷開鏈接連接到節點Vi.然后,通過結合所有與節點Vi相關聯的比率,定義了該節點Vi的

3 算例分析

3.1 實驗數據

實驗是在一系列時間序列數據的基礎上完成的,主要是3組不同大小的時間序列數據.第一,隨機生成500個時間序列,每一個都包含1 050個點.對這組綜合數據使用所有時間序列的前1 000個生成不變網絡.由于有多個相關聯的不變網絡生成,選擇具有最大鏈接的不變網絡進行量測異常排序,其中包含129個節點和1 584條鏈接.然后,用剩下的50個相關聯的觀察值來跟蹤這個不變網絡.在某一時刻對這50個觀察值進行量測異常排序.第二,用相同的方式分別生成包含2 000個時間序列和5 000個時間序列的兩組綜合數據集.每個時間序列包含1 050個點,前1 000個點被用來搜索不變量.對于擁有2 000個時間序列的數據集,選擇的最大不變網絡,其中包含439個節點和10 234條鏈接.對于擁有5 000個時間序列的數據集,選擇的最大不變網絡,其中包含319個節點和2 842條鏈接.

由3組綜合數據集所生成的3個不變網絡的一些統計量如表1所示.需要注意的是,對于不變量搜索,階[n,m,k]的范圍為0≤n,m,k≤2,且最佳閾值τ為0.7.然而,為了詳細地顯示在稀疏網絡中排序算法的效果,在5 000個時間序列數據中進行不變量搜索時,指定τ＝0.85,因為更高的τ通常會導致不變網絡的鏈接變少.另外,不變量搜索的時間復雜度會隨著時間序列的數目增加而增加.3組綜合數據集的不變量搜索的計算時間如表2所示.

表1 實驗數據集的一些統計量

表2 不變量的搜索時間

3.2 排序方法

主要排序算法如表3所示.為了便于比較,以首字母縮寫來表示這4種方法.

表3 4種排序方法的符號

3.3 基準生成

從現實世界的分布式信息系統中很難獲得異常排序的基準[6].系統專家也許能夠手動診斷系統故障,找出根本原因并解決問題,但要求他們根據異常水平給所有量測排序幾乎是不可能的[5,9],因為一個系統的各個組成部分與各量測之間有顯著的相關性.

為此,利用綜合數據集來人工生成基準,并依此提供了一個標準來評價不同的異常排序算法.時間系列的異常通常表示為幅度的異常變化.這樣,可以通過測量時間序列幅值的變化率來生成異常基準.具體來說,在某一個時刻,人為地為時間序列注入異常.基于幅度的基準圖如圖3所示.由圖3可知,一個時間系列某一個觀察值的初值為y1,手動地將觀察值由y1改為y2后,可以得到手動注入異常的程度為

3.4 驗證指標

考慮到異常排序的基準,在這里使用準確率、召回率和增益值(normalize Discounted Cumulative Gain,nDCG)[11]來驗證異常排序算法的有效性和優越性.這3種驗證指標被廣泛應用于與排序相關的工作中[12-13].準確率和召回率通常告訴我們在排序列表中排名靠前的量測的性質,但不能得到排名靠前的量測的順序.在這個系統量測排序情況下,高準確率和召回率只表明在排序列表中靠前的量測大多數是不正常的.n DCGp是對排序列表中超過p位置的量測進行評估,該量測排序列表是以假設高度異常的量測應該出現在排序列表的前面和高度異常的量測比輕微異常的量測更重要為基礎的.它的定義式為n DCGp＝.在這里其中,reli代表在排序列表中位于i處量測的異常程度(基準),并且,IDCGp是在理想排序列表中p位置的理想DCG,理想排序列表是通過異常程度(基準)來排序所有量測(不變網絡的所有節點)得到的.通常情況下,如果考察排序列表前K個量測的性質,就會有p≤K.

3.5 基于綜合數據的排序性能比較

對于綜合數據集I,所選不變網絡包含129個節點和1 584條鏈接.在所有129個節點中,隨機選擇8個節點在第1 001個觀測值注入異常.進行10次這樣的隨機選擇,得到每組的8個異常節點的基準排序.對于每組的8個異常節點,進行不變網絡的在線跟蹤.綜合數據集I在準確率、召回率和n DCG方面的比較如圖4、圖5、圖6所示.由圖4可知,排序在前K的量測的平均準確率,同時,比較了有不同K值的4種算法的平均準確率.基于gRank算法的迭代解,憑經驗設定最大迭代次數為50來停止迭代.事實上,經過50次迭代,gr、grn和gxrn都得到穩定的排序結果.從圖4中還可以看出,gr、grn、gxrn這3種算法都優于基準方法.例如,在這3種算法中前6個量測是異常的,而基準方法中只有前2個量測是異常的.同時,可以看出在性能方面gxrn算法略優于grn算法.由圖5可知,與準確率相似,所有算法在K取不同值時,就召回率方面有非常類似的比較結果.

由圖6可知,p表示在排序列表中的位置.對于大多數p值,所有提出的算法均比基準算法有更好的性能(較高的n DCG值).gxrn算法排序結果較其他算法好.

對于綜合數據集Ⅱ,在439個節點中隨機選取19個節點在第1 001個觀測值注入異常,得到基準排序,并執行10次得到平均結果.然后,在不同算法、驗證指標和K值之間做了類似比較,如圖7、圖8、圖9所示.由圖7～圖9可以看出,不同算法的比較結果在不同驗證指標上有著相似的趨勢.

對于綜合數據集Ⅲ,在319個節點中隨機選取32個節點在第1 001個觀測值注入異常,并執行10次得到平均結果.不同算法之間的比較如圖10、圖11、圖12所示.從圖10～圖12中可以看出,在稀疏的不變網絡中就準確率和召回率而言,gxrn算法仍優于grn算法.文中所用的3種算法都比基準算法有更好的結果.

4 結論與展望

利用從分布式信息系統中的不同監測點收集到的監測數據,對系統故障檢測與診斷進行研究.在綜合數據集的基礎上,用準確率、召回率和增益值這3個指標來評估排序算法的有效性.實際上,對于一個特定的分布式信息系統,某些量測有獨特的語義標簽.例如,一些語義標簽“DB15 DISK HDAW Block”和“WEB26PAGEOUTRATE”.從這些標簽中,可以很容易地推斷出某些量測的信息以及與之相關聯的量測.在真實數據中,使用算法給異常量測排序可以利用這些先驗知識排除一些偽異常,系統專家可以將最終的排序結果與語義標簽綜合起來,更好更準確地進行系統故障檢測.

[1] S A Yemini,S Kliger,E Mozes,et al.High speed and robust event correlation[J].IEEE Communications Magazine, 1996,34(5):82-90.

[2] S Hangal,M S Lam.Tracking down software bugs using automatic anomaly detection[C]//Orlando:Institure of Electrical and Electronics Engineers Computer Society.Proceedings of the 24th International Conference on Software Engineering,2002:291-301.

[3] M Jiang,M A Munawar,T Reidemeister,et al.Detection and diagnosis of recurrent faults in software systems by invariant analysis[C]//Nanjing:Institute of Electrical and Electronics Engineers Computer Society.Proceedings of the 11th IEEE high assurance systems engineering symposium,2008:323-332.

[4] G F Jiang,H F Chen,K J Yoshihira.Discovering likely invariants of distributed transaction systems for autonomic system management[C]//Dubin:Institute of Electrical and Electrunics Engineers Computer Society.Proceedings of the 3rd International Conference on Autonomic Computing,2006:199-208.

[5] G F Jiang,H F Chen,K J Yoshihira.Modeling and tracking of transaction flow dynamics for fault detection in complex systems[J].IEEE Transactions on Dependable and Secure Computing,2006,3(4):312-326.

[6] G F Jiang,H F Chen,K J Yoshihira.Efficient and scalable algorithms for inferring likely invariants in distributed systems[J].Transactions on Knowledge and Data Engineering,2007,19(11):1 508-1 523.

[7] L Ljung.System identification:theory for the user[M].New Jersey:Prentice Hall PTR,1998.

[8] Y Ge,G F Jiang,M Ding,et al.Ranking metric anomaly in invariant networks[J].ACM Transactions on Knowledge Discovery from Data,2014,8(2):311-322.

[9] J Gertler.Fault detection and diagnosis in engineering systems[M].CRC:Marcel Dekker,1998.

[10]R Isermannn,P Balle.Trends in the application of model-based fault detection and diagnosis of industrial process[J].Control Engineering Practice,1997,5(5):709-719.

[11]K Jarvelin,J Kekalainen.Cumulated gain-based evaluation of IR techniques[J].ACM Transactions on Information Systems,2002,20(4):422-446.

[12]H Valizadegan,R Jin,R Zhang,et al.Learning to rank by optimizing ndcg measure[C]//Vanwuver:Curran Associates Inc,57 Morehouse Lane,Red Hook,NY 125 T1,United Statrs.Proceedings of the 23rd Annual Conference on Neural Information Processing Systems,2009:1 883-1 891.

[13]S Wei,Y Zhao,Z Zhu,et al.Multimodal fusion for video search reranking[J].Transactions on Knowledge and Data Engineering,2010,22(8):1 191-1 199.

Study on fault detection of large-scale distributed information system

YIN Juan,GE Yuan?,WANG Yan,XU Wang,CHEN Xin
(College of Electrical Engineering,Anhui Polytechnic University,Wuhu 241000,China)

By introducing flow intensity and searching invariant relationships among all flow intensity measurements,large-scale distributed information system is modeled as an invariant network,in which a node denotes a flow intensity measurement and a link indicates an invariant relationship.When a failure happens on a node in the invariant network,it will cause the links related to the node to be broken.Moreover,the failure usually propagates among monitoring data,therefore more nodes will be abnormal and more links will be broken,which increases the difficulty of fault detection.This paper proposes an algorithm named gRank＋to rank nodes in the invariant network according to the anomaly levels of nodes, which will realize the rapid detection and location of system failure.Finally,the effectiveness and superiority of the proposed method is illustrated by using three synthetic data sets in precision rate,recall rate and gain value.

large-scale distributed information system;invariant network;fault detection;gRank＋algorithm

TP13

A

1672-2477(2015)05-0045-08

2015-06-11

國家自然科學基金資助項目(61203034);安徽省自然科學基金資助項目(1308085QF120)

尹 娟(1990-),女,安徽宣城人,碩士研究生.

葛 愿(1979-),男,江蘇徐州人,教授,博士.