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

大型分布式信息系統(tǒng)故障檢測(cè)研究

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

通過引入流強(qiáng)度并搜索全部流強(qiáng)度量測(cè)之間的不變關(guān)系,將大型分布式信息系統(tǒng)建模成一個(gè)不變網(wǎng)絡(luò),其中節(jié)點(diǎn)代表流強(qiáng)度量測(cè),邊代表不變關(guān)系.當(dāng)系統(tǒng)發(fā)生故障時(shí),會(huì)導(dǎo)致不變網(wǎng)絡(luò)中與故障點(diǎn)相關(guān)的邊發(fā)生中斷,且由于故障會(huì)在監(jiān)測(cè)數(shù)據(jù)中進(jìn)行傳播,從而導(dǎo)致多條邊發(fā)生中斷以及多個(gè)節(jié)點(diǎn)出現(xiàn)異常,加大了系統(tǒng)故障檢測(cè)的難度.為此,設(shè)計(jì)了gRank＋算法,根據(jù)節(jié)點(diǎn)測(cè)量的異常水平對(duì)不變網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行排序,從而實(shí)現(xiàn)系統(tǒng)故障的快速檢測(cè).最后使用3組綜合數(shù)據(jù)集通過準(zhǔn)確率、召回率和增益值3個(gè)指標(biāo)來驗(yàn)證g Rank＋算法的有效性和優(yōu)越性.

大型分布式信息系統(tǒng);不變網(wǎng)絡(luò);故障檢測(cè);g Rank＋算法

大型分布式信息系統(tǒng)的故障檢測(cè)是一項(xiàng)艱巨而有價(jià)值的任務(wù),已經(jīng)引起了廣泛關(guān)注.文獻(xiàn)[1]基于系統(tǒng)故障與癥狀之間預(yù)知的依賴關(guān)系,使用事件關(guān)聯(lián)法進(jìn)行故障檢測(cè).然而,在實(shí)際系統(tǒng)中很難精確地獲得這種故障與癥狀之間的依賴關(guān)系.文獻(xiàn)[2-3]分別使用貝葉斯網(wǎng)絡(luò)和神經(jīng)網(wǎng)絡(luò)從標(biāo)記樣本數(shù)據(jù)中學(xué)習(xí)故障癥狀,顯著改善了故障診斷效果.但對(duì)于大型分布式信息系統(tǒng),想要預(yù)先得到這種故障知識(shí)是非常困難的.

事實(shí)上,從分布式系統(tǒng)組件中收集到的大量監(jiān)測(cè)數(shù)據(jù)(如日志文件、系統(tǒng)審計(jì)事件、網(wǎng)絡(luò)流量統(tǒng)計(jì)等)可用于故障檢測(cè).文獻(xiàn)[4-6]提出了用系統(tǒng)不變量分析技術(shù)(System Invariant Analysis Technique,SIAT)來模擬系統(tǒng)動(dòng)力學(xué)及檢測(cè)系統(tǒng)故障.文獻(xiàn)[4]引入“流強(qiáng)度”概念來測(cè)量?jī)?nèi)部監(jiān)測(cè)數(shù)據(jù)對(duì)用戶請(qǐng)求數(shù)量的反應(yīng)強(qiáng)度,且首次提出“不變量”這樣一個(gè)新概念,并將其廣泛應(yīng)用于大規(guī)模的系統(tǒng)管理中.在分布式信息系統(tǒng)中,文獻(xiàn)[4,7]用帶有外源輸入的自回歸模型(AutoRegressive model with eXogenous inputs,ARX)來模擬各個(gè)測(cè)量組件測(cè)量到的流強(qiáng)度量測(cè)之間的關(guān)系.

考慮到一個(gè)信息系統(tǒng)所有流強(qiáng)度量測(cè),它可能生成一個(gè)不變網(wǎng)絡(luò),如圖1所示.由圖1可知,虛線鏈接表示正常,實(shí)線鏈接表示異常.其中,每個(gè)節(jié)點(diǎn)代表一個(gè)流強(qiáng)度量測(cè),而兩個(gè)節(jié)點(diǎn)之間的邊代表這兩個(gè)量測(cè)之間的一個(gè)不變量(不變關(guān)系).

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

