基于動態時間窗口的異常數據周期分析模型研究

姜 勇 韋朝奧 陳紹輝 陳 亮 馬 力

（云南電網有限責任公司大理供電局，云南大理671000）

0 引言

實際生產過程對計算能力的需求在不斷增長，基于此情況，很多機構在生產設施中設計以及部署了擁有數十萬堆核心的大型并行HPC系統[1]。然而，系統中增加的組件數量使得系統范圍內的MTBF（平均故障間隔時間）在一定范圍內呈現減少趨勢，從而影響了生產設施的可靠性[2]。目前大多數大型應用程序皆是根據檢查點重啟技術來恢復修正錯誤信息，且組件中所使用應用程序的每一個錯誤都可能在最后一個檢查點的應用程序重新啟動過程中結束。因此最新研究認為這種方法不能擴展到未來的Exascale系統使用過程中[3]。另外，近年來，相關研究的重點主要是對系統行為進行表征，從而采取主動監測措施來對錯誤信息進行恢復修改。為此，監測系統需要一個可靠的預測系統來提供系統的生產信息和位置信息。然而，如何快速準確地預測給定時間內系統的各項事件數據仍是當前系統應用所面臨的一個問題。

為了解決這個問題，本文提出了一種生成事件信息的新方法。此方法的目的是通過提取經常發生的事件序列來對正常事件行為及異常事件行為進行預測。而且這個方法也可以通過使用不同的時間窗口來分析不同事件之間的時間間隔，從而對每個事件的日志段進行分析。同時認為，系統運行時的序列更新對任何給定時刻事件的行為反映與訓練階段中序列的初始提取都是重要的，這個結果將在實驗部分進行驗證。

目前在研究過程中大多使用一種預先確定的時間窗口來對規則進行研究和提取[4]。然而，對于所有的事件類型以及整個系統的生命周期來說，只有一個固定的時間間隔是不現實的。基于這種情況，本文提出了一種基于動態時間窗口的異常數據周期分析模型。此模型根據系統每個事件的行為來調整分析系統運行的時間間隔，而且也研究每個事件類型中相鄰事件之間所生成的所有事件，從而預測具有很強相關性的事件。

1 事件預測相關研究

近幾年主要是通過使用統計及數據挖掘來對大型系統生成的日志文件進行分析。當然，并不是所有的研究都依賴于日志文件，有的研究則主要考慮系統除日志文件以外的不同特性。例如，在文獻[5]中對系統性能指標進行檢查，然后使用概率方法建立事件之間的相關性。在文獻[6]中，通過一種方法來預測不同類別的系統事件故障，這種方法能夠預測80%的內存和網絡故障及47%的應用程序故障。然而其將這些故障分為五類，通過對預測系統進行了解，我們發現這五個類別不足以概括所有類型的故障，如預測的內存錯誤類型也是常見的故障類型。

除此之外，有關事件預測的其他方法主要是使用數據挖掘算法來提取導致失敗的事件序列，并使用允許事件預測的不同方法來對其進行存儲。例如，文獻[7]中使用了一種改進的Apriori方法和基于PCA的算法[8]，這兩種方法皆被用于Hadoop，而且其每個生成的消息都具有一個任務以及一條工作信息。我們將會證明這個方法對于HPC系統日志是不實用的，因為沒有很多消息共享通用的參數。

分析日志在事件預測過程中最為常用，其中一種常見方法就是通過對以往異常事件和致命事件之間的相關性進行檢查，進而了解未來失敗預測的模式[9]。文獻[9]中依據固定時間窗口來對規則進行提取，而且其只對致命事件提供預測。當然，分析日志也會在致命事件和非致命事件之間產生關聯規則，從而使得預測窗口大到足以采取主動措施。然而對BlueGene/P系統的分析表明，這種方法僅能捕獲大約15%的故障，而誤報率大約為60%。

另一個常用方法是使用故障日志[10]，因為在故障日志中可以對過去以及未來的故障信息進行合理有效的累積分析。同時，基于這些特性，可以應用不同的決策樹分類器來預測故障和固定時間窗口。但這種方法不是很普遍，因為不是所有的系統都有故障日志。然而其預測結果非常好，可以達到大約70%的精度。

結合以上事件預測的相關研究可以發現，所有分析系統日志文件的方法都會利用一個預處理步驟來對系統時間和空間中的事件進行過濾分析，而且主要使用固定時間窗口來對事件相關性進行搜索。但在預測過程中這些研究方法只考慮少量的故障類別，并且需要一個最新的故障日志，同時在對系統事件進行預測時必須由系統管理員輸入工作信息。

