蒲嘉宸 王 鹏 汪 卫

(复旦大学计算机科学与技术学院 上海 200433)

0 引 言

日志是指在各种服务、框架和程序中生成的文本消息，是开发人员和用户之间的重要接口。如今，日志数据的数量正在迅速增长，日志数据已成为有价值的数据源，因为其中包含用户的真实数据，而且它是部分结构化的，因此无须费力即可提取某些数据。因此，数据挖掘技术通常应用于日志数据以执行日志分析。该工作流程广泛应用于服务管理。日志分析包括异常检测、故障诊断和性能改进等领域。但是，要充分利用日志数据，日志解析是首要任务。

由于日志解析的重要性，已经有很多学者对其进行了深入研究。随着日志结构的日益复杂，这些方法的效果并不理想。在解析粒度的选择上，倾向于使用粗粒度的解析。而在相似性度量的选择上，Drain[1]使用了相同长度的日志之间的简单比较，而Spell[2]设计了基于LCS的相似度量。文献[3-4]引入了细粒度的解析，但是主要应用于离线的场景，使用MapReduce来处理日志解析任务。

细粒度的解析通过提取日志中的变量来提高解析的准确性，例如，如果使用粗粒度分析，则“FA‖URL‖taskID [2019353678] dealloc”将表示为“*dealloc”，而在细粒度分析中，使用“FA URL taskID*dealloc”表示此日志。后者表征包含更多信息，使得查找两条相似日志变得更加容易。与Drain中的简单比较相似性度量相比，LCS可以处理不同长度的日志之间的比较。因此，理想情况下，将细粒度分析与LCS相似性度量相集成的方法具有更好的解析质量。但是，由于通过引入细粒度的预处理而增加了单词的数量，并且LCS的计算成本很高，因此该方法的效率不高，不适合在联机日志解析场景中进行日志解析。

本文提出了一种在线日志解析方法ML-Parser，可以高效且准确地以流式的方式解析原始日志数据集。本文主要的贡献包括：(1)将解析的粒度和相似性度量的选择视为日志解析中的两个重要因素；(2)引入了两层框架的设计，可以高效且准确地解析日志，并在理论和方法上确保每一层的比较结果保持一致；(3)对多个日志数据集进行了大量的实验，测试结果表明，本文方法以较高的性能开销取得了更好的解析质量。

1 相关知识

1.1 相关工作

日志可广泛用于软件系统的许多方面，例如行业中的异常检测、使用情况分析和故障诊断。但由于它们具有非结构化的性质，因此无法直接进行分析。许多研究设计了将其解析为结构化格式的方法。传统方法使用手动定义的正则表达式来提取日志模板。为了避免传统方法中的繁琐的编写过程，Xu等[5]提出了一种使用源代码知识来推断消息模板的方法。

由于获取所有源代码总是不切实际的，因此在学术界和工业界都已广泛研究了数据驱动的自动日志解析方法。SLCT[6]是第一个自动日志解析方法，利用频繁的模式挖掘来提取日志模板，但无法提取不太频繁的日志模板。LogSig[7]和LKE[8]设计了日志间的距离度量，并使用聚类算法将原始日志分为不同的类。IPLoM[9-10]通过日志的某些特征(例如长度及单词之间的二元关系)来迭代地划分日志消息。一些研究使用分布式计算来处理大量日志。LogMine[11]以分层的方式提取模板，其中不同级别对应于具有不同粒度的模板。Logan[3]是一种细粒度的日志模板提取方法，在预处理阶段使用通用变量识别并基于LCS进行相似性评分。还为日志解析方法引入了一种不需要人工标注的评估指标。

在过去的几年中，一些在线方法支持以流式方式来解析日志。通过设计一种相似性度量，用于测量事件模板和原始日志之间的相似性。在处理日志消息时，选择最相似的模板进行合并。但是，由于模板数量众多，计算日志消息和所有模板之间的相似度非常耗时。因此，每种方法都使用不同的技术来加快过程。在LenMa[12]中，每个日志消息都可以表示为一个由单词长度组成的向量，通过余弦相似度来计算日志之间的相关性。但是其中相同模板的日志具有相似的单词长度分布的假设太强，无法应用于所有情况。Spell[2]使用LCS作为相似性度量，并利用Jaccard相似度和前缀树来减少处理时间。本文方法优于Spell，并且可以支持细粒度级别和粗粒度级别的日志解析。Drain[1]使用固定深度的前缀树，以设计好的规则对需要比较的日志模板集进行编码，因此每个日志只需要与日志模板集中少数模板进行比较。尽管Drain在某些数据集上表现良好，但对日志中单词的长度敏感，而且在日志以变量开头的情况下效果不佳。

