基于动态时间窗口的异常数据周期分析模型研究

姜 勇 韦朝奥 陈绍辉 陈 亮 马 力

（云南电网有限责任公司大理供电局，云南大理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.