高 劍，于 康，卿 鵬，尉紅梅

(江南計(jì)算技術(shù)研究所，江蘇 無(wú)錫 214083)(*通信作者電子郵箱gaojian_whu@163.com)

0 引言

高性能計(jì)算系統(tǒng)廣泛應(yīng)用于國(guó)防建設(shè)、科學(xué)研究以及國(guó)民金融等重要領(lǐng)域，隨著系統(tǒng)規(guī)模的擴(kuò)大，系統(tǒng)的平均無(wú)故障時(shí)間(Mean Time Between Failures, MTBF)逐漸降低，為系統(tǒng)可靠性帶來(lái)了嚴(yán)峻挑戰(zhàn)[1]。根據(jù)可靠性理論的論述，若系統(tǒng)組件的故障(fault)在運(yùn)行時(shí)被激活，將導(dǎo)致系統(tǒng)內(nèi)部出現(xiàn)錯(cuò)誤狀態(tài)(error)，錯(cuò)誤狀態(tài)會(huì)在組件間不斷地傳播，最終引發(fā)系統(tǒng)的失效(failure)，即系統(tǒng)失效是一個(gè)由故障引起錯(cuò)誤狀態(tài)并逐漸積累的漸進(jìn)過(guò)程[2]。

故障管理是維護(hù)高性能計(jì)算系統(tǒng)可靠性的重要基礎(chǔ)，故障定位作為故障管理的核心功能，發(fā)揮著關(guān)鍵作用。故障定位主要包括檢測(cè)和分析兩個(gè)主要步驟：故障檢測(cè)負(fù)責(zé)及時(shí)發(fā)現(xiàn)由故障引起的異常表現(xiàn)，也稱作癥狀(symptom)；故障分析負(fù)責(zé)根據(jù)檢測(cè)到的癥狀快速、準(zhǔn)確地推理得出故障，縮短故障響應(yīng)時(shí)間。高效的故障定位有利于系統(tǒng)在失效前采取相應(yīng)的處理策略以避免故障的擴(kuò)散，從而提高系統(tǒng)利用率。

1 相關(guān)工作

目前，從計(jì)算機(jī)科學(xué)的不同領(lǐng)域派生出的故障定位方法主要分為事件關(guān)聯(lián)[3]與主動(dòng)探測(cè)[4]兩類。

1.1 事件關(guān)聯(lián)

事件關(guān)聯(lián)是應(yīng)用最為廣泛的故障定位技術(shù)，要求被管設(shè)備在自身狀態(tài)出現(xiàn)異常時(shí)，能夠向外發(fā)出癥狀告警，由中央管理器負(fù)責(zé)收集并分析被管設(shè)備發(fā)出的告警事件。文獻(xiàn)[5]對(duì)事件關(guān)聯(lián)進(jìn)行了較為全面的綜述，包括基于規(guī)則、模型以及案例等具體的實(shí)現(xiàn)方式。

基于故障傳播模型(Fault Propagation Model, FPM)[6]，也稱作“癥狀-故障”模型的事件關(guān)聯(lián)是高性能計(jì)算系統(tǒng)中常用的故障定位方式，該方式通過(guò)挖掘歷史故障經(jīng)驗(yàn)建立“癥狀-故障”之間的映射關(guān)系。當(dāng)故障發(fā)生時(shí)，以系統(tǒng)日志中的監(jiān)控狀態(tài)作為“癥狀-故障”模型的癥狀輸入，并利用不同的分析算法進(jìn)行推理和調(diào)試。這種方式的不足在于：1)定位不及時(shí)，由于故障具備傳播性，滯后性可能引發(fā)更多的故障；2)隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，事件數(shù)量劇增，構(gòu)建“癥狀-故障”模型的復(fù)雜度大幅提高；3)事件在傳播過(guò)程中不可避免地出現(xiàn)延遲、丟失等情況，容易造成故障的誤報(bào)或漏報(bào)；4)管理員的干預(yù)調(diào)試影響系統(tǒng)的正常運(yùn)行。

1.2 主動(dòng)探測(cè)

主動(dòng)探測(cè)是近年來(lái)的研究熱點(diǎn)，這種方式基于系統(tǒng)的拓?fù)浣Y(jié)構(gòu)在運(yùn)行時(shí)主動(dòng)地執(zhí)行不同的探針，根據(jù)探針的探測(cè)結(jié)果實(shí)現(xiàn)故障的檢測(cè)和分析。探針是指執(zhí)行在特定機(jī)器也稱作探測(cè)站上的一類特殊程序，它通過(guò)發(fā)送命令或請(qǐng)求到系統(tǒng)組件實(shí)現(xiàn)端到端的探測(cè)，例如ping和traceroute命令可視作檢測(cè)網(wǎng)絡(luò)可用性的探針。文獻(xiàn)[7]指出探測(cè)站與探針集的選擇是影響主動(dòng)探測(cè)效率的關(guān)鍵因素；文獻(xiàn)[8]對(duì)目前常用的探測(cè)站和探針集選擇算法進(jìn)行了總結(jié)與對(duì)比。

