生活在字典树上 —— 存储和匹配海量的域名和 IP 地址
如果你经受过正经的 CS 教育（在课堂上亦或是自学），那么你无需花费过多的时间读完本文；本文试图讲解的数据结构非常基础、你理应早就掌握了。原本我甚至不屑于将这些内容写成一篇文章，但是在见识到网络反审查社区参与者的平均水平和技术素养的多样性之后，我觉得这么一篇最基础的数据结构的扫盲科普还是很有必要的。
不然某些核心，30 万域名和 1 万个 IP 竟然要用 200 MiB 内存，这真的很难让人绷住，你们知道吗？
开胃小菜：规则集
在开始讲解数据结构之前，先让我们看看下面这个规则集文件：
DOMAIN-SUFFIX,google.com
IP-CIDR,8.8.8.0/24
IP-CIDR,114.51.4.0/24,no-resolve
DOMAIN,ip.skk.moe
AND,((PROCESS-NAME,Telegram),(IP-CIDR,91.0.0.0/8))
DOMAIN-KEYWORD,facebook这个规则文件包含了常见的规则类型，有域名规则，有需要触发 DNS 解析的 IP 规则，有 no-resolve 这样的规则修饰符，也包含了复杂的逻辑组合。这种规则集文件的格式适用于 Surge、Loon、Surfboard 等软件的 RULE-SET 和 Mihomo 的 classical 类型的 Rules Provider。
关于为什么 IP-CIDR 规则在匹配过程就需要触发 DNS 解析，推荐阅读我之前的博客「浅谈在代理环境中的 DNS 解析行为」、「我有特别的 Surge 配置和使用技巧」，和 Surge 的中文白皮书「Surge 官方中文指引：理解 Surge 原理」
这样的规则文件通常会被引用到主配置文件中，并被分配一个策略（如 Global 或者 Proxy 之类）：
[Rule]
RULE-SET,https://example.com/ruleset.txt,Proxy现在请大家思考一个问题：像这样的 RULE-SET 文件内部的多条规则，它们的顺序重要吗？换句话说，如果你把同一个规则文件、打乱其中的规则顺序，最终的匹配结果会发生变化吗？
先不要着急回答，你可以在下面的交互式演示中试试看打乱规则的顺序、以及输入不同的域名和 IP 地址，看看最终的匹配结果。
我们可以注意到，虽然我们的 RULE-SET 规则集中包含了不同类型的多条规则，其中有的规则还需要触发 DNS 解析，但是不论我们如何打乱规则的顺序，最终的匹配结果都是不会发生变化的。
虽然 RULE-SET 与 RULE-SET 多个规则集之间确实存在先后顺序关系，但是对于每个 RULE-SET 来说，规则匹配引擎只关心这个 RULE-SET 规则集本身是否被匹配：只要这个 RULE-SET 之中有任何一条规则匹配了当前请求，那么这个请求就需要走 Proxy 策略；如果 RULE-SET 中没有任何一条规则匹配当前请求，那么这一整个 RULE-SET 就没有被匹配，规则匹配引擎需要继续匹配其它规则。换句话说，在一个 RULE-SET 文件内部的多条规则之间的逻辑关系是「或」。相同的结论在 DOMAIN-SET 等格式的规则集文件也同样成立。
既然在一个 RULE-SET / DOMAIN-SET 等规则集文件内部的多条规则之间的顺序无关紧要，解析规则集就变得简单多了。我们不需要把规则集文件完整载入内存之中，而是可以逐行、逐条地读取这些规则集文件，然后对着每一条规则、按规则类型把 RULE-SET 中的规则进行分类：DOMAIN 和 DOMAIN-SUFFIX 分一类、DOMAIN-KEYWORD 自成一类，IP-CIDR 和 IP-CIDR6 等分成一类，剩下的规则（GEOIP、DOMAIN-WILDCARD、PROCESS-NAME、USER-AGENT、URL-REGEX 等等）也按各自的规则类型自成一类。
为什么要这么分类呢？这是因为...
高效地存储和匹配海量域名
再让我们看一个例子。例如下面这个只包含 DOMAIN 的 RULE-SET：
DOMAIN,github.com
DOMAIN,google.com
DOMAIN,skk.moe
DOMAIN,blog.skk.moe
DOMAIN,ip.skk.moe
DOMAIN,gitlab.com
DOMAIN,apple.com
DOMAIN,cloudflare.com
DOMAIN,amazon.com因为这个 RULE-SET 只包含域名，我们还可以写成 Surge、Loon 等兼容的 DOMAIN-SET 格式：
github.com
google.com
skk.moe
blog.skk.moe
ip.skk.moe
gitlab.com
apple.com
cloudflare.com
amazon.com在匹配这些域名，最简单的方式就是直接将这些域名原样载入到内存中，在匹配时，每一个网络请求都需要和这些域名一一比较。但是这样做显然并不具备可扩展性。将上述 9 个域名原样载入内存至少需要 109 byte 的内存（9 个域名 + 分隔符；实际上因为指针的存在，需要消耗的内存只会更多）；并且在最坏的情况下（无法匹配任何一个域名），每个网络请求最多需要进行 9 次匹配。而以 SukkaW/Surge 提供的规则组为例，reject.conf 包含将近 11 万域名，reject_extra.conf 包含将近 9 万域名，而 reject_phishing.conf 包含将近 15 万域名，如果同时引入这三个配置文件，那么至少需要消耗 7.5 MiB 内存（因为指针的存在，实际需要消耗的内存更多）、并且在最坏情况下，规则匹配引擎可能需要做 35 万次比较并得出「没有匹配」的结论，此时假设规则匹配引擎每秒钟可以进行 1 亿次比较，35 万域名仍然需要耗费 3.5 毫秒的时间！
有没有什么办法既能节省需要占用的空间、又能提高匹配速度呢？当然是有的。让我们再回到刚才 7 个域名，看看我们是否能发现一些规律：
github.com
google.com
skk.moe
blog.skk.moe
ip.skk.moe
gitlab.com
apple.com
cloudflare.com
amazon.com我们可以注意到，虽然这里有 7 个域名，但是只有 2 个 TLD（Top Level Domain，顶级域名），com 和 moe；再比如，blog.skk.moe、ip.skk.moe 其实都是 skk.moe 的子域名。我们完全可以利用域名天生的分层性质（TLD -> 域名 -> 子域名）来去除重复、从而减少我们实际需要存储的数据。如果我们更进一步，我们甚至可以注意到 google.com 和 apple.com 都是以 le.com 结尾。现在，一个从后往前构建的树形数据结构已经呼之欲出了。
如果你觉得脑子已经开始冒烟、难以想象如何利用域名的分层性质来构建一个树形的数据结构，那么下面这个交互式演示应该就能让你豁然开朗了。
在输入框中输入其它域名，看看我们的数据结构会发生什么变化。
形如这样的用于存储关联数组的树形数据结构被称为 Trie（字典树）。由于域名的分层结构的特征、我们的树形结构是从域名从后往前构建的，因此我们构建的数据结构被称为 Suffix Trie（后缀树）。
使用后缀树还有一个好处，规则匹配引擎 需要比较的次数不再随域名的数量决定，而是由域名的长度决定了。
试试在输入框中输入其它域名，看看字典树是如何进行匹配的。
在上面的交互式演示中，我们将完整的 TLD（moe、com）作为一个节点，这是因为截至本文写就，ICANN 总共分配了 1593 个 TLD，换句话说不论我们有多少域名，TLD 永远只会是这 1593 个变种中的一个。而且相比 不断有域名被新注册、ICANN 审批和竞拍 TLD 的速度是非常缓慢的。我们将域名剩下的部分逐个字符分解成节点，从而利用 google.com 和 apple.com 都以 le.com 结尾的特性以进一步节省内存。
在内存压力并不大的应用中，我们一般按域名的 label 而不是逐个字符划分节点，如
blog.skk.moe会被划分成blog、skk和moe三个节点，虽然不能极致节省内存，但是减少了每次匹配时需要比较的次数，用空间换时间（速度）。
Surge 则在 TLD 的基础上更进一步，不仅仅是将 com、net、moe 这样的 TLD 作为一个节点，而是利用「Public Suffix List」，将一整个 Public Suffix（除了 TLD 之外，还包含 github.io 之类的公共后缀）作为一整个节点。
虽然我们有了 Trie 这样的数据结构，但是我们可以注意到，我们构建的树形结构依然存在可优化的空间，如 cloudflare.com 中的 c-l-o-u-d-f-l-a-r、amazon.com 中的 a-m-a-z-o-n、github.com 中的 g-i-t-h-u，这些节点在字典树中都是孤零零一串、不能够和其它域名复用。
而由于我们的规则匹配引擎「只读」这个特点（Surge、Loon、Mihomo 等只需要在启动时构建一次字典树，之后这个字典树便成为只读的，只匹配、不改变。配置和外部规则文件更新时，字典树可以从头重新构建），我们实际上可以在构建 Trie 之后，进行一次压缩，合并这些「孤零零」的节点：
这种压缩后的字典树结构被称为 Radix Trie（基数字典树）。由于需要存储的节点数量变少了、需要连接节点的指针也变少了、占用的内存也变少了。而在查找上，Radix Trie 需要比较的次数也变少了：
上述案例和交互演示中，我们插入字典树的都是完整的域名（
DOMAIN）。如果要兼容域名后缀规则（DOMAIN-SUFFIX），字典树的数据结构本身并不需要改变，我们只需要在节点上额外存储一个信息，记录这个节点是DOMAIN还是DOMAIN-SUFFIX，这样未来在匹配时，到这个节点时，通过这个信息，我们就可以判断是继续往下匹配更多子域名（DOMAIN），还是就此停止（DOMAIN-SUFFIX）。
现在我们解决了简单的域名问题，让我们看看相对域名关键词：
融汇贯通，高效储存和匹配海量关键词
现在再来看一个 DOMAIN-KEYWORD 的 RULE-SET 规则集的例子：
DOMAIN-KEYWORD,github
DOMAIN-KEYWORD,gitlab
DOMAIN-KEYWORD,google
DOMAIN-KEYWORD,gstatic
DOMAIN-KEYWORD,gitbook
DOMAIN-KEYWORD,amazon
DOMAIN-KEYWORD,abema
DOMAIN-KEYWORD,abc.com
DOMAIN-KEYWORD,apple
DOMAIN-KEYWORD,facebook这些域名关键词不再具备域名的分层结构了，而且关键词可以完全匹配一个完整域名中的任意部分，如 github 可以匹配 github.com 也可以匹配 githubstatus.com，google 既可以匹配 www.google.com 也可以匹配 play.googleapis.com。那么我们如何高效地储存和匹配关键词呢？
俗话说，「一招鲜，吃遍天」。我们可以注意到，在这些关键词中，github、gitlab、gitbook 都以 git 开头，和 google 又都以 g 开头；abema 和 abc.com 都以 ab 开头，和 apple 又都以 a 开头。所以，我们将这些关键词前往后构建一个相同的字典树出来：
试试在输入框中输入其它关键词，看看生成的树形结构会变成什么样。
实际上，上述交互演示所展示的是 Aho-Corasick 算法（AC 自动机算法），其核心是一个 Trie（由于我们将关键词从前往后构建的 Trie，所以是 Prefix Trie，前缀树）；而在 Trie 的基础上，Aho-Corasick 算法额外增加了节点之间 Failure Link（失配指针）以减少匹配次数：
在进行匹配（如 gogoogle.com）时可以注意到，如果我们遇到字典树走不下去时，我们并没有回到域名的开头、重新试图用另一条路径重新匹配域名，而是顺着 Failure Link 跳到了字典树的另一个节点上。这正是 Failure Link 的意义所在：它在构建时就提前扫描和算好了「这条路走不通时，该从哪里接着走」，因此在匹配时、输入的域名只需要被遍历一次，而不需要 lookback（回溯）。
正因为如此，在使用 Aho-Corasick 算法匹配域名和关键词时，需要的时间取决于输入的域名有多长，和我们到底存了多少个关键词没有关系：无论是 10 个关键词还是 10 万个关键词，匹配 gogoogle.com 的用时都是一样的。
现在我们解决了域名规则，现在让我们把目光转向 IP 地址...
高效地储存和匹配海量 IP 地址段
本文这里介绍的 Tree BitMap 数据结构 基于 Jasper den Hertog 于 2021 年 6 月 4 日在 APNIC 官方博客上发表的「Storing and retrieving IP prefixes efficiently」。
IP-CIDR,10.0.0.0/8
IP-CIDR,100.64.0.0/10
IP-CIDR,127.0.0.0/8
IP-CIDR,172.16.0.0/12
IP-CIDR,169.254.0.0/16
IP-CIDR,192.168.0.0/16
IP-CIDR,224.0.0.0/4IP 地址和域名虽然乍一看有很大区别，但是实际上为 IP 地址设计数据结构要容易得多，因为域名需要是人类可读的，我们在为域名相关规则设计数据结构时需要考虑到域名的语义；而 IP 地址从一开始就是写给机器看的二进制。
以 IPv4 地址 114.51.4.19 为例，我们看到 IPv4 被小数点分成了四个 0 到 255 之间的数字，而 255 这个范围并不是随便定的，它恰好是 8 个二进制位（bit）能表示的全部范围。所以，IPv4 在计算机眼里 无非是由 4 组 8 个 0 和 1 组成的二进制数而已：
114 51 4 19
01110010 . 00110011 . 00000100 . 00010011IPv4 长度为 32 bit，即 32 个 0 和 1 即可表示所有的 IPv4 地址（从 0.0.0.0 到 255.255.255.255）；而 IPv6 长度为 128 bit，即需要 128 个 0 和 1 来表示所有的 IPv6 地址。
现在我们来看 CIDR 规则里 / 后面的那个数字的含义。再以 IPv4 为例，114.51.4.0/24 表示的是从 114.51.4.0 到 114.51.4.255，在人类眼中，也就是被小数点隔开的四个数字中 最后一个数字可以随意变化。让我们把这个范围的 IPv4 用二进制表示出来：
114.51.4.0 -> 01110010 00110011 00000100 00000000
114.51.4.255 -> 01110010 00110011 00000100 11111111
└────────────────────────┘ └──────┘
前 24 位：完全一样 后 8 位：从全 0 到全 1规律一目了然，/24 这个范围里的所有 IP 地址，前 24 位都是一模一样的 011100100011001100000100，而后面的 8 位则可以随意变化。
再看一个 /16 的例子，114.51.0.0/16 表示 114.51.0.0 到 114.51.255.255，在人类眼中，也就是被小数点隔开的四个数字中、后两个数字可以随意变化。同样以二进制形式表现出来：
114.51.0.0 -> 01110010 00110011 00000000 00000000
114.51.255.255 -> 01110010 00110011 11111111 11111111
└───────────────┘ └───────────────┘
前 16 位：完全一样 后 16 位：可以变化同样的道理，只不过 /16 这次固定不变的部分变成了前 16 位，可以随意变化的部分变成了后 16 位。
聪明的读者应该已经意识到，CIDR /N 后面的数字 N 的含义就是一段 IP 地址以二进制表示时，开头的 N 位 bit 必须是固定不变的、而后面剩下的都可以随意变化。所以，我们把匹配 IP-CIDR 规则的问题，又转变成了一个「输入的 IP 地址的二进制 是否以某一个二进制前缀 开头」的问题。而解决前缀匹配问题，兜兜转转，我们又回到了 Trie。不过，在为 IP 地址设计 Trie 时，我们还是有一些技巧可以运用的。
如果使用最朴素的做法，每次只看一个二进制位，用 0 和 1 做分支，但是对于 32 bit 的 IPv4 地址，最坏的情况下我们需要走 32 层（IPv6 更是要走 128 层），比较和跳转的次数都太多了。所以我们一次看 4 位而不是 1 位二进制：把二进制 bit 分成 4 个一组、整组比较，这样最多 8 层就能走完整个 IPv4 地址。
当然，按 4 个 bit 分组的代价是每个节点的分支一下子从 2 个变成了 16 个（4 位二进制有 16 种组合）—— 而绝大多数节点不一定用得满 16 个分支，如果老老实实给每个节点都准备 16 个指针，内存就浪费掉了。
Tree Bitmap 数据结构相比 Trie，精髓就在于此：相比直接用 16 个指针指向 16 个分支，先用一个 16 位的 Bitmap（可以理解成 16 个开关，每个开关代表一个或 0 或 1 的 bit）来记录「这 16 中潜在的分支里，到底哪几个真的存在」。这一排小格子只占 16 个 bit（即 2 个 byte），而真正存在的那些分支以及分支上的数据，则紧凑地挨在一起单独存放。
需要注意，不是所有的 CIDR 长度都是 4 的倍数。100.64.0.0/10 是「二进制的开头 10 位不会改变」，切成 4 位一组之后，会剩下 2 位不上不下。为此，每个节点上还需要第二个 Bitmap，专门记录这些「不足一组的零头」。所以，每个节点上有了两个 Bitmap：
- External Bitmap：记录哪些分支存在，「接下来还能往哪走」
- Internal Bitmap：记录停在这个节点上的规则，「走到这里时是不是已经匹配了」
下面这个交互式演示展示了 7 条私有 IPv4 网段的规则是如何被逐条拆成二进制、切成 4 位一组，然后一层层地在树上安家落户的：
可以注意到 10.0.0.0/8 和 127.0.0.0/8 虽然都是 8 位、都走了两层，却因为第一组 4 位不同（0000 和 0111）而分道扬镳；而唯一带零头的 100.64.0.0/10，前 8 位老老实实走了两层，剩下的 2 位则被记在了终点节点的 Internal Bitmap 上。
匹配的过程也就顺理成章了：把待匹配的 IP 地址同样切成 4 位一组，每到一个节点，先查 Internal Bitmap 看看「是不是已经命中了某条规则」，再查 External Bitmap 看看「接下来还能往哪走」，一直走到无处可走为止：
试试在交互演示中输入各种 IPv4 地址，看看命中和不命中的情况。
如果你希望进一步了解 Tree Bitmap 的实现细节和在短路优化方法，APNIC 那篇博客的作者在 GitHub 上提供了他在博客中提到的所有数据结构的 Rust 示例代码。
本文标题 neta 自 中华人民共和国 2020 浙江自主命题高考语文满分作文《生活在树上》。