让路由查询与规则数无关：代理路由索引的一次重新设计

TL;DR — 代理软件的路由规则是一张有序表：逐条检查，第一条命中的规则决定出口。这个语义天然导致”规则越多、未命中越慢”，因为一个不命中任何规则的请求要把整张表扫完，而带地理类别的规则每条都是几万个域名或网段。这篇文章记录一次不改变任何语义的重新设计：利用”最早规则赢”对匹配维度可分配这一性质，把所有规则的同类选择器合并进三个静态索引（冻结哈希表、一个 Aho-Corasick 自动机、一棵前缀树），每个索引只回答”本维度最早命中的规则是哪一条”，跨维度取最小即得全局答案。结果是未命中延迟从微秒级降到几十纳秒，并且不再随规则数增长；等价性由与朴素线性实现的百万次差分保证。

---

一、问题：规则越多，未命中越慢

先把规则模型说清楚。一份路由配置是一个有序列表，每条规则有一个出口目标和若干选择器：

选择器	含义
full	域名完全相等
suffix	域名以某后缀结尾，按标签边界对齐
keyword	域名包含某子串
regex	域名匹配正则
cidr	目标地址落在某网段
域名类别	一组预置的 full / suffix / keyword 条目，通常几千到几十万条
网段类别	一组预置的 cidr，按国家或运营商划分

语义只有一条：按规则顺序，第一条有任意选择器命中的规则决定出口；都不命中则走默认。

最直接的实现就是照着语义写：外层遍历规则，内层遍历选择器。类别选择器会被展开成一张哈希表或一棵树，所以单条规则的匹配是常数时间；但规则之间没有共享结构，N 条带类别的规则就是 N 次独立查表。命中靠前的规则时很快，问题出在未命中：一个不该走任何特殊出口的请求，必须把所有规则试完。

我们在一个 32 条规则的配置上测过这条路径的代价：

路径	8 条规则	32 条规则
域名类别，命中 / 未命中	110 ns / 901 ns	109 ns / 3500 ns
网段类别，命中 / 未命中	60 ns / 95 ns	62 ns / 310 ns
关键字，命中 / 未命中	94 ns / 417 ns	94 ns / 1565 ns

命中列几乎不变，未命中列随规则数线性增长。而在真实流量里，大部分请求恰恰是”未命中任何特殊规则、走默认出口”的那一类。

内存侧也有同样形状的问题：每条规则各自持有自己的类别表，同一个域名在多条规则里被多次索引；表结构含指针，堆越大垃圾回收扫描越久。

二、核心观察：最早规则赢是可分配的

把语义写成式子。记 q 为一次请求，match_d(rule, q) 表示规则 rule 在维度 d（full/suffix、keyword、regex、cidr）上命中 q。全局答案是：

answer(q) = min { rule : ∃ d, match_d(rule, q) }

对一个”存在”取最小，可以按维度拆开：

answer(q) = min over d ( min { rule : match_d(rule, q) } )

也就是说，每个维度只需要回答”本维度最早命中的规则是哪一条”，跨维度取最小就是全局答案，与逐规则扫描严格等价。这条式子是整个设计的合法性基础：它允许我们把所有规则的同类选择器合并进一个索引，让索引在每个键上只记住最早引用它的规则。

平局：同一条规则被多个维度命中

规则下标相同时结果一样，但诊断信息里要报告”是哪种匹配命中的”，这需要确定性。我们给每个维度的结果附一个 rank：

命中方式	rank
普通 full / suffix	0
域名类别展开的 full / suffix	1
普通 keyword / regex	2
普通 cidr	0
网段类别	1

比较键是 (rule, rank)。把它打包进一个 32 位整数：

packed = (rule + 1) << 2 | rank       // 0 保留为"空"

打包后整数的大小顺序就是 (rule, rank) 的字典序，索引内部所有的”取最小”都直接在整数上做，不需要解包。

早退

规则 0 是最优可能。任何维度一旦返回规则 0 且 rank 为最小可能值，后续维度都不必再查。更一般地，把当前最优 best 传进下一个维度，索引内部只在 packed < best 时才更新。

三、域名维度：一张冻结哈希表，一趟反向扫描

full 和 suffix 是同一类问题：suffix 的候选键是查询域名在每个标签边界处的后缀，full 是”从位置 0 开始的那个后缀”。所以两者合并进同一张表，用一个标志位区分。