由于能夠自適應(yīng)地選擇執(zhí)行的探針集，主動(dòng)探測(cè)與事件關(guān)聯(lián)相比，具有較強(qiáng)的主動(dòng)性、實(shí)時(shí)性以及針對(duì)性，能夠避免癥狀延遲或丟失對(duì)故障定位準(zhǔn)確性的影響，但將主動(dòng)探測(cè)直接應(yīng)用于高性能計(jì)算系統(tǒng)的缺陷[9]在于：1)系統(tǒng)的規(guī)模不斷增長(zhǎng)，所需探針的數(shù)目也隨之劇增，且探針的設(shè)計(jì)復(fù)雜度高；2)具備強(qiáng)探測(cè)能力的探針是有限的，部署探測(cè)站的能力也是有限的；3)探測(cè)站和探針集的選擇已被證明是NP問(wèn)題，相關(guān)選擇算法的執(zhí)行時(shí)間隨系統(tǒng)規(guī)模的增加呈指數(shù)級(jí)增長(zhǎng)；4)大量探針的執(zhí)行將加劇網(wǎng)絡(luò)的負(fù)載，占用系統(tǒng)寶貴的計(jì)算資源。

針對(duì)事件關(guān)聯(lián)和主動(dòng)探測(cè)技術(shù)應(yīng)用于高性能計(jì)算系統(tǒng)的問(wèn)題，本文提出了一種基于消息傳遞的故障定位(Message-Passing based Fault Localization, MPFL)框架，MPFL框架首次將消息庫(kù)與故障定位問(wèn)題聯(lián)系起來(lái)，并采用分布式的設(shè)計(jì)思想，將故障定位任務(wù)分配給計(jì)算節(jié)點(diǎn)，能夠在系統(tǒng)運(yùn)行時(shí)實(shí)現(xiàn)異常狀態(tài)的檢測(cè)，并且將事件關(guān)聯(lián)與主動(dòng)探測(cè)的優(yōu)勢(shì)相結(jié)合，提高了故障分析的準(zhǔn)確性。

2 MPFL故障定位框架

高性能計(jì)算系統(tǒng)的節(jié)點(diǎn)通過(guò)特定的硬件以及高速網(wǎng)絡(luò)互連，大部分節(jié)點(diǎn)具有同構(gòu)性且節(jié)點(diǎn)狀態(tài)在執(zhí)行計(jì)算任務(wù)時(shí)具備相似性。每個(gè)節(jié)點(diǎn)獨(dú)立運(yùn)行，并與其他節(jié)點(diǎn)相互通信來(lái)協(xié)同完成計(jì)算任務(wù)，節(jié)點(diǎn)的通信機(jī)制廣泛使用消息傳遞。

因此，MPFL框架的基本思路是充分利用節(jié)點(diǎn)間的消息傳遞在系統(tǒng)運(yùn)行時(shí)獲取節(jié)點(diǎn)狀態(tài)。在此基礎(chǔ)上，設(shè)計(jì)基于樹(shù)形拓?fù)涞墓收蠙z測(cè)(Tree-based Fault Detection, TFD)和故障分析(Tree-based Fault Analysis, TFA)算法。

2.1 MPFL軟件架構(gòu)

如圖1所示，MPFL框架主要包括故障檢測(cè)和故障分析兩個(gè)功能模塊，在系統(tǒng)軟件架構(gòu)中與消息庫(kù)位于同一層次，兩者相互協(xié)作為上層并行應(yīng)用程序提供故障定位服務(wù)。此外，作業(yè)管理、網(wǎng)絡(luò)管理、操作系統(tǒng)及文件系統(tǒng)等系統(tǒng)組件為故障定位提供支持，如提供故障信息和觸發(fā)故障定位等。

圖1 MPFL通用架構(gòu)

MPFL將故障定位任務(wù)與消息庫(kù)緊密聯(lián)系起來(lái)，能夠更好地適應(yīng)高性能計(jì)算系統(tǒng)，主要原因包括：

1)受作業(yè)調(diào)度和節(jié)點(diǎn)分配策略等因素影響，高性能計(jì)算系統(tǒng)的部分故障往往只在特定的運(yùn)行環(huán)境中被激活，故障難以重現(xiàn)和調(diào)試；若能在節(jié)點(diǎn)運(yùn)行時(shí)獲取節(jié)點(diǎn)異常狀態(tài)，有利于解決此類故障。

2)參與大規(guī)模計(jì)算的節(jié)點(diǎn)數(shù)巨大，且節(jié)點(diǎn)之間需要相互通信協(xié)作，部分節(jié)點(diǎn)的故障更易于在其他節(jié)點(diǎn)中體現(xiàn)，此時(shí)需要基于消息傳遞協(xié)同多個(gè)節(jié)點(diǎn)進(jìn)行綜合分析。

3)通過(guò)與消息庫(kù)的緊耦合，能夠主動(dòng)地獲取并行應(yīng)用程序運(yùn)行時(shí)的內(nèi)部狀態(tài)信息，具備較強(qiáng)的實(shí)時(shí)性和針對(duì)性，能夠避免將極大的時(shí)間與計(jì)算成本消耗在海量系統(tǒng)日志的數(shù)據(jù)挖掘工作中。

4)故障定位可獨(dú)立于節(jié)點(diǎn)計(jì)算等工作進(jìn)程，節(jié)點(diǎn)在進(jìn)行故障檢測(cè)和分析時(shí)不影響系統(tǒng)的正常工作，并且整個(gè)過(guò)程對(duì)用戶是透明的，用戶只需要關(guān)心故障定位結(jié)果以采取相應(yīng)的處理策略。

