《Drain: 一种基于固定深度树的在线日志解析方法》论文详细笔记-EW帮帮网

文章目录

- Drain: 一种基于固定深度树的在线日志解析方法 - 详细笔记

Drain: 一种基于固定深度树的在线日志解析方法 - 详细笔记

作者: Pinjia He, Jieming Zhu, Zibin Zheng, Michael R. Lyu [page 1]

摘要 (Abstract) [page 1]

问题: 现有的日志解析方法大多侧重于离线、批量处理，随着日志量的快速增长，这变得非常耗时。在收集所有现有日志后进行离线模型训练效率低下。
提出的解决方案 (Drain): 一种在线日志解析方法，能够以流式和及时的方式解析日志。
Drain 的主要特性:
- 使用固定深度的解析树来加速解析过程。
- 在树中编码专门设计的解析规则。
评估:
- 在五个包含超过1000万条原始日志消息的真实世界日志数据集上进行了评估。
- 在四个数据集上达到了最高的准确率，在其余一个数据集上准确率相当。
- 与最先进的在线解析器相比，运行时间改进了 51.85%~81.47%。
- 通过一个异常检测任务的案例研究证明了 Drain 在日志分析中的有效性。
关键词: 日志解析；在线算法；日志分析；Web服务管理。

I. 引言 (Introduction) [page 1]

背景:
- 日志对于Web服务管理至关重要，记录了有价值的系统运行时信息。
- 典型的日志分析首先解析原始的非结构化日志消息，然后应用数据挖掘模型。
- 云计算和面向服务架构 (SOA) 非常普遍。Web服务管理对提供商（确保无故障/SLA违规）和用户（高效管理采用的服务）都具有挑战性。
- 日志分析广泛用于异常检测、故障诊断、性能改进、业务模型挖掘和用户行为分析。
日志解析的挑战:
- 原始日志消息是非结构化的（时间戳、详细级别、自由文本内容）。数据挖掘模型需要结构化输入。
- 传统的日志解析依赖于手动设计的正则表达式，这不适用于现代服务，原因如下：
  1. 日志量快速增长。
  2. 系统由许多开发人员的组件构成（难以了解原始日志记录目的）。
  3. 日志记录语句频繁更新（维护正则表达式繁琐且易出错）。
现有自动解析器的局限性:
- 大多数现有的自动解析器是离线/批处理的（例如，Xu 等人），需要所有日志进行训练，速度较慢。
- 基于源代码的方法（例如，从源代码生成正则表达式）通常不可行，因为源代码不可访问（例如，Web服务组件）。
- 数据驱动的方法直接提取模板，但是离线的且受内存限制，与流式日志收集方式不符。
- 关于在线日志解析的初步工作很少，且不够准确或高效，无法满足现代系统的需求。
Drain 的贡献:
- 一种名为 Drain 的在线日志解析方法，能够以流式方式准确高效地解析原始日志消息。
- 不需要源代码，只需要原始日志消息。
- 自动提取模板并将日志分成不相交的日志组。
- 采用固定深度的解析树来指导日志组搜索过程，有效避免了构建过深和不平衡的树。
- 专门设计的解析规则紧凑地编码在树节点中。
论文的主要贡献: [page 2]
1. 设计了一种在线日志解析方法 (Drain)，该方法采用固定深度的解析树，并在树中编码专门设计的解析规则。
2. 在五个真实世界的数据集上进行了广泛的实验，证明了 Drain 在准确性和效率方面的优越性。
3. 公开发布了源代码，便于研究人员和从业者进行未来研究。

II. 日志解析概述 (Overview of Log Parsing) [page 2]

目标: 将原始日志消息转换为结构化的日志消息 (参见图1)。
过程: 区分原始日志消息中的常量部分（系统操作模板/日志事件）和变量部分（动态运行时信息）。
示例 (图1):
- 原始: 081109 204655 Received block blk_3587 of size 67108864 from /10.251.42.84
- 模板: Received block * of size * from *
- 变量: blk_3587, 67108864, /10.251.42.84
日志解析即聚类: 典型的日志解析器将日志解析视为一个聚类问题，将具有相同日志事件的原始日志消息分组。Drain 也以流式方式将消息聚类到不同的日志组中。

