解读

在国内内容安全场景里，敏感词库由网信、公安、行业监管等多方渠道每日推送增量包，要求系统零停机、毫秒级生效。传统做法是凌晨全量重建自动机，但百亿级请求不能停服，且词库已达百万级词条、日增量5k~2w条，全量重建一次需3~5 min，显然不可接受。因此面试官想确认两点：

1. 你是否真正理解 Aho-Corasick（AC）自动机的双数组 Trie + failure 表的耦合关系；
2. 能否在线程安全、内存可控、回滚可审计的前提下，给出增量更新方案，而不是“重启服务”这种初级答案。

知识点

1. AC 自动机三件套：Trie 树（goto）、failure 表（fail）、输出表（output）；任何 goto 或 fail 变动，均需级联修正。
2. 双数组 Trie（Double-Array Trie, DAT）的base/check 数组一旦连续，插入新分支就可能大规模搬迁，导致O(n²) 最坏时间。
3. 增量更新≠热补丁：必须保证新旧版本并发安全，常用Copy-on-Write + 版本号或RCU机制，读线程无锁，写线程发布新版本后延迟回收旧内存。
4. 国内合规要求：
   • 增量包必须留痕审计（who、when、what）；
   • 支持秒级回滚到任意历史版本；
   • 灰度发布到多机房、多业务线；
   • 极端情况下可一键清空（应急舆情）。
5. 工程指标：
   • 更新延迟 < 500 ms；
   • 内存涨幅 < 10%；
   • 99.9 次更新不能出现一次fail 表错误，否则漏杀即事故。

答案

整体采用**“双 DAT + 版本 RCU”** 策略，分五步：

1. 增量预处理
   每日凌晨拉取监管通道的jsondiff 包，解析成「新增、删除、修改」三类词条，去重归一化（繁简、大小写、谐音、变形体），生成内部OpLog。
   对删除词条，仅打墓碑标记（逻辑删），物理回收延后到低峰期。

2. 构造「影子 DAT」
   复用旧 DAT 的base/check 数组，采用动态数组 + 空闲链表管理未用槽位；
   对新增词条，优先在旧 DAT 的空洞里插入，若空洞不足，再尾部扩容；
   同步重新计算受影响节点的failure 指针，但不立即修改生产内存，而是写入一块新的连续内存块（shadow）。

3. Fail 表级联修正
   采用BFS 分层算法，只对「新增节点及其祖先」子树重新求 fail；
   利用位图标记已验证节点，避免全树遍历，时间从 O(σ×m) 降到O(Δm)，Δm 为增量节点数。

4. RCU 发布与灰度
   shadow 构建完成后，生成版本号（epoch），写入无锁共享指针；
   读线程通过原子读获取当前 epoch，保证无锁并发；
   写线程延迟两个完整请求周期（通常 200 ms）后，调用rcu_free 回收旧 DAT；
   灰度阶段先把5% 流量切换到新版本，敏感词命中率对比无误后全量。

5. 回滚与审计
   每个版本附带crc64 指纹与OpLog 哈希，写入etcd；
   若发现误杀或漏杀，一键回滚只需切换 epoch 指针，<50 ms；
   所有变更写入Kafka审计队列，保留180 天，供监管抽查。

通过以上策略，单次日增量 1w 词条的更新耗时稳定在180~300 ms，内存涨幅 < 8%，线上运行一年未出现fail 表断裂导致的漏杀事故。

拓展思考

1. 如果敏感词长度分布极不均匀（平均 2 字，最大 128 字），DAT 会出现严重空洞，此时可引入分层 Trie：
   • 0~4 字用 DAT，保证速度；
   • 5 字以上用传统指针 Trie + 哈希分片，更新时仅重建分片，空间换时间。
2. 当业务线扩展到海外多语言（阿拉伯、泰米尔），字符集爆炸，双数组base 溢出，可改用Mmap + 64 bit 虚拟地址，并配合NUMA 绑核，防止跨 Node 访问延迟。
3. 未来若词库突破千万级，可考虑分布式 AC：
   • 按首字哈希拆成 256 分片，每片一微服务；
   • 网关层用GPU 正则做预过滤，仅可疑片段走 AC，QPS 提升 3 倍；
   • 但分布式后fail 表跨片无法直接构建，需引入重叠分片 + 后校验，权衡精度与性能。