2.6 系统故障根源跟踪

系统日志分析除了要找出异常和故障的系统日志及事件外，还要找出故障出现的根源。只有当系统维护人员了解故障根源，才能对症下药，彻底解决这个问题。

在实际的大型企业信息环境下，信息平台通常架构于多层系统之上，且每一层可能也有多个并行计算的服务器。图2-9显示了一个典型的企业多层信息系统架构。这个架构包含了4层服务器：Web服务器、应用程序服务器、数据库引擎和存储服务器。前一层的服务器依赖于后一层。当后一层的服务器出现故障的时候，前面一层服务器也可能产生相应的故障提示。如图2-9所示，如果磁盘陈列存储发生故障，其依赖的数据库引擎会因为数据文件无法读取而上报异常。应用程序服务器依赖数据库系统查询信息也因此无法完成，同时导致Web服务器的响应无法正常返回。最终表现为给用户的就是网页上的错误提示。

网页上的报错可能是由这4层服务器中任意一层出现的故障导致的，在实际运行系统中不可能花大量时间去排除每一层服务器上的硬件和软件问题。系统日志可以提供高效且有力的故障根源跟踪。若知道日志事件A会触发事件B，然后事件B会触发C，以此类推，则从观察日志数据事件发生的链条即可知道故障的根源是由哪个事件触发的。然而，在实际复杂和动态的系统内，要知道各种系统模块和日志事件之间的相互依赖关系并不容易。以企业存储系统的配置为例，通常一个大型应用程序要访问的数据源都不只包含一个存储设备。比如客户关系数据会保存在关系数据库内，海量历史操作数据会保存在分布式文件系统（如 HDFS[45]）内，多媒体数据保存在专用的 EMC 并行存储设备里等。不同应用程序的数据源各自不同，可能有交织，也可能完全独立。

实际大型企业的应用程序和数据源部署网络通常十分复杂，而且变化不断，对于系统管理员来说，在很多情况下并不是透明的。一个原因是涉及软件系统和数据的隐私问题。现实世界里很多系统维护（IT Service）都是外包给第三方企业来做的。原企业不一定愿意公开所有的内部信息给第三方企业。另一个原因是实际系统维护流程里很难应付时刻变化的存储网络，即便是原企业自己的开发人员也只了解和自己相关的应用程序和存储设备之间的关系。不同部门不同项目组对存储设备的需求千差万别，统一的规划和管理反而限制各个部门的运行效率。很多情况下大型企业IT 环境内的存储设备，对于管理员来说是一个黑盒子（如图 2-10 所示）。除了存储设备网络外，还有各种通信网络和部署网络等也有类似的问题。因此，在这样的环境下如果出现系统故障，追溯故障根源并不是一件容易的事情。本节将介绍如何通过数据挖掘技术分析系统运行日志，揣测不同设备和系统模块之间的依赖关系。

2.6.1 日志事件的依赖性挖掘

2.6.1.1 关联、相关、因果与依赖

在数理统计上，随机变量具有依赖性和具有相关性是两个不同的概念。依赖性可以理解为在物理上两个随机变量的取值具有某种内在联系。这种内在联系的对象是观察的物体，而不是随机变量采样的取值。相关性则是随机变量取值上的某种关系。确切来说，相关性就是指这些随机变量的联合分布具有同高同低的或者对立相反的现象。有相关性的两个随机变量不一定有依赖性，因为它们也可能是由巧合导致的。有依赖性的随机变量也不一定具有相关性，因为这种依赖关系并不一定导致两个随机变量在联合概率分布上有特别的表现特征。关联性就是指依赖性，不是独立的。因此，关联性并不是指相关性。因果关系是这种依赖性的一种具体形式。例如日志事件A的产生导致了日志事件B的发生。但是现实世界里面并不只有因果关系的依赖，也可能有其他关系的依赖，比如刚提到的两个随机变量虽同时产生，但有互相牵制和抵触的依赖关系。