1.2 日志解析中的概念与问题定义

在本文中，日志数据集中的日志在解析过程中可转换为日志模板。下面给出这些概念的定义。

定义1一个日志数据集由一个长度为m的日志序列构成：L=(e1,e2,…,em)，该日志序列通常按日志上的时间戳进行排序。

定义2给定一组分割符D，一条日志可以被分割为一条单词序列：t=(t1,t2,…,tn)，其中n为序列的长度。该日志的类型被称为日志模板，可以通过将单词序列中的变量替换为通配符得到。

例如，在程序中有如下的输出语句“print("IP:{},Port:{}-Connection open".format(ip,port)),”，则在日志中可能出现“IP:172.217.160.110,Port:443-Connection open.”，其对应的日志模板为“IP:*,Port:*-Connection open”。

问题1在线日志解析。

给定一个日志文件L=(e1,e2,…,em)，以流式的方式找出日志模板集T=(t1,t2,…,tp)，其中p是T中日志模板的数量。

日志数据集与日志模板集及其之间映射关系如图1和图2所示。下文将使用图1、图2中的日志来举例说明本文的方法。

图1 日志数据集的样例

图2 日志模板集的样例

1.3 具体问题定义

尽管将日志转换为日志模板对人来说似乎是比较容易的，但实际上很难在日志中确定哪些部分是变量。首先，由于日志的复杂性，很难判断某个单词是否是变量；其次，由于存在大量的日志，因此作出上述判断不能花费太多时间。本文将其看成是日志上的聚类问题，其中存在两个关键问题：① 使用哪些分割符将日志拆分为单词序列；② 使用哪种相似性度量来确定两条日志是否属于同一类。

1)分割符。在早期，分隔符的选择不是问题，因为仅将空格视为单词之间的分隔符。这种情况下，分隔符可以记为Ds={space}。但是日志的结构变得越来越复杂，例如Logan[3]和Delog[4]选择所有非字母数字字符作为分割符。本文使用Da表示所有非字母数字字符的集合。这种分割符的选择对于从日志中提取隐藏变量非常有效，例如，对于日志“FA‖URL‖taskID [2019353678] dealloc”，在分别使用Ds和Da作为分割符的情况下，获得的日志模板分别为“*dealloc”和“FA Url taskID*dealloc”。可以看到，后者可以保留更多的常量信息，因此更容易分辨两个日志模板是否相似。假设使用相同位置相同单词占整条日志的比例作为相似性度量，在阈值为0.6的情况下，在使用粗粒度预处理时，两个taskID不同的模板不能进行合并，但是如果借助于细粒度预处理，那么两条日志就可以被合并。然而，细粒度预处理引入了更多分割符，因此会生成更长的单词序列，与粗粒度预处理相比，需要更长的处理时间。

2)相似性度量。作为聚类问题，相似性度量的选择是一个关键因素。对于在线日志解析器，相似性度量有两种常见选择。Spell[2]使用基于LCS[13]的相似性度量，它可以对不同长度的日志进行比较，其时间复杂度为O(n2)；而Drain[1]基于固定深度前缀树选取日志候选集，对相同长度的日志进行比较，其计算复杂度为O(n)。

LCS是最长的公共子序列的简称，本文使用LCS(X,Y)来表示两个序列X和Y之后的最长公共子序列。

本文同时使用了基于线性比较及基于LCS的相似性度量，分别表示为：

(1)

(2)

其中:

(3)

式中：n是两条日志的长度；LCS*是LCS的一个变体，即在计算最长公共子串的过程中忽略通配符。

给定分割符和相似性度量的选择，本文要解决的问题2可以定义如下：

问题2给定日志数据集L，以流式的方式找出日志模板集T，即如果日志s和日志模板t满足：

SimDa,LCS*(s,t)≥ε

(4)

则将日志s的日志模板设置为t，否则使用日志s来创建新的日志模板，ε是用户指定的相似性阈值。

1.4 挑战与方法概述

一个简单的解决方案是针对新的日志，遍历所有的日志模板，然后选择最相似日志模板的日志集与其合并，或基于该日志创建新的日志模板。但是，该方法具有较高的计算复杂度O(mpn2)。因此本文研究面对的主要挑战是如何提高日志解析的效率。

