付曉毓 任 睿 詹劍鋒 孫凝暉

(*計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室 北京 100190) (**中國科學(xué)院計(jì)算技術(shù)研究所 北京 100190) (***中國科學(xué)院研究生院 北京 100049)

?

一種基于日志結(jié)合分析的集群系統(tǒng)失效預(yù)測方法①

付曉毓②******任 睿***詹劍鋒***孫凝暉***

(*計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室 北京 100190) (**中國科學(xué)院計(jì)算技術(shù)研究所 北京 100190) (***中國科學(xué)院研究生院 北京 100049)

研究了大規(guī)模超級(jí)計(jì)算機(jī)群系統(tǒng)的失效預(yù)測。針對(duì)現(xiàn)有的單一分析系統(tǒng)日志的方法不僅需要復(fù)雜的分布式數(shù)據(jù)挖掘技術(shù)，而且失效預(yù)測的召回率普遍不高的問題，提出了一種通過將記載集群系統(tǒng)負(fù)載變化的作業(yè)日志同系統(tǒng)日志結(jié)合起來分析來進(jìn)行失效預(yù)測的方法。該方法的原理如下：首先，通過對(duì)原始系統(tǒng)日志和作業(yè)日志進(jìn)行預(yù)處理和過濾，分別得到細(xì)粒度的二維的事件序列和作業(yè)序列；然后從中抽取出在系統(tǒng)日志的失效事件發(fā)生前作業(yè)日志所表現(xiàn)出的三種典型失效征兆；最后，利用失效征兆進(jìn)行失效預(yù)測。在真實(shí)的IBM BlueGene/P系統(tǒng)的系統(tǒng)日志和作業(yè)日志上的實(shí)驗(yàn)結(jié)果表明，基于兩種日志結(jié)合分析的方法能以較高的準(zhǔn)確率和召回率實(shí)現(xiàn)細(xì)粒度的失效預(yù)測。

大規(guī)模集群系統(tǒng)， 系統(tǒng)日志， 作業(yè)日志， 日志分析， 失效預(yù)測

0 引 言

大規(guī)模集群系統(tǒng)是云計(jì)算和高性能計(jì)算的常用平臺(tái)。隨著越來越多傳統(tǒng)的社交和經(jīng)濟(jì)活動(dòng)被搬到互聯(lián)網(wǎng)上，數(shù)據(jù)中心的計(jì)算任務(wù)變得日益復(fù)雜，超級(jí)計(jì)算機(jī)也正朝著百億億次級(jí)(exascale)的規(guī)模發(fā)展，相應(yīng)地，大規(guī)模集群系統(tǒng)的失效(failure)則成了大規(guī)模集群系統(tǒng)的常態(tài)[1]。可靠性與功耗、并發(fā)、存儲(chǔ)等問題一起成為了實(shí)現(xiàn)超大規(guī)模集群系統(tǒng)的巨大挑戰(zhàn)。由于系統(tǒng)日志(system log)詳細(xì)記錄了集群系統(tǒng)發(fā)生狀態(tài)變化的各種事件，能夠長期地比較精確地追蹤系統(tǒng)行為，因而對(duì)系統(tǒng)日志的分析是進(jìn)行失效預(yù)測的關(guān)鍵。失效預(yù)測是一種利用系統(tǒng)的歷史狀態(tài)信息預(yù)測不久的將來系統(tǒng)是否會(huì)再次發(fā)生失效的有效的可靠性主動(dòng)管理和失效預(yù)防機(jī)制。其中，通過分析海量的歷史系統(tǒng)日志事件來預(yù)測失效事件是否會(huì)在未來某個(gè)時(shí)間點(diǎn)發(fā)生的失效預(yù)測方法成為近幾年該領(lǐng)域研究的熱點(diǎn)。然而，通過單一分析海量系統(tǒng)日志來進(jìn)行失效預(yù)測往往需要復(fù)雜的并行數(shù)據(jù)挖掘技術(shù)，且失效預(yù)測的召回率普遍不高[2-5]。本研究考慮到集群系統(tǒng)負(fù)載的變化與集群系統(tǒng)失效往往有著密切的聯(lián)系，提出了一種通過記載集群系統(tǒng)負(fù)載變化的作業(yè)日志(Job log)和系統(tǒng)日志結(jié)合起來處理、分析來實(shí)現(xiàn)失效預(yù)測的有效方法，并通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

1 相關(guān)工作

在對(duì)集群系統(tǒng)進(jìn)行主動(dòng)失效管理的機(jī)制中，失效預(yù)測已經(jīng)被國內(nèi)外許多工作證明是實(shí)現(xiàn)集群系統(tǒng)可靠性的有效手段。文獻(xiàn)[6]將失效預(yù)測的方法分為兩大類：第一類是通過采集系統(tǒng)參數(shù)并分析系統(tǒng)參數(shù)周期性變化規(guī)律的特征采集分析方法；第二類是通過追蹤系統(tǒng)事件形成RAS(reliability——可靠性，availability——可用性，and serviceability——可服務(wù)性)日志并分析日志的日志收集分析方法。文獻(xiàn)[7]證明基于日志的方法更適用于實(shí)現(xiàn)大規(guī)模集群系統(tǒng)的可靠性。

