云智慧 AIOps 社区是由云智慧发动，针对运维业务场景，提供算法、算力、数据集整体的服务体系及智能运维业务场景的解决方案交换社区。该社区致力于流传 AIOps 技术，旨在与各行业客户、用户、研究者和开发者们独特解决智能运维行业技术难题，推动 AIOps 技术在企业中落地，建设衰弱共赢的 AIOps 开发者生态。

日志模式解析是将日志从半结构化数据解析为结构化数据的一种算法，能够帮忙咱们疾速理解大量日志的概貌，在日志的自动化剖析过程中，常作为两头步骤，服务于日志后续的异样检测等工作。本技术黑板报中，咱们将围绕三个问题来具体解说日志模式解析：日志模式解析是什么，为什么要做日志模式解析，如何实现日志模式解析。

一、日志模式解析是什么：

咱们能够用上面这张图来了解日志模式解析所做的工作：

首先须要明确的是，日志是一种半结构化数据，他是由特定的代码生成的。如上图中，日志音讯：2015-10-18 18:05:29,570 INFO dfs.DataNode$PacketResponder: Received block blk_-562725280853087685 of size 67108864 from /10.251.91.84。就是由代码 LOG.info(“Received block ” + block + ” of size ” + block.getNumBytes() + ” from ” + inAddr); 生成。日志模式解析的目标就是将日志解析成如上图所示的结构化数据的模式，即从日志中提取出工夫戳、等级、组件、日志模板和参数信息。日志的工夫戳、等级、组件这三个信息通过简略的正则就能够非常容易取得，所以日志模式解析算法真正关注的是日志模板及参数的提取。

什么是日志模板和参数呢？略微有一点代码常识，咱们都能晓得代码 LOG.info(“Received block ” + block + ” of size ” + block.getNumBytes() + ” from ” + inAddr)打印出的日志中，都会呈现文本：Received block、of size、from，这些文本咱们称为常量，而因为每次打印日志时零碎状态的不同，每条日志打印出的 block、block.getNumBytes()、inAddr 可能不同，这些文本咱们称为参数。咱们将日志中的常量保留，参数用特定符号 <*> 代替，这样所生成的文本就是日志的模板。

日志模式解析过程能够了解为是一个倒推日志打印代码的过程，也是一个对日志聚类的过程（雷同模板的日志认为是同一类日志）。不同文章对日志模式解析有不同的称说，日志模板开掘、日志模式发现、日志模式识别、日志聚类等，其实指的都是日志模式解析。

二、为什么要做日志模式解析：

日志模式解析是当初很多日志产品中都有的一个性能，为什么大家都要做日志模式解析这件事呢？首先，日志模式解析能够帮忙咱们疾速理解日志概貌，在现在的计算机系统中，日志数量往往十分宏大，一个零碎一天内可能就会产生上百万条日志，人眼间接观测显然不事实，但通过日志模式解析，咱们能够将上百万条日志压缩成几百个模板，这样就能够达到人眼可看的目标（如下图）。

其次，模式解析经常是自动化剖析过程的两头步骤，服务与后续异样检测等工作，因为模式解析后的后果是更易于剖析的。比方，咱们能够通过对某种模式的日志的打印工夫进行剖析，取得模式的周期性，将不合乎周期的点认为是异样；又比方，咱们能够通过剖析失去模式之间的呈现程序关系，如若当咱们发现模式 2 总是会跟在模式 1 前面呈现，如果忽然发现在某个工夫，模式 2 独自呈现了，这大概率也是一个异样；此外，对某种模式参数的占比进行剖析，也能判断异样。

三、如何实现日志模式解析：

本技术黑板报一共调研了 13 种经典日志解析算法，其中大部分出自于综述《Tools and Benchmarks for Automated Log Parsing》中。本技术黑板报中，依据算法的原理，将这些算法分为三类：基于聚类的日志模式解析算法、基于频繁项开掘的日志模式解析算法、基于启发的日志模式解析算法。下图为本技术黑板报中设计到的算法及其分类：

被同一条代码打印进去的日志必定是类似的，所以咱们能够失去第一种模式解析的思路，给出文本类似度公式或间隔公式，通过聚类算法，将雷同模式的日志聚到一起，而后再获取日志模板，即基于聚类的日志模式解析算法，如 Drain、Spell（LCS 也能够认为是一种文本类似度）、Lenma、Logmine、SHISO 等。