事件的相关性并不代表事件的依赖关系或者因果关系。例如在日志数据上，事件A和事件B具有相关性，并不代表事件A引发事件B，或者事件B引发事件A。有可能是一个未知的事件C同时引发事件A和B，也可能事件A和事件B的相关性纯属巧合。本节涉及的算法都有一个大前提假设，那就是具有相关性的事件很有可能是具备依赖性或者因果性的。因此，通过找相关性来寻找依赖关系或者因果关系，是一种缩小搜索范围的办法，而并非一种判定依赖和因果的准则。对于数据挖掘算法来说，能够分析的仅仅是观察得到的数据。计算机的输入也只能是数据，而无法真正了解数据产生的物理规律，因此也无法真正判定产生数据的随机变量是否真的具有关联性。所以在实际问题的分析中，依然需要人工对找出的结果做进一步的判定。本章后面介绍的各种日志事件的关联和依赖的挖掘算法，都是停留在发现数据分布的表现上，而不是真正对产生日志的系统模块之间是否具有依赖性下定论。

2.6.1.2 离散型和连续性的相关性

数据挖掘中寻找相关性的办法大部分都是基于大量事件的观察。系统日志事件的相关性分析方法根据数据类型分为两种：一种是基于时序数据（Time Series）的相关性；一种是基于离散数据的相关性。在系统日志事件里，有很多系统测量值，诸如CPU使用率、磁盘使用率、虚拟内存交换速率等，都是很重要的连续观察值。值得注意的是，存储在计算机内的数据都是离散的值。这里指的连续值是指一个测量值的数据类型。离散数据可以表示一个事件或者一个现象是否出现以及它的类别等。例如，当Java应用程序抛出一个异常（Exception），这个观察现象就可以用离散值来表示。

相关性的日志数据如图2-11所示。

图2-11（a）是一个典型的时序数据上的相关性展示。图2-11（a）中有两个时间序列的数据：数据库服务器的磁盘I/O速率和网络I/O速率。数据库的数据消费者和生产者都来自于应用服务器，所以大部分数据库服务器的主要任务就是读写硬盘和传输数据，因此这两个时序数据具有很强的相关性。当数据库忙碌的时候，两个序列的值同时变高；当数据库空闲的时候，两个序列的值同时变低。这种相关性也常被用来做异常检测的判定。

图 2-11（b）显示的是一个离散型的时间相关性。通过日志抽取可以发现，数据库deadlock的日志事件和Web服务器的500异常错误事件始终同时出现，从而可以推断Web服务器的500错误主要是由数据库deadlock导致的。离散的日志事件可视化到一个二维坐标图里就是一系列的点，每个点代表一个事件的发生。

2.6.1.3 相关性的评估

离散型的日志事件相关性挖掘目标不是挖掘数值上的相关性，而是对事件发生的时间前后做相关性的分析。在数理统计与概率论中，相关性的定义通常是指两个或者多个随机变量之间分布的关系。例如现在有两个随机变量X和Y，常用的Pearson相关性度量为：

其中corr(X,Y)表示X和Y的协方差，σ X、σY是X、Y的标准方差，μX、μY是X、Y的数学期望，E(·)表示求数学期望。那么为什么Pearson相关性要这么计算呢？假设X和Y的独立分布都是已经给定的，那么σX和σY都是固定值，唯一可以决定相关性大小的则是E[(X −μX)(Y−μY)]。通过排序不等式，我们知道顺序和≥乱序和≥逆序和，反映到（X,Y）的联合分布的时候就是：当X和Y同时取大或取小的时候，E[(X−μX)(Y−μY)]的值是最大的（顺序和），当X取大但Y取小的时候（乱序和）,E[(X−μX)(Y−μY)]则较小。所以，当E[(X −μX)(Y−μY)]较大的时候，意味着X和Y大多数时候是同时取大取小，因此这个时候X和Y就有直观意义上的相关性。在离散型的日志事件里，定义的随机变量可以看作只有0和1两个值，0表示这个事件没有发生，1表示这个事件发生。不同的事件类型用不同的随机变量表示，但是取值都只有0和1。传统的Pearson度量方法在此依然可用。

2.6.1.4 事件依赖挖掘