一趟算出全部候选键的哈希

后缀匹配的朴素做法是对每个标签边界物化一个子串再哈希，域名有几个标签就要几趟。改成从字符串末尾向前做哈希：处理完位置 i 的字节时，哈希状态恰好就是后缀 domain[i..] 的哈希。于是一趟反向扫描，在每个标签边界处顺手拿到一个候选键的哈希，不物化任何子串，不分配。

函数 匹配域名(domain, limit):
    best = 0
    hash = 初始偏移
    for i 从 len(domain)-1 递减到 0:
        hash = (hash xor domain[i]) * 质数            // 反向 FNV-1a
        if i == 0 或 domain[i-1] == '.':              // 标签边界
            候选 = domain[i..]
            r = 表.查找(候选, 后缀=true, hash)
            if r != 0 且 r < limit: best = min(best, r)
            if i == 0:
                r = 表.查找(候选, 后缀=false, hash)
                if r != 0 且 r < limit: best = min(best, r)
    return best

后缀键和完全键用同一个哈希值加一个固定扰动区分，这样一个哈希状态能同时服务两次探测。

表的形状

• 开放寻址，容量为 2 的幂，装载因子不超过 0.75，线性探测。
• 每个槽 32 字节：字符串头、完整 64 位哈希、标志位、rule + 1。rule + 1 为 0 表示空槽。
• 槽里的字符串头直接引用共享的类别数据区或规则里的选择器字符串，不拷贝字节。
• 同一个键被多条规则引用时只保留最早的 (rule, rank)：建表时直接插入并做 min 更新，没有中间 map。
• 建表前按引用数预留容量，建完后按实际条目数收缩一次，用槽里已存的哈希重排，不再重新哈希字符串。

一个设计变更记录：初版方案写的是”反向排序数组加二分查找”。实现时发现排序数组的前缀连续性根本没被利用，因为候选键本来就可以按标签逐个枚举；换成冻结哈希表后，每次查找从 O(log n) 次比较变成约一次探测，内存同阶。

四、关键字维度：一个自动机，failure 链向下传播最小规则

keyword 是子串匹配，所有规则的 keyword（包括类别展开出来的）进同一个 Aho-Corasick 自动机。

• 模式终端记录该 keyword 的最早 packed 值。
• 构建 failure 链时顺便做一件事：failure 目标一定比当前节点浅，它的输出已经是最终值，所以把它的输出 min 到当前节点上。传播完成后，每个节点的输出等于”终止于该节点或其任一 failure 祖先的所有模式”中的最早规则。
• 查询对域名扫一趟，取沿途节点输出的最小值，O(len) 得到 keyword 维度的答案。

构建:
    对每个 keyword 按最早 packed 去重           // 被多条规则引用的类别只建一次
    建 trie，终端 output = min(output, packed)
    BFS 计算 failure:
        对每个节点 next:
            next.failure = 沿父节点 failure 链找到的转移
            next.output = min(next.output, failure.output)   // 向下传播
    记录 minOutput = 全机最小 output

查询(domain, best):
    if best == minOutput: return best          // 已经不可能更好
    state = root
    for 每个字节 c:
        state = 转移(state, c)                  // 失配沿 failure 回退
        if state.output != 0 且 state.output < best:
            best = state.output
            if best == minOutput: return best   // 早退
    return best

节点是扁平数组：每个节点保存 failure、边的起始下标和数量、输出；所有边按字节值排序放在两个平行数组里，转移用二分。整个自动机里没有一个指针。

minOutput 早退很重要：合并之后，命中路径原本可能要扫完整个域名才能确认没有更早的规则，有了全机最小值，一旦碰到它就能立刻停下，命中路径不会因为合并而变慢。

五、IP 维度：网段、地理库、私网合并进一棵前缀树

cidr 选择器、所有网段类别、内置的私网集合，全部进同一棵前缀树。

• 节点 12 字节：两个子节点下标加一个 packed。子节点下标存”下标加一”，0 表示没有子节点。整棵树是一个数组。
• IPv4 与 IPv6 各一个根。插入前做规范化：清掉主机位，IPv4 映射地址的 /96 及更长前缀折算成 IPv4 前缀。
• 终端存该网段上最早的 packed；同一网段被多条规则引用只留最小。
• 查询按位下行，经过的每个节点如果 packed 非零且规则下标不超过 limit，就参与取最小。一次下行同时回答了普通 cidr 和所有网段类别。
• 编译期顺便记下全树最小的规则下标 earliestIPRule，惰性解析要用它。