III. 方法论 (Drain) [page 2, 3, 4]

Drain 是一种基于固定深度树的在线日志解析方法。

A. 整体树结构 (Overall Tree Structure) (图2) [page 2, 3]

目的: 加速搜索最合适的日志组或创建新的日志组，限制比较次数。
结构:
- 根节点 (Root Node): 顶层。
- 内部节点 (Internal Nodes): 中间层。编码专门设计的规则。不包含日志组。
- 叶节点 (Leaf Nodes): 底层。存储一个日志组列表。从根到叶的每条路径都终止于一个叶节点。
- 日志组 (Log Group): 包含：
  - 日志事件 (Log Event): 描述该组中消息的模板（常量部分）。
  - 日志ID (Log IDs): 记录属于该组的消息的ID。
关键设计特性:
- 固定深度 (depth): 所有叶节点具有相同的预定义深度 (例如，图2中 depth=3)。这提高了效率。
- maxChild: 限制节点最大子节点数的参数，以避免树分支爆炸。
过程概述: 当新的日志消息到达时：
1. 使用领域知识（简单正则表达式）对其进行预处理。
2. 通过遵循内部节点中编码的规则来搜索日志组（叶节点）。
3. 如果找到合适的组，则将消息与事件匹配。否则，创建一个新组。

B. 步骤1: 基于领域知识的预处理 (Step 1: Preprocess by Domain Knowledge) [page 3]

原理: 预处理可以提高解析准确性。
方法: 用户可以提供基于领域知识的简单正则表达式来表示常用变量（例如，IP地址、块ID）。Drain 会移除这些正则表达式匹配到的令牌 (tokens)。
示例: 块ID，如 blk_35875...，通过 blk_[0-9]+ 被移除。
简单性: 这些正则表达式通常很简单（匹配令牌而非整个消息），每个数据集通常只需要少量此类表达式。

C. 步骤2: 按日志消息长度搜索 (Step 2: Search by Log Message Length) [page 3]

动作: 根据预处理后日志消息的长度（令牌数量），从根节点遍历到第一层节点。
示例: 对于日志消息 “Receive from node 4”（长度为4），Drain 遍历到内部节点 “Length: 4”。
**假设:**具有相同日志事件的日志消息可能具有相同的日志消息长度。（差异可以通过简单的后处理来处理，尽管 Drain 即使没有后处理也显示出优越性）。

D. 步骤3: 按前缀令牌搜索 (Step 3: Search by Preceding Tokens) [page 3]

动作: 从第一层节点遍历到一个叶节点。
假设: 日志消息起始位置的令牌更可能是常量。
方法: Drain 根据日志消息的起始令牌选择下一个内部节点。遍历的内部节点数量为 (depth - 2)。
示例 (depth=3): 对于日志消息 “Receive from node 4”，Drain 从第一层节点 “Length: 4” 遍历到第二层节点 “Receive”，因为第一个令牌是 “Receive”。然后 Drain 遍历到与内部节点 “Receive” 连接的叶节点。
处理参数/分支爆炸:
- 如果一个令牌包含数字（例如：“120 bytes received”），它将匹配一个特殊的内部节点 *，而不是令牌本身（例如 “120”），以避免将每个参数值编码为一个内部节点。
- 此外，如果一个节点已经拥有 maxChild 个子节点，任何不匹配的令牌都将匹配其子节点中的特殊内部节点 *。

E. 步骤4: 按令牌相似度搜索 (Step 4: Search by Token Similarity) [page 4]

背景: Drain 已经遍历到一个包含日志组列表的叶节点。这些日志组符合沿路径的内部节点中编码的规则。
动作: 从日志组列表中选择最合适的日志组。计算当前日志消息与叶节点中每个日志组的日志事件（模板）之间的相似度 simSeq。simSeq 定义如下：
$simSeq(seq_1, seq_2) = \frac{\sum_{i=1}^{n} equ(seq_1(i), seq_2(i))}{n}$
其中 $seq_1$ 和 $seq_2$ 分别代表日志消息和日志事件； $se q (i)$ 是序列的第 $i$ 个令牌； $n$ 是序列的日志消息长度；函数 $e q u$ 定义如下：
$equ(t_1, t_2) = \begin{cases} 1 & \text{if } t_1 = t_2 \\ 0 & \text{otherwise} \end{cases}$
其中 $t_1$ 和 $t_2$ 是两个令牌。
选择:
- 找到具有最大 simSeq 的日志组。
- 如果 $s im S e q > s t$ （预定义的相似度阈值），Drain 返回该组作为最合适的日志组。
- 否则，Drain 返回一个标志（例如，Python中的 None）以指示没有合适的日志组。