5)作業(yè)管理等系統(tǒng)組件雖然能夠主動(dòng)或被動(dòng)地檢測(cè)到部分系統(tǒng)異常，但它們之間相互獨(dú)立，并不共享異常信息。MPFL將不同組件的異常信息進(jìn)行匯總分析，有利于提高故障定位的準(zhǔn)確性。

2.2 基于故障定位樹(shù)的故障檢測(cè)

目前，高性能計(jì)算系統(tǒng)普遍采用全局的集中式故障管理，隨著系統(tǒng)規(guī)模擴(kuò)大，故障概率增加、故障關(guān)聯(lián)性增強(qiáng)，并且故障類型更為復(fù)雜多樣，這種方式容易陷入性能瓶頸[10]。

2.2.1 故障定位樹(shù)

MPFL框架采用層次化和分布式的設(shè)計(jì)思想，將全局的故障定位任務(wù)分配給不同的節(jié)點(diǎn)，由各節(jié)點(diǎn)運(yùn)行輕量級(jí)的故障定位進(jìn)程對(duì)局部范圍內(nèi)的多個(gè)節(jié)點(diǎn)進(jìn)行故障的檢測(cè)和分析。具體地，當(dāng)系統(tǒng)在對(duì)每個(gè)作業(yè)進(jìn)行初始化時(shí)，根據(jù)相關(guān)配置將所有參與計(jì)算的節(jié)點(diǎn)進(jìn)行邏輯上的樹(shù)形劃分，邏輯劃分得到的樹(shù)形拓?fù)浞Q作故障定位樹(shù)(Fault Localization Tree, FLT)。在系統(tǒng)中并行執(zhí)行的每個(gè)作業(yè)都擁有各自的FLT結(jié)構(gòu)，參與多個(gè)作業(yè)的節(jié)點(diǎn)可以屬于不同的FLT，但在每個(gè)FLT中的位置可能并不相同。

在FLT中，除根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是唯一的；除葉節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)擁有若干個(gè)子節(jié)點(diǎn)。MPFL指定由父節(jié)點(diǎn)負(fù)責(zé)所有與子節(jié)點(diǎn)故障相關(guān)的癥狀信息收集與分析工作，即父節(jié)點(diǎn)是其所有子節(jié)點(diǎn)的故障定位節(jié)點(diǎn)(Fault Localization Node, FLN)。FLT的結(jié)構(gòu)在作業(yè)的生命周期內(nèi)不會(huì)改變，但由于父節(jié)點(diǎn)可能失效，同時(shí)考慮節(jié)點(diǎn)負(fù)載、性能開(kāi)銷等因素，每個(gè)節(jié)點(diǎn)能夠根據(jù)相關(guān)參數(shù)及其閾值(如帶寬、CPU利用率等)選擇替代的故障定位節(jié)點(diǎn)(Substitute of Fault Localization Node, SFLN)。顯然，同一子樹(shù)內(nèi)的節(jié)點(diǎn)狀態(tài)與存儲(chǔ)的癥狀信息往往具備更強(qiáng)的關(guān)聯(lián)性，失去FLN的節(jié)點(diǎn)通常選擇同一子樹(shù)的更高層節(jié)點(diǎn)作為SFLN。

在FLT中，雖然每個(gè)節(jié)點(diǎn)的FLN是唯一的，但SFLN可以有多個(gè)。此外，MPFL指定根節(jié)點(diǎn)負(fù)責(zé)接收不同節(jié)點(diǎn)上報(bào)的故障定位結(jié)果并向用戶報(bào)告，同時(shí)提供接口使得用戶能夠?qū)收隙ㄎ贿^(guò)程進(jìn)行管理。

故障定位樹(shù)的優(yōu)勢(shì)在于邏輯層次清晰，具備較強(qiáng)的可擴(kuò)展性，系統(tǒng)可自適應(yīng)地增加或刪減節(jié)點(diǎn)；此外，各節(jié)點(diǎn)獨(dú)立工作，能夠同時(shí)處理多個(gè)并發(fā)性故障；同時(shí)，樹(shù)形拓?fù)淠軌蚱鹾辖^大多數(shù)高性能計(jì)算系統(tǒng)的物理拓?fù)?，同一子?shù)的節(jié)點(diǎn)可獲得較高的通信效率，有利于提高故障定位的整體效率。

2.2.2 故障檢測(cè)算法——TFD

故障檢測(cè)的目標(biāo)是及時(shí)地發(fā)現(xiàn)由故障引起的癥狀，而癥狀的空間性和時(shí)間性將直接影響故障分析的準(zhǔn)確性?？臻g性是指收集的癥狀能否覆蓋所有可能的故障，因此需要獲取不同硬件部件和不同軟件層次的狀態(tài)，擴(kuò)大對(duì)故障的覆蓋范圍；時(shí)間性指的是癥狀的收集應(yīng)當(dāng)在系統(tǒng)失效之前，并且能夠體現(xiàn)節(jié)點(diǎn)狀態(tài)隨時(shí)間的變化過(guò)程。

為滿足癥狀收集的空間性和時(shí)間性，結(jié)合FLT的結(jié)構(gòu)及其工作機(jī)制，節(jié)點(diǎn)在運(yùn)行時(shí)可利用消息庫(kù)、網(wǎng)絡(luò)管理以及操作系統(tǒng)等組件實(shí)現(xiàn)對(duì)癥狀的檢測(cè)。表1給出了各組件報(bào)告的主要癥狀模式。