之前网段类别的匹配是”按规则、按类别逐棵树查”，32 条规则的未命中要走 32 趟；合并后是一趟。

一个真实的坑：别名地址族

在把这个设计移植到另一套实现时，审计发现一个结果差异：某个 6to4 形式的 IPv6 地址在原始地理数据库里能查到国家，但按默认方式迭代数据库条目时别名网段被省略了，合并进前缀树后这个地址就漏匹配。IPv4 兼容地址、6to4、Teredo、IPv4 翻译地址和 NAT64 这几个地址族都有同样的问题，而且不同版本的数据库对别名的覆盖并不一致。

修法不是把所有别名展开成重复网段塞进树里，而是对这几个地址族保留一次对原始数据库的回退查询，同时保证普通 IPv4 网段规则不会被误用到真实 IPv6 流量上。教训是：合并索引的输入是”数据库告诉你的网段”，而数据库自己有没有把别名算进去，要用真实数据对照，不能假设。

六、查询流水线与惰性解析

把三个索引串起来：

函数 路由(request):
    if UDP 且端口 53 且存在 DNS 交换器: return DNS 目标      // 先于一切规则
    domain = 归一化(request.domain)                            // 小写、去尾点
    best = 域名表.匹配(domain, limit = 规则总数)
    if best 不优于 "规则 0 经类别命中":
        best = 关键字自动机.匹配(domain, best)
    for regex 规则按规则序:
        if 规则下标 >= best: break                              // 慢扫只剩 regex
        if 正则命中: best = min(best, packed)
    if 目标是 IP:
        best = min(best, 前缀树.查询(ip, limit = best))
    else if earliestIPRule < best 且允许解析:
        解析域名，对每个地址查前缀树，命中 earliestIPRule 即停   // 惰性 DNS
    return 解码(best)

几个细节：

• regex 留在慢路径。它是唯一没有合并的维度，但 regex 规则按规则序排列，一旦当前规则下标已经不小于 best 就停止，所以它的代价被前面的索引压得很低。
• 惰性解析的判定不变。只有当”最早的 IP 规则”确实可能改善当前答案时才发起 DNS 解析。合并树的 earliestIPRule 就是这个判定需要的那个数。
• 快路径零分配。域名归一化不产生新字符串（小写化和去尾点在查询前由调用方保证或原地处理），候选后缀不物化，自动机和前缀树都是数组下标运算。

七、内存布局：让垃圾回收看不见它

• 快照内全部匹配状态是字节数组和无指针的结构体数组。对带垃圾回收的运行时来说，这些段不需要扫描；堆增长不再放大回收暂停。
• 域名、关键字、类别来源在编译期做 intern，重叠的类别只存一份字节。
• 每个快照新增的查询索引不超过每条目 64 字节；类别数据本体由跨快照的注册表共享，不随快照份数翻倍。
• 编译复杂度从 O(规则数) 变成 O(条目数)，因为代价从查询时搬到了编译时。所以给编译设绝对预算：3.2 万条目稳态编译低于 5 ms，10 万条目低于 50 ms。实测 3.2 万条目约 2.0 ms、478 次分配、索引约 2.9 MB。

一条自我修正：设计初版写的目标是”内存下降三倍以上”，后来发现基线假设错了，旧实现里大类别集合早就是紧凑存储而不是散列表。这次重构真正的收益在查询延迟与规则数无关化，不在内存。文档保留了这条修正记录，而不是把目标悄悄改掉。

八、等价性：三路差分

“不改变任何语义”不能靠信心，要靠比对。我们用了三路差分而不是双实现对照：

1. 冻结的旧实现副本作为过渡期的 oracle，锚定真实的旧行为。
2. 按语义契约直接写的朴素线性参考实现：外层遍历规则，内层遍历选择器，怎么慢都行，但每一行都能对着契约审计。它永久保留。
3. 新实现。