在数据挖掘研究领域，很多事件相关性挖掘更多是发现一种关联性的模式（Pattern）。在统计上，关联性模式的挖掘除了要求不同事件在联合分布上的相关性外，还要求这种观察现象是频繁出现的，不是偶然导致的。直观来说，在对随机变量依赖性的推测上，频繁出现的相关性会比偶尔出现的相关性更加可靠。偶尔出现的相关性很可能就是偶然导致的，而非两个实际变量内在物理牵连导致的。

此外，数据挖掘与统计学里的研究侧重点也有不一样的地方。数据挖掘算法除了关注挖掘的数学模型外，也十分关注如何快速地在大量高维的数据集中找到满足这个数学模型的参数。很多现实的数据集通常都是海量数据。“快速”在处理海量数据的算法中不单单是快几秒钟或者几分钟的意义，更多是决定了一个分析任务能够顺利完成与否。例如一个O(N log N)算法恰好1 s运行完成， N=109，而O(N2)的算法运行时间则是109/log(109)个1 s，可能需要超过30多年才能完成。因此，本章后面提到的各种针对日志数掘的挖掘算法都涉及算法运行效率上的考虑。

最早分析序列数据上的事件依赖模式的论文是1995年出版的参考文献[46]。算法寻找的目标就是寻找频繁出现在一起的事件类型集合。该算法的大致思想是将序列数据按照事件分成多个可以重叠的时间窗口。如果事件A和事件B经常出现在同一个时间窗口，则可以认定事件A和事件B是频繁出现的事件类型集合，从而揣测他们可能具有一定依赖性。其中，频繁的度量是：

其中ϕ是事件类型集合，S是序列数据，ω是时间窗口的长度，αω(S,ω)是S所有时间窗口的集合，|{W∈αω(S,ω),|W|=ϕ}|则表示所有时间窗口里包含ϕ的子集。算法需要用户给定一个阈值minfr。当频率大于或等于这个阈值的时候，这个ϕ才能成为频繁事件的集合。算法主要解决的问题是在事件类型组合很多的情况下，需要计算的ϕ则会很多。算法直接利用关联规则挖掘的 Apriori 性质来做搜索剪枝[32]：若ϕ不是频繁的，则其超集也不可能是频繁的。

2.6.1.5 时间窗口

后来针对序列数据的研究者提出了不同的改进算法。例如，频繁出现在一起的事件并不意味着有依赖性。例如在日志数据里，周期性的状态显示日志事件肯定是频繁出现的，它可能跟任何一个频繁事件形成频繁事件的集合。但是，它们两者并没有依赖性。因此，通常还需要引入其他指标来判定找出的模式是否真的具有一定意义。人们后来逐步用lift和Pearson相关度量等其他指标（除去支持度和置信度）来评判频繁集合。此类的改进方法与后来对关联规则挖掘算法的改进基本没有太大区别。在序列数据挖掘中，时间窗口这个概念是与普通关联挖掘算法最大的不同之处。参考文献[46]要求用户给定这个时间窗口的长度，然后有可能用户并不知道合适的窗口宽度。如果时间窗口宽度过小，有可能会丢掉真正的依赖性模式；如果时间窗口过大，有可能找到大量无意义的相关事件模式[47]。

图2-12显示的是一个时间窗口的宽度过小的例子。抛开时间窗口，可以明显看出图2-12中的事件A和事件B具有一定的相关性。然而当时间窗口的宽度过小，任何一个时间窗口都无法同时包含一个事件A和一个事件B，于是按照之前的算法，事件A和事件B的相关性就会被丢失。图2-13显示的是一个时间窗口的宽度过大的例子。图2-13中除了事件A和事件B外，还有其他一些分布在时间轴上的不相关事件。然后，w过大，包含事件A的窗口几乎都包含了至少一个其他类型事件。于是按照之前的算法，任意两个事件都会被判定为相关的。一个极端的例子就是当ϕ无穷大的时候，无论数据内的各类事件怎么分布，任意一个事件类型的集合都会被判定成为具有相关性的。