在日志分析領(lǐng)域，日志預(yù)處理的工作[1，8]能夠精簡日志內(nèi)容并去除冗余記錄以利于后續(xù)的日志分析。文獻(xiàn)[9]通過分析大量高性能計(jì)算(high performance computing，HPC)日志發(fā)現(xiàn)了一些簡單的失效事件的分布特征。后續(xù)工作試圖利用統(tǒng)計(jì)分析來揭示失效事件的行為模型以進(jìn)行失效預(yù)測。例如，文獻(xiàn)[10]研究了失效事件的統(tǒng)計(jì)特征以及失效事件和非失效事件之間的相關(guān)性來進(jìn)行失效預(yù)測。文獻(xiàn)[11]首先利用球面協(xié)方差模型和隨機(jī)模型分別量化失效事件在時(shí)間上和空間上的相關(guān)性，然后對(duì)失效事件聚類得到失效事件發(fā)生的時(shí)間間隔，據(jù)此進(jìn)行失效預(yù)測。文獻(xiàn)[12]利用信號(hào)分析的概念模擬事件在非失效和失效狀態(tài)下的行為以此進(jìn)行失效預(yù)測。

文獻(xiàn)[13]指出基于模型的方法無法適應(yīng)HPC系統(tǒng)越來越高的復(fù)雜性，于是越來越多的工作采用基于數(shù)據(jù)挖掘的日志分析方法。文獻(xiàn)[4，13]采用了將統(tǒng)計(jì)分析和關(guān)聯(lián)規(guī)則挖掘相結(jié)合的方法得到失效模式進(jìn)行失效預(yù)測。文獻(xiàn)[2]采用了基于Apriori的算法對(duì)日志進(jìn)行挖掘，并提出了基于事件關(guān)聯(lián)圖的失效預(yù)測方法。文獻(xiàn)[3]也采用基于Apriori的算法挖掘事件序列，并利用動(dòng)態(tài)窗口對(duì)日志進(jìn)行劃分。雖然以上方法在失效預(yù)測上可以得到70%以上的準(zhǔn)確率，而召回率卻不足50%。文獻(xiàn)[14]在提高召回率上采用了抽取事件因果關(guān)系的方法，但其依賴于前一階段復(fù)雜的數(shù)據(jù)挖掘所得到的事件關(guān)聯(lián)序列。由于挖掘非失效事件和失效事件的關(guān)聯(lián)需要巨大的時(shí)空開銷，現(xiàn)有方法往往采用分布式挖掘的方式處理[15，16]。因此，不論是基于數(shù)據(jù)挖掘還是基于簡單統(tǒng)計(jì)的方法，僅僅依靠從RAS日志中獲得失效的征兆進(jìn)行失效預(yù)測顯然是不足的。

Job日志記載了集群系統(tǒng)上負(fù)載運(yùn)行的詳細(xì)信息，而許多工作也已經(jīng)指出負(fù)載的類型、負(fù)載的數(shù)量和負(fù)載的變化與系統(tǒng)是否失效有很大的關(guān)聯(lián)。例如，文獻(xiàn)[17]指出變化的負(fù)載(負(fù)載的大小和類型、負(fù)載的周期、隊(duì)列和調(diào)度方法以及所需的節(jié)點(diǎn)數(shù))影響了失效事件的行為。文獻(xiàn)[9]強(qiáng)調(diào)密集的負(fù)載下往往會(huì)有較高的失效事件發(fā)生率。文獻(xiàn)[18]指出正確執(zhí)行相同負(fù)載的系統(tǒng)往往會(huì)產(chǎn)生相同的日志。文獻(xiàn)[19]指出需要在大量節(jié)點(diǎn)上運(yùn)行的Job類型更可能引起失效事件的發(fā)生。文獻(xiàn)[20]指出集群上負(fù)載的強(qiáng)度增大時(shí)更多的失效事件將會(huì)發(fā)生。所以，本文擬利用Job日志中提供的Job運(yùn)行時(shí)信息，并結(jié)合RAS日志對(duì)集群系統(tǒng)進(jìn)行失效預(yù)測。

2 基于RAS日志和Job日志的失效預(yù)測

基于RAS日志和Job日志的失效預(yù)測流程如圖1所示。首先對(duì)原始日志進(jìn)行預(yù)處理和過濾，然后從中抽取出有價(jià)值的征兆形成失效規(guī)則，最后進(jìn)行失效預(yù)測。

圖1 基于RAS日志和Job日志的失效預(yù)測流程

2.1 系統(tǒng)和日志簡介

IBM Blue Gene/P (藍(lán)色基因系列)是一個(gè)可擴(kuò)展到80個(gè)機(jī)箱的低功耗大規(guī)模并行處理系統(tǒng)，其中每一個(gè)機(jī)箱有兩個(gè)中間背板(midplane)，總共包括了512個(gè)擁有四核PowerPC450處理器的計(jì)算節(jié)點(diǎn)，一個(gè)服務(wù)節(jié)點(diǎn)和四個(gè)網(wǎng)卡。有關(guān)更多系統(tǒng)結(jié)構(gòu)的細(xì)節(jié)可以參考文獻(xiàn)[21]。