而因为代码在打印日志的时候，常量在所有打印进去的日志中都会呈现，参数则在日志中可能大不相同，所以咱们认为，常量在日志中呈现的频率较高，参数在日志中呈现的频率较低，换言之，呈现频率较高的为常量，呈现频率较低的为参数，通过这个性质，咱们能够失去第二种模式解析的思路，即基于频繁项开掘的日志模式解析算法，如 SLCT、Logram、FT-Tree。

此外，某些算法中蕴含对日志的一些启发性假如，比方雷同长度的日志才有可能是同一类日志、前几个单词雷同的日志才有可能是同一类日志，这些假如也能用于模式解析中。某些聚类算法也有可能含有一些启发性假如，但能够通过算法是否应用了类似度来分辨基于聚类的日志模式解析算法与基于启发的日志模式解析算法。

整体来说，这三类办法，都能够形象为以下流程，其中，少部分办法中会波及到模式交融流程，大部分办法只有预处理、聚类、模板取得过程，而模板取得经常与聚类过程交融，局部算法甚至先取得模板，而后将雷同模板的日志聚在一起，所以本技术黑板报将这两个流程合在聚类流程中介绍。

1、预处理：

不论是基于聚类的日志模式解析算法、基于频繁项开掘的日志模式解析算法还是基于启发的日志模式解析算法，在对日志进行解析前，都会先进行分词，因为词是表白残缺含意的最小单位。除了分词之外，Drain、DAGDrain、POP、LogMine、LkE 均提到要进行类型辨认，即通过正则匹配，将一些非凡词，如 IP 地址、工夫等给辨认进去，而后替换为特殊字符或去掉，这是因为这些非凡词显著是参数，如此解决能够无效进步雷同模式日志的类似度。AEL 则提出要辨认 key-value 对，并将 value 替换成非凡字段，也是相似的考量。此外，Logram 提出，在进行解析之前，须要将日志的 header 给去除（即日志的工夫戳、等级、组件信息）。而 Lenma、SHISO 算法，是基于日志提取的特征向量计算类似度的，而不是基于分词后的日志单词列表，所以这俩算法预处理时会多特征提取这一步骤。

2、聚类：

本节将依据解析算法的类别来对聚类办法进行阐明。

(1). 基于聚类的日志模式解析：

a. 类似度

基于聚类的日志模式解析，都会通过文本类似度或间隔公式，判断日志是否属于某一模式。有些算法在计算文本类似度时，间接通过单词列表计算类似度，如 Drain、DAGDrain 等；而有些算法，则是先通过单词列表提取特色，而后计算特色的类似度，如 Lenma、SHISO。有些算法应用的文本类似度公式要求输出等长，而有些算法则不须要。

从上表中能够看到，大部分算法应用的文本类似度公式中，都是要求输出要等长的，这是因为这些算法都有假设，同一模式的日志长度雷同，这一假设能够无效缩小类似度计算的次数，升高类似度计算的难度，但也存在肯定的局限性。

Drain 和 DAGDrain 应用的类似度公式雷同，都为：

公式翻译下来，就是两条日志从左往右，一个一个单词看，相不雷同，统计雷同单词的数量，除以日志长度就失去类似度了，如日志 [Node,001,is,unconnected] 与日志[Node,002,is,unconnected]，Node、is、unconneted 三个单词雷同，且地位统一，所以两条日志的类似度为 3 /4。

LogMine 应用的间隔公式为：

这个间隔公式与 Drain 应用的类似度公式十分类似，不过他容许两条日志不等长，也容许手动设置单词雷同时的分数。公式翻译下来，也是两条日志从左往右，一个一个单词看相不雷同，直到更短的日志看到了结尾就不看了，统计雷同单词的数量，除以更大的日志长度失去类似度。如，若 k1=1，日志 [Node,001,is,unconnected] 与日志 [Node,002,is, unconnected,too]，Node、is、unconneted 三个单词雷同，且地位统一，所以两条日志的类似度为 3 /5。然而这个间隔公式同样有局限性，若日志地位呈现了一点偏移，那么雷同模式的日志计算出的类似度也会非常低，如日志[Node,001,is,unconnected] 与日志[Node,002,003,is,unconnected]。尽管日志都蕴含单词 Node、is、unconneted，属于同一模式，但 is、unconneted 在两条日志中的地位不同，所以两条日志的类似度算下来只有 1 /5。

Spell 中，则通过 LCS(最大公共子序列)来判断类似度：

LCS 是计算机科学中的一个经典问题，不理解的同学能够自行百度一下，Spell 通过 LCS 判断类似度的形式冲破了长度的局限性，然而也带来了效率的问题，因为准确解决 LCS 问题的算法须要 O(mn) (m,n 为 seq1、seq2 长度) 的工夫复杂度。

