分享一次巨量关键词匹配服务的性能优化过程

大牛前辈，这个关键词匹配服务具体是干什么的？

小菜啊，我们这个服务的业务场景很简单，1、调用方输入多段长文本，2、关键词服务遍历关键词词库，找到输入文本中命中了哪些关键词，3、返回命中的所有关键词。

前辈，那做这个关键词匹配服务有什么用呢？

小菜，命中不同的关键词有不同的处置策略，比如：用于视频上传阶段的禁止上传策略；用于审核阶段的关键词过滤策略、审核删除策略等。关键词匹配服务返回关键词与相应的策略，视频上传服务和审核服务再根据相应的策略做出相应的处理。

前辈，那我明白了，可为啥要做性能优化呢？

小菜，咱们现在的关键词词库已经有上百万了，在qps不高时服务还能保证实时性，但在qps比较高时比如达到上百个qps时，服务已经不能满足实时性要求了，rt时间达到了几秒，调用方对咱们这个服务的性能十分不满。

前辈，目前咱们的关键词匹配使用的是什么算法呢？

算法？不就是两层循环遍历，1、循环多段输入文本，2、循环遍历词库，3、判定输入文本是否包含关键词。示例伪码如下：

for (input : inputs) {
for (keyword : keywords) {
if (input.contains(keyword.name)&&keyword.products.contains(input.product)) {
} else {
}
}
}

第3步判定输入文本包含关键词时，为啥还要加一个判定输入文本和关键词的适用产品是否一致？即keyword.products.contains(input.product)判定？

小菜观察的很仔细嘛，输入文本的适用产品指的是来自不同的产品线的调用；而不同的产品线的关键词词库并不相同，比如咱们有十几种产品线，这十几种产品线包含有视频、图片、文字等产品，他们的关键词词库有共享的，也有独享的。而我们设计的关键词词库的数据结构如下：

CREATE TABLE `keyword` (
`id` bigint(20) NOT NULL AUTO_INCREMENT,
`type` int(5) NOT NULL COMMENT '关键词策略',
`name` varchar(100) NOT NULL COMMENT '关键词内容',
`description` varchar(1000) COMMENT '关键词描述',
`products` varchar(1200) COMMENT '适用产品，多个产品,分隔',
`status` int(11) DEFAULT NULL
)

我们的关键词服务为了提高匹配速度，会在服务启动时将全量词库按以上数据结构载入内存的list列表中，用于循环匹配。

。。。前辈，我感觉匹配算法的时间复杂度太高了，我想一想怎么优化。。。

那ac自动机和Trie树有什么关系呢？

我还是没有明白ac自动机的原理，你能画个图举个例子说明一下吗？

goto表实际上就是一颗trie树结构，如下图所示：

因为output表比较简单，但实际实现的时候output表会在建立failure表的时候进行一次拓充。output表如下表格所示：

Output表实际上就是从根节点到对应数字节点的字符输出的所有组合，并且满足其存在于关键词词库中。

failure表的构建是ac自动机实现的重点，其要满足几点限制：

最终找到每个节点对应的fail跳转节点如下表格所示：

下面将整体的ac自动机的构造图画出来，实际就是在步骤1，trie树的基础上画上每个节点的fail跳转路径，以虚线绘制。Trie树的实线为goto路径。若命中output表也在图中绘制出来。整体构造图如下图所示：

我再说明一下ushers字符串匹配关键词的具体过程：

7、 尝试下一个字符r，发现goto路径，转移到节点8，没有命中output表；

8、尝试下一个字符s，发现goto路径，转移到节点9，命中output表关键词，hers。

匹配结束后，共命中三个关键词he,she,hers。

这样看来ac自动机确实比循环遍历效率要高，循环遍历的时间复杂度也可以理解为O(mn)吧？

对，但还有一个问题，前面说过构建ac自动机要先构建一个trie树，但trie树本身占用内存空间比较大，我最近看了一篇文章可以使用双数组trie树来实现ac自动机，这样可以保证ac自动机的内存消耗可控。