寻找合理时间窗口的首要问题是判定一个给定的时间窗口是否合理，其次才是如何寻找。参考文献[48]介绍一种基于统计检验的方法，后来被很多人采用。参考文献[48]认为单看时间窗口的宽度是没有意义的。时间窗口是否合理还需要看定义的阈值minfr大小。直观来说，当窗口很大的时候，无论两个事件是否有依赖性，同时包含两个事件的窗口个数都会增多，因此这个minfr应该设置得更大一些；当窗口很小的时候，无论两个事件是否依赖，包含两个事件的窗口个数都会减小，那么minfr应该设置得更小一些。因此，需要观测的是（ω,minfr）这个两个参数的组合是否合理。

给定一个时间窗口，宽度为ω，阈值为minfr。通过上述算法，我们找到Nco个时间窗口同时包含了事件 A 和事件 B,Nco≥minfr。按照之前的算法逻辑，事件 A和事件B可以被认定具有依赖关系。那么需要验证的就是他们是否真的有统计意义上的依赖关系。可以提出一个相反的假设：事件A和事件B不是真的具有依赖关系。那么事件A和事件B其实是独立产生的。在统计学家的眼里，世界上任何一个事件发生的可能性都是存在的，只是概率多少的问题。那么接下来需要知道的就是基于这个假设，找到Nco个时间窗口同时包含了事件A和事件B的概率是多少。如果这个概率很低，比如小于5%，那么我们就有信心（置信度）否定这个假设，从而认为事件A和事件B不是独立产生的。于是，问题转换成如何计算在事件A和事件B独立的情况下，找到 Nco个时间窗口同时包含两个事件的概率。要产生两个独立的事件序列其实很容易，只需要用两个独立的随机变量不断模拟生成事件A和事件B即可。但是需要注意的是，针对事件A和事件B模拟生成的序列数据需要保证事件A和事件B的采样频率不变。可以用这样的模拟方法生成很多条由独立的事件A和事件B序列组成的序列数据，记为S1,…,Sm。对第i个模拟数据序列，计算出有Ni个时间窗口同时包含事件A和事件B（在时间窗口宽度为ω的情况下）。于是得到了一堆数值N1,…,Nm。这m个数值被看作由另外一个随机变量产生的，那么通过这m个数值可以拟合出这个随机变量的概率分布。最后把之前根据实际数据算出来的Nco映射到这个概率分布上，就可以得到在事件 A 和事件 B 独立的情况下找到 Nco个时间窗口同时包含了两个事件的概率。

如表2-1显示的就是一个N1,…,Nm的取值分布例子。如果Nco=20，对应的概率就是20.1%，大于5%，所以我们不能否定这个假设的存在。换句话说，我们没有把握确定事件A和事件B是不是有依赖关系的，因为即便在独立情况下，出现Nco=20的概率也高达20.1%。如果Nco=105，对应的概率就只有0.2%。换句话说，在独立的情况下，不太可能出现Nco=20，所以在l−0.2%=99.8%的置信度情况下，可以认为这个独立的假设是不成立的，即事件A和事件B是存在依赖关系的。

在实际计算的时候，可能需要产生很多模拟独立的序列才能产生完整的N1,…,Nm的概率分布，否则某些整数取值可能没有被覆盖到，于是出现的次数都是0，但是这并不代表其概率应该是0。参考文献[48]实际使用的是X方检验的方法，计算一个统计变量X2：

其中，N是时间窗口的个数，P是指在事件A和事件B独立的情况下，一个时间窗口同时包含A和B的概率。χ2方检验中X2满足χ2分布。而χ2分布是已知的，所以只需要计算出X2的值，然后查χ2分布表就可以知道之前假设发生的概率。

还有一些情况不要求两个关联的事件同时在一个时间窗口。例如我们描述：“事件B通常都发生在事件A之后的5~10 s内”。那么，这个时间窗口并不需要同时包含事件A和事件B。它只需要包含每个事件发生之后的5~10 s即可，然后观测初始事件是不是事件A，而不是观测整个连续10 s内是否同时包含事件A和事件B。如果把时间窗口设置成连续的10 s，虽然能够同时包含互相关联的事件A和事件B，但是如上所述，过宽的时间窗口会导致大量的假关联。如果用统计检验的办法，就需要提高阈值minfr，那么这个阈值并不反映5~10 s这5 s的实际情况。

