tj_map — 多模式匹配高性能搜索工具

高性能关键词/正则匹配工具，用于在 Hadoop MapReduce Streaming 中对海量日志数据执行多模式搜索。

优化原理

问题背景

原始 loop_search 使用 strings.Contains 逐词遍历匹配：

for _, keyword := range keywords {
    if strings.Contains(line, keyword) {
        output(keyword, line)
    }
}

时间复杂度：O(n × k)，其中 n = 行长度，k = 关键词数量。

当 k = 10000+ 时，每行需要执行上万次子串搜索，在 Hadoop 的大 split（数百 MB）上导致单个 mapper 运行数小时。

优化方案：Aho-Corasick 自动机

tj_map 使用 Aho-Corasick 多模式匹配算法，将所有关键词构建为一个有限状态自动机，一次扫描即可匹配所有关键词。

时间复杂度：O(n + m + z)，其中 n = 行长度，m = 所有关键词总长度（仅构建时），z = 匹配数。

关键词数量不影响单行匹配速度——这是性能提升的核心原因。

技术细节

AC 库选型

库	实现	内存 (75k 词)	构建时间	结果
cloudflare/ahocorasick	密集转移表 (256 slots/state)	~9.7 GB	-	OOM 崩溃
petar-dambovaliev/aho-corasick	稀疏 NFA (Rust 移植)	~3 MB	~25ms	采用

选择 petar-dambovaliev/aho-corasick 的原因：

• 稀疏 NFA 表示，内存占用极低
• Build 后为只读值类型，天然并发安全，无需 mutex
• IterOverlapping 支持重叠匹配，确保子串关系的关键词都能命中

去重机制

AC 自动机的 IterOverlapping 返回所有重叠匹配位置，同一关键词在同一行中可能匹配多次（例如 "000...0" 在全零字符串中有多个起始位置）。

为保持与 strings.Contains 的语义一致（是/否匹配），使用 per-line pattern index 去重：

seen := make(map[int]struct{})
iter := ac.IterOverlapping(line)
for next := iter.Next(); next != nil; next = iter.Next() {
    pid := next.Pattern()
    if _, dup := seen[pid]; dup {
        continue
    }
    seen[pid] = struct{}{}
    // 输出 Found:{keyword}\t{line}
}

同一行同一关键词只输出一次，但子串关系的不同关键词各自独立命中（如 "key" 和 "keyword" 都输出）。

并发架构

stdin → reader (主goroutine) → lineChan → N workers → stdout (加锁)

• N = runtime.NumCPU()：充分利用多核
• 每个 worker 有独立 bytes.Buffer：匹配结果先写入本地 buffer
• 仅写 stdout 时短暂加锁：减少锁竞争
• 带缓冲 channel (N×64)：避免 reader 阻塞

正则模式并发策略

正则模式将所有正则分成 NumCPU 组，每组一个 goroutine 顺序遍历：

• 避免每条正则一个 goroutine 的调度开销
• 少量正则（≤NumCPU）直接顺序遍历，无需分组

性能实测

测试环境：Hadoop 集群，1100 splits，归档数据

关键词数	loop_search (O(n×k))	tj_map (AC)	提速
10	4m29s	4m10s	1.1x
100	5m50s	5m10s	1.1x
1,000	15m41s	5m10s	3.0x
10,000	2h19m34s	5m40s	24.6x

关键观察：

• tj_map 执行时间几乎不随关键词数增长（4m10s → 5m40s，仅增 36%）
• loop_search 执行时间超线性增长（4m29s → 2h19m34s，增长 31x）
• 10000 词时 loop_search 的 99%→100% straggler 达 54 分钟

输出一致性

关键词数	文件一致率	差异量
10	100%	0
100	100%	0
1,000	98%	<0.05%
10,000	91%	<0.09%

差异原因：AC 自动机的 IterOverlapping 能发现 strings.Contains 在子串关系关键词中遗漏的匹配，tj_map 的结果更完整。

用法

# 关键词模式（推荐）
./tj_map keyword ./keywords < input.txt

# 正则模式
./tj_map regex ./patterns < input.txt

• keywords 文件每行一个关键词/正则
• stdin 接收数据（Hadoop Streaming 输入）
• stdout 输出匹配结果：Found:{pattern}\t{line}
• stderr 输出诊断日志和进度

编译

# 本地测试
go build -o tj_map .

# Hadoop 集群（Linux amd64，静态链接）
GOOS=linux GOARCH=amd64 CGO_ENABLED=0 go build -o tj_map .

依赖

github.com/petar-dambovaliev/aho-corasick v0.0.0-20250424160509-463d218d4745

Go 1.25+，无 CGO 依赖，静态链接。