从逐条查询 ES 到本地匹配:手动关键词消费者的算法优化
从逐规则 ES 查询带来的压力出发,结合统一示例解释 AC 自动机的多关键词扫描、关键词倒排的候选筛选、预编译布尔表达式的最终判断,逐项分析它们解决的问题、可替代实现和运行成本,并保留规则更新与匹配语义的验收边界。
上一篇介绍了我为什么将部分 Python 消费者逐步迁入独立的 Go 项目。促成这次选型的一个直接问题,是手动关键词匹配给 Elasticsearch(下文简称 ES)带来的压力。
手动关键词功能最初按机构逐步开放。覆盖范围扩大后,逐规则查询持续增加 ES 负载,接口响应与消费进度受到影响。
排查后,我准备将实时匹配从逐条请求 ES,改为消费者本地的内存计算。评估如何承载这部分工作时,再综合考虑多核并行、规则共享、内存和依赖,最终选择了 Go。
技术选型确定后,手动关键词消费者成为第一个落地改造的对象。调整后,我观察到 ES 的检索负载明显下降。
本地匹配采用了 AC 自动机、关键词倒排和预编译布尔表达式。它们分别处理文本扫描、候选筛选与规则求值,工作可以拆开理解,也有各自的替代方式。
一、旧方案怎样放大了 ES 请求
一个机构可以配置多个手动关键词专题,每个专题有一条规则。一篇文章进入消费者后,需要判断它属于哪些专题,也可能同时命中多个专题。
假设有下面四条规则。
R1 电池动态 = 新能源 AND 电池
R2 行业资讯 = 新能源 AND NOT 招聘
R3 招聘信息 = 新能源 AND 招聘
R4 咖啡行业 = 咖啡 AND 门店
旧 Python 实现先从 ES 读取该机构启用的规则,再遍历规则,为每条规则构建查询 DSL,向 ES 请求一次搜索,判断当前文章是否符合条件。
查询带有当前文章的 article_id 过滤,同时设置 size: 1 和 _source: false。查询目标是一篇已知文章,压力主要体现为大量重复请求及其执行成本。
某个机构有 R 条可执行规则时,一篇文章进入这段流程,需要一次规则读取和 R 次匹配查询。
用 N 表示进入这段流程的“文章—机构”处理次数,这一段查询次数近似为 N × (1 + R)。
举一个假设算例。某个机构每天处理 100 万篇文章,平均有 20 条有效规则,仅逐规则匹配就约有 2000 万次查询,另有逐篇读取规则的请求。这个算例用于说明放大关系,实际数量需要按机构和规则规模统计。
每次请求都包含 DSL 构建、序列化、网络传输、ES 执行和响应处理。机构数量、文章流入速度和规则数量一起增长时,请求压力会集中增加。
旧异步实现同样需要完成这些查询。调整等待方式之后,每篇文章所触发的请求数量仍然由这条处理路径决定。
二、先把规则准备与文章处理分开
这个业务有两个适合预处理的特点。
- 同一批规则会被大量文章反复使用。
- 当前文章的匹配文本可以随 Kafka 消息传入消费者。
因此,新方案在规则加载或变化时准备匹配结构,文章到来后使用进程内的规则快照。
消息携带六类文本,分别是标题、正文、图片 OCR、视频 OCR、原帖标题和原帖正文。它们共同参与文章级规则判断。
在四条示例规则中,关键词总共被引用了八次,去重后只有五个。
新能源、电池、招聘、咖啡、门店
程序给这些词分配统一编号,并准备三个结构。
- 将词表构建为 AC 自动机,用于找出文本出现过的词。
- 建立关键词到规则的倒排关系,用于找到需要检查的候选规则。
- 将每条表达式预编译为布尔指令,用于计算最终是否符合规则。
规则准备的成本由之后的多篇文章分摊。文章处理阶段主要使用已经准备好的内存结构。
三、AC 自动机减少逐词重复搜索
逐个调用 Contains 可以完成匹配
一种直接实现,是对每个唯一关键词调用一次类似 strings.Contains 的搜索,记录它是否出现在文章任一字段中。
对于五个示例关键词,需要分别查找“新能源”“电池”“招聘”“咖啡”和“门店”。
词表较小时,这个方案容易实现和验证。它已经可以把实时匹配移到本地,减少原来的逐规则 ES 请求。
随着关键词增加,同一段文章会参与更多次字符串搜索。不同规则重复使用同一个词时,还应先去重,避免对这个词反复搜索。
如果用 K 表示唯一关键词数量,L 表示文本规模,逐词搜索需要完成 K 组针对文本的查找。具体代价与搜索实现、词长、命中位置和短路方式有关,不能直接按字符数算出实际耗时。
将多个关键词组织成一个匹配结构
AC 是 Aho–Corasick 的简称,面向多模式字符串匹配。它先根据关键词构建状态机,再用这个结构识别文本中的多个关键词。NIST Aho–Corasick 说明
当前 Go 实现先构建前缀树。假设词表中有“新能源”“新能源车”和“电池”,树的局部结构可以画成下面这样。
根
├─ 新
│ └─ 能
│ └─ 源 命中“新能源”
│ └─ 车 命中“新能源车”
└─ 电
└─ 池 命中“电池”
“新能源”和“新能源车”共用一段前缀,扫描程序随着文本字符向前移动,同时跟踪可能命中的关键词。
前缀树之外,AC 还维护失败指针,用于衔接已经读过的文本后缀与其他关键词的前缀。
假设另一个小词表只有“新能源”和“能源车”,文本是“新能源车”。
- 读到“新能源”时,报告一次“新能源”命中。
- 继续读“车”,当前路径无法直接接续。
- 失败指针让状态保留已经读过的后缀“能源”。
- 接上“车”后,报告“能源车”命中。
扫描过程复用了此前读取的信息,文本位置继续向前。重叠关键词也能被识别。
当前实现按 Unicode 字符处理状态转移,因此中文关键词可以沿同样的结构匹配。这仍然是字面子串匹配,业务上的词义和分词规则需要另外定义。
AC 的成本和适用条件
构建自动机需要时间和内存。规则变化引入新关键词时,也需要更新相应结构。
如果词表只有几个词,或者每构建一次只处理很少的文章,逐词搜索可能更合适。词表较大、文本持续流入、同一套结构被反复使用时,AC 更值得评估。
每个机构都有明确的规则容量上限,一条规则又可以包含多个关键词,唯一关键词数量可能明显多于规则数。
AC 的扫描成本还包含命中输出。一个词在文本中出现很多次,或多个词重叠出现,都会产生输出处理工作。常见分析会将文本长度与命中输出数量一起计入,而候选筛选和布尔求值还需要另外计算。Aho–Corasick 原始论文
在当前实现中,同一个词首次命中后会标记到命中位图。后续再次出现时,程序可以跳过重复的候选合并,自动机识别这些出现位置仍有成本。
六个字段怎样参与匹配
六个字段分别扫描,每次扫描从自动机根状态开始,再合并关键词命中结果。
例如标题以“新能”结尾,正文以“源”开头,这两个片段不会被拼接成“新能源”。
如果标题完整出现“新能源”,正文完整出现“电池”,两个词则会共同参与文章级判断,可以使 新能源 AND 电池 成立。
回到示例文章“某企业发布新能源汽车电池技术”,假设其余字段没有额外命中词,扫描结果就是“新能源”和“电池”。
四、倒排关系减少无关规则判断
从命中词找到相关规则
AC 扫描结束后,已经知道哪些词出现过。
接下来可以遍历全部规则,一条条计算是否成立。规则较少时,这是可行且容易理解的实现。
倒排关系提供了另一个入口。准备规则时,把“规则引用哪些词”的关系整理为“一个词可以召回哪些规则”。
在示例中,正向召回关系如下。
新能源 → R1、R2、R3
电池 → R1
招聘 → R3
咖啡 → R4
门店 → R4
文章命中“新能源”和“电池”后,合并对应集合,得到候选 {R1, R2, R3}。这时可以跳过 R4 的布尔求值。
这里索引的目标是规则集合,整个关系保存在消费者内存中。
候选范围取决于正向出现的词
R2 是 新能源 AND NOT 招聘。
“新能源”可以把它带入候选,“招聘”则负责参与后面的排除判断。在 R2 这条规则的倒排中,“招聘”不会单独将 R2 召回。
但“招聘”依然在 AC 词表中。程序需要知道它是否出现,才能正确计算 NOT 招聘。
当前编译器会结合关键词所处的逻辑极性建立倒排。每经过一层 NOT,极性翻转一次,因此还会处理双重否定等表达式。
如果文章只出现“招聘”,按上面的关系只能召回 R3。后续发现 R3 缺少“新能源”,最终仍然没有专题命中。
为什么需要限制纯负向规则
单独的 NOT 招聘 在文章没有出现任何关键词时也可能成立。此时没有命中词,正向倒排自然得不到候选入口。
因此,当前解析器会检查表达式,将所有关键词都设为“未命中”。如果表达式在这种条件下仍然成立,就拒绝加载。
这个检查也会拒绝 新能源 OR NOT 招聘。即使表达式包含“新能源”,所有词都未出现时,右侧仍会让整条规则成立。
这项约束使有效规则的命中能够从正向词获得候选入口。若采用全规则判断或额外的负向规则候选来源,可以设计其他支持方式,相应的规则契约和测试也需要一起调整。
位图让集合合并更直接
当前实现用两个 uint64 表示候选规则集合,每一位对应一个规则槽位。命中词对应的倒排位图通过按位 OR 合并。
示例的候选状态可以直观表示为下面这样,列顺序仅用于讲解。
规则 R1 R2 R3 R4
候选 1 1 1 0
同一规则被多个词召回后,对应位仍然只标记一次。
两个 uint64 提供 128 个位置,业务允许的有效规则数量还受显式容量配置约束。位图的表示能力和业务容量需要分别核对。
省略倒排时怎样处理
可以在 AC 得到命中集合后,直接判断全部规则,保留同样的匹配语义。
这会减少一套倒排关系的构建与维护,同时增加逐篇文章的规则求值工作。
当规则只有几条,或者一个高频词会召回绝大多数规则时,倒排筛选的收益可能有限。规则更复杂、每篇文章只涉及少量规则时,候选筛选更有价值。
当前实现采用倒排,是为了减少无关规则的求值。它的独立收益需要结合候选比例、表达式复杂度和更新成本观察。
五、布尔表达式完成业务条件判断
候选规则还需要完整求值
对于只出现“新能源”和“电池”的示例文章,候选是 R1、R2、R3。
逐条计算后得到下面的结果。
- R1 同时要求“新能源”和“电池”,成立。
- R2 要求“新能源”出现,同时“招聘”未出现,成立。
- R3 需要“招聘”出现,条件未满足。
因此,最终命中 R1 和 R2。
如果文章换成“新能源企业发布招聘计划”,候选仍然是这三条,结果变为仅命中 R3。
仅凭命中词关联,就把候选全部归入专题,会改变规则表达的业务含义。AND、OR、NOT 和括号决定了这些词需要怎样组合。
将解析工作提前到规则准备阶段
最直接的执行方式,是每来一篇文章就重新读取表达式字符串,识别关键词、括号和运算符,再求值。
规则会反复使用,这部分语法解析也可以提前完成。
当前实现加载规则时先解析为语法树,为关键词分配统一 termID,再将语法树转换为后缀指令序列。
例如 R2 对应的表达式和指令可以表示为下面这样。
表达式 新能源 AND NOT 招聘
指令 新能源 招聘 NOT AND
运行时,关键词指令根据 termID 查询文章命中位图,布尔指令处理栈中的结果。
对于“新能源”出现、“招聘”未出现的文章,求值过程如下。
读取 新能源 [true]
读取 招聘 [true, false]
执行 NOT [true, true]
执行 AND [true]
最后留下的 true 表示这条规则成立。
如果表达式是 (新能源 OR 电动车) AND 电池 AND NOT 招聘,加载时便确定括号和运算关系,生成相应指令。文章处理阶段使用命中值执行这些指令。
这里的预编译生成的是布尔指令序列,由程序执行求值。
预编译指令也有替代实现
可以在加载时只解析一次语法树,之后针对每篇文章遍历这棵树求值。这样同样能避免反复解析字符串。
也可以在规则非常简单时,直接用业务代码表达固定条件。
当前采用后缀指令,便于统一使用 termID 和命中位图完成判断。语法树遍历、后缀指令及专门的条件求值,各有实现方式和成本。
当前后缀执行器按顺序处理指令。AND、OR 对应的操作数会先被计算,执行特点与带短路判断的语法树遍历有所不同。
因此,预处理的直接价值是复用解析结果。不同执行形式的速度,还需要结合实际规则和命中情况测量。
六、三个结构怎样串成一次匹配
对于四条示例规则,以及标题“某企业发布新能源汽车电池技术”,整条链路可以表示为下面这样。
规则加载或更新
↓
关键词去重、规则解析
↓
构建 AC 自动机、正向倒排、布尔指令
文章进入消费者
↓
分别扫描六个文本字段
↓
记录命中词集合
新能源、电池
↓
合并正向倒排
候选 R1、R2、R3
↓
执行候选规则的布尔指令
R1=true、R2=true、R3=false
↓
得到最终专题
R1、R2
↓
写入结果与维护状态
也可以逐步构建一个本地方案。
第一步,缓存并预先解析规则,在本地通过逐词搜索求值,先移除实时匹配所需的远程请求。
第二步,对规则中的关键词去重,记录文章的统一命中集合,减少相同词的重复搜索。
第三步,使用 AC 自动机合并多关键词扫描。
第四步,通过倒排缩小需要完整求值的规则范围。
这些步骤解决不同层面的工作。当前实现将它们组合起来,适配规则重复使用、文章持续流入的场景。
七、规则变化时更新快照
规则保存在内存中,需要处理新增、修改、停用和删除。
当前实现按机构维护带版本的规则快照。启动时从 MySQL 加载,运行期间通过 Redis 的版本信息发现变化,并通过 MySQL 周期核对补充检查。
发现变化后,先构建和校验新快照,再替换当前引用。加载或校验失败时保留旧快照,增量更新不可用时可以回退到全量加载。
增量处理尽量复用已有结构,只重新解析和编译变化规则。出现新关键词时重建 AC,没有新关键词时可以复用已有自动机。
为保持关键词编号稳定,增量快照中可能保留已经失去规则引用的旧词。这些词对应的倒排关系会被清理,文章扫描得到它们时不会因此产生有效候选。
快照更新存在传播时间。匹配期间若发现规则版本变化,处理逻辑会重新匹配,再根据后续检查推进结果处理。
八、效果与匹配语义需要分别验收
代码层面能确认的直接变化,是实时关键词匹配从逐条 ES 查询转成了本地处理。
没有匹配结果时,这段处理可以在本地结束。有匹配结果时,仍需写入专题关系、维护聚合状态和更新文章信息。关系查询、异常恢复和历史回填等路径,也还会使用 ES。
这组 CPU 数据来自运行前后的观察。文章量、机构数、规则数和其他负载并未被严格控制,具体吞吐和各层算法的独立收益仍需单独测量。
匹配语义也需要核对。旧方案的 match_phrase、query_string 涉及 ES 分析器和查询语法,新方案执行区分大小写的字面子串匹配,再计算布尔条件。验收时应使用真实规则和样本对照这些差异。ES 短语查询说明、query_string 说明
当前本地实现允许不同字段分别提供 AND 所需的词。NOT 所引用的词在任一字段出现都会被记录,并按完整表达式结构参与求值。自动分词、模糊匹配和英文完整词边界等需求,需要单独定义和实现。
算法与运行语言同样需要分别观察。Python 也可以实现这些匹配结构。Go 为当前项目提供了单进程规则共享、多核计算和独立消费者工程,匹配路径的调整则减少了实时 ES 请求。
本次整理时,现有三项内存测试实际运行通过,覆盖跨字段布尔判断、后续字段出现 NOT 词时的排除、非法及全词未命中仍成立的规则校验,并包含 1000 组随机字段与 Contains 基线的对照。验证范围是这些输入下的解析和匹配行为,外部系统与性能需要结合相应环境继续验证。
记录过程,也留下判断。
← 继续阅读其他文章