对此，本文设计了一个两层框架，用于计算日志s和模板t之间的相似度，如图3所示。在第一层中，在s和每个长度相同且为n的日志模板t之间计算基于粗粒度预处理的相似度SimDs,HAMD(s,t)。先过滤掉在开始位置具有不同单词的模板来进一步限制搜索空间，就像在Drain[1]中所做的一样。在第二层中，使用基于细粒度预处理的相似度SimDa,LCS*(s,t)来比较s和日志模板t。若在上一层中找到合适的日志模板t，则跳过后续层中的计算。

图3 两层框架示意图

该框架将时间复杂度降低到接近O(mpn)，极大地提高了原始解决方案的性能，因为大多数日志都可以在第一层中处理。

1.5 理论基础

上文介绍了如何使用两层的框架来加速日志解析。框架中的第一层可以显著加快日志解析，本节证明使用这种框架不会影响结果的正确性。

引理1给定长度为n的日志s与模板t，有：

(5)

定义3线性合并条件。给定分割符Da和Ds，假设日志s与模板t从分割符Ds切换至Da后新增的单词数的最大值为b，其中相同的单词数为a，则线性合并条件可以写为:

a≥ε×b

(6)

使用线性合并条件，可以给出正确性的证明。

定理1给定长度为n的日志s与模板t，若满足:

SimDs,HAMD(s,t)≥ε

(7)

a≥ε×b

(8)

则有:

SimDa,LCS*(s,t)≥ε

(9)

证明由式(7)可以得到:

(10)

结合引理1得:

|LCS*(s,t)|≥ε×n

(11)

由式(8)和式(11)可以得到:

|LCS*(s,t)|+a≥ε×(n+b)

(12)

变换后可以得到式(9)，证毕。

通过上述证明，可以保证在第一层合并的模板，在第二层也会进行合并，从而在提升解析速度的同时，保证了解析结果的准确性。

2 日志解析方法

为了提供一个快速而有效的解决方案，本文提出了一个两层框架来表示日志模板。当新的原始日志出现时，将首先使用用户定义的正则表达式集对其进行预处理，然后在具有最大深度固定值的前缀树中搜索待比较的日志模板集。如果找到合适的日志模板，则将该日志添加到该模板的日志集合中，并更新日志模板；否则，将基于该日志创建一个新的日志模板和一个输出节点。如果生成了新的日志模板或者原有的日志模板得到了更新，则将通过使用基于LCS的相似性度量和细粒度的预处理，与较大的一组日志模板一起进行匹配。如果找到类似的日志模板，则两个日志模板的输出节点将进行合并，并且数据节点中的日志模板将更新。本节介绍使用的数据结构以及本文方法如何逐步处理日志消息。

2.1 数据结构

使用1.4节中介绍的两层框架。第一层是具有最大深度的前缀树，与Drain[1]中的固定深度前缀树类似，主要区别在于放宽了固定深度树的约束条件，从而可以将日志模板集存储在内部节点中，因而可以在较早阶段将具有相同日志模板的日志集合进行合并。第一层中的每个节点都指向一个输出节点，该节点包含两层日志模板。它们分别对应于通过对线性匹配及采用细粒度预处理和LCS匹配生成的日志模板。

2.2 预处理

由先前的文献[1，3-4]和综述文献[14]可知，预处理是提高日志解析质量并减少日志模板数量的重要步骤。在解析之前，通过使用一些正则表达式来删除原始日志中的一些变量。这些正则表达式由用户提供，作为可选的领域知识的输入方式。为了避免减慢日志解析的速度，预处理中仅使用了数量非常有限的简单正则表达式。使用正则表达式后，通过一些分割符将日志拆分为单词序列。使用两种类型的分割符Da和Ds在两种方法之间取得平衡。例如，图1中的第三条日志消息在分别应用Da和Ds后转换为“Process python.exe exited 0”和“Process python exe exited*”。

2.3 第一层中的日志模板匹配

给定新日志s，找到需要比较的日志模板，可以通过在前缀树中进行遍历来实现。使用前缀树的原因是因为大多数日志满足以下假设：(1)大多数相同类型的日志往往具有相同的长度；(2)相同类型的日志的在开始的若干个位置上可能具有相同的单词。

根据上述假设，可以获得与日志s长度相同且在起始位置具有相同单词的那些日志模板，这些是要比较的日志模板。这里可以基于SimDs,HAMD(s,t)找到最适合该日志消息的日志模板，即这些日志模板中具有最大相似度的日志模板。如果该日志模板与日志s的相似性大于等于用户定义的阈值ε，则应该将该日志添加到该日志模板的日志集合中。