RAS日志：BlueGene/P 的核心監(jiān)視控制系統(tǒng)(core monitoring and control system，CMCS)用來實(shí)時(shí)監(jiān)視計(jì)算節(jié)點(diǎn)、I/O節(jié)點(diǎn)和節(jié)點(diǎn)間的網(wǎng)絡(luò)。CMCS以日志事件記錄的形式匯報(bào)監(jiān)控信息。事件記錄都被存儲(chǔ)在后端的DB2數(shù)據(jù)庫中。RAS日志中事件記錄的例子如圖2所示。

圖2 RAS日志事件記錄的例子

下面按照?qǐng)D2中各個(gè)域的順序依次進(jìn)行介紹。

RECID(Record ID)域是日志中事件記錄的序列號(hào)。當(dāng)有一個(gè)新的記錄被記載到日志中時(shí)，序列號(hào)加1。

MSG_ID(Message ID)域指示了該事件記錄的類型。

COMPONENT域包括APPLICATION，KERNEL，MC，MMCS，BAREMETAL，CARD，DIAGS，指示了監(jiān)測和匯報(bào)該事件記錄的軟件部件類型。具體地，APPLICATION指運(yùn)行的作業(yè)；KERNEL指操作系統(tǒng)內(nèi)核；MC(Machine Control System)指機(jī)器控制系統(tǒng)；MMCS(Midplane Monitoring and Control System)指服務(wù)節(jié)點(diǎn)上的控制系統(tǒng)；BAREMETAL指與服務(wù)相關(guān)的功能；CARD指網(wǎng)卡控制器；DIAGS(Diagnostic functions)指計(jì)算節(jié)點(diǎn)或服務(wù)節(jié)點(diǎn)的監(jiān)測功能。

SUBCOMPOENT域指示了相應(yīng)的軟件部件COMPONENT記錄和匯報(bào)事件的具體部件。

ERRCODE(Error Code)域指示了與事件類型MSG_ID對(duì)應(yīng)的具體的事件類型信息。

SEVERITY域包括INFO(Information)，WARNING，ERROR和FATAL，按照嚴(yán)重程度遞增來指示事件的等級(jí)。INFO級(jí)事件提供了系統(tǒng)軟件的一些運(yùn)行時(shí)信息。WARNING級(jí)事件通常指一些可自行恢復(fù)的小錯(cuò)誤。ERROR級(jí)事件指一些有危害但不影響應(yīng)用繼續(xù)運(yùn)行的錯(cuò)誤。FATAL級(jí)事件指會(huì)導(dǎo)致應(yīng)用或系統(tǒng)崩潰的失效事件。所以，失效預(yù)測的關(guān)鍵是能否提前預(yù)測該類型事件會(huì)在未來發(fā)生。

EVENT_TIME域指示了事件的發(fā)生時(shí)間。

LOCATION域指示該事件發(fā)生在哪個(gè)節(jié)點(diǎn)。

MESSAGE域給出了該事件的一個(gè)簡略總結(jié)。

Job日志：該日志是由作業(yè)調(diào)度器Cobalt[22]收集的。Job日志記錄的例子如圖3所示。下面按照?qǐng)D3中各個(gè)域的順序依次進(jìn)行介紹。

Submission Time域是該Job提交的時(shí)間。

Job_ID 域是該Job的序列號(hào)。

圖3 Job日志作業(yè)記錄的例子

Execution File域是該Job的執(zhí)行路徑。

Queuing Time是域該Job入等待隊(duì)列的時(shí)間。

Starting Time域是該Job開始執(zhí)行的時(shí)間。

End Time域是該Job運(yùn)行完或被中斷的時(shí)間。

Location域是該Job執(zhí)行時(shí)所在的節(jié)點(diǎn)。

User域是該Job的用戶名。

Project域是該Job的工程名。

2.2 RAS日志預(yù)處理和過濾

由于RAS日志的每條事件記錄由RECID等9個(gè)域組成，所以有如下定義：

Event：由9元組(RECID，MSG_ID，COMPONENT，SUBCOMPONENT，ERRCODE，SEVERITY，EVENT_TIME，LOCATION，MESSAGE)表示。RAS日志可以看作一個(gè)包含n個(gè)Events的序列，其中n∈N*。

Event ID：對(duì)于一個(gè)Event，如果其對(duì)應(yīng)9元組中的兩個(gè)域(MSG_ID，SEVERITY)與已產(chǎn)生的Events的都不同，則賦予該Event一個(gè)新的Event ID。Event ID表示了該Event的類型。

Log ID：對(duì)于一個(gè)Event，如果其對(duì)應(yīng)9元組中的3個(gè)域(MSG_ID，SEVERITY，Location)與已產(chǎn)生的Events的都不同，則賦予該Event一個(gè)新的Log ID。RAS日志可以看作一個(gè)包含m個(gè)Log ID的序列，其中m, n∈N*, m

