论文名称：
Drain: An Online Log Parsing Approach with Fixed Depth Tree

1、简介

image.png

drain算法的全称是depth tree based online log parsing

image.png

这种解决方案非常慢，因为随着日志组的增加，解析时间增长的非常迅速。

image.png

根节点是顶层节点，叶子节点是底层节点，其余都叫做内部节点。

image.png

根节点和内部节点的编码是特殊设计过的规则用来引导整个搜索过程

image.png
每一个log group都由两个部分组成，log event和log IDs，而log event是描述一个log group的最佳模板。 image.png

parse tree的一个特殊设计就是所有的叶子节点的深度都是相同的（取决于你预先设定的参数depth），这个参数会限制算法在搜索过程中访问到的叶子节点，但是会大幅度的提升效率。

2、算法思想

1、先验知识

根据先验知识设定一些正则表达式

image.png

一个数据集通常只需要很少，且很简单的正则。

2、通过Log Message 的长度进行搜索

image.png

解析树的第一层节点表示日志组，他们是日志消息长度不同的分组。日志消息长度，这里指的是一个日志消息里面tokens的个数。

image.png

这个做法依赖于一个假设：相同的log event具有相同的日志信息长度。即便是这个假设不成立，也可以通过简单的后续处理来控制，即便是后续不处理，Drain这个算法的表现也很好。（换句话来说就是，管他假设成立不成立，老子就是要这么做，你能把我咋地）

3、按首标记（token）进行搜索

image.png
这一步基于这样的假设：一个日志消息在开始位置上的tokens更有可能是常量。
具体来说，就是根据日志消息的起始tokens来选择下一个内部节点。例如Receive from node 4这个消息，第一层的节点是length：4，第二层的节点就是Receive，因为第一个位置上的token就是Receive
如果开头的token不是常量而是变量怎么办呢？？？
image.png
为了防止分支爆炸，我们在这一步仅考虑不包含数字在内的tokens，如果一个token是数字，那么他就用表示。（怎么理解，是不是第一个token必须是不“”的）
image.png

我们还设定了一个参数maxChild，最大子节点数，用以约束一个节点的最大子节点数。如果一个节点已经有了maxChild个子节点，那么任何没有被匹配的tokens都将会被匹配为内部特殊符号*

image.png

注意一点：如果depth是2，那么Drain值考虑第一层（step2中提到的）也就是说只考虑长度那一层，不考虑第一个token。原因如下：

image.png
root那一层虽然没啥意义，但是占了一层，所以这么说的话，我们的树深度最少要是3，因为总不能完全依赖于日志长度吧。

4、根据token的相似度进行搜索

image.png

在这一步骤中，Drain将会从日志组的列表里面选择最合适日志组。

我们计算每个日志组中日志消息和日志事件之间的相似度simSeq（公式一）。

其中seq1和seq2分别表示日志消息和日志事件。

image.png

Log event是最适合描述该组日志消息的模板，它由日志消息的常量部分组成。（这里的log event可以理解成模板，但是问题来了，我们解析完成时才会生成结构化日志和模板，那么这个时候的模板是怎么来的？什么样子的？）

image.png
log event参照图2（上面有）

seq(i)表示这个sequence中的第i个token，n是信息的长度。方程equ的定义如公式二。

t1和t2是两个token。在找到simSeq最大的日志组之后，我们将其与预定义的相似度阈值st进行比较。如果simSeq ≥ st，那么就返回这个分组作为最相似的日志组。否则，就返回一个flag（python是None）来表示没有合适的日志组。

5、更新解析树

如果在上一个步骤中找到了合适的日志组，就把当前日志的ID添加到日志组的后面。

如果没有找到，就要创建一个新的日志组，并且更新解析树

---

这里有一点要注意一下：首先根据日志内容的长度分类，构建根节点，然后再根据设定的deepth，比如深度是2，第一层就是根节点root，第二层就是长度。比如深度是3，第三层就是第一个单词。以此类推。以深度为3为例，如果root（第一层），长度（第二层），第一个单词（第三层）都相同，就是一个节点。然后在经过step4的计算，遍历所有长度相同第一个单词也相同的日志，来计算step4中的相似度，并且和设定好的相似度阈值对比，如果符合就合并到一个group里，如果不符合就分裂成两个叶子节点。
如果第三层不同，则分裂成两个节点。