1 問題描述

1.1 流強(qiáng)度與不變量

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

1.2 不變量的建模和提取

文獻(xiàn)[4,7]中用帶有外源輸入的自回歸模型來獲知流強(qiáng)度量測(cè)間的關(guān)系.根據(jù)文獻(xiàn)[7]中的符號(hào),在時(shí)間t,用x(t)和y(t)分別表示一個(gè)組件輸入端和輸出端測(cè)得的流強(qiáng)度.ARX模型用下面的式子來描述兩個(gè)流強(qiáng)度量測(cè)間的關(guān)系:

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

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

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

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

1.3 不變網(wǎng)絡(luò)

考慮一個(gè)信息系統(tǒng)所有量測(cè)(流強(qiáng)度量測(cè)),不變量搜索在每個(gè)量測(cè)都有觀測(cè)值的成對(duì)量測(cè)之間進(jìn)行.然后,可以為這個(gè)信息系統(tǒng)獲得一組不變量.假設(shè)在兩個(gè)量測(cè)之間將每個(gè)量測(cè)描繪成節(jié)點(diǎn)、每個(gè)不變量描繪成鏈接,就能夠生成如圖1所示的被稱為不變網(wǎng)絡(luò)的圖形.

1.4 不變網(wǎng)絡(luò)的在線跟蹤

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

2 故障檢測(cè)

2.1 兩種測(cè)量值

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

iScoreVi＝A/B,其中,A表示節(jié)點(diǎn)Vi所有斷開鏈接的數(shù)目;B表示節(jié)點(diǎn)Vi所有鏈接的數(shù)目.x ScoreVi其中,C表示節(jié)點(diǎn)V i與BINNs相連的所有斷開鏈接的數(shù)目;D表示節(jié)點(diǎn)V i與BINNs相連的所有鏈接的數(shù)目.

需要注意的是,如果一個(gè)鏈接是連接到BINNs的多個(gè)節(jié)點(diǎn),計(jì)算x Score時(shí)只計(jì)算該鏈接一次.將iScore和x Score合并在一起得到ix Score,即ix Score＝iScore＋x Score.這個(gè)ix Score用來測(cè)量不變網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的異常程度.從上面的定義可知ix Score是結(jié)合一個(gè)節(jié)點(diǎn)本身及其鄰近節(jié)點(diǎn)的狀態(tài)來推斷節(jié)點(diǎn)的異常程度.由于節(jié)點(diǎn)本身和它的鄰近節(jié)點(diǎn)是相互影響的,所以不能單獨(dú)地推斷某個(gè)節(jié)點(diǎn)的異常程度.

2.2 gRank算法

在此基礎(chǔ)上介紹g Rank算法,它有一個(gè)迭代過程,計(jì)算一個(gè)分?jǐn)?shù)量化每個(gè)節(jié)點(diǎn)的異常程度.將權(quán)重iScore表示為wiScore.根據(jù)iScore的定義,可以為每個(gè)節(jié)點(diǎn)計(jì)算出iScore.然后,如果一個(gè)節(jié)點(diǎn)的BINNs所有iScore都相對(duì)較低,就假設(shè)這個(gè)節(jié)點(diǎn)的iScore是高度可靠的.基于此,wiScore的定義如下:

式中,Vk表示節(jié)點(diǎn)Vi的BINNs中的一個(gè)單獨(dú)節(jié)點(diǎn).

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

2.3 噪聲的影響

在上述迭代過程中,實(shí)際上由斷開鏈接連接的兩個(gè)節(jié)點(diǎn)的異常分?jǐn)?shù),在某一輪迭代結(jié)束時(shí)可能會(huì)縮小到相當(dāng)小.這是因?yàn)樵谶@些斷開鏈接中存在噪聲,意味著某些斷開鏈接是假的.為此,需要引入一個(gè)機(jī)制中斷上述迭代.具體來說,在每一輪迭代時(shí),通過檢查由斷開鏈接連接的兩個(gè)節(jié)點(diǎn)的異常分?jǐn)?shù)是否小于閾值τ來識(shí)別并過濾掉噪聲斷開鏈接.然后,當(dāng)下一輪更新每個(gè)節(jié)點(diǎn)的wiScore時(shí),將濾出的鏈接作為非斷開鏈接.

