IP 数据库体积缩小 31%，关键竟然是合并重复子树

根据 IPinfo 的文章 How We Made Our MMDB Files a Third Smaller Without Changing a Byte of Data 整理。原文作者：Tiago Martins、Silvano Cerza。

MMDB 是一种用于查询 IP 地址的二进制格式。IPinfo 发现，文件的搜索树中有许多重复子树，只要把它们合并，就能在不改变查询结果的情况下缩小文件。

这一方法让 IPinfo 的 89 个生产数据库总大小从 91.2 GB 降至 62.8 GB，减少了约 31%；其中缩减幅度最大的数据库达到了 80%。优化后的文件仍是标准 MMDB，无需解压，也不用更换读取库。并且开源啦！ mmdbshrink

MMDB 文件的结构

MMDB 文件主要由搜索树和数据段组成。

搜索树是一棵按 IP 地址比特位构建的二叉前缀树。查询从根节点开始，逐位读取 IP 地址：遇到 0 向左，遇到 1 向右，直到抵达叶节点。叶节点指向数据段中的记录，例如国家、城市、ASN 和隐私标志。

数据段中的重复记录只需存储一次，多个叶节点可以通过指针引用它。常见的 MMDB 写入器已经做了这类去重。

搜索树却可能包含大量重复子树。传统写入器会写出遍历到的每个节点，即使已经写过结构相同的节点，也会再存一份。

重复子树从哪里来

IP 数据中有大量重复值。例如，隐私数据库可能将少数几种判定结果应用到数百万个地址范围；地理位置数据库中的同一城市记录也可能对应许多不同前缀。

如果两个前缀下的子树结构相同，对应位置又指向相同的数据记录或空结果，那么它们就是重复子树。写入器虽然会把它们分别存储，查询时却不需要保留这些独立副本。

用哈希驻留共享子树

哈希驻留可以用来复用结构相同的对象。它用一张哈希表记录已有节点：创建新节点前，先检查是否存在结构相同的节点；如果存在，就直接复用。

对 MMDB 搜索树，可以从叶节点向根节点自底向上处理：

1. 先处理子节点，再处理父节点。
2. 将子节点引用替换为对应的规范节点标识；数据记录和空结果的引用保留原有含义。
3. 将左右两个子节点引用组成的有序对作为哈希表的键。如果已有完全相同的有序对，就复用对应节点；否则创建并登记新节点。查表时还要比较完整的有序对，避免因哈希碰撞错误合并节点。
4. 写出去重后的节点，保留根节点编号为 0，重新编号节点引用，并更新 node_count 和编码后的数据引用。

处理后，搜索树变成了有向无环图：多个父节点可以指向同一棵子树，文件中只需保存一份。

MMDB 节点本来就能指向其他节点、数据记录或空结果；格式规范也描述了 IPv4 别名中的节点共享。因此，这种优化不需要修改文件格式。对任意 IP 地址，查询仍会经过相同的分支选择，最终到达相同的记录或空结果。

相关背景可参考 Filliâtre 和 Conchon 的哈希驻留论文，以及 Bryant 的二元决策图论文。

实际效果

不同数据库的缩减幅度取决于搜索树中重复子树的数量。以下是 IPinfo 给出的部分生产数据：

在原文的 ipinfo_lite 示例中，文件从 37.76 MB 降至 25.08 MB，节点数从 3,790,310 降至 2,205,358。搜索树从 30.32 MB 缩至 17.64 MB，数据段则保持 7.44 MB 不变：节省的空间全部来自搜索树。

原文报告的一百万次查询基准中，单次查询耗时从 797 ns 降至 757 ns；映射文件的缓存大小从 36.02 MiB 降至 23.92 MiB。实际进程常驻内存则从 29.34 MiB 降至 27.58 MiB。文件更小有利于降低存储和传输成本，内存收益则取决于实际访问和映射情况。

如何验证查询结果不变

优化索引结构的前提是不能改变查询结果。IPinfo 使用了以下检查：

• 双向枚举前缀： 在优化后的文件中查询原文件的每个前缀，再反向执行。ipinfo_lite 涉及 3,783,922 个前缀、7,567,844 次查询，结果全部一致。
• 随机地址查询： 分别检查一百万个随机 IPv4 和 IPv6 地址，没有发现不匹配。
• 格式和差异检查： mmdbctl verify 验证文件有效；mmdbctl diff 显示没有子网或记录被修改；MaxMind 的 mmdbverify 也通过验证。
• 兼容性与性能测试： 使用 12 个 MMDB 读取器 SDK 测试，并比较优化前后的查询延迟与内存表现。

其中，双向前缀枚举比单独依赖随机地址采样更系统地检查了两个文件的映射关系。