---
title: "让路由查询与规则数无关：代理路由索引的一次重新设计"
source: https://www.embermoth.blog/2026/09/27/routing-index-rule-count-independent-lookup/
date: 2026-09-27
updated: 2026-09-27
tags: [performance, proxy, routing, index, algorithm, data-structure, hash-table, aho-corasick, trie]
categories: [开发笔记]
---

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

> **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。全局答案是：

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

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

```text
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 位整数：

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

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

### 早退

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

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

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

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

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

```text
函数 匹配域名(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 维度的答案。

```text
构建:
    对每个 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 流量上。教训是：合并索引的输入是”数据库告诉你的网段”，而数据库自己有没有把别名算进去，要用真实数据对照，不能假设。

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

把三个索引串起来：

```text
函数 路由(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 打包，平局在整数比较里自动解决；有了朴素参考实现的差分，”不改变语义”从承诺变成了可以跑一百万次的事实。

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