网站名字设计,注册外国网站,苏州战斧网络科技有限公司,镇江网站关键字优化公司在现实场景中#xff0c;业务程序输出的日志往往规模庞大并且类型纷繁复杂。我们在查询和查看这些日志时#xff0c;平铺的日志列表会让我们目不暇接#xff0c;难以快速聚焦找到重要的日志条目。
在观测云中#xff0c;我们在日志页面提供了聚类分析功能#xff0c;可以…在现实场景中业务程序输出的日志往往规模庞大并且类型纷繁复杂。我们在查询和查看这些日志时平铺的日志列表会让我们目不暇接难以快速聚焦找到重要的日志条目。
在观测云中我们在日志页面提供了聚类分析功能可以快速聚合相似的日志文本帮助你全览不同类型的日志。这个功能背后就由基于 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 算法我们可以提前对每个日志组计算好特征向量在判断匹配时给日志行计算雅卡尔距离时可以更高效。
同时要注意的是如果你的数据集是请求日志这样的数据单词的长度可能都差不多并且不同的日志组本身的相似度其实已经很高了。这样的数据集下你不能只优先匹配相邻长度的日志组应该优先把前后一定长度范围的全部日志组放在一个大池子里来找到最优解。
总结
经过我们对 Drain 的深入剖析和改良新算法的流程是这样的
1、直接对日志文本进行分词并在 Drain 的搜索树的第一层找到对应单词数量的子节点
2、再逐个根据日志中的单词序列在下层的前缀搜索树上找到对应的日志聚类桶
3、遍历对应前缀树指向的日志聚类桶分别判断当前日志跟对应日志类的相似度是否达到阈值
相似度算法两条日志从左往右依次对比如果类别模板中对应位置是占位符则使用占位符对应的正则表达式匹配原始文本跟原有算法一样计算相似度
4、如果相似则将当前的日志加入该类别不相似则拿出来前后一定范围长度的全部日志类别对比这些日志于当前的日志的 minhash 的笛卡尔距离判断相似度是否达到阈值
5、如果前面两种相似度判断都失败则创建新的日志分类此时注意需要对现有的日志进行完整的占位符替换最后将创建的新的日志类别加入前缀搜索树中
经过如上的处理流程该算法对于定长、变长、JSON 等格式的日志聚合表现相比于原版 Drain 都更加优异同时也能保持极高的匹配效率。
