日志聚类算法 Drain 的实践与改良

在现实场景中，业务程序输出的日志往往规模庞大并且类型纷繁复杂。我们在查询和查看这些日志时，平铺的日志列表会让我们目不暇接，难以快速聚焦找到重要的日志条目。

在观测云中，我们在日志页面提供了聚类分析功能，可以快速聚合相似的日志文本，帮助你全览不同类型的日志。这个功能背后就由基于 Drain 的改良算法驱动。

快速理解 Drain 算法

根据 logparser 项目提供的 Benchmark 数据和论文原文可知，Drain 在一众日志聚类算法中准确度和性能都几乎是最好的，所以我们选择基于 Drain 算法来实现产品功能。

在这里我们尝试根据 Drain 论文来总结和梳理一下算法的主要逻辑：

1、首先对日志进行业务预处理，将一些常见的日志模式替换为占位符，比如时间、用户 ID、IP 等

2、对预处理的数据进行分词，并在 Drain 的搜索树的第一层找到对应单词数量的子节点

3、再逐个根据日志中的单词序列，在下层的前缀搜索树上找到对应的日志聚类桶

4、遍历对应前缀树指向的日志聚类桶，分别判断当前日志跟对应日志类的相似度是否达到阈值

相似度算法：两条日志从左往右，一个一个单词看相不相同，统计相同单词的数量，除以日志长度就得到相似度

5、如果相似则将当前的日志加入该类别，不相似则创建新的类别并加入到前缀树中

我们回顾一下上述的处理流程：

1、占位预处理的目标是为了将日志中最常见的变量替换为相同的占位符，来提升相同单词的比例，以提升最终文本的相似度

2、Drain 第一层的按照单词数区分的子树和后续根据前缀树拆分的子树目标都是缩小相似度计算的开销，我们只用跟最可能相似的日志组来对比计算

相信到这里，你已经基本理解了 Drain 算法的基本设计思路。这个算法思路总体并不复杂，固定深度的查找树、简单的相似度匹配算法都让算法的运行非常高效。

改良 1：占位处理后置，并提升处理效率

我们在最初的使用中按照论文的描述给日志增加了一些常见的日志模式占位符，比如：

时间： [0-9]{1,}:[0-9]{1,}:[0-9]{1,}.?[0-9]{1,}?
IPv4： \\d{1,3}\\.\\d{1,3}\\.\\d{1,3}\\.\\d{1,3}
Hex： 0x[a-f0-9A-F]+
数字： -?[0-9]{1,}.?[0-9]*
ID： [0-9a-f]{4,}

众所周知，时间在日志中输出的格式是可能有非常多种类型的，我这里只添加了最简单的一种，还有 IPv6 因为正则表达式的规则过于复杂也还没加。

在初步添加上述少量的占位符匹配之后，我们就发现 Drain 算法的匹配效率显著下降。

在我们内部一个 1w 行的测试数据集上，完成训练的时间由 80ms 增长到 2.2s，匹配效率降低约 30 倍，通过 CPU Profiler 调用树可以观察到性能的主要开销都在正则表达式的替换上。

那么不进行占位处理可以吗？不可以，这些变量会严重影响日志相似度的判定。

那么可以换更高效的正则表达式库吗？我们尝试了一些常见的优化方案，但提升的幅度没有这么显著。

我们使用多个正则表达式对全部日志的每个单词都进行了一遍正则的匹配，这个的开销自然是不低的。那这个完整的匹配是必须的吗？哪些路径的正则匹配是必须的？

前面我们已经强调过，我们期望的通过占位处理之后不影响日志相似度的判断。那么我们其实只需要在日志相似度运算的时候对必要的单词来做这个正则匹配就好了。

假设当前日志组的模板变量是：Just A Log Template <Number> ，现在我们有一个日志 Just A Log Template 123 需要跟这个模板对比相似度，我们在逐个单词进行对比相似度时，只需要判断日志的最后一个单词是否匹配中 <Number> 占位符对应的正则表达式，我们不用判断这个单词是否能匹配中其他的占位符，也不用关注其他的单词是什么情况，更不必要提前对这个日志进行完整占位处理。

Drain 本身通过多层的分桶降低了我们日志需要判断的聚类组的数量，另外我们根据日志组的模板变量确定了需要进行哪种占位符的判断，所以实际的匹配开销经过这两重剪枝就大大降低了。在刚才提到的数据集下，我们把占位符的匹配后置，完成训练的时间就降低到只有 120ms 左右了。

改良 2：提升占位处理通用性

在通过剪枝解决了匹配效率问题之后我们还关注到当前的占位处理的逻辑其实不太通用，IPv4、IPv6、超多种时间格式、用户自行输出的结构体、JSON 文本等等其实结构非常复杂，根据不同的使用习惯不同也难以罗列完整，维护也比较复杂。

我们最终的方案是尝试将常见的符号比如 :.," 等前后添加空格，在分词时就可以把这些符号拆分成单独的单词，这样比如一个 IPv4 的地址会被拆分为 <Number>:<Number>:<Number>:<Number> ，一个 IPv6 地址会被拆分为 <ID> 和 : 子元素，时间格式会被拆分为数个 <Number> 和 : 。

按这种逻辑，我们最终只维护了三个基本的占位元素，分别是：

数字： [-+]?[0-9]+
Hex： 0x[a-f0-9A-F]+
ID： [a-f0-9A-F]{4,}

这样除了维护更简单，常见的占位格式都不用维护，而且对 JSON 文本的支持也更友好了，可以将其中的 KV 都完全拆分。

改良 3：支持变长日志聚类

回忆一下 Drain 的处理流程，我们在知道日志长度的时候就直接划分子树了。那么显而易见的，Drain 对变长的日志支持效果都不会太好。

举个实际点的例子，两个包含 UA 的请求日志：

1、[28/Aug/2022:07:01:36 +0800] "GET / HTTP/1.1" 200 "Mozilla/5.0 (Linux; Android 12; PEEM00 Build/RKQ1.211119.001; wv) AppleWebKit/537.36 (KHTML, like Gecko) Version/4.0 Chrome/97.0.4692.98 Mobile Safari/537.36"

2、[28/Aug/2022:07:50:18 +0800] "GET / HTTP/1.1" 200 "Mozilla/5.0 (Linux; Android 9; MI 8 Build/PQ3A.190801.002; wv) AppleWebKit/537.36 (KHTML, like Gecko) Version/4.0 Chrome/87.0.4280.101 Mobile Safari/537.36"

这两条日志的长度是不一样的，一个的手机型号是 PEEM00 一个的手机型号是 MI 8 。所以虽然两个日志非常相像，但还是不会被聚合到同一个类别中。

这合理吗？显然是不合理的。

所以我们给 Drain 额外增加了一个相邻长度聚类组的相似度判断逻辑。同时要注意到，之前我们的相似度判断算法是逐个单词匹配的，当这里单词数不一样的时候，中间可能会错位，导致相似度计算可能会很严重偏低，我们原有的算法已经不太适用这种情况了。

常见的文本相似度算法都不限定两个文本单词长度必须相等，比如计算欧几里得距离、曼哈顿距离、明可夫斯基距离、余弦相似度等。这里我们最终选用了 minhash 算法，我们可以提前对每个日志组计算好特征向量，在判断匹配时给日志行计算雅卡尔距离时可以更高效。

同时要注意的是，如果你的数据集是请求日志这样的数据，单词的长度可能都差不多，并且不同的日志组本身的相似度其实已经很高了。这样的数据集下，你不能只优先匹配相邻长度的日志组，应该优先把前后一定长度范围的全部日志组放在一个大池子里来找到最优解。