F. 步骤5: 更新解析树 (Step 5: Update the Parse Tree) [page 4]

情况1: 找到合适的日志组 (在步骤4中):
- 将当前日志消息的ID添加到返回的日志组的 Log IDs 中。
- 更新返回的日志组中的 Log Event（模板）：Drain 扫描日志消息和日志事件中相同位置的令牌。如果两个令牌相同，则不修改该令牌位置的令牌。否则，将该令牌位置的令牌更新为通配符 (*)。
情况2: 未找到合适的日志组:
- 基于当前日志消息创建一个新的日志组，其中 Log IDs 仅包含当前日志消息的ID，Log Event 与当前日志消息完全相同。
- 然后，Drain 将使用新的日志组更新解析树。直观地，Drain 从根节点遍历到应该包含新日志组的叶节点，并相应地沿路径添加缺失的内部节点和叶节点。
- 例如，假设当前的解析树是图3的左侧树，并且一条新的日志消息 “Receive 120 bytes” 到达。然后 Drain 将解析树更新为图3的右侧树。注意，第三层中的新内部节点编码为 *，因为令牌 “120” 包含数字。

IV. 评估 (Evaluation) [page 4, 5, 6, 7]

A. 实验设置 (Experimental Settings) [page 4, 5]

1) 日志数据集 (表I): [page 4]
- 五个真实世界数据集：
  - BGL: BlueGene/L 超级计算机 (LLNL)
  - HPC: 高性能计算集群 (Los Alamos)
  - HDFS: Hadoop 分布式文件系统 (Amazon EC2 平台)
  - Zookeeper: 分布式系统协调器 (实验室集群)
  - Proxifier: 代理客户端 (独立软件)
- 详细信息：日志消息数量、日志消息长度范围、事件数量（真实模板数）。
2) 对比的解析器: [page 4]
- 离线: LKE, IPLoM
- 在线: SHISO, Spell
3) 评估指标和实验装置: [page 5]
- 准确性指标: F-measure (精确率和召回率的调和平均值)。
  $\frac{2 \times Precision \times Recall}{Precision + Recall}$
  其中 Precision 和 Recall 定义如下：
  $\frac{TP}{TP + FP}$
  $\frac{TP}{TP + FN}$
  - TP (True Positive): 将两条具有相同日志事件的日志消息分配到同一个日志组。
  - FP (False Positive): 将两条具有不同日志事件的日志消息分配到同一个日志组。
  - FN (False Negative): 将两条具有相同日志事件的日志消息分配到不同的日志组。
- 装置: Linux 服务器，Intel Xeon E5-2670v2 CPU，128GB DDR3 RAM。每个实验运行10次以避免偏差。
- Drain的预处理: 移除了日志消息中明显的参数（即HPC、Zookeeper和HDFS中的IP地址，BGL中的核心ID，HDFS中的块ID以及Proxifier中的应用程序ID）。
- Drain的参数设置 (表II): depth 和 st 根据每个数据集进行调整。maxChild 根据经验设置为100。其他解析器的参数也进行了重新调整。

B. Drain的准确性 (表III) [page 5]

结果:
- Drain 在四个数据集上获得了最佳准确率 (BGL, HDFS, Zookeeper 均为0.99; HPC 为0.84)。
- 在 Proxifier 上准确率相当 (Drain 0.86, Spell 0.87 - 最高)。
- LKE (离线) 由于其 $O(n^2)$ 的时间复杂度，难以处理大型数据集；对于其他四个数据集，是在从原始数据中随机抽取的2k条日志消息样本集上评估LKE的准确性。
讨论:
- Drain (在线) 即使与离线日志解析方法相比，也获得了最佳的准确率。
- Drain 高准确率的原因:
  1. 它结合了日志消息长度和前几个令牌（这些是有效且专门设计的规则）来构建固定深度的树。
  2. Drain 仅使用不包含数字的令牌来指导搜索过程，有效避免了过度分区。
  3. 可调整的树深度 depth 和相似度阈值 st 允许用户针对不同的数据集进行细粒度调整。