通過上述定義，在日志預(yù)處理階段可以首先將原始RAS日志解析成一個(gè)Log ID序列，其中每一個(gè)Log ID代表了一個(gè)具有細(xì)粒度9元組信息的Event。原始RAS日志包含龐大的日志事件，而其中有些事件在短時(shí)間內(nèi)被重復(fù)記錄了很多次，導(dǎo)致產(chǎn)生了大量冗余。這里采用一個(gè)簡單的統(tǒng)計(jì)算法來過濾掉重復(fù)的日志事件。對(duì)于一個(gè)日志事件，統(tǒng)計(jì)在該事件發(fā)生前與該事件Log ID相同的事件與該事件的時(shí)間間隔。若該時(shí)間間隔小于預(yù)設(shè)的閾值σ_filter，則該事件被認(rèn)為是重復(fù)事件并從Log ID序列中將其刪除。

RAS日志過濾后，利用一個(gè)滑動(dòng)的時(shí)間窗口(比如一個(gè)小時(shí))來劃分Log ID序列。如圖4所示，將發(fā)生時(shí)間落入某一時(shí)間窗口的所有Log ID組成一個(gè)日志事務(wù)(Log Transaction， LT)，則原始RAS日志轉(zhuǎn)化為一個(gè)Log Transaction序列。需要注意的是，雖然每一個(gè)Log Transaction里的事件間是有發(fā)生先后順序的，但這里簡便地認(rèn)為它們都是在該Log Transaction對(duì)應(yīng)的時(shí)間段內(nèi)發(fā)生的。

圖4 用時(shí)間窗口將事件日志劃分成Log Transaction序列

2.3 Job日志預(yù)處理

由于Job日志的每條日志記錄是由Job_ID等9個(gè)域組成，所以有如下定義：

Job：由9元組(Job ID，Submission Time，Execution File，Queuing Time，Starting Time，End Time，Location，User，Project)表示。Job日志中可以包含n個(gè)Jobs，其中n∈N*。

Job ID：對(duì)于日志中所有具有相同Execution File的Jobs賦予一個(gè)共同的Job ID。則Job日志可以包含m個(gè)Job ID，其中m, n∈N*, m

Job 生存時(shí)間：每一個(gè)Job都會(huì)在Job日志的時(shí)間跨度內(nèi)存在一小段自己的運(yùn)行時(shí)間，我們稱之為Job存在時(shí)間，用二元組(Starting Time，End Time)表示。

通過上述定義，在日志預(yù)處理階段首先將原始Job日志中每一個(gè)Job分配一個(gè)Job ID，其中每一個(gè)Job ID代表了一個(gè)具有細(xì)粒度9元組信息的Job。由于Job日志精確記錄了集群上Job的運(yùn)行情況，所以不需要過濾。然后，利用一個(gè)滑動(dòng)的時(shí)間窗口(比如一個(gè)小時(shí))來劃分Job日志。如圖5所示，將存在時(shí)間落入某一時(shí)間窗口的所有Job ID組成一個(gè)Job Transaction(JT)，則原始Job日志轉(zhuǎn)化為一個(gè)Job Transaction序列。需要注意的是，如果某一Job的存在時(shí)間跨越了多個(gè)時(shí)間窗口，則將該Job劃分到對(duì)應(yīng)的多個(gè)Job Transaction中。

圖5 用時(shí)間窗口將作業(yè)日志劃分成Job Transaction序列

2.4 失效征兆抽取

結(jié)合Job日志和RAS日志的失效預(yù)測基于RAS日志中失效事件發(fā)生前Job日志中負(fù)載作業(yè)所表現(xiàn)出的征兆。如果這種Job征兆先于某一失效事件發(fā)生的現(xiàn)象多次出現(xiàn)，則將其抽取出來形成失效規(guī)則用于預(yù)測失效。

2.4.1 征兆窗口的確定

要確定某一失效事件發(fā)生的Job征兆，一一判斷生存時(shí)間處于該失效事件發(fā)生前的所有Jobs是沒有必要的。如果Job征兆與對(duì)應(yīng)失效事件的時(shí)間間隔大于有效預(yù)測窗口Win_valid，失效預(yù)測是沒有意義的。所以，只需要判斷生存時(shí)間處于失效事件有效預(yù)測窗口范圍內(nèi)的Jobs。一方面，有效預(yù)測窗口參數(shù)不能選取太小，否則被排除的Jobs過多會(huì)不利Job征兆的抽取且管理員將沒有足夠的時(shí)間處理馬上要發(fā)生的失效；另一方面，有效預(yù)測窗口參數(shù)不能選取太大，否則失效事件何時(shí)發(fā)生就很難判斷。

由于Job征兆和對(duì)應(yīng)的失效事件發(fā)生的時(shí)間間隔往往是不固定的，這里需要生成一個(gè)動(dòng)態(tài)時(shí)間窗口，稱為該失效事件的真征兆窗口。對(duì)于某一失效事件，其真征兆窗口從該失效事件發(fā)生的時(shí)間追溯到同一節(jié)點(diǎn)上的時(shí)間上最靠近的一個(gè)失效事件的發(fā)生時(shí)間。如果有效預(yù)測窗口和真征兆窗口發(fā)生沖突，則選取其中較小的一個(gè)作為該失效事件的征兆窗口。對(duì)于一個(gè)失效事件，其在日志中的每一次出現(xiàn)都對(duì)應(yīng)一個(gè)征兆窗口。

2.4.2 三種征兆抽取

