首页 > 基础资料 博客日记
LogParser-LLM 前缀树算法实现
2025-12-25 10:07:03基础资料围观1次
根据 LogParser-LLM 的架构设计，前缀树（Prefix Tree / Prefix Parse Tree）的核心目标是作为高速缓存，拦截 99% 的重复日志模式，仅在无法“严格匹配”时才调用 LLM。以下是基于论文描述的 Java 实现方案。该实现涵盖了核心数据结构设计、日志匹配逻辑（Strict Match）以及模版更新机制。
核心设计思路
1. 节点设计 (TreeNode)：
◦ 每个节点代表日志中的一个 Token（单词）。
◦ 节点分为两种路径：静态路径（精确匹配单词）和通配符路径（匹配动态参数，论文中用 <*> 表示）。
◦ 非根节点（不仅是叶子节点）都可以指向一个或多个 LogCluster（日志簇），因为不同长度的日志可能共享前缀。
2. 工作流程：
◦ 插入 (Update)：当 LLM 提取出新模板（例如 User <*> login）后，将模板分词并插入树中。
◦ 查询 (Search)：新日志进来后，逐词遍历树。如果能完全走通某条路径（静态词匹配或对应位置有 <*> 节点），则判定为 Strict Match（严格匹配）。
--------------------------------------------------------------------------------
Java 代码实现
1. 定义基础类：LogCluster 和 TreeNode
import java.util.*;
// [6] Log Cluster: 存储日志模板信息的容器
class LogCluster {
String template; // LLM 提取出的模板，例如 "Connection from <*>"
String clusterId;
public LogCluster(String template, String clusterId) {
this.template = template;
this.clusterId = clusterId;
}
@Override
public String toString() {
return "Cluster[" + clusterId + ": " + template + "]";
}
}
// [4] Prefix Parse Tree Node
class TreeNode {
// 静态Token的子节点映射 (例如 "Connection" -> nextNode)
Map<String, TreeNode> children = new HashMap<>();
// [4] 通配符节点：用于处理模板中的 <*>，匹配任意动态参数
TreeNode wildcardChild = null;
// [4] 该节点可能关联的日志簇（非叶子节点也可能有簇）
List<LogCluster> clusters = new ArrayList<>();
// 获取或创建普通子节点
public TreeNode getOrCreateChild(String token) {
return children.computeIfAbsent(token, k -> new TreeNode());
}
// 获取或创建通配符子节点
public TreeNode getOrCreateWildcardChild() {
if (wildcardChild == null) {
wildcardChild = new TreeNode();
}
return wildcardChild;
}
}
2. 实现前缀树逻辑：LogPrefixTree
public class LogPrefixTree {
private final TreeNode root;
private static final String WILDCARD = "<*>"; // [4] 论文定义的通配符
public LogPrefixTree() {
this.root = new TreeNode();
}
/**
* [7] 更新树 (Update Tree)
* 当 LLM 返回一个新的模板时，将其解析并存入树中
* @param template 例如 "User <*> logged in"
* @param cluster 对应的日志簇对象
*/
public void insertTemplate(String template, LogCluster cluster) {
// [8] 简单的分词，论文中使用空格分割
String[] tokens = template.trim().split("\\s+");
TreeNode current = root;
for (String token : tokens) {
if (token.equals(WILDCARD)) {
// 如果模板当前位置是 <*>, 走通配符路径
current = current.getOrCreateWildcardChild();
} else {
// 否则走精确匹配路径
current = current.getOrCreateChild(token);
}
}
// 在路径末尾绑定簇信息
current.clusters.add(cluster);
}
/**
* [5, 9] 匹配搜索 (Cluster Matching)
* 尝试为新日志寻找 "Strict Match" (严格匹配)
* @param logMsg 原始日志消息
* @return 匹配到的 LogCluster，如果没有严格匹配则返回 null
*/
public LogCluster search(String logMsg) {
String[] tokens = logMsg.trim().split("\\s+");
return searchRecursive(root, tokens, 0);
}
// 递归搜索以处理可能的路径分支
private LogCluster searchRecursive(TreeNode node, String[] tokens, int index) {
// 1. 终止条件：日志所有 Token 处理完毕
if (index == tokens.length) {
// 检查当前节点是否有关联的簇
if (!node.clusters.isEmpty()) {
// [5] 严格匹配要求 Token 数量一致。
// 简单实现中，如果路径走完且节点有簇，通常即为匹配。
// 实际可能需要校验 Cluster 里的模板长度。
return node.clusters.get(0);
}
return null;
}
String currentLogToken = tokens[index];
LogCluster result = null;
// 2. 优先尝试：精确匹配 (Static Match)
// [5] 检查是否存在与当前日志 Token 完全一致的路径
if (node.children.containsKey(currentLogToken)) {
result = searchRecursive(node.children.get(currentLogToken), tokens, index + 1);
if (result != null) return result;
}
// 3. 备选尝试：通配符匹配 (Wildcard Match)
// [5] 如果精确匹配失败，检查当前是否有 <*> 路径
// 逻辑：模板里的 <*> 可以匹配日志里的任何 Token (如 IP, ID 等)
if (node.wildcardChild != null) {
result = searchRecursive(node.wildcardChild, tokens, index + 1);
if (result != null) return result;
}
// 4. 无法匹配 (No Match)
return null;
}
}
3. 模拟运行流程
以下代码展示了系统如何利用前缀树处理日志，并在匹配失败时模拟调用 LLM 的过程。
public class LogParserLLMDemo {
public static void main(String[] args) {
LogPrefixTree parser = new LogPrefixTree();
// 模拟场景：
// 1. 系统刚启动，树是空的
String log1 = "User 1001 logged in";
System.out.println("Processing: " + log1);
LogCluster match1 = parser.search(log1);
if (match1 == null) {
System.out.println("-> No Match. Calling LLM...");
// [10] 模拟 LLM 提取模板
String llmGeneratedTemplate = "User <*> logged in";
LogCluster newCluster = new LogCluster(llmGeneratedTemplate, "C1");
// [7] 更新树
parser.insertTemplate(llmGeneratedTemplate, newCluster);
System.out.println("-> Tree Updated with: " + llmGeneratedTemplate);
}
// 2. 相同的模式，但参数不同 (Strict Match)
String log2 = "User 9999 logged in";
System.out.println("\nProcessing: " + log2);
LogCluster match2 = parser.search(log2);
if (match2 != null) {
// [5] 严格匹配成功，无需调用 LLM
System.out.println("-> Strict Match Found! " + match2);
} else {
System.out.println("-> No Match.");
}
// 3. 全新的日志模式
String log3 = "Connection failed at 10.0.0.1";
System.out.println("\nProcessing: " + log3);
LogCluster match3 = parser.search(log3); // 应该返回 null
if (match3 == null) {
System.out.println("-> No Match. Calling LLM...");
// 模拟流程继续...
}
}
}
关键实现细节解析
1. Strict Match (严格匹配) 的判定：
◦ 在 searchRecursive 方法中，代码逻辑优先寻找 children (精确匹配)。
◦ 如果找不到精确匹配，但存在 wildcardChild (即模板中该位置是 <*>)，则代码会进入通配符分支。
◦ 只有当日志的 Token 序列能够完美对应树上的一条路径（静态词对应静态节点，动态参数对应通配符节点），且长度一致（走完路径到达存有 Cluster 的节点）时，才返回结果。这对应了论文中无需调用 LLM 的场景。
2. Loose Match (宽松匹配) 的处理：
◦ 上述代码实现了最核心的树结构。论文提到的“宽松匹配”（Loose Match）是指当严格匹配失败时，系统会尝试寻找“部分匹配”的簇（例如长度相同但某些静态词不匹配）。
◦ 在实际工程中，如果 search 返回 null，你可以遍历所有 Cluster 或基于 Token 长度进行二次筛选（Candidate Selection），如果发现相似度够高，再交给 LLM 决定是否 Merge（合并）。
3. 分词策略：
◦ LogParser-LLM 明确指出使用简单的空格分词（split("\\s+")），不进行复杂的正则预处理（如把 IP 替换成 *），保留原始信息给 LLM 理解。前缀树也遵循这一原则。
高并发的日志解析场景
线程安全和迭代搜索，这里提供一个针对 search 方法的优化思路
// 使用 ConcurrentHashMap 保证并发读写的安全性 (基础保障)
import java.util.concurrent.ConcurrentHashMap;
class TreeNode {
// 替换为线程安全的 Map
Map<String, TreeNode> children = new ConcurrentHashMap<>();
volatile TreeNode wildcardChild = null; // 保证可见性
// ...
}
// 迭代式搜索 (防止栈溢出，稍微复杂但更健壮)
public LogCluster searchIterative(String logMsg) {
String[] tokens = logMsg.trim().split("\\s+");
// 使用栈来保存回溯点：存储 (当前节点, 当前Token索引)
Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
stack.push(new Pair<>(root, 0));
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.pop();
TreeNode node = current.getKey();
int index = current.getValue();
// 1. 匹配完成
if (index == tokens.length) {
if (!node.clusters.isEmpty()) return node.clusters.get(0);
continue; // 路径走通但没有簇（可能是中间节点），回溯
}
String token = tokens[index];
// 2. 压入通配符路径 (作为后备选项，先入栈后出)
// 注意：栈是后进先出，所以如果我们希望“静态优先”，应该先压入通配符，再压入静态
if (node.wildcardChild != null) {
stack.push(new Pair<>(node.wildcardChild, index + 1));
}
// 3. 压入静态路径 (优先处理)
if (node.children.containsKey(token)) {
stack.push(new Pair<>(node.children.get(token), index + 1));
}
}
return null;
}
今天先到这儿，希望对AI，云原生，技术领导力， 企业管理，系统架构设计与评估，团队管理, 项目管理, 产品管理，信息安全，团队建设 有参考作用 , 您可能感兴趣的文章:
微服务架构设计
视频直播平台的系统架构演化
微服务与Docker介绍
Docker与CI持续集成/CD
互联网电商购物车架构演变案例
互联网业务场景下消息队列架构
互联网高效研发团队管理演进之一
消息系统架构设计演进
互联网电商搜索架构演化之一
企业信息化与软件工程的迷思
企业项目化管理介绍
软件项目成功之要素
人际沟通风格介绍一
精益IT组织与分享式领导
学习型组织与企业
企业创新文化与等级观念
组织目标与个人目标
初创公司人才招聘与管理
人才公司环境与企业文化
企业文化、团队文化与知识共享
高效能的团队建设
项目管理沟通计划
构建高效的研发与自动化运维
某大型电商云平台实践
互联网数据库架构设计思路
IT基础架构规划方案一(网络系统规划)
餐饮行业解决方案之客户分析流程
餐饮行业解决方案之采购战略制定与实施流程
餐饮行业解决方案之业务设计流程
供应链需求调研CheckList
企业应用之性能实时度量系统演变
如有想了解更多软件设计与架构, 系统IT,企业信息化, 团队管理 资讯，请关注我的微信订阅号：
作者：Petter Liu
出处：http://www.cnblogs.com/wintersun/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
该文章也同时发布在我的独立博客中-Petter Liu Blog。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！
标签：
相关文章
最新发布
点击排行
本站推荐