LKE 应用的间隔为文本的编辑间隔，及计算将 seq1 转化为 seq2，所须要操作 (增、删、改) 的最小单词数量。此外，LKE 提出，在计算间隔时，要思考到操作的单词的地位，操作的单词越靠前，两条文本的间隔越大。因而，文章提出了加权的编辑间隔：

编辑间隔同样冲破了长度的局限性，但工夫复杂度依然是一个痛点。

Lenma 计算类似度时，须要先依据日志音讯，提取特征向量。Lenma 应用的特征向量叫做词长度向量，提取的形式很简略，即记下日志每个单词的长度，而后将长度拼接在一块就能够了。如日志[Node,001,is,unconneted]，其词长度向量为[4,3,2,10]。其类似度计算公式为词长度向量的余弦类似度：

先提取特征向量再计算类似度的长处在于，向量能够并行进行矩阵计算，在类似度计算这一模块计算效率会更高，然而提取特色，也意味着失落信息。

SHISO 的所应用的类似度公式为：

其中，C(W1[i])、C(W2[i])为依据单词 W1[i]、W2[i]生成的特征向量。SHISO 中思考的特征向量有大写字母、小写字母、数字、及其他，则生成的向量为 4 维，每一维度别离是大写字母、小写字母、数字、及其他的个数。如单词 Node，生成的特征向量为[1,3,0,0]。

b. 聚类逻辑：

有了类似度计算公式之后，就能够进行聚类了。一种最简略的聚类逻辑就是，将所有聚类簇存储下来，当有一条日志须要解析时，将该日志与所有聚类簇的聚类核心（聚类核心可能是单词列表，也可能是特征向量，由第一个进入该聚类簇的日志决定，并随着进入的日志而更新）一一计算类似度，找到类似度最大的聚类簇。若类似度满足阈值要求，则将待解析日志并入该聚类簇中，并更新聚类核心，若没有满足阈值要求的聚类簇，则将待解析日志作为聚类核心，创立新的聚类簇。Spell 和 Lenma 用的都是这样的聚类逻辑。

这种聚类逻辑非常简单，但有一个问题，就是计算类似度的次数太多，有多少个聚类簇就要计算多少次类似度，计算效率低下。所以，更多的算法，在计算类似度之前，会先给日志进行分组，而后每个组内采纳这样的聚类逻辑进行聚类。

如 Drain 算法，就采纳了树结构的形式对日志进行分组。Drain 的分组策略有两块：依据日志的长度分组以及依据日志的前几个单词分组。Drain 的树深度可设，树深度决定了用前多少个单词进行分组。其分组策略如图所示，当有一条日志须要解析时，会依据该日志的长度及前几个单词顺次向下搜寻，直到叶子节点。叶子节点下存储着该组别中的聚类簇，搜寻到叶子节点后再计算类似度，依据类似度计算结果更新聚类核心或者创立新的聚类簇。

DAGDrain 算法与 Drain 算法相似，也采纳了树结构进行分组，分组策略有两块：依据日志的长度分组及依据日志的首单词或尾单词分组。日志的长度容易了解，依据日志的首单词或尾单词分组的形式是：依据日志的首单词或者尾单词是否含有数字及特殊字符，提取出日志的首单词或者尾单词，并给其加上首单词或者尾单词的标记作为 split_token，split_token 统一的日志才会被分到同一组别当中。

AEL 算法则会依据日志长度及 key-value 对的对数给日志进行分组，而后在组别下计算类似度进行聚类。

总结下来，提前分组的形式一共有四种：依据日志长度分组，依据日志前几个单词分组，依据日志的首单词或者尾单词分组，依据 key-value 对的对数分组，这四种形式其实都有其不足之处。依据日志长度分组受分词影响太大，不当的分词可能会使雷同模式的日志有不同的长度，而且，对于某些参数占多个地位的日志，长度也会将其谬误的分到不同组别中。如日志 [Node,000,is,unconnected] 与日志[Node,001,002,is,unconnected]。依据日志前几个单词分组在大部分时候是有用的，但有时参数也有可能在日志前列。依据日志的首单词或者尾单词分组的策略，若日志的 header 未去除，则大概率无奈施展其成果。依据 key-value 对的对数分组，则有可能受到正则匹配不当的影响。