表1 系統(tǒng)組件報(bào)告的主要癥狀模式

算法1描述了基于故障定位樹(shù)的故障檢測(cè)算法TFD，作業(yè)初始化后，節(jié)點(diǎn)正常工作，若系統(tǒng)組件發(fā)現(xiàn)可疑節(jié)點(diǎn)(Suspected Fault Node, SFN)出現(xiàn)異常癥狀，計(jì)算合適的癥狀接收節(jié)點(diǎn)并發(fā)送。

算法1 TFD算法。

對(duì)每個(gè)節(jié)點(diǎn)：

輸入：故障定位樹(shù)FLT；

WHILE (Job_Finished!=true) DO

IF Find_Symp(SFN) THEN

//檢測(cè)到故障癥狀

IF Available_FLN(SFN) THEN

//判斷可疑節(jié)點(diǎn)的FLN是否可用

Send theSymptomto SFN’s FLN;

ELSE

Select the SFN’s SFLN;

Send theSymptomto SFN’s SFLN;

END IF

END IF

IF (Recv_Symp==true) THEN

Store_ Symp (Symptom);

//將接收到的癥狀保存到癥狀集

END IF

END WHILE

TFD算法在一個(gè)作業(yè)中的示例如圖2所示，假設(shè)該作業(yè)在一個(gè)集群的9個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行，圖中的樹(shù)形拓?fù)錇檫壿嬐負(fù)洌c物理連接無(wú)關(guān)，即為該作業(yè)的故障定位樹(shù)，序號(hào)表示了事件發(fā)生的順序：

1)節(jié)點(diǎn)n在與節(jié)點(diǎn)m通信時(shí)，發(fā)現(xiàn)來(lái)自節(jié)點(diǎn)m的消息錯(cuò)誤，節(jié)點(diǎn)n將此癥狀報(bào)告給節(jié)點(diǎn)m的FLN；同時(shí)，當(dāng)節(jié)點(diǎn)y在給節(jié)點(diǎn)x發(fā)送點(diǎn)對(duì)點(diǎn)消息時(shí)，發(fā)現(xiàn)節(jié)點(diǎn)x響應(yīng)超時(shí)。

2)節(jié)點(diǎn)y試圖將節(jié)點(diǎn)x響應(yīng)超時(shí)的癥狀報(bào)告給其FLN，但通過(guò)可用性探測(cè)發(fā)現(xiàn)其FLN已經(jīng)過(guò)載，不再接收新癥狀；作業(yè)管理同樣對(duì)節(jié)點(diǎn)x的FLN進(jìn)行了探測(cè)并排除，為簡(jiǎn)單起見(jiàn)，圖中并未標(biāo)出。

3)根據(jù)系統(tǒng)配置，節(jié)點(diǎn)y選擇根節(jié)點(diǎn)作為節(jié)點(diǎn)x的SFLN，并將其響應(yīng)超時(shí)癥狀發(fā)送到根節(jié)點(diǎn)；同時(shí)，作業(yè)管理向根節(jié)點(diǎn)報(bào)告節(jié)點(diǎn)x無(wú)心跳信息。

TFD算法的優(yōu)勢(shì)在于節(jié)點(diǎn)只需負(fù)責(zé)局部范圍內(nèi)的故障，并且能夠自適應(yīng)地選擇故障定位節(jié)點(diǎn)，有效緩解了單點(diǎn)瓶頸問(wèn)題；同時(shí)，基于消息傳遞能夠獲取節(jié)點(diǎn)運(yùn)行時(shí)的狀態(tài)，并且支持并行處理多個(gè)癥狀報(bào)告，提高了故障定位的效率。

圖2 TFD算法的示例

2.3 故障分析算法的設(shè)計(jì)

當(dāng)節(jié)點(diǎn)接收到的癥狀集滿足用戶設(shè)定的觸發(fā)條件時(shí)，例如與某一節(jié)點(diǎn)相關(guān)的癥狀數(shù)量達(dá)到設(shè)定的閾值時(shí)，節(jié)點(diǎn)的故障定位進(jìn)程將進(jìn)入分析階段。

高性能計(jì)算系統(tǒng)規(guī)模龐大且結(jié)構(gòu)復(fù)雜，為故障分析帶來(lái)了許多挑戰(zhàn)：1)相同的癥狀可能是由不同組件的故障引起；2)同一組件的故障也可能引發(fā)多種不同的癥狀；3)某些故障可能導(dǎo)致其余多個(gè)故障的發(fā)生，甚至引發(fā)事件風(fēng)暴[11]，即將一個(gè)癥狀的發(fā)生稱作一個(gè)事件，由于故障的關(guān)聯(lián)性，同一時(shí)刻出現(xiàn)大量重復(fù)、冗余的事件導(dǎo)致系統(tǒng)性能嚴(yán)重下降。

為應(yīng)對(duì)上述挑戰(zhàn)，本文將事件關(guān)聯(lián)與主動(dòng)探測(cè)兩種方法的優(yōu)勢(shì)相結(jié)合，在TFD算法的基礎(chǔ)上，提出基于故障定位樹(shù)的分析(TFA)算法。圖3描述了TFA算法的結(jié)構(gòu)，首先，故障定位節(jié)點(diǎn)使用基于規(guī)則的事件關(guān)聯(lián)對(duì)TFD算法檢測(cè)到的癥狀集進(jìn)行推理，獲得多個(gè)不同的候選故障集；然后，利用消息探測(cè)分別對(duì)不同的候選故障集進(jìn)一步地分析，最終得到若干個(gè)不同的故障。