一些已有工作定性地指出了集群上負(fù)載的行為和失效事件之間存在關(guān)聯(lián)。這些負(fù)載的行為包括運(yùn)行負(fù)載的類型、運(yùn)行負(fù)載的數(shù)量和運(yùn)行負(fù)載的變化。

首先，文獻(xiàn)[19]已經(jīng)指出需要在大量節(jié)點(diǎn)上運(yùn)行的Job類型更可能引起失效事件的發(fā)生，這里將其稱為大作業(yè)征兆。在進(jìn)行征兆抽取前，首先將生存時(shí)間處于某一失效事件征兆窗口內(nèi)的所有作業(yè)進(jìn)行Job過濾，即將與該失效事件不在同一節(jié)點(diǎn)發(fā)生的作業(yè)過濾掉。對(duì)于h個(gè)失效事件{F1，…，F(xiàn)h}，某一失效事件Fi和其征兆窗口內(nèi)經(jīng)Job過濾后的m個(gè)剩余作業(yè){J1，…，Jm}，作業(yè)Jj與失效事件Fi的相關(guān)性用提升度表示為

(1≤j≤m, 1≤i≤h) (1)

其中，P(Fi)是失效事件Fi在Log Transaction中出現(xiàn)的概率，等于包含該失效事件的Log Transaction的個(gè)數(shù)除以Log Transaction的總個(gè)數(shù)。P(Jj)是負(fù)載作業(yè)Jj在Job Transaction中出現(xiàn)的概率，等于包含該負(fù)載作業(yè)的Job Transaction的個(gè)數(shù)除以Job Transaction的總個(gè)數(shù)。P(JjFi)等于負(fù)載作業(yè)Jj恰好會(huì)在失效事件Fi的征兆窗口內(nèi)出現(xiàn)的總次數(shù)除以Job Transaction的總個(gè)數(shù)。如果lift>1，則Jj與Fi正相關(guān)，形成失效規(guī)則：

Jj→Fi

(2)

其次，文獻(xiàn)[17]已經(jīng)指出集群上運(yùn)行不同的作業(yè)類型會(huì)經(jīng)歷不同的失效事件，這里將其稱為不同作業(yè)組合征兆。在判斷不同作業(yè)的組合與失效事件的相關(guān)性前，首先將P(Fi|Jj)=P(Jj, Fi)/P(Jj)小于置信度閾值0.6的作業(yè)Jj排除掉以減小組合規(guī)模。對(duì)于h個(gè)失效事件{F1,…,Fh}中某一失效事件Fi和其征兆窗口內(nèi)經(jīng)Job過濾且未被排除的n個(gè)剩余作業(yè){J1,…,Jn}，不同作業(yè)的組合{Jj1,…,Jjr}與失效事件Fi的相關(guān)性用提升度表示為：