2.4 gRank＋算法

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

在此,介紹基于ix Score的rScore,可以被直接應(yīng)用到wiScore.先得到節(jié)點(diǎn)Vi和Vj的ix Scorei和 ix Scorej,接下來,可以得到如下兩種比率:

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

3 算例分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)是在一系列時(shí)間序列數(shù)據(jù)的基礎(chǔ)上完成的,主要是3組不同大小的時(shí)間序列數(shù)據(jù).第一,隨機(jī)生成500個(gè)時(shí)間序列,每一個(gè)都包含1 050個(gè)點(diǎn).對(duì)這組綜合數(shù)據(jù)使用所有時(shí)間序列的前1 000個(gè)生成不變網(wǎng)絡(luò).由于有多個(gè)相關(guān)聯(lián)的不變網(wǎng)絡(luò)生成,選擇具有最大鏈接的不變網(wǎng)絡(luò)進(jìn)行量測(cè)異常排序,其中包含129個(gè)節(jié)點(diǎn)和1 584條鏈接.然后,用剩下的50個(gè)相關(guān)聯(lián)的觀察值來跟蹤這個(gè)不變網(wǎng)絡(luò).在某一時(shí)刻對(duì)這50個(gè)觀察值進(jìn)行量測(cè)異常排序.第二,用相同的方式分別生成包含2 000個(gè)時(shí)間序列和5 000個(gè)時(shí)間序列的兩組綜合數(shù)據(jù)集.每個(gè)時(shí)間序列包含1 050個(gè)點(diǎn),前1 000個(gè)點(diǎn)被用來搜索不變量.對(duì)于擁有2 000個(gè)時(shí)間序列的數(shù)據(jù)集,選擇的最大不變網(wǎng)絡(luò),其中包含439個(gè)節(jié)點(diǎn)和10 234條鏈接.對(duì)于擁有5 000個(gè)時(shí)間序列的數(shù)據(jù)集,選擇的最大不變網(wǎng)絡(luò),其中包含319個(gè)節(jié)點(diǎn)和2 842條鏈接.

由3組綜合數(shù)據(jù)集所生成的3個(gè)不變網(wǎng)絡(luò)的一些統(tǒng)計(jì)量如表1所示.需要注意的是,對(duì)于不變量搜索,階[n,m,k]的范圍為0≤n,m,k≤2,且最佳閾值τ為0.7.然而,為了詳細(xì)地顯示在稀疏網(wǎng)絡(luò)中排序算法的效果,在5 000個(gè)時(shí)間序列數(shù)據(jù)中進(jìn)行不變量搜索時(shí),指定τ＝0.85,因?yàn)楦叩摩油ǔ?huì)導(dǎo)致不變網(wǎng)絡(luò)的鏈接變少.另外,不變量搜索的時(shí)間復(fù)雜度會(huì)隨著時(shí)間序列的數(shù)目增加而增加.3組綜合數(shù)據(jù)集的不變量搜索的計(jì)算時(shí)間如表2所示.

表1 實(shí)驗(yàn)數(shù)據(jù)集的一些統(tǒng)計(jì)量

表2 不變量的搜索時(shí)間

3.2 排序方法

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

表3 4種排序方法的符號(hào)

3.3 基準(zhǔn)生成

從現(xiàn)實(shí)世界的分布式信息系統(tǒng)中很難獲得異常排序的基準(zhǔn)[6].系統(tǒng)專家也許能夠手動(dòng)診斷系統(tǒng)故障,找出根本原因并解決問題,但要求他們根據(jù)異常水平給所有量測(cè)排序幾乎是不可能的[5,9],因?yàn)橐粋€(gè)系統(tǒng)的各個(gè)組成部分與各量測(cè)之間有顯著的相關(guān)性.

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

3.4 驗(yàn)證指標(biāo)