1)基于規(guī)則的事件關(guān)聯(lián)。

基于規(guī)則的實(shí)現(xiàn)是事件關(guān)聯(lián)應(yīng)用最為廣泛的一種方式，這種方式預(yù)先建立規(guī)則庫(kù)，每條規(guī)則包含控制邏輯，規(guī)則形式為：IF condition A THEN action B，在進(jìn)行分析時(shí)，采用前向鏈推理機(jī)制，選擇滿足條件的規(guī)則并執(zhí)行相應(yīng)的動(dòng)作。

根據(jù)文獻(xiàn)[12]對(duì)高性能計(jì)算系統(tǒng)的故障概率、故障位置、時(shí)間分布等特征的分析與論述，結(jié)合文獻(xiàn)[13]對(duì)事件壓縮、聚類以及泛化等規(guī)則的分類和總結(jié)，TFA算法的事件關(guān)聯(lián)主要包括3個(gè)步驟：

a)排重。排除事件集合中大量重復(fù)、相似及冗余的事件，有效地減少事件的數(shù)量。

b)組合。將具備關(guān)聯(lián)性的不同事件歸并為同一事件組，事件集被劃分為互不相交的事件組，充分增強(qiáng)事件語(yǔ)義。

c)分析。對(duì)各事件組分別進(jìn)行推理，得到相應(yīng)的候選故障集，每個(gè)候選故障集中包含所有可能的事件原因。

圖3 TFA算法結(jié)構(gòu)

2)消息探測(cè)。

TFA算法中的消息探測(cè)借鑒了主動(dòng)探測(cè)的思想，并結(jié)合高性能計(jì)算系統(tǒng)天然的節(jié)點(diǎn)通信優(yōu)勢(shì)，可以視作基于消息傳遞設(shè)計(jì)實(shí)現(xiàn)的輕量級(jí)主動(dòng)探測(cè)。

消息探測(cè)的主要目標(biāo)是針對(duì)候選故障集主動(dòng)獲取更多的節(jié)點(diǎn)狀態(tài)信息，以對(duì)多個(gè)故障假設(shè)進(jìn)行篩選，進(jìn)一步地確定故障。消息探測(cè)主要包括三類消息探針：

a)響應(yīng)探測(cè)。判斷與目標(biāo)節(jié)點(diǎn)是否能夠正常通信，即探測(cè)目標(biāo)節(jié)點(diǎn)的可用性。

b)狀態(tài)探測(cè)。負(fù)責(zé)獲取目標(biāo)節(jié)點(diǎn)的特定性能指標(biāo)，如帶寬、CPU利用率等；狀態(tài)探測(cè)常用于節(jié)點(diǎn)的SFLN選擇。

c)日志探測(cè)。要求目標(biāo)節(jié)點(diǎn)返回某個(gè)時(shí)間范圍內(nèi)的消息日志[14]，消息日志通常包含了消息的類型、標(biāo)記、時(shí)間戳以及完成狀態(tài)等信息。

在消息探測(cè)階段，故障定位節(jié)點(diǎn)需要針對(duì)候選故障集使用不同的探測(cè)策略，包括不同的消息探針組合及其執(zhí)行順序。消息探測(cè)的優(yōu)勢(shì)在于探針實(shí)現(xiàn)簡(jiǎn)單，每個(gè)計(jì)算節(jié)點(diǎn)都可作為探測(cè)站發(fā)送探針，并且探針的執(zhí)行不會(huì)增加過(guò)大的網(wǎng)絡(luò)負(fù)載，也無(wú)需占用計(jì)算資源。

無(wú)論是基于規(guī)則的事件關(guān)聯(lián)中的三個(gè)分析步驟，還是消息探測(cè)中探針的組合及其執(zhí)行順序的選擇，都需要得到相關(guān)性規(guī)則庫(kù)的支持。相關(guān)性規(guī)則庫(kù)通常是根據(jù)系統(tǒng)歷史故障記錄中的關(guān)聯(lián)性建立的，與TFA算法的分析效率緊密相關(guān)，可基于關(guān)聯(lián)規(guī)則、頻繁序列模式等算法充分挖掘事件記錄間的關(guān)聯(lián)性。同時(shí)，相關(guān)性規(guī)則庫(kù)也為用戶提供了接口，支持用戶動(dòng)態(tài)部署和更新規(guī)則。以節(jié)點(diǎn)的停機(jī)故障為例，表2給出了部分相關(guān)規(guī)則。

TFA算法的描述見(jiàn)算法2。特別地，雖然針對(duì)不同的候選故障集，消息探測(cè)分別執(zhí)行相應(yīng)的探測(cè)策略并根據(jù)探測(cè)結(jié)果確定故障，但從不同候選故障集推導(dǎo)出的故障可能相同。

算法2 TFA算法。

輸入：癥狀集Symp_Set。

輸出：故障集Fault_Set。

Initialization:Fault_Set=?;

Purify_Set=Event_Purify(Symp_Set);

//排重

Grouping_Set=Event_Grouping(Purify_Set);

//組合

FORi=0 to |Grouping_Set| DO