如图2-14所示的时间窗口除了有宽度参数ω外，还有一个位移参数s。所描述的时间窗口就是[s,s+ω]，表示事件B会在事件A之后的s~s+ω个时间单位内发生。这里以A→[s,s+ω]B来表示这种关系。如果A=B，那么这里的[s,s+ω]就是事件A的发生周期。之前的各种数据挖掘的文献针对时序数据和事件数据提出了各种不同的事件发生模式。一个有趣的现象是，当我们对这里的时间窗口加以一定约束时，会发现大部分这些事件模式都可以划归到一个简单的事件依赖关系和一个带约束的时间窗口（见表2-2）。

给定一个时间窗口的参数ω，通过上述统计检验的方法可以找到一个合理的阈值minfr。但是参数s、ω的取值范围通常都很大。在最坏的情况下，s和ω的取值个数都是O(n2)，其中n是总共数据集内时间戳的个数[47]。那么s和ω的组合情况个数就高达O(n4)了。显然，我们不可能一个一个去测试所有的组合情况。通常在系统日志数据内，记录的事件集都相当庞大。很多生产机在运行的时候，除了异常事件生成日志外，各种状态变化，甚至Web请求都会引发日志事件的产生。在这种大数据集的情况下，一个一个的组合测试方法是不可行的。参考文献[49]介绍了一种基于时间间隔的聚类算法。给定两个事件类型A和B，通过扫描数据序列，找到每个事件A和事件A之后第一个事件B之间的时间间隔，记为intervali，其中i是事件A的序号，i=1,2,…。如果事件A和事件B有关联性，那么其合理的时间窗口[s,s+ω]必然能够包含大量的时间间隔：

一个直观的办法就是通过对 intervali进行聚类分析，找出比较大的聚簇，然后通过这个簇中心找到[s,s+ω]。参考文献[49]引入一个用户定义参数 E 来控制窗口的宽度，其时间窗口则表示成为[λ-ε,λ+ε]，其中A就是聚类得到的簇中心，E是簇的半径。参考文献[49]的方法中时间窗口的宽度2ε依然是由人为给定的，人可能并不知道合适的E取值。另外，此方法生成的时间间隔都是计算每个事件A和接下来一个事件B的时间间隔。这里依赖的一个假设条件就是，如果事件A和事件B有关联性，那么每个事件A仅仅有可能与下一个事件B有关系，而不可能与下面第二个事件B、第三个事件B或者第k（k>2）个事件B发生关联。如图2-14所示，与第五个事件B最近的事件A是第六个事件A，而不是对应的第五个事件A。当时间的位移s较大，而事件分布较密集的时候，这种错开的相关性是很普遍的。

参考文献[47]介绍了一种无人工参数的时间窗口寻找方法。虽然s和ω的组合个数高达O(n4)，但是通过有效的数据结构，可以避免重复多次扫描序列数据。图2-15显示的就是扫描事件A和事件B的一个有序表（Sorted Table）。这个表的中间是一个链接表（Linked List），其中每个节点的值表示一个可能的时间间隔。这里的时间间隔并不要求是相邻两个事件A和B。在扫描序列数据的同时，算法也记录下拥有这个时间间隔Ei的事件A和事件B的序号（Index），并保存到图2-15中对应的IAi和IBi数列中。扫描序列数据并生成Sorted Table需要O(n2)的时间复杂度。在Sorted Table创建之后，任意一个可能的时间窗口[s,s+ω]就可以由图2-15中E1E2…的一个子串来表示，如[s,s+ω]=[20,120]可以表示成E2E3E4。那么，要知道有多少事件A和事件B被[20,120]包含，只需要合并IA2、IA3、IAi和IB2、IB3、IB4。因为IAi和IBi是有序的数列，可以很快得到合并之后的事件A和事件B的序号集。在初始化生成这个Sorted Table的时候，依然需要进行时间复杂度为O(n2)的扫描操作。参考文献[47]针对此问题做过时间复杂度的分析，证明可以将著名的3SUM问题[52]划归到这个问题。如果这个问题存在时间复杂度为O(n2)的解法，那么著名的3SUM问题也存在时间复杂度为O(n2)的解法。3SUM是一个十分经典的算法问题：给定n个整数，是否存在3个数a、b和c满足a+b=c?