考慮到異常排序的基準(zhǔn),在這里使用準(zhǔn)確率、召回率和增益值(normalize Discounted Cumulative Gain,nDCG)[11]來驗(yàn)證異常排序算法的有效性和優(yōu)越性.這3種驗(yàn)證指標(biāo)被廣泛應(yīng)用于與排序相關(guān)的工作中[12-13].準(zhǔn)確率和召回率通常告訴我們?cè)谂判蛄斜碇信琶壳暗牧繙y(cè)的性質(zhì),但不能得到排名靠前的量測(cè)的順序.在這個(gè)系統(tǒng)量測(cè)排序情況下,高準(zhǔn)確率和召回率只表明在排序列表中靠前的量測(cè)大多數(shù)是不正常的.n DCGp是對(duì)排序列表中超過p位置的量測(cè)進(jìn)行評(píng)估,該量測(cè)排序列表是以假設(shè)高度異常的量測(cè)應(yīng)該出現(xiàn)在排序列表的前面和高度異常的量測(cè)比輕微異常的量測(cè)更重要為基礎(chǔ)的.它的定義式為n DCGp＝.在這里其中,reli代表在排序列表中位于i處量測(cè)的異常程度(基準(zhǔn)),并且,IDCGp是在理想排序列表中p位置的理想DCG,理想排序列表是通過異常程度(基準(zhǔn))來排序所有量測(cè)(不變網(wǎng)絡(luò)的所有節(jié)點(diǎn))得到的.通常情況下,如果考察排序列表前K個(gè)量測(cè)的性質(zhì),就會(huì)有p≤K.

3.5 基于綜合數(shù)據(jù)的排序性能比較

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

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

對(duì)于綜合數(shù)據(jù)集Ⅱ,在439個(gè)節(jié)點(diǎn)中隨機(jī)選取19個(gè)節(jié)點(diǎn)在第1 001個(gè)觀測(cè)值注入異常,得到基準(zhǔn)排序,并執(zhí)行10次得到平均結(jié)果.然后,在不同算法、驗(yàn)證指標(biāo)和K值之間做了類似比較,如圖7、圖8、圖9所示.由圖7～圖9可以看出,不同算法的比較結(jié)果在不同驗(yàn)證指標(biāo)上有著相似的趨勢(shì).

對(duì)于綜合數(shù)據(jù)集Ⅲ,在319個(gè)節(jié)點(diǎn)中隨機(jī)選取32個(gè)節(jié)點(diǎn)在第1 001個(gè)觀測(cè)值注入異常,并執(zhí)行10次得到平均結(jié)果.不同算法之間的比較如圖10、圖11、圖12所示.從圖10～圖12中可以看出,在稀疏的不變網(wǎng)絡(luò)中就準(zhǔn)確率和召回率而言,gxrn算法仍優(yōu)于grn算法.文中所用的3種算法都比基準(zhǔn)算法有更好的結(jié)果.

4 結(jié)論與展望

利用從分布式信息系統(tǒng)中的不同監(jiān)測(cè)點(diǎn)收集到的監(jiān)測(cè)數(shù)據(jù),對(duì)系統(tǒng)故障檢測(cè)與診斷進(jìn)行研究.在綜合數(shù)據(jù)集的基礎(chǔ)上,用準(zhǔn)確率、召回率和增益值這3個(gè)指標(biāo)來評(píng)估排序算法的有效性.實(shí)際上,對(duì)于一個(gè)特定的分布式信息系統(tǒng),某些量測(cè)有獨(dú)特的語(yǔ)義標(biāo)簽.例如,一些語(yǔ)義標(biāo)簽“DB15 DISK HDAW Block”和“WEB26PAGEOUTRATE”.從這些標(biāo)簽中,可以很容易地推斷出某些量測(cè)的信息以及與之相關(guān)聯(lián)的量測(cè).在真實(shí)數(shù)據(jù)中,使用算法給異常量測(cè)排序可以利用這些先驗(yàn)知識(shí)排除一些偽異常,系統(tǒng)專家可以將最終的排序結(jié)果與語(yǔ)義標(biāo)簽綜合起來,更好更準(zhǔn)確地進(jìn)行系統(tǒng)故障檢測(cè).

[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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61203034);安徽省自然科學(xué)基金資助項(xiàng)目(1308085QF120)

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

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