//對(duì)每個(gè)事件組進(jìn)行分析，得到相應(yīng)候選故障集

Candidate_Faultsi=Event_Reasoning(Groupi);

AddCandidate_FaultsitoCandidate_Fault_Sets;

END FOR

FORi=0 to |Candidate_Fault_Sets| DO

//對(duì)每個(gè)候選故障集進(jìn)行消息探測(cè)

FORj=0 to |Candidate_Faultsi| DO

//對(duì)候選故障集中的多個(gè)故障假設(shè)進(jìn)行分析

IF Msg_Probing(Candidate_Faultsij) THEN

AddCandidate_FaultsijtoFault_Set;

break;

END IF

END FOR

END FOR

Return(Fault_Set);

TFA算法有效緩解了事件關(guān)聯(lián)的效率下降問(wèn)題；同時(shí)，消息探測(cè)在高性能計(jì)算系統(tǒng)中適應(yīng)性強(qiáng)，主動(dòng)、及時(shí)且有針對(duì)性地獲取節(jié)點(diǎn)的運(yùn)行時(shí)狀態(tài)，能夠避免癥狀延遲或丟失對(duì)故障定位準(zhǔn)確度的影響。

表2 與節(jié)點(diǎn)停機(jī)故障相關(guān)的規(guī)則示例

3 實(shí)驗(yàn)評(píng)價(jià)

本章通過(guò)模擬實(shí)驗(yàn)對(duì)MPFL框架的故障定位能力及其對(duì)應(yīng)用程序的性能影響進(jìn)行評(píng)價(jià)。

本實(shí)驗(yàn)的平臺(tái)是一個(gè)具有10個(gè)計(jì)算節(jié)點(diǎn)的典型集群，每個(gè)節(jié)點(diǎn)擁有64 GB內(nèi)存，2個(gè)8核心Intel Xeon處理器，節(jié)點(diǎn)使用InfiniBand高速網(wǎng)絡(luò)互連；操作系統(tǒng)為Red Hat Enterprise Linux Server release 6.3；消息庫(kù)的版本為MVAPICH2- 2.2。

3.1 功能評(píng)價(jià)

高性能計(jì)算系統(tǒng)的故障模式主要有通信網(wǎng)絡(luò)故障、計(jì)算節(jié)點(diǎn)故障及存儲(chǔ)節(jié)點(diǎn)故障[15]，其中計(jì)算節(jié)點(diǎn)的停機(jī)故障是影響并行程序運(yùn)行穩(wěn)定性，甚至引發(fā)系統(tǒng)失效的主要原因[16]，因此，本實(shí)驗(yàn)以定位節(jié)點(diǎn)的停機(jī)故障為目標(biāo)，以證明MPFL框架的故障定位能力。

為模擬節(jié)點(diǎn)的停機(jī)故障，本文對(duì)消息傳遞接口(Message Passing Interface, MPI)的典型開(kāi)源實(shí)現(xiàn)，即MVAPICH源碼進(jìn)行簡(jiǎn)單的修改：在作業(yè)初始化時(shí)，所有進(jìn)程從配置文件獲取模擬節(jié)點(diǎn)停機(jī)故障的進(jìn)程號(hào)，并且進(jìn)程在執(zhí)行消息發(fā)送操作前需滿足要求：

1)若本進(jìn)程模擬故障，不執(zhí)行任何動(dòng)作，直接結(jié)束。

2)若目標(biāo)進(jìn)程模擬故障，對(duì)于探測(cè)消息，默認(rèn)本次探測(cè)超時(shí)并結(jié)束發(fā)送操作；否則不執(zhí)行任何動(dòng)作，結(jié)束操作。

3)本進(jìn)程與目標(biāo)進(jìn)程均正常，正常發(fā)送消息。

這些要求保證了模擬故障進(jìn)程不發(fā)送任何消息，也不可能接收到消息。此外，節(jié)點(diǎn)無(wú)心跳、帶寬下降、CPU利用率過(guò)高等多個(gè)癥狀在程序運(yùn)行時(shí)被注入，以模擬其余系統(tǒng)組件的行為，從而達(dá)到模擬節(jié)點(diǎn)停機(jī)故障的效果。

通常，一個(gè)節(jié)點(diǎn)的停機(jī)故障將導(dǎo)致運(yùn)行在該節(jié)點(diǎn)上的所有程序都終止，因此運(yùn)行一個(gè)測(cè)試程序且僅有一個(gè)進(jìn)程模擬節(jié)點(diǎn)停機(jī)故障即可。同時(shí)，為滿足進(jìn)程間的通信量需求，測(cè)試程序需進(jìn)行多次全交換(all-to-all)通信，并且基于多線程實(shí)現(xiàn)癥狀信息的收集與分析。

假設(shè)程序的進(jìn)程規(guī)模為P，實(shí)驗(yàn)分為N組，每組實(shí)驗(yàn)的進(jìn)程規(guī)模不同，且重復(fù)測(cè)試M次，每次實(shí)驗(yàn)隨機(jī)選擇1個(gè)進(jìn)程Pf模擬節(jié)點(diǎn)停機(jī)故障。本實(shí)驗(yàn)的參數(shù)如表3所示。