除了提前分组之外，档次聚类也是进步解析效率的一个办法，如 SHISO，SHISO 也是一个树结构的解析算法，树的每个节点都对应一个聚类簇，算法要求每个节点的子节点个数都要小于阈值 t。其算法流程为：遍历子节点，看是否存在类似度满足要求的聚类簇。若存在，则更新聚类核心；若不存在，且子节点个数小于阈值，则在该节点下插入新聚类簇；若不存在，且子节点个数等于阈值，则找到类似度最大的节点，在该节点下持续遍历子节点，始终迭代直到找到类似度满足要求的聚类簇。

Logmine 中也提到能够用档次聚类算法，不过他的档次聚类目标却并不是提高效率，相同，可能还会升高肯定的解析效率，但却给人工灵活处理解析等级提供了可能。Logmine 也是采纳的树结构进行聚类，其提出，在树的第一层，用十分小的间隔阈值对日志进行聚类，造成聚类簇，这样，能够将日志分的足够细，防止不同模式的日志聚在一起，聚类簇的聚类核心为第一个进入该聚类簇的日志，且不更新。第二层开始，用更大的间隔阈值，对上一层的聚类核心进行聚类，造成聚类核心的聚类簇，聚类核心为第一个进入聚类簇的数据，且随着新的数据进入而更新。

c. 主动阈值：

大部分基于聚类的解析算法，类似度阈值都是须要人工设置的，LKE 和 DAGDrain 给出了两种主动阈值的思路。LKE 提出能够通过 k -means 聚类取得类似度阈值，而 DAGDrain 则提出如下的主动阈值公式：

然而主动阈值的有效性还有待验证，在此就不再开展阐明。

(2). 基于频繁项开掘的日志模式解析：

基于频繁项开掘的日志模式解析算法，在聚类前，要对频率进行统计(大部分是单词频率，Logram 统计的是 n -gram 频率)。

SLCT 是最早的日志模式解析算法，其原理较为简单，算法流程如下：如果某条日志中日志单词 W(i)的呈现频率大于阈值 s，那么认为 W(i)是一个频繁词，将该条日志的所有频繁词及其地位提取进去，作为聚类候选。如日志 [Interface,eth0,down] 中，若 Interface，down 的呈现频率大于阈值，则该日志生成的聚类候选为{(Interface, 1) (down, 3)}，聚类簇候选呈现次数大于阈值则正式称为聚类簇。

Logram 创新性的将 n -gram 引入到频繁项开掘算法中。其在解析前，须要统计日志中所有的 n -gram 频率 (n=1,2,……k, k 为设置参数)。解析时，先取得日志的 k -gram 频率，将频率小于 k -gram 阈值的 k -gram 挑出来作为参数候选，而后，将筛选进去的 k -gram 合成为 k -1-gram，再从其跳出 k -1-gram 的参数候选，直到 2 -gram。对于日志的任一单词，若其所有 2 -gram 都在 2 -gram 参数候选中，则该单词为参数，反之为常量。如日志[Node,000,is,unconnected] 中，000 的 2 -gram 有 Node->000，000->is，若 Node->000，000->is 都在 2 -gram 参数候选中，则 000 为参数。将常量固定，参数转化为特殊符号 <*> 即可取得日志模式。

SLCT 与 Logram 都是效率十分快的算法，然而他们均有一个问题：判断频繁词（或频繁 n -gram）的阈值不好确定。而且，在事实中，存在这样一种状况：某些代码打印的次数非常少，但有些代码打印的次数十分多，这就意味着，那些打印次数少的代码生成的日志中，常量的频率也会很低，非常容易被认为是参数。所以，这两种算法不太举荐应用。

FT-tree 也是一种基于频繁项开掘的日志模式解析算法，采纳了独创的 FT-tree 的数据结构进行解析。在解析前，该算法会遍历所有日志，而后取得日志中单词的呈现频率，将单词依据其呈现频率从大到小排序，造成列表 L。解析日志时，对于待解析日志，会依据列表 L 对日志的单词进行排序，而后插入到 FT-tree 中（这样能够让频率高的单词更凑近根节点，频率低的单词更远离根节点），如图所示，直到所有日志都插入实现。那接下来 FT-tree 又是如何判断常量与参数的呢？

咱们思考对于同一代码打印进去的日志，如[Node,000,is,unconnected]，[Node,001,is,unconnected]，[Node,002,is,unconnected]，将这些日志插入到 FT-tree 中后，越凑近根节点的单词必定越有可能是常量，因为呈现频率越高。而且，咱们会发现，在凑近根节点时，树简直没有分岔，但到某个节点后，子节点的个数将指数型回升，该节点正是常量与参数的分界线。通过这个思维试验，咱们能够很天然的失去 FT-tree 接下来的操作——剪枝。这样一来，留在 FT-tree 中的节点代表的就都是常量了。含有雷同常量的日志，FT-tree 认为属于同一模式。