2 系統模型設計

我們的系統分析模型主要由兩部分組成，即在預處理條件下提取頻繁事件初始序列的訓練方法和提供預測的在線模塊。該模型主要從日志文件中收集數據，然后對其解析并進行預處理，當提取出故障類別并過濾重復事件后，便可通過挖掘模塊對數據進行分析，最終生成不同事件之間的相關鏈。而這項任務如果想要有效進行，則需在系統模型能夠快速提取序列和收集多少信息之間找到一個平衡，以便使得相關鏈具有較高的精確度。

本節將分別對系統分析模型中涉及的事件預處理、提取頻繁事件序列以及在線模塊進行介紹，從而展示基于動態時間窗口的異常數據周期分析模型的運行特點。

首先，對事件預處理作簡要介紹。在預處理過程中，系統優先對原始格式的日志進行解析，從而生成一個模板列表。隨后使用分層事件日志管理器[11]從本質上提取系統生成的所有事件類型，包括異常和正常的事件信息，繼而通過提供不同類型的網絡事件來生成具有更細粒度的模板。我們知道組件的故障可能導致存儲大量事件信息的日志記錄遭到破壞，因為從以往的研究中發現內存和處理器緩存失敗通常會導致相關組件在不到一天的時間內生成成百上千條消息[12]。

為了在預處理過程中優化空間濾波，分析研究了不同傳播位置所對應的事件信息。分析后，對日志記錄進行二次預測，并提取出每個模板的傳播序列，隨后將傳播序列定義為不同位置上傳播消息的次數與特定模板出現總次數之間的比率。但具有傳播序列的模板更有可能出現在多個位置，并在分析過程中不易被過濾。

其次，對頻繁事件序列的提取過程進行敘述。頻繁事件序列通常在具有不同關聯的系統事件中被提取出來，例如在非故障事件和故障事件之間由不同組件生成的安裝信息，又如故障事件中警告消息鏈的產生。而且在序列提取的過程中可以發現兩個相關事件之間的時間總會延遲幾秒到幾小時不等，延遲的時間可以是常數，也可以呈現變化趨勢。例如“工作開始”和“工作結束”在某些情況下可能會同時發生，也可能在相隔幾分鐘之后才陸續發生。基于此種情況，分析系統在頻繁事件序列提取過程中主要利用如下算法進行分析研究（表1）。

該算法將會生成頻繁的k-length項集，即表示k種不同事件的頻繁序列。同時對于每個事件類型，都會將所對應的時間間隔定義為對應模板的相鄰事件之間的時間窗口。而且可以發現該算法的輸出由一組頻繁的序列表示，這樣輸出的好處在于可使HPC系統不必使用中央時鐘來同步節點。

表1 算法偽代碼

最后，對在線模塊的預測進行說明。在對在線模塊進行預測時需要使用前一階段提取的頻繁事件序列，然后將其存儲在一個簡單的列表結構中，這個列表結構中也保存有系統的內存信息。同時根據列表中所有過去事件的信息對在線模塊中每個事件元素進行預測。即使存在較低的時間標準偏差，也能夠對在線模塊進行有效預測。

3 系統實驗分析

本節將建立實驗，并對實驗的設計預測思路進行介紹，最后通過實驗所得的合成記錄來驗證基于動態時間窗口的系統分析模型在預測過程中的優點。

將分析模型中的預測精確度定義為修正的預測事件總數與預測事件的總數之比，而精確度的確定則基本上表示了所生成序列是可信的。但如果這個事件是由系統生成的，那便需要構建一個正確的預測事件，而且這個預測事件需要考慮到標準偏差。為此，通過兩個定義來對相關誤差進行一定范圍內的修正，第一個定義是修正預測事件的數量超過現有日志和事件的總數；第二個定義為通過計算修正后的預計數量來對總數、類型以及比率相同的多個事件進行分析。為了使預測結果合理且具有說明性，從而滿足驗證要求，在實驗進行過程中通過選擇參數來創建不同的測試集，繼而使事件總數和生成的行列總數滿足實驗要求的比率關系。