三方逐字段比对：目标、规则下标、匹配种类、是否解析过 DNS、解析结果与错误。朴素参考的意义在于防止新旧实现共享同一个语义误读：如果旧实现本来就有 bug，冻结副本会把 bug 也冻结进 oracle，只有从契约出发独立写的参考能揭示它。

差分的输入由生成器按维度笛卡尔积产生，而不是手写：

• 规则拓扑：单规则、多规则不重叠、同一键出现在规则 i < j、同一请求被多条规则的不同维度同时命中、类别规则固定在规则 0、空选择器规则、十万级合成大类别。
• 平局：同一规则被 full/suffix、类别、keyword/regex 两两及三者同时命中，穷尽 rank 表的全部组合。
• 请求形态：大写、尾点、单标签、253 字节边界、空串、punycode、连字符；纯 IPv4、纯 IPv6、IPv4 映射地址。
• DNS 条件：无解析器、解析成功、失败、空结果、best 恰好等于 earliestIPRule 的边界（此时不得解析）。
• 类别数据：资产缺失、类别不存在、空类别、属性过滤、资产原子替换后重新编译。

规模：600 份随机配置乘 11 万次决策三路零分歧作为阶段门禁，收尾前 100 万次决策零分歧。语义契约共 9 条，每条有定向用例，重点是 rank 平局表。分阶段推进，每个阶段的合入条件是差分零分歧加基准不劣化，任一阶段出问题回滚该阶段即可。

九、结果

32 条规则的配置，同一台桌面机，重构前后：

路径	重构前	重构后	倍数
域名类别，未命中	3500 ns	36 ns	97×
域名类别，命中	109 ns	45 ns	2.4×
域名类别混关键字，未命中	3500 ns	70 ns	50×
关键字，未命中	1565 ns	63 ns	25×
关键字，命中	94 ns	78 ns	1.2×
网段类别，未命中	310 ns	22 ns	14×
网段类别，命中	62 ns	56 ns	1.1×
普通 suffix	46 ns	42 ns	1.1×

未命中列不再随规则数变化：8 条规则和 32 条规则的未命中同值。命中列基本持平，说明合并没有让原本就快的路径变慢。

同一设计后来被移植到另一套实现里，规则表放大到 32768 条独立规则时：域名后缀未命中从 1.3 ms 降到 19 ns，关键字未命中从 294 µs 降到 27 ns，网段未命中从 93 µs 降到 4 ns。这些倍数没有实际意义，只说明一件事：旧实现是 O(规则数)，新实现不是。

也有变慢的地方，要写出来：8 条普通网段规则、命中最后一条的场景，从 23 ns 变成 26 ns。初版对小表用了专门的掩码扫描，统一进前缀树后反而多了几次节点跳转。并不是每种小配置都会受益，我们接受这个代价换取实现只有一份。

十、没做的两件事

设计里还有两项优化，评估之后都跳过了，而且写明了重新评估的触发条件。

• regex 字面量门控：从每条正则提取必需字面量，并入关键字自动机做预筛，未命中门控的正则直接跳过。实测 32 条 regex 规则的慢扫未命中是 551 ns，比其他维度的问题低一个数量级，且实际配置里 regex 极少。触发条件：生产配置 regex 规则超过 64 条且路由在 profile 里可见。
• IPv4 每步 8 位的前缀树：把逐位下行的 32 次跳转变成 4 次。合并树落地后 IP 查询已在 22 到 56 ns，逐位下行不再是路由路径的瓶颈。触发条件：IP 基准显示前缀树是瓶颈。

不做的理由和做的理由一样重要：每一项优化都对应一个能被测出来的问题，测不出来的问题不值得为它多养一份代码。

---

结语

这次重新设计只用了三个古老的数据结构：哈希表、Aho-Corasick、前缀树。真正的工作不在结构本身，而在前面那一步：

证明”最早规则赢”可以按维度拆开取最小，于是”谁先匹配”这个问题从查询时的循环，变成了编译时的一次 min。

有了这条式子，所有规则的同类选择器就可以合并，未命中不再需要把表扫完；有了 rank 打包，平局在整数比较里自动解决；有了朴素参考实现的差分，”不改变语义”从承诺变成了可以跑一百万次的事实。

如果你也维护着一个按顺序匹配的规则引擎，我的建议只有两条：先把语义写成契约再动手，然后去测未命中，不要只测命中。命中很少是问题，把整张表扫完才是。