C. Drain的效率 (表IV, 图4) [page 5, 6]

运行时间结果 (表IV): [page 5]
- Drain 在所有五个数据集上所需的运行时间最少。
- 改进: 与当时最先进的在线解析器Spell相比，改进幅度从 74.07% (BGL) 到 68.97% (Proxifier)。具体数值：
  - 对比 Spell: BGL (74.07%), HPC (81.47%), HDFS (51.85%), Zookeeper (65.65%), Proxifier (68.97%)。
- 例如：解析4百万条BGL日志仅需2分钟，解析1千万条HDFS日志仅需6分钟。
- Drain 在速度上也优于离线方法 IPLoM。
- Drain 不受单台计算机内存的限制（逐条处理日志），不像 IPLoM 等离线方法。
可扩展性 (图4 - 对数刻度): [page 6]
- 在不同大小的采样数据集上测量运行时间（表V显示了采样大小）。
- LKE 的 $O(n^2)$ 时间复杂度使其扩展性较差。其他方法为 $O (n)$ 。
- Drain 比其他在线解析器 (SHISO, Spell) 更快。
Drain 高效率的原因 (时间复杂度): [page 6]
- 整体复杂度: $O ((d + c m) n)$
  - $d$ : 解析树的深度 (常数)
  - $c$ : 叶节点中候选日志组的数量 (小的常数)
  - $m$ : 日志消息长度 (常数)
  - $n$ : 日志消息的数量
  - 因此，时间复杂度实际上是 $O (n)$ 。
- 与SHISO/Spell的比较: 它们的解析树深度在解析过程中可能会增加。
- simSeq 计算: 时间复杂度为 $O(m_1+m_2)$ ，在Drain中， $m_1=m_2$ (消息长度)。而SHISO和Spell计算两个序列之间的最长公共子序列，其时间复杂度为 $O(m_1m_2)$ 。

D. Drain在真实世界异常检测任务中的有效性 (表VI) [page 6, 7]

案例研究: HDFS日志数据集（575,061个HDFS块，总共29种日志事件类型。其中16,838个块被原始作者手动标记为异常）。
工作流程:
1. 日志解析: 使用不同的日志解析方法将原始HDFS日志解析为结构化的日志消息（每个结构化日志消息包含相应的HDFS块ID和日志事件）。（原始论文中使用的是基于源代码的日志解析方法）。
2. 日志挖掘:
  - 生成事件计数矩阵（每行代表一个HDFS块；每列代表一种日志事件类型；每个单元格表示某个HDFS块上某个事件的发生次数）。
  - 使用 TF-IDF 预处理事件计数矩阵（直观上，TF-IDF会给常见事件类型赋予较低的权重，这些事件类型不太可能对异常检测过程做出贡献）。
  - 最后，将事件计数矩阵输入到主成分分析 (PCA) 中，PCA会自动将块标记为正常或异常。
评估 (表VI): 比较了 IPLoM, SHISO, Spell, Drain, 以及 Ground Truth 解析在异常检测任务中的表现。
- 指标: 解析准确率、报告的异常数、检测到的异常数 (真阳性)、错误告警数 (假阳性)。
- 结果:
  - Drain 获得了近乎最佳的异常检测性能（检测到10,720个真实异常，仅有278个错误告警），与 IPLoM 相同，并且非常接近使用 Ground Truth 解析的结果。
  - SHISO 尽管解析准确率达到0.93，但其错误告警数很高 (1,907)，比其他方法差6倍。
- 结论: Drain 不仅具有最高的解析准确率，而且在后续的异常检测案例研究中也获得了近乎最佳的性能，证明了其有效性。

V. 相关工作 (Related Work) [page 7, 8]

