设计查询系统

# 设计一个查询系统 | arya dradjica 来源：https://bal-e.org/speed/krabby/2026/query-system-design/ 今年年初以来，我一直在慢慢为 Krabby 设计一个查询系统。我花了五个月的时间静坐深思，现在我相信自己已经清晰把握了整个设计。接下来我会解释为什么 Krabby 需要一个查询系统（因为有一段时间我曾以为不需要），我想要的特殊功能，以及所有这些是如何组合在一起的。 ## 前奏：基于推送的架构 我对 Krabby 最初的愿景是一个[基于推送的架构](https://bal-e.org/speed/krabby/2025/the-architecture/)，其中任务将它们的输出“推送”给后续需要它们的任务。我当时认为这比“基于拉取”的查询系统开销更低。而且这感觉是可行的，因为（特别是在编译的早期阶段）任务之间的依赖关系可以预先知道。编译器可以很容易地并行化执行许多同类型的独立任务。这极大地影响了我设计名称解析算法的方式。 我的想法是（通常是抢先地）从目标 crate 的 `src/` 文件夹中解析 Rust 源文件，并将结果注入一个全局的 Rust 项数据库。该数据库还会存放到目前为止尚未发现的项的待定引用，当这些项被添加时，引用就会被解析。 我对这个设计满意了一段时间，但当我去年十二月深入实现细节时，我意识到这个设计存在一些重要的缺陷。 - 因为全局数据库需要跟踪待定引用，它本质上就是一个专门的查询系统——我并没有绕过这种复杂性。 - 因为它是惰性的，它无法充分利用 CPU 缓存：项的添加（从而插入缓存）可能远早于它们的首次使用。相反，急切的方法——在首次需要时才查找项——会更好地利用缓存。 - 不平衡的依赖图（包含许多必须串行执行的长任务链）无法得到高效处理。这种架构无法识别哪些任务被高度依赖，也无法控制它们的执行时机。它们可能在编译很晚的时候才被执行，并导致单个 CPU 在其他工作完成后仍然持续运行。相比之下，基于拉取的方法会增加一种*需求驱动的优先级*。 - 基于拉取的方法可以轻松地针对不同目标（例如 `cargo check` 与 `cargo build` 与识别某个特定的 Rust 项）。这对让 Krabby 可用于 LSP 至关重要，因为用户发起的操作（例如“查找 `foo()` 的所有引用”）应该以尽可能少的不相关工作量尽快得到评估。 这使我的名称解析实现工作戛然而止。我在 2026 年一开始就着手设计查询系统，并且（除了花了两个月时间写 `housekeeping` (https://crates.io/crates/housekeeping) 这个岔路之外）它一直是我的首要关注点。让我告诉你们：设计一个查询系统可是个大工程！！ ## 我的愿望清单 我一直对代码库从根本上受限于其历史设计选择而感到悲哀。程序被架构的方式使其专门化，并让它走上一条难以脱离的路径。我不断看到一些功能与优化被多年以前的决策所阻碍，而那些决策从未考虑过这些可能性。事情就是这样，但我觉得这令人心碎。 在我所有的项目中，尤其是 Krabby，我尝试尽可能彻底地探索设计空间——向前看五步，甚至十步。我努力设计出能优雅地容纳我能预见的所有可能性的方案。这当然会犯错，但知道我曾尝试过，我感到欣慰。这就是我为写一篇七千字的博客文章找的借口。 以下是我为 Krabby 的查询系统想到的、有趣的功能列表。我主要关注它与 `rustc` 的[查询系统](https://rustc-dev-guide.rust-lang.org/query.html)和 [`salsa`](https://salsa-rs.github.io/salsa/) 的不同之处。我不会立刻尝试实现所有这些功能，但我已经努力在设计中整合了它们的需求。 - **并发**：查询系统应能跨多个线程工作，并高效地在它们之间分配任务（任务是细粒度的工作单元）。它需要处理竞争（不同线程试图计算相同数据）并跨线程检测循环。这不是一个独特的功能，但我认为它对设计的影响最大。`rustc` 的前端已经支持并发（它已经开发了一段时间，现在已作为 [CI 的一部分](https://github.com/rust-lang/rust-project-goals/issues/121#issuecomment-5103073282)进行测试）。我希望在 Krabby 中更进一步拥抱并行性，从一开始就将其视为需求，并让它塑造其余的设计。`housekeeping` (https://crates.io/crates/housekeeping) crate 是迈向并发的重要一步。它提供了构建高性能并发数据结构的一个关键要素：一种安全地在线程之间共享的释放资源的方式。虽然已有其他实现，但 `housekeeping` 提供了一些额外功能（并且，我希望，更好的性能）。我计划找时间写一写它的设计。 - **异步**：任务应该能够暂停和恢复。这本身就解锁了几个功能，值得单独列一个列表： - 如果一个任务依赖于在不同线程上运行的事物，它可以暂停，允许当前线程执行其他任务，并在依赖任务完成后恢复。`salsa` 不支持异步任务，它通过阻塞当前线程来处理这种情况。 - 一个任务可以同时依赖于*多个*其他任务，并且只有在所有这些任务都完成时才恢复。这是第二种批处理：任务可以同时发起多个查询，如果其中任何一个无法立即计算，就暂停。这类似于 `async` 函数的结构化并发：并发等待多个 future 完成，而不是逐个 `.await` 它们。 - 可以实现异步 I/O 任务。由于 Krabby 集成了 Cargo，一个关键的异步 I/O 任务是从网络获取资源。这使得 Krabby 能够完全用查询来实现 Cargo 的功能。 - 它解锁了 `io_uring` 的使用，这是一个用于批处理系统调用并削减开销（通常是巨大的削减！）的 Linux 子系统。有点令人惊讶的是，I/O 有时*确实*可能成为 Rust 编译的瓶颈：在保存增量编译状态，以及加载源文件以识别自上次编译以来的更改时，就会出现这种情况。我不会用 Rust 真正的 `async` 机制来实现它，因为我对它的性能有一些担忧。我已经思考了某些具体类型的任务及其异步状态会是什么样子，我的结论是，使用 `async` 并不能大幅减少样板代码。手动实现的开销（内存和运行时）会更少。 - **批处理**：查询系统应该按类型收集任务（例如“对此 Rust 模块进行名称解析”），并尝试一次执行一批（例如 64 个）同类型任务。批处理是我经常在 Krabby 中尝试探索的一个原则。它应该会立即带来一些次要好处（例如更好地利用代码缓存），但它的真正价值会在遥远的将来。我认为 Rust 编译器中的某些任务确实有可能以显式批处理的方式编写，这可能会解锁无法预见的优化。虽然我手头没有数据（我计划很快收集一些），但哈希表查找（在编译器中*到处都是*）可以通过批处理得到显著优化。它们几乎完全受内存限制，所以它们的延迟远差于它们的吞吐量：执行起来很慢，但它们不会占用太多 CPU 资源。现代 CPU 已经非常擅长 ILP，并且可以在哈希表查找的内存获取进行期间完成其他工作；我认为显式批处理可以将运行时间再提高 20-40%。批处理能解锁的另一项优化当然是 SIMD。虽然你可能在野外找到基于 SIMD 的词法分析器，但我从未见过人们为更复杂的编译阶段（如 AST 降级或类型检查）探索 SIMD。我不知道是否会有所成果，但我相信这样的途径值得探索，而批处理最有可能让它们变得有价值。 - **抢先任务**：即使某些任务尚未被查询，也应该执行它们。每当一个工作线程完成其当前任务时，它应当急切地寻找新任务来执行。任务可以被排序（使用一些简单的临时启发式方法），以优先执行其结果可能很快就会被查询的任务。“等等，你需要一个多线程队列来分发任务，而且你还希望它支持优先级？你打算从哪儿找这么个东西？”好吧，亲爱的读者，事实上我去年已经为 Krabby 的[基于推送的架构](https://bal-e.org/speed/krabby/2025/takeaway/) 写了一个！而且它很快！正如你将看到的，这个任务队列还有助于实现其他几个功能。 - **集成 Cargo**：Krabby 将内置对 Cargo 的支持，自己实现 `cargo` CLI、解析 `Cargo.toml` 并解析依赖关系。（你仍然可以像使用 `rustc` 一样使用它，或者将其修补到自己的构建系统中。）虽然这不是查询系统的功能，但它有深远的影响，我认为值得一提。我经常遇到 `cargo build` 和 `cargo check` 不必要地重建 crate，并且让单个 CPU 运行很长时间的情况。一个简单的例子：在开发 `rustc` 时，我删除了 `rustc_ast` 中的一些未使用代码，这导致*另外 48 个 crate* 被重建，耗时*超过 90 秒*。这里有几个问题： - Cargo 对 `rustc` 的理解非常简陋；如果任何源文件的修改时间（参见[使用校验和的跟踪问题](https://github.com/rust-lang/cargo/issues/14136)）或 crate 的依赖发生了变化，Cargo 都会重新调用 `rustc`。我认为它假设每次 `rustc` 调用都会产生不同输出，因此它也会重建依赖该输出的任何 crate。运行 `touch compiler/rustc_ast/src/lib.rs`（改变 mtime 但不改变文件内容）再重新编译，这本应是一个简单的无操作，但仍然重建了 48 个 crate，耗时 15 秒。 - 虽然 `rustc` 使用查询系统并避免重复工作，但它只对编译的后续阶段这样做。解析、名称解析和宏展开目前并不属于查询系统。任何一次 `rustc` 调用都会导致这些阶段被完整地重复执行。 - `rustc` 要求在开始编译一个 crate 之前，其依赖项已经被编译。这表面上听起来合理，但它严重妨碍了并行性，而且在功能上也不是必须的。给定一条长长的、彼此依赖的 crate 链，对最内层 crate 的更改会导致整条链被串行地重建。`rustc` 已经在尝试分摊这一点：它将代码生成与其余编译过程分开，因此每个 crate 编译的前半部分与其依赖项的代码生成并行进行。要完全解决这个问题，需要一种细粒度的方法。 我相信我能在 Krabby 中避免这些问题。Krabby 将同时编译依赖图中的所有 crate，并且即使两个 crate 彼此依赖，也可以并行开始编译它们。我将 Krabby 的依赖图按 Rust 项（而不是 crate）为单位来表述，因此你需要一条很长的、彼此依赖的 Rust 项链才能使 Krabby 成为瓶颈。而且 Krabby 会绕过许多类似的情况；例如，一个函数调用 `foo()` 可以在知道 `foo` 的签名（而非其实现）的情况下进行类型检查；因此，给定 20 个相互调用的函数，Krabby 可以先并行解析全部 20 个函数签名，然后再并行处理全部 20 个函数调用。我认为 Krabby 将在很大程度上消除最终用户遇到的单 CPU 瓶颈带来的挫败感。 集成 Cargo 会增加也减少开销：Krabby 必须跟踪每一点数据（例如一个 Rust 项）来自哪个 crate，而 `rustc`（通常）只需要考虑正在编译的 crate。另一方面，Krabby 可以通过内存而不是磁盘上的文件读写来在依赖 crate 之间传递数据。无论瓶颈是否得到缓解，我都非常确信集成 Cargo 将显著加速编译。 - **更好的增量性**：查询结果应保存到一个简单、用户可配置的缓存中，用于增量编译。缓存的查询应以与上下文无关的方式（即不绑定到先前编译）作为键。这听起来很简单，但这是一个真正雄心勃勃的改变，我非常兴奋。你看，`rustc` 的增量缓存只保存它在上一次编译期间使用的信息。上一次编译未使用、而是来自更早编译的数据会被移除。因此，简单的更改——比如撤销之前的添加，或在 Git 提交之间来回跳转——很容易使 `rustc` 绊倒并做不必要的工作。此外，`rustc` 要求增量缓存中必须有上次编译的*全部*信息。你不能限制 `target` 文件夹的大小（这个问题在 Cargo 下会严重得多）。在 Krabby 中，我计划将有关查询的数据保存到一个简单的键值缓存中，并且你可以配置缓存淘汰策略（例如 LRU）。例如，“对这个函数进行类型检查”这个查询可以以函数的内容为键。我认为这会为用户带来许多可见的好处： - 你可以配置缓存的最大大小，例如将 `target` 文件夹限制为 1GiB。如果 Krabby 无法把想要的数据都放进去，它就必须更频繁地重新计算数据，但这种情况很少发生，而且它可以给你警告；为了避免 50GB 的 `target` 文件夹爆炸，这是一个值得的权衡。我们可以调整缓存淘汰策略，优先保留重要的、计算成本高的数据。 - 即使你更改 Cargo 的特性标记，大部分缓存也可以复用。今天，Cargo 在 `target` 中存储多个增量缓存，以目标 crate 及其特性标记为键。在 Cargo 下编译一组不同的特性标记会导致完全重建；在 Krabby 中不会出现这种情况。 - 在此基础上，你可以为常见 crate 设置一个系统级缓存，即使你用不同的特性标记编译这些 crate，也能获得加速。这有点像内置的 `sccache`。它可以跟踪经常使用的 crate，并优先将它们存储在这个缓存中。 - Krabby 可以使用共享缓存来编译同一代码库在不同提交下的多个检出；如果你同时查看一个大型代码库的不同版本（例如用于二分 bug 或基准测试），这将非常有用。 - **流式查询**：有时 Krabby 需要计算一个数据集合。想想 IDE 中的“查找所有引用”命令；通配符导入（即 `use foo::*`）；或 Cargo 的 `--workspace` 选项。在所有这些情况下，编译器都必须识别集合中的每一项（每个使用、每个被导入的项、每个 Cargo 包）。有些项可能很快就能被发现，而另一些则可能非常耗时。你可能有位于其他 crate 中的引用、来自包含其自身通配符导入的模块的通配符导入，或者由文件系统通配符（如 `crates/**`）标识的 C