基于以上情況分析，主要進行了兩種實驗。在第一個實驗中，對三個真實系統的日志文件進行分析，然而在實驗過程中發現很難對系統事件進行有效預測，因為系統中某些序列所包含的事件總列表是未知的。為改善這個問題，進行了第二種實驗，其主要是在合成原木上利用HPC系統隨機生成的特征來進行。我們據此構建了一個日志生成器，其可將事件的數量、事件序列的數量、每個序列中事件的最小和最大數量以及每個序列的最小和最大重復次數作為輸入項，從而將序列隨機地繪制在不同的時間段中。

由于在實驗過程中創建了不同的測試集，且利用日志生成器生成了針對系統的消息日志，所以在最后的合成記錄中便發現不同系統之間的精確度差異是由許多因素決定的。例如因為多次執行正常的行為序列使得在序列中引入了錯誤事件類型，也就是說當系統生成的事件類型增多，那么所提取的事件序列的精度便不再準確。而且，合成記錄顯示系統日志想要有效，就必須具有消息共享時所應具備的參數，但基于Apriori方法和基于PCA的算法只具有一個任務和一條工作信息，所以這兩種方法并不適用于HPC系統日志分析。同時由于序列更新有利于HPC系統日志分析，所以系統運行時的序列更新對任何給定時刻事件的行為反映與訓練階段中序列的初始提取都是重要的。除此之外發現，當系統分析過程中所擁有的事件序列由2～3個事件類型組成時，其預測精度相對較高，最終所得結果也最合理，且之后的預測值也可以得到平衡。

4 結語

本文提出了一種基于動態時間窗口且可利用大型HPC系統生成不同事件類型的系統分析模型，這種模型能夠在不考慮時間延遲的條件下提取事件之間的相關性，而且可對序列進行更新。同時在此系統模型中對事件進行分析的粒度比其他相關研究都要精細，所以不會影響預測的準確性。最后通過分析實驗所得的合成記錄了解系統中影響序列精度的相關特性，并且驗證了分析系統在基于動態時間窗口的條件下能夠預測絕大多數的事件，而且在較低的事件粒度上同樣有著較高的預測精度。

[1]The TOP500 Supercomputer List[EB/OL].https://www.top500.org/lists/2017/11/.

[2]KERBYSON D J,HOISIE A,WASSERMAN H J.Use of Predictive Performance Modeling During Large-scale System Installation[J].Parallel Processing Letters,2005,15(04):387-395.

[3]ELNOZAHYE,PLANKJS.Checkpointingforpeta-scale systems:a look into the future of practical rollbackrecovery [J].IEEE Transactions on Dependable and Secure Computing,2004,1(2):97-108.

[4]CHUAH E,KUO S H,HIEW P,et al.Diagnosing the Root-Causes of Failures from Cluster Log Files[C]//International Conference on High Performance Computing,2010:1-10.

[5]SAHOO R K,OLINER A J,RISH I,et al.Critical Event Prediction for Proactive Management in Large-scale ComputerClusters[C]//International conference on Knowledge discovery and data mining,2003:426-435.

[6]LIANGY,ZHANGY,JETTEM,etal.BlueGene/LFailure Analysis and Prediction Models[C]//Proceedings of the International Conference on Dependable Systems and Networks,2006:425-434.

[7]LOUJG,FUQ,WANGY,etal.MiningDependencyin Distributed Systems through Unstructured Logs Analysis[J].Acm Sigops Operating Systems Review,2010,44(1):91-96.

[8]XU W,HUANG L,FOX A,et al.Online System Problem Detection by Mining Patterns of Console Logs[C]//IEEE International Conference on Data Mining,2009:588-597.

[9]ZHENGZ,LANZ,GUPTAR,etal.APracticalFailure Prediction with Location and Lead Time for Blue Gene/P[C]//InternationalConference on Dependable Systems and Networks Workshops,2010:15-22.

[10]NAKKA N,AGRAWAL A,CHOUDHARY A.Predicting Node Failure in High Performance Computing Systems from Failure and Usage Logs [C]// IEEE International Symposium on Parallel & Distributed processing workshop&phd forum,2011:1557-1566.

[11]GAINARU A,CAPPELLO F,TRAUSAN-MATU S,et al.Event log mining tool for large scale HPC systems[C]//International Conference on Parallel Processing,2011:52-64.

[12]HEIEN E,KONDO D,GAINARU A,et al.Modeling and Tolerating Heterogeneous Failures in Large Parallel Systems[C]//High Performance Computing,Networking,Storage&Analysis,2011:1-11.