表3 功能評(píng)價(jià)的實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)結(jié)果表明，進(jìn)程Pf總是在幾秒的時(shí)間內(nèi)被找到，與通常情況相比，不再需要提供冗長(zhǎng)的運(yùn)行狀態(tài)上下文給用戶進(jìn)行人工分析，用戶只需要關(guān)心故障定位的結(jié)果，這極大地減輕了用戶的負(fù)擔(dān)，因此，可以認(rèn)為MPFL框架是有效的。

實(shí)際上，故障定位的準(zhǔn)確性與相關(guān)性規(guī)則緊密相關(guān)，但規(guī)則庫(kù)往往無(wú)法覆蓋所有的系統(tǒng)異常，故障定位不可能做到100%正確。例如，表2的組合規(guī)則將時(shí)間窗口T內(nèi)的事件劃分為一個(gè)事件組，若T值過(guò)小，由于消息存在延遲性，某些癥狀可能在T之外到達(dá)，導(dǎo)致故障信息不足；若T值過(guò)大，事件之間的關(guān)聯(lián)性將降低，影響故障分析的準(zhǔn)確性。

3.2 性能評(píng)價(jià)

本節(jié)使用美國(guó)航空航天局在NAS(Numerical Aerodynamic Simulation)項(xiàng)目中開(kāi)發(fā)的面向高性能計(jì)算的并行基準(zhǔn)測(cè)試集(NAS Parallel Benchmark, NPB)[17]中的兩個(gè)核心程序：快速傅里葉變換(NPB Fast Fourier Transformation, NPB-FT)與整數(shù)排序(NPB Integer Sort, NPB-IS)對(duì)MPFL的性能進(jìn)行測(cè)試：

1)NPB-FT利用快速傅里葉變換來(lái)解決三維的偏微分方程，其初始階段包含大量的迭代，每次迭代包含大量的all-to-all通信。

2)NPB-IS用于求解基于桶排序的二維大整數(shù)排序，同樣包含大量的all-to-all通信。

實(shí)驗(yàn)分別對(duì)部署MPFL前后的NPB-FT、NPB-IS計(jì)算性能進(jìn)行比較。與3.1節(jié)類似，為了模擬各系統(tǒng)組件發(fā)布癥狀的行為，當(dāng)測(cè)試部署MPFL的NPB-FT和NPB-IS時(shí)，在運(yùn)行時(shí)周期性地注入不同的癥狀。不同的是，本實(shí)驗(yàn)注入的癥狀不會(huì)使得TFA算法推導(dǎo)出故障。

此外，NPB-FT要求進(jìn)程規(guī)模為2的冪次，本實(shí)驗(yàn)將沿用表3所示的參數(shù)設(shè)置，Pf除外，即無(wú)需模擬故障。

實(shí)驗(yàn)結(jié)果如圖4～5所示，本文進(jìn)行了4組對(duì)比實(shí)驗(yàn)，測(cè)試程序規(guī)模(CLASS)選擇A規(guī)模，進(jìn)程規(guī)模依次為16，32，64以及128?？梢钥闯?，MPFL部署前后的NPB-FT、NPB-IS計(jì)算性能無(wú)明顯差距，在圖中用程序的每秒百萬(wàn)次浮點(diǎn)運(yùn)算(Million Floating-point Operations per Second, MFLOPS)進(jìn)行表示。究其原因，這是由于在正常程序的運(yùn)行過(guò)程中不會(huì)觸發(fā)完整的故障分析過(guò)程。同時(shí)，測(cè)試程序的性能減速?zèng)]有隨著進(jìn)程規(guī)模的持續(xù)增加而呈上升趨勢(shì)。經(jīng)過(guò)統(tǒng)計(jì)分析，部署MPFL僅僅分別給NPB-FT和NPB-IS帶來(lái)了5.68%和2.12%的運(yùn)行開(kāi)銷，這說(shuō)明MPFL對(duì)系統(tǒng)的性能影響較小，具備較強(qiáng)的可擴(kuò)展性。

圖4 NPB-FT測(cè)試結(jié)果(CLASS=A)

圖5 NPB-IS測(cè)試結(jié)果(CLASS=A)

4 結(jié)語(yǔ)

故障定位作為故障管理的核心，對(duì)提高系統(tǒng)可靠性有重要意義，但當(dāng)前的故障定位技術(shù)難以有效地直接應(yīng)用于高性能計(jì)算系統(tǒng)。本文首次將故障定位問(wèn)題與消息庫(kù)緊密聯(lián)系起來(lái)，且考慮充分利用各系統(tǒng)組件獨(dú)立獲取的異常信息，提出一種基于消息傳遞的故障定位框架MPFL，并設(shè)計(jì)實(shí)現(xiàn)基于故障定位樹(shù)的故障檢測(cè)與分析算法，能夠?yàn)楦咝阅苡?jì)算系統(tǒng)提供實(shí)時(shí)的輕量級(jí)分布式故障定位服務(wù)。本文通過(guò)定位模擬的節(jié)點(diǎn)停機(jī)故障對(duì)MPFL的功能進(jìn)行了原型實(shí)驗(yàn)驗(yàn)證，并分別利用NPB-FT與NPB-IS基準(zhǔn)測(cè)試程序?qū)PFL進(jìn)行了性能評(píng)價(jià)。實(shí)驗(yàn)結(jié)果表明，MPFL框架是有效的，并且具備較強(qiáng)的可擴(kuò)展性。