在合并之前，根据定理1，还需要满足线性合并条件。如果满足，则应执行合并操作；否则，应该拒绝这次合并，并认为该日志没有合适的日志模板。这一步可以减少过度合并的情况。例如，有两条日志“Process java.exe exited with 1”和“Process java.exe exited with java.io.FileNotFoundException”，假设ε=0.5，则SimDs,HAMD=0.8≥ε，在没有线性合并条件限制的情况下，会造成不合理的合并。此时线性合并相似度的值为0.4<ε，因此可以通过使用线性合并条件来拒绝这次合并。

如果在上一步中找到了合适的日志模板，则将日志添加到日志模板的日志模板集中，并通过在日志模板和日志的相同位置的循环比较来更新该日志模板；否则，将基于当前日志创建一个新的日志模板，其日志集合仅包含该日志本身。

2.4 第二层中的日志模板匹配

第二层主要处理可变参数长度的日志模板。一些单词可能由一些与某些分隔符相连的元素组成，例如日期时间字符串(例如“12:00:00”，“2019/12/01”)、URL(例如“https://www.google.com/”)和文件路径(例如“/usr/local/bin/root”)。尽管可以通过引入一些手工编写的正则表达式来识别这些元素，但用户学习编写正则表达式需要付出巨大的精力。通过引入细粒度的预处理，使用户避免编写正则表达式的过程的同时也能处理这些情况。

给定一个新创建或更新后的日志模板，需要确定应该与之进行比较的日志模板，这可以使用倒排索引来完成，倒排索引在数据库领域中被广泛使用。倒排索引基于单词构建，如图4所示。创建新的日志模板时，对于ID为id的日志模板的单词集合中的每个单词将其记录为(id,count)，其中count是这条日志中这个单词的出现次数。对于更新后的日志模板，统计在模板更新阶段被通配符替换的单词，并减去这些单词在倒排索引中的模板id的计数。通过引入倒排索引，可以减少待比较的日志模板的数量。

图4 日志模板的倒排索引示例

通过使用倒排索引得到待比较的日志模板，然后根据相似性度量SimDa,LCS*(s,t)来寻找一个合适的日志模板。如果该日志模板与当前日志模板的最大相似性值超过了用户定义的阈值ε，则将当前日志模板与日志模板的输出节点合并。为避免影响第一层中的日志模板，将更新后的日志模板作为第二层中的模板存储在输出节点中。更新后的日志模板可以通过计算LCS得到，即将找到的日志模板中所有与当前日志模板不匹配的单词全部替换为通配符。例如，对于新创建的日志模板“Process NVIDIA Share.exe exited with 1”和找到的日志模板“Process python.exe exited with 0”，第二层中的模板应为“Process*exe exited with*”，如图5所示。

图5 日志模板合并样例

3 实 验

本节将ML-Parser与三种流行的、支持以流式的方式处理的在线日志解析算法在公开数据集[15]上进行比较，测试日志解析的效率和质量。测试环境是在Windows计算机上构建的，该计算机具有24核的CPU。所有日志解析算法的代码都在Python 3.7环境下运行。

测试中使用的数据集的信息见表1，其中包含大小从2 MB到2 GB的各种日志文件。它涵盖了文献[1-2，8]中介绍的常见测试用例。

表1 数据集信息概览

本文从效率和质量两方面进行评估，并选择了三种在线方法进行比较，分别为Spell[2]、Drain[1]和Drain的改进版本(记为DrainV2)[16]。Spell的想法是将日志模板使用基于LCS的相似性度量进行比较。此外，还使用基于前缀树和简单的循环比较的方法来加快执行速度。而Drain根据长度对所有日志模板进行分块，然后在固定深度的前缀树中执行搜索。DrainV2引入了一些改进，例如不需要定义相似性阈值，将日志最后的单词也放入前缀树中，以及为长度不同的日志模板引入了可选的合并机制。

表2显示了在测试中算法所使用的参数。对于Spell和Drain，使用文献[15]所建议的参数值。对于DrainV2[16]仅对Proxifier数据集启用了可选的合并机制，并且合并阈值设置为0.95。

表2 ML-Parser与其他方法的参数设置

3.1 解析质量

本节将评估ML-Parser的有效性。为避免手动定义日志模板的正则表达式，使用文献[3]中的非监督指标进行评估。此度量标准要求日志模板不应过度泛化，也不应有变量未被发现的情况。给定一组日志模板T，计算以下指标：

AvgTokenLost(t)=AvgMatchLength(t)-|t|

(13)

LengthLoss(T)=(log|T|)θ

(14)

(15)

Loss=LengthLoss(T)+QualityLoss(T)

(16)

式中：ti是T中的模板；AvgMatchLength(t)是评估模板t的日志集合中所有原始日志与模板t的平均匹配长度；LengthLoss反映了T中生成了多少模板；QualityLoss评估生成的模板是否存在过度泛化；θ是一个超参数，用于控制两个因素之间的重要性。根据原始论文，θ设置为1.5。

本文使用细粒度的预处理将原始日志转换为单词序列。因此，为了使测试公平，还使用了细粒度的预处理来评估Drain和Spell的结果，在测试中以后缀“S”命名。从表3和表4所示的比较结果可以看出，采用细粒度预处理的方法可以得到较少的日志模板，并且在大多数日志中的损失较小，这可能是因为可以在细粒度预处理的帮助下找到更多隐藏的变量。SpellS和ML-Parser生成的日志模板少于其他方法。但是，SpellS在某些数据集中具有较高的损失值和较少的模板，这意味着某些重要的单词在模板中丢失。就损失和生成模板的数量而言，ML-Parser在所有数据集中的表现都优于Drain和Spell，并且在所有方法中，十个任务中有七个任务的损失最低。

表3 ML-Parser与其他方法之间的损失比较

表4 ML-Parser与其他方法之间的模板数比较

3.2 解析速度

表5显示了ML-Parser和其他方法的性能。可以看到，采用细粒度预处理的方法运行时间比除Spell以外的方法长。SpellS之所以快速，是因为它在前缀树和简单循环进行预过滤的过程中采用了固定的阈值0.5。通过引入更多分割符，日志会更长，因此更容易找到匹配项，但也可能导致日志模板过于泛化。ML-Parser比Drain和DrainV2慢一些，这是可以预期的，因为这两种方法具有相对较小的搜索空间，仅采用线性匹配，而且没有细粒度的预处理过程。但是，本文认为这是一个在解析质量和解析速度之间的权衡。ML-Parser以较长的运行时间为代价，实现了更好的解析性能。

表5 ML-Parser与其他方法之间的运行时间比较 单位：s

续表5

此外，由表1、表4、表5可以看出，对于两个日志模板数和日志长度相当的数据集，例如HDFS和Apache，方法的运行时间与日志行数基本呈正相关，这说明了在线日志解析方法对于读取并解析单条日志的时间基本是恒定的。而对于日志条数与日志长度差别不大的数据集，比如Linux和Proxifier，方法用时的差异很小，这说明基于流式的日志解析方法都有针对日志模板比较的过滤方式，只会对其中少量的模板进行比较。从HPC和Hadoop的结果来看，运行时间与日志长度也基本呈正相关，然而一般日志数据集在日志长度上的区别并不大。综合以上三个因素及实验结果，可以分析得出三个因素对于运行时间的影响从大到小分别为日志数量、日志长度和模板个数。

3.3 详细分析

在两个日志数据集Hadoop和Spark上进行详细分析，结果如图6所示。ML-Parser在两个日志中都实现了较低的长度损失，这是通过引入细粒度的预处理可以预见的结果。当日志更大且更复杂时，长度损失的差异更加明显。就质量损失而言，在Hadoop数据集上达到与Drain几乎相同的质量损失，而在Spark中具有较低的质量损失。这显示了线性合并条件的有效性，它拒绝了日志模板的过度泛化。

图6 ML-Parser与其他方法的详细比较

表6显示了ML-Parser中每个步骤返回的日志模板的数量以及占原始日志的比例。在第一层中，日志模板的数量减少了99%以上。线性合并约束拒绝了基于前缀树的将近一半的日志模板的合并，并且耗时的LCS比较涉及的日志模板数不足原始日志数的0.2%。

表6 ML-Parser每个步骤返回的模板个数与比例

4 结 语

本文提出了一种新的在线日志解析方法ML-Parser，该方法可以以流式方式工作。本文设计并构建了两层框架来存储与处理日志模板；使用具有最大深度的前缀树和具有线性合并约束条件的线性相似性搜索来加快LCS比较过程；通过引入细粒度的预处理，识别出了更多的变量并生成了更少的日志模板。本文还根据实验给出了详细的评估结果，展现了ML-Parser在日志解析任务上的质量和性能。