服务管理的日志分析: 日志记录系统运行时信息，广泛用于服务管理任务（如异常检测、故障诊断、性能改进等）。日志解析是实现自动化和有效日志分析的关键步骤。我们相信我们提出的在线解析方法可以使这些技术和未来的日志分析研究受益。 [page 7]
日志解析: [page 7]
- 基于源代码的方法（例如，Xu 等人）：准确性高，但源代码通常难以获取。
- 数据驱动方法（LKE, IPLoM, SHISO, Spell）：采用数据挖掘技术提取日志模板。
  - LKE, IPLoM: 离线解析器（在我们之前对离线解析器的评估研究中进行了研究）。
  - SHISO, Spell: 在线解析器，以流式方式解析日志消息，并且不受单台计算机内存的限制。
- Drain 在准确性和效率方面均优于现有的在线日志解析器，甚至优于最先进的离线解析器。
Web服务系统的可靠性: 许多近期研究侧重于增强Web服务系统的可靠性（例如动态软件产品线、服务选择和推荐、基于客户端反馈的QoS监控、性能预测）。我们提出的在线日志解析器对于日志分析技术至关重要，这些技术可以补充这些方法以增强Web服务系统的可靠性。日志分析方法还可以提高许多现有服务系统的可靠性。 [page 8]

VI. 结论 (Conclusion) [page 8]

本文提出了一种名为 Drain 的在线日志解析方法，用于基于日志分析的Web服务管理技术。
Drain 以流式方式解析原始日志消息，采用固定深度的解析树，并在树节点中编码专门设计的规则。
对五个真实世界日志数据集的实验结果表明，Drain 在准确性和效率方面均大大优于现有的在线日志解析器。Drain 甚至表现优于受单台计算机内存限制的最先进的离线日志解析器。
此外，我们进行了一个真实世界异常检测任务的案例研究，证明了 Drain 在日志分析任务中的有效性。

关键图表总结

图1: 日志解析概述 (Overview of Log Parsing) [page 2]
- 展示了原始日志行如何转换为带有变量占位符的解析后模板。
图2: Drain中的解析树结构 (depth = 3) (Structure of Parse Tree in Drain (depth = 3)) [page 3]
- 显示了根节点、内部节点（例如 “Length:4”, “Receive”）以及一个包含日志组（日志事件 + 日志ID）的叶节点。
图3: 解析树更新示例 (depth = 4) (Parse Tree Update Example (depth = 4)) [page 4]
- 演示了当一条新的日志消息 (“Receive 120 bytes”) 到达且不适合现有路径时，树结构如何被修改，从而导致创建新节点（包括一个用于令牌 “120” 的 * 节点）。
图4: 不同规模数据集上日志解析方法的运行时间 (Running Time of Log Parsing Methods on Data Sets in Different Size) [page 7]
- 以对数刻度绘制了不同解析器在不同数据集上的运行时间与日志大小的关系，直观显示了 Drain 优越的可扩展性和效率。
表I: 日志数据集摘要 (Summary of Log Data Sets) [page 4]
- 列出了五个数据集 (BGL, HPC, HDFS, Zookeeper, Proxifier) 及其消息数量、消息长度范围和唯一事件模板的数量。
表II: Drain的参数设置 (Parameter Setting of Drain) [page 5]
- 显示了 Drain 在五个数据集上调整后的 depth 和相似度阈值 st 的值。
表III: 日志解析方法的解析准确率 (Parsing Accuracy of Log Parsing Methods) [page 5]
- 比较了 Drain 与 LKE, IPLoM (离线) 和 SHISO, Spell (在线) 在五个数据集上的 F-measure 得分。突出了 Drain 的高准确率。
表IV: 日志解析方法的运行时间(秒) (Running Time (Sec) of Log Parsing Methods) [page 5]
- 比较了 Drain 与其他解析器的执行时间，展示了 Drain 显著的速度优势，并列出了改进百分比。
表VI: 不同日志解析方法下的异常检测 (16,838个真实异常) (Anomaly Detection with Different Log Parsing Methods (16,838 True Anomalies)) [page 7]
- HDFS异常检测案例研究的结果，显示了解析器的选择 (IPLOM, SHISO, Spell, Drain, Ground Truth) 如何影响报告的、检测到的和错误告警的异常数量。显示了 Drain 的有效性。

《Drain: 一种基于固定深度树的在线日志解析方法》论文详细笔记