下一步的工作重點(diǎn)包括：1)對(duì)歷史故障經(jīng)驗(yàn)進(jìn)行更深度的挖掘以提高故障定位的準(zhǔn)確性；2)除消息庫(kù)外，開(kāi)發(fā)網(wǎng)絡(luò)管理、操作系統(tǒng)等系統(tǒng)組件對(duì)MPFL框架的支持；3)針對(duì)MPFL框架的故障定位準(zhǔn)確率、性能開(kāi)銷、可擴(kuò)展性等方面進(jìn)行更全面的評(píng)價(jià)。

References)

[1] ZHENG Z, LI Y, LAN Z. Anomaly localization in large-scale clusters [C]// Proceedings of the 2007 IEEE International Conference on Cluster Computing. Piscataway, NJ: IEEE, 2007: 322-330.

[2] AVIZIENIS A, LAPRIE J C, RANDELL B. Fundamental concepts of dependability [R]. Newcastle: LAAS-CNRS, 2001: 4.

[3] JORDAAN J F, PATEROK M. Event correlation in heterogeneous networks using the OSI management framework [C]// Proceedings of the IFIP TC6/WG6.6 Third International Symposium on Integrated Network Management with Participation of the IEEE Communications Society CNOM and with Support from the Institute for Educational Services. Amsterdam: North-Holland Publishing Co., 1993: 683-695.

[4] NATU M, SETHI A S. Active probing approach for fault localization in computer networks [C]// Proceedings of the 2006 4th IEEE/IFIP Workshop on End-to-End Monitoring Techniques and Services. Piscataway, NJ: IEEE, 2006: 25-33.

[5] LGORZATA STEINDER M, SETHI A S. A survey of fault localization techniques in computer networks [J]. Science of Computer Programming, 2004, 53(2): 165-194.

[6] KATKER S, PATEROK M. Fault isolation and event correlation for integrated fault management [C]// Proceedings of the 5th IFIP/IEEE International Symposium on Integrated Network Management. Berlin: Springer, 1997: 583-596.

[7] CHENG L, QIU X, MENG L, et al. Efficient active probing for fault diagnosis in large scale and noisy networks [C]// Proceedings of the 29th IEEE International Conference on Computer Communications. Washington, DC: IEEE Computer Society, 2010: 1-9.

[8] PATIL B M, PATHAK V K. Survey of probe set and probe station selection algorithms for fault detection and localization in computer networks [J]. IEEE Transactions on Networks and Communications, 2015, 3(4): 57.

[9] 孟洛明,黃婷,成璐,等.支持多故障定位的探測(cè)站點(diǎn)部署方法[J].北京郵電大學(xué)學(xué)報(bào),2009,32(5):1-5.(MENG L M, HUANG T, CHENG L, et al. Probe station placement for multiple faults localization [J]. Journal of Beijing University of Posts and Telecommunications, 2009, 32(5): 1-5.)

[10] HUKERIKAR S, DINIZ P C, LUCAS R F, et al. Opportunistic application-level fault detection through adaptive redundant multithreading [C]// Proceedings of the 2014 International Conference on High Performance Computing & Simulation. Piscataway, NJ: IEEE, 2014: 243-250.

[11] GARDNER R D, HARLE D A. Network fault detection: a simplified approach to alarm correlation [C]// Proceedings of the 16th IEEE Global Telecommunications Conference. Washington, DC: IEEE Computer Society, 1997: 44-51.

[12] SCHROEDER B, GIBSON G. A large-scale study of failures in high-performance computing systems [J]. IEEE Transactions on Dependable and Secure Computing, 2010, 7(4): 337-350.

[13] JAKOBSON G, WEISSMAN M. Real-time telecommunication network management: extending event correlation with temporal constraints [C]// Proceedings of the Fourth International Symposium on Integrated Network Management IV. London: Chapman & Hall, 1995: 290-301.

[14] LEMARINIER P, BOUTEILLER A, KRAWEZIK G, et al. Coordinated checkpoint versus message log for fault tolerant MPI [J]. International Journal of High Performance Computing and Networking, 2004, 2(2/3/4): 146-155.

[15] SCHROEDER B, GIBSON G A. Understanding failures in petascale computers [C]// Proceedings of the 6th Scientific Discovery through Advanced Computing Conference. Bristol: IOP Publishing Ltd, 2007: 2022-2032.

[16] 武林平,孟丹,梁毅,等.LUNF——基于節(jié)點(diǎn)失效特征的機(jī)群作業(yè)調(diào)度策略[J].計(jì)算機(jī)研究與發(fā)展,2005,42(6):1000-1005.(WU L P, MENG D, LIANG Y, et al. LUNF—a cluster job schedule strategy using characterization of nodes’ failure [J]. Journal of Computer Research and Development, 2005, 42(6): 1000-1005.)

[17] BAILTY D, HARRIS T, SAPHIR W, et al. The NAS parallel benchmarks 2.0: NAS- 95- 020 [R]. Washington: NASA Ames Research Center, 1995: 12.

This work is partially supported by the National Key Research and Development Program of China (2016YFB0200502).

GAOJian, born in 1992, M. S. candidate. His research interests include parallel computing, runtime system.

YUKang, born in 1987, Ph. D., assistant engineer. His research interests include parallel computing.

QINGPeng, born in 1979, M. S., senior engineer. His research interests include parallel compilation, runtime system.

WEIHongmei, born in 1968, Ph. D., senior engineer. Her research interests include parallel computing, parallel compilation.