3SUM问题的发展历史跟计算机科学的发展历史相似。到目前为止，人类还没有发现一个时间复杂度为 O(n2)的算法。所以可以说，现在还不存在时间复杂度为O(n2)的算法能够彻底解决序列数据中两个关联事件的时间窗口问题。当然，快速的近似算法还是值得研究和发现的。另外一个问题是关于Sorted Table的空间复杂度的问题。完整的Sorted Table空间复杂度是O(n2)。参考文献[47]也提出了一个针对Sorted Table空间复杂度的改进算法。其实扫描Sorted Table和构建Sorted Table两个步骤是可以同时进行的，并不需要等所有的时间间隔（Time Lag）都填到Sorted Table之后才开始扫描。另外一方面，扫描Sorted Table是顺序扫描，不需要回溯，所以扫描完前面一部分的时候，就可以删除再创建下面一部分的内容。因此空间复杂度可以控制在 O(ωmax·n)以内，ωmax是训练可取的最大值。当 ω>ωmax的时候，即便所有的事件 A 和事件 B 都被这个时间窗口包含，根据统计验证也不能把事件 A和事件B判定为具有相关性。但是，ωmax其实并不是一个关于n的函数，而是一个关于序列数据采样率和统计验证的p-value的常数，其具体证明见参考文献[47]。

图2-16对比了参考文献[49]的聚类算法inter-arrival、时间窗口穷举法brute - force、基于Sorted Table的算法STScan 3种方法的实际运行效率。数据集是人工产生的，并混入了预先定义好的几个关联事件与时间窗口。因为这里的正确结果是人工预先定义的，所以判定算法的有效性就是直接看找出来的关联事件与时间窗口是否和预定义的一致。其中brute-force*和STScan*利用了ωmax作为ω搜索上界。可以看出inter-arrival明显比各种算法快几个数量级，实际发现inter-arrival并不能总是找到正确的时间窗口。

2.6.2 基于依赖关系的系统故障追踪

复杂系统内的故障跟踪方法大多基于系统组件的依赖关系图（Dependency Graph）[53-55]。如果用户对系统内部架构十分清楚，依赖关系图可以由人工创建。如果系统内部十分复杂且不断变化，那么可以通过各种数据挖掘算法，根据日志数据来自动创建依赖图。第2.6.1节介绍的依赖关系挖掘，主要涉及系统组件两两之间的关系。当把所有找到的两两依赖关系汇总时，就得到了一个整体系统的依赖关系图。假设一个组件出现故障后，其依赖的组件也应该出现某种故障，如同Java程序里面的Exception抛出一样，我们可以根据一层一层的依赖关系推测最深层出现故障的组件，并可以认定这个组件就是故障的根源。实际系统内，一个组件出现的故障事件可能并非由其依赖的上一层组件的故障导致的，也有可能是上一层的组件某些异常指标导致了当前组件的故障。我们可以将故障、异常等观察现象用一个组件的状态的集合来描述。相互依赖的组件互相的关系可以由一个条件概率分布来表达。例如node2依赖于node1。假设我们有2个状态{A,B}，那么P(node2=A|node1=B)表达了当node1状态是B的时候，node2状态是A的条件概率。在已知的系统依赖图基础上，我们就可以创建出贝叶斯网络[32]，然后观察对出现的某些组件的日志事件数据，得到那些组件的当前状态。当故障出现之后，利用其前后的日志数据得到该贝叶斯网络中某些节点的当前状态，再通过此贝叶斯网络估计其他未观测到的组件最有可能的状态，即可知道故障根源的组件。