FT-tree 构造奇妙，但也有可能存在一些问题，如有些参数可能是无限的，在 FT-tree 上不会造成那么大的分岔，可能也会留在 FT-tree 上，此外，不同模式之间，若含有独特的常量，在该常量下也有可能会造成分岔而导致子节点被剪枝，将多种模式分到一起。

(3). 基于启发的日志模式解析

本文调研的基于启发的日志模式解析算法只有两种，POP 和 IPLOM，然而其实，在基于聚类的日志模式解析算法中，也用到了很多启发式规定，如 Drain、DAGDrain 的分组策略。

POP 中所用的启发式策略有两个：1、依据日志长度分组。2、依据单词地位分组。依据单词地位分组的思路与 FT-tree 的思路有些相似，都是基于认为参数会导致分岔过多而设计的。其步骤是：在组别内，统计每个地位上，该组别中一共有几种单词，找到单词品种起码但不为 1 的地位进行分组。如下图四条日志中，就能够抉择地位 1 或地位 2 进行分组，因为地位 1 和地位 2 都只有 2 种单词，而地位 3 有 4 种。始终如此分，直到非 1 的最小单词品种数及单词品种数除以组内日志数的值都大于阈值。

IPLOM 中用的启发式策略有三个：1、依据日志长度分组。2、依据单词地位分组。3、依据双射关系分组。其中，启发式策略 3 的原理同样是认为参数会导致分岔过多，在此不持续介绍。

3、模式交融：

DAGDrain 算法及 POP 算法中，都提到在失去日志模式之后，能够将通过计算日志模式之间的类似度，将日志模式再次聚类进行交融。日志模式交融是一个高杠杆的操作，因为模式的交融须要聚类的数据量为模式数量，远小于日志数量，所以绝对于日志聚类，模式交融破费的工夫非常少，而其又能够起到改善聚类后果的作用。

DAGDrain 中，采纳的模式交融类似度为：

其中，lenNew 为交融后的新模式的长度，lenExist 为原有模式的长度，lenLCS 为新模式与原有模式的最大公共子序列长度。

POP 中，采纳的模式交融间隔公式为曼哈顿间隔：

其中，N 为两个文本所含有的公共单词，ai、bi 别离值文本 a、b 中，第 i 个单词的数量。

四、小 tip:

日志解析算法很多，而且通过方才的介绍咱们能够发现，上述算法中，很多步骤，都能够了解为是一个分组的过程，分组是相互不影响的过程，咱们依据这个策略分组之后，在分完的组内，持续通过其余策略分组也是能够的。所以咱们无妨大胆一些，有很多算法中的办法都是能够互相交融组成新算法的。比如说，在 Drain 算法的树结构中，是否能够退出依照 key-value 对个数分组的层呢？又比如说，是否能够将 FT-tree 的树结构，看做是一个分组的过程，分组之后，再依据类似度计算进行聚类呢？又比如说，Drain 算法分完组后，是否能够再应用 SHISO 的档次聚类策略，防止 Drain 算法某个叶子节点下的模式过多影响效率呢？然而，在交融的过程，永远要留神成果，与效率。

写在最初

近年来，在 AIOps 畛域疾速倒退的背景下，IT 工具、平台能力、解决方案、AI 场景及可用数据集的迫切需要在各行业爆发。基于此，云智慧在 2021 年 8 月公布了 AIOps 社区， 旨在树起一面开源旗号，为各行业客户、用户、研究者和开发者们构建沉闷的用户及开发者社区，独特奉献及解决行业难题、促成该畛域技术倒退。

社区先后 开源 了数据可视化编排平台 -FlyFish、运维治理平台 OMP 、云服务治理平台 - 摩尔平台、 Hours 算法等产品。

可视化编排平台 -FlyFish：

我的项目介绍：https://www.cloudwise.ai/flyF…

Github 地址：https://github.com/CloudWise-…

Gitee 地址：https://gitee.com/CloudWise/f…

行业案例：https://www.bilibili.com/vide…

局部大屏案例：

请您通过上方链接理解咱们，增加小助手（xiaoyuerwie）备注：飞鱼。退出开发者交换群，可与业内大咖进行 1V1 交换！

也可通过小助手获取云智慧 AIOps 资讯，理解云智慧 FlyFish 最新进展！