(1≤j1, …, jr≤n, 1

(3)

其中，P(Jj1,…,Jjr)是負(fù)載作業(yè)組合{Jj1,…,Jjr}在Job Transaction中出現(xiàn)的概率，等于同時(shí)包含這些負(fù)載作業(yè)的Job Transaction的個(gè)數(shù)除以Job Transaction的總個(gè)數(shù)。P(Jj1,…,Jjr, Fi)等于作業(yè)組合{Jj1,…,Jjr}恰好會(huì)在失效事件Fi的征兆窗口內(nèi)出現(xiàn)的總次數(shù)除以Job Transaction的總個(gè)數(shù)。如果lift>1，則{Jj1,…,Jjr}與Fi正相關(guān)，形成失效規(guī)則：

{Jj1,…,Jjr}→Fi

(4)

(1≤k≤l, 0<σ_r<1) (5)

則記錄在JTk中發(fā)生但未在JTk-1中發(fā)生的作業(yè)集合{J1,…,Js}，其中σ_r是預(yù)設(shè)的突發(fā)率閾值。將滿足式(5)條件的該Job Transaction表示為JTk{RJTk,{J1,…,Js}}。則JTk{RJTk,{J1,…,Js}}與失效事件Fi的相關(guān)性用提升度表示為

lift3(JTk{RJTk,{J1,…,Js}},Fi)=

(1

P(JTk{RJTk,{J1,…,Js}})是JTk{RJTk,{J1,…,Js}}在所有Job Transaction中出現(xiàn)的概率，等于該Job Transaction的個(gè)數(shù)除以Job Transaction的總個(gè)數(shù)。P(JTk{RJTk,{J1,…,Js}},Fi)等于JTk{RJTk,{J1,…,Js}}恰好會(huì)在失效事件Fi的征兆窗口內(nèi)出現(xiàn)的總次數(shù)除以Job Transaction的總個(gè)數(shù)。如果lift>1，則JTk{RJTk,{J1,…,Js}}與Fi正相關(guān)，形成失效規(guī)則：

JTk{RJTk,{J1,…,Js}}→Fi

(7)

2.5 基于失效征兆的細(xì)粒度失效預(yù)測

在僅僅依靠RAS日志進(jìn)行失效預(yù)測的工作[2,3]中，失效預(yù)測算法在預(yù)測階段需要不斷分析系統(tǒng)收集的大量RAS日志，從中找到與失效規(guī)則匹配的事件序列，輔以置信度給出預(yù)測結(jié)果。而我們的方法實(shí)現(xiàn)了從簡單的作業(yè)運(yùn)行行為信息中得到失效征兆，將其作為失效規(guī)則存儲(chǔ)在規(guī)則表里，用于在失效預(yù)測時(shí)進(jìn)行匹配查詢。由于每一個(gè)由Log ID表示的失效事件都含有細(xì)粒度的9元組信息，所以這里實(shí)現(xiàn)了能夠鎖定失效事件發(fā)生節(jié)點(diǎn)和失效事件類型等信息的精確的失效預(yù)測。

對(duì)于大作業(yè)征兆，只要集群系統(tǒng)中出現(xiàn)與失效規(guī)則匹配的需要很多個(gè)節(jié)點(diǎn)參與運(yùn)行的大作業(yè)出現(xiàn)，則失效以置信度lift1×P(Fi)的概率發(fā)生。

對(duì)于不同作業(yè)組合征兆，只要集群上運(yùn)行與失效規(guī)則匹配的作業(yè)組合，則失效以置信度lift2×P(Fi)的概率發(fā)生。

對(duì)于作業(yè)突發(fā)征兆，只要集群上運(yùn)行的作業(yè)單位時(shí)間內(nèi)個(gè)數(shù)和類型的變化與失效規(guī)則匹配，則失效以置信度lift3×P(Fi)的概率發(fā)生。

3 實(shí) 驗(yàn)

本部分將按照前一部分介紹的方法對(duì)240天的Intrepid系統(tǒng)的RAS日志和Job日志進(jìn)行分析，并從中得到的失效規(guī)則進(jìn)行失效預(yù)測。Intrepid是美國阿貢國家實(shí)驗(yàn)室的一個(gè)由40個(gè)Blue Gene/P機(jī)箱組成的系統(tǒng)，為美國能源部服務(wù)。其總共包括了40960個(gè)計(jì)算節(jié)點(diǎn)，每秒峰值速度可達(dá)到556萬億次浮點(diǎn)運(yùn)算次數(shù)。表1給出了兩個(gè)日志的基本信息。兩個(gè)日志的前2/3用來抽取失效征兆，后1/3用來失效預(yù)測。

表1 RAS日志和Job日志

3.1 日志預(yù)處理和過濾

首先對(duì)原始RAS日志中具有相同(MSG_ID，SEVERITY，Location)的事件記錄賦予同一個(gè)Log ID，對(duì)原始Job日志中具有相同Execution File的作業(yè)賦予同一個(gè)Job ID，處理后得到72187個(gè)Log ID和9664個(gè)Job ID。

對(duì)由原始RAS日志生成的Log ID序列進(jìn)行去重時(shí)，重復(fù)記錄的時(shí)間間隔若小于閾值，則刪除這個(gè)重復(fù)記錄?？紤]到日志中重復(fù)事件的時(shí)間跨度分布，這里閾值選取30秒鐘，去重后得到1746568個(gè)記錄。

表2 RAS日志和Job日志

3.2 征兆抽取和失效預(yù)測

在基于失效征兆的細(xì)粒度的失效預(yù)測方法中，采用準(zhǔn)確率和召回率兩個(gè)指標(biāo)來評(píng)價(jià)預(yù)測的效果。準(zhǔn)確率precision是預(yù)測正確的失效事件個(gè)數(shù)除以預(yù)測出的失效事件總個(gè)數(shù)：

(8)

召回率recall是預(yù)測正確的失效事件個(gè)數(shù)除以失效事件總個(gè)數(shù)：

(9)

其中，TP是預(yù)測正確的失效事件個(gè)數(shù)。FP是預(yù)測發(fā)生但實(shí)際未發(fā)生的失效事件個(gè)數(shù)。FN是未預(yù)測出但實(shí)際發(fā)生了的失效事件個(gè)數(shù)。

在確定征兆窗口時(shí)，為了保留更多的Job征兆又不影響失效預(yù)測的時(shí)效性，應(yīng)合理選取有效預(yù)測窗口的大小。由于集群系統(tǒng)上的失效率往往呈現(xiàn)以周為單位的周期性，即周一到周五失效率比較高，而周末會(huì)降低[9]。所以，這里有效預(yù)測窗口參數(shù)Win_valid分別取24h(1d)、48h(2d)、72h(3d)、96h(4d)和120h(5d)并進(jìn)行比較。在抽取作業(yè)突發(fā)征兆時(shí)，為了比較合理判斷單位時(shí)間內(nèi)作業(yè)突然增加對(duì)失效事件的影響，突發(fā)率閾值σ_r選取0.5。由于BlueGene/P系統(tǒng)節(jié)點(diǎn)規(guī)模較大，某些失效事件在RAS日志中僅僅出現(xiàn)了一兩次，不足以滿足失效征兆所必須的提升度條件，而已有工作[14]中指出具有相同event ID 的失效事件具有相似的發(fā)生行為。所以，這里首先將具有相同event ID的失效事件分為一組(總共得到了85組)，然后將每一組中的每一個(gè)失效事件的失效征兆作為該組中所有失效事件的失效征兆進(jìn)行間接失效預(yù)測。

圖6和圖7列出了分別在5個(gè)不同有效預(yù)測窗口下直接利用3種失效征兆(用情景1表示)和間接利用3種失效征兆(用情景2表示)進(jìn)行失效預(yù)測的準(zhǔn)確率和召回率。首先，在直接失效預(yù)測中，3種失效征兆下的準(zhǔn)確率普遍都比較高，但召回率普遍都不高。其中，作業(yè)突發(fā)征兆下的準(zhǔn)確率相對(duì)最高，大作業(yè)征兆下的召回率相對(duì)最低。其次，在情景1和情景2兩種情景下，縮小有效預(yù)測窗口雖然對(duì)準(zhǔn)確率影響不大，但是會(huì)顯著減少失效征兆的抽取進(jìn)而降低召回率。其中，基于不同作業(yè)組合征兆的失效預(yù)測召回率降得最多。另外，通過對(duì)不同有效預(yù)測窗口下準(zhǔn)確率和召回率的對(duì)比，可以發(fā)現(xiàn)在窗口達(dá)到72h后，召回率的提高開始變得緩慢。如果對(duì)失效預(yù)測時(shí)效性要求比較高，那么設(shè)置72h(3d)的有效預(yù)測窗口將能同時(shí)保證較高的準(zhǔn)確率和召回率。最后，與直接失效預(yù)測相比，間接失效預(yù)測雖然可以提高召回率，但準(zhǔn)確率也會(huì)隨之降低。其中，作業(yè)突發(fā)征兆下的召回率提高最多，同時(shí)準(zhǔn)確率也降得最多?？傊ьA(yù)測要合理選取有效預(yù)測窗口；負(fù)載作業(yè)強(qiáng)度突然增加會(huì)導(dǎo)致失效事件更頻繁發(fā)生；失效事件的失效征兆可以用來預(yù)測具有與該失效事件相同事件類型的其它失效事件，但要合理權(quán)衡準(zhǔn)確率和召回率。

圖6 兩種情景(情景1和情景2)、5種有效預(yù)測窗口和3種征兆下的失效預(yù)測準(zhǔn)確率

圖7 兩種情景(情景1和情景2)、5種有效預(yù)測窗口和3種征兆下的失效預(yù)測召回率

4 結(jié) 論

本文設(shè)計(jì)并實(shí)現(xiàn)了一種利用集群系統(tǒng)的系統(tǒng)日志和作業(yè)日志進(jìn)行結(jié)合分析來實(shí)現(xiàn)失效預(yù)測的方法。經(jīng)過預(yù)處理和過濾，將原始RAS日志和Job 日志解析成具有細(xì)粒度信息的Log Transaction序列和Job Transaction序列。在動(dòng)態(tài)地生成征兆窗口后，在Log Transaction中的所有失效事件的征兆窗口內(nèi)從Job Transaction中抽取出負(fù)載作業(yè)所表現(xiàn)出的三種失效征兆：大作業(yè)征兆，不同作業(yè)組合征兆和作業(yè)突發(fā)征兆。最后，利用3種征兆實(shí)現(xiàn)失效預(yù)測。從對(duì)美國阿貢國家實(shí)驗(yàn)室Intrepid系統(tǒng)的RAS日志和Job日志進(jìn)行結(jié)合分析和失效預(yù)測實(shí)驗(yàn)的結(jié)果中可以看出，我們的方法可以實(shí)現(xiàn)較高的準(zhǔn)確率。并且，當(dāng)間接利用3種失效征兆進(jìn)行失效預(yù)測時(shí)，可以實(shí)現(xiàn)高于50%的召回率。與其它提高召回率的方法相比，我們不需要復(fù)雜的分布式數(shù)據(jù)挖掘技術(shù)。下一步的工作中，一方面將深入分析利用3種失效征兆間接失效預(yù)測時(shí)準(zhǔn)確率降低的原因并提出改進(jìn)的方法；另一方面將考察負(fù)載作業(yè)在系統(tǒng)失效時(shí)的其它行為并提出其它有效的失效征兆類型進(jìn)行失效預(yù)測。

[1] Liang Y, Zhang Y, Sivasubramaniam A, et al. Filtering failure logs for a BlueGene/L prototype. In: Proceedings of IEEE International Conference on Dependable Systems and Networks, Yokohama, Japan, 2005. 476-485

[2] Fu X, Ren R, Zhan J, et al. LogMaster: mining event correlations in logs of large-scale cluster systems. In: Proceedings of IEEE International Symposium on Reliable Distributed Systems, Irvine, USA, 2012. 71-80

[3] Gainaru A, Cappello F, Fullop J, et al. Adaptive event prediction strategy with dynamic time window for largescale HPC systems. In: Proceedings of ACM SOSP Workshop on Managing Large-Scale Systems via the Analysis of System Logs and the Application of Machine Learning Techniques, NY, USA, 2011. 4-11

[4] Gujrati P, Li Y, Lan Z. A meta-learning failure predictor for Blue Gene/L systems. In: Proceedings of International Conference on Parallel Processing, Washington, USA, 2007. 40-48

[5] Zheng Z, Lan Z, Park B, et al. System log preprocessing to improve failure prediction. In: Proceedings of the International Conference on Dependable Systems and Networks, Lisbon, Portugal, 2009. 572-577

[6] Salfner F, Lenk M, Malek M. A survey of online failure prediction methods.JournalofACMComputtingSurveys, 2010, 42(3): 1-42

[7] Li Y, Zheng Z, Lan Z, et al. Practical online failure prediction for Blue Gene/P: Periodbased vs Event-driven. In: Proceedings of IEEE International Conference on Dependable Systems and Networks, Hong Kong, China, 2011. 259-264

[8] Chen C, Singh N, Yajnik S. Log analytics for dependable enterprise telephony. In: Proceedings of IEEE International Conference on Dependable Computing Conference, Sibiu, Romania, 2011. 94-101

[9] Schroeder B, Gibson G. A large-scale study of failures in high-performance computing systems.IEEETransonDependableandSecureComputing, 2006, 7(4): 337-350

[10] Liang Y, Zhang Y, Sivasubramaniam A, et al. BlueGene/L failure analysis and prediction models. In: Proceedings of IEEE International Conference on Dependable Systems and Networks, Philadelphia, USA, 2006. 425-434

[11] Fu S, Xu C Z. Exploring event correlation for failure prediction in coalitions of clusters. In: Proceedings of ACM/IEEE International Conference on Supercomputing, Reno, USA, 2007. 1-10

[12] Gainaru A, Cappello F, Kramer W. Taming of the shrew: modeling the normal and faulty behavior of large-scale HPC Systems. In: Proceedings of IEEE International Conference on Parallel Distributed Processing Symposium, Shanghai, China, 2012. 1168-1179

[13] Gu J, Zheng Z, Lan Z, et al. Dynamic meta-learning for failure prediction in large-scale systems: A case study. In: Proceedings of IEEE International Conference on Parallel Processing, Portland, USA, 2008. 157-164

[14] Fu X, Ren R, McKee S, et al. Digging deeper into cluster system logs for failure prediction and root cause diagnosis. In: Proceedings of IEEE International Conference on Cluster Computing, Madrid, Spain, 2014. 103-112

[15] Moens S, Aksehirli E, Goethals B. Frequent itemset mining for big data. In: Proceedings of IEEE International Conference on Big Data, Santa Clara, USA, 2013. 111-118

[16] Wu G, Zhang H, Qiu M, et al. A decentralized approach for mining event correlations in distributed system monitoring.ElsevierJournalofParallelandDistributedComputing, 2013,73(3):330-340

[17] Martino C D, Cinque M, Cotroneo D. Assessing time coalescence techniques for the analysis of supercomputer logs. In: Proceedings of IEEE International Conference of Dependable Systems and Networks, Boston, USA, 2012. 1-12

[18] Oliner A, Stearley J. What supercomputers say: a study of five system logs. In: Proceedings of IEEE International Conference on Dependable Systems and Networks, Edinburgh, England, 2007. 575-584

[19] Zheng Z M, Yu L, Lan Z L, et al. 3-dimensional root cause diagnosis via co-analysis. In: Proceedings of ACM International Conference on Autonomic Computing, San Jose, USA, 2012. 181-190

[20] Yigitbas Y, Gallet M, Kondo D, et al. Analysis and modeling of time-correlated failures in large-scale distributed systems. In: Proceedings of IEEE International Conference on Grid Computing, Brussels, Belgium, 2010. 65-72

[21] Zheng Z, Yu L, Tang W, et al. Co-analysis of ras log and job log on Blue Gene/P. In: Proceedings of IEEE International Conference on Parallel Processing, Anchorage, USA, 2011. 1530-2075

[22] Tang W, Lan Z, Desai N, et al. Fault-aware utility-based job scheduling on Blue Gene/P systems. In: Proceedings of IEEE International Conference on Cluster Computing, New Orleans, USA, 2009. 1-10

A log co-analysis based failure prediction method for large-scale cluster systems

Fu Xiaoyu******, Ren Rui***, Zhan Jianfeng***, Sun Ninghui***

(*State Key Laboratory of Computer System and Architecture, Beijing 100190) (**Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190) (***University of Chinese Academy of Sciences, Beijing 100049)

The failure prediction for large-scale cluster supercomputer was studied. Aiming at the prolem that the existing prediction method only analyzing the single system log needs complex data mining techniques while its prediction recall rate is generally lower, this study presented an effective failure prediction method based on co-analysis of system logs and job logs that records the running workload information. The principle of the method is below: Firstly, the fine-grained two-dimensional event sequence and job sequence are produced through preprocessing and filtering of the two raw logs; Secondly, three failure symptoms are extracted from job logs before the occurrence of failure events; Finally, failure predictions are carried out by using these symptoms. The results of the experiments on real logs of the BlueGene/P system show that the proposed method can predict failures with a higher precision and a higher recall rate.

large-scale cluster system, system log, job log, log analysis, failure prediction

10.3772/j.issn.1002-0470.2016.06.001

①863計(jì)劃(2015AA015308)和973計(jì)劃(2014CB340402)資助項(xiàng)目。

2016-03-14)

②女，1985年生，博士生；研究方向：分布式數(shù)據(jù)挖掘，集群系統(tǒng)可靠性和性能分析；聯(lián)系人，E-mail: fuxiaoyu@ncic.ac.cn