Jane Street Incremental: 增量计算库

Incremental 通过在计算图中跟踪依赖关系来最小化重新计算

Jane Street 的 Incremental 是一个旨在解决当源数据发生变化时，对计算图进行部分更新（partially hydrating）问题的库。Incremental 不会在输入发生变化时重新执行整个计算流水线，而是跟踪计算之间的依赖关系，并仅更新受变化影响的具体节点。这种方法将计算开销降低到了理论最小值，使其在处理复杂的、相互依赖的数据转换时非常高效。

核心概念与实现

Incremental 的功能类似于计算的构建系统，将数据输入与输出之间的关系视为有向无环图 (DAG)。

依赖跟踪与传播

• 自动图构建：该库通过在执行期间内省依赖关系来自动构建计算图。
• 变化传播：当源值更新时，库会将该变化通过图进行传播。此模式的一些实现使用基于高度的算法来确定评估顺序，并避免冗余更新。
• 批处理：stabilize 命令允许开发者将多个变化打包在一起，确保在完成一组更新后，计算图仅重新评估一次。

与 Observable 模式的比较

虽然与 Observable 模式（即输入向监听器发布值）类似，但 Incremental 专注于优化变化检测并最小化节点的重新计算次数。它通过确保如果计算值在输入变化后仍保持不变，则停止传播，从而避免了朴素的推送式系统的陷阱。

行业应用与生态系统

增量计算是一种基础模式，广泛应用于从金融建模到现代用户界面的各个领域。

金融工作负载与高性能计算

增量计算在金融领域有着悠久的历史。例如，Goldman Sachs 等公司的金融工具定价系统在几十年前就利用了类似的基于图的方法，以最小化昂贵的微分计算。现代迭代版本包括 Differential Dataflow、Timely Dataflow 和 DBSP（由 Feldera 使用），这些系统针对大规模金融数据工作负载进行了优化。

UI 框架与 "Signals"

在 JavaScript 生态系统中，这种模式目前正以 "Signals" 的形式流行起来。Vue, SolidJS, Svelte, Ember, 和 Angular 等框架使用 signals 来实现细粒度的响应性。

• SolidJS 特别利用了类似于 Incremental 中使用的基于高度的 DAG 评估算法。
• Bonsai 是由 Jane Street 开发的一个 UI 库，它直接构建在 Incremental 之上。它通过使 VDOM 本身具有增量性，改进了 Virtual DOM 方法（React 使用），从而减少了构建树的时间。

编译器与构建系统

增量计算是现代构建系统和编译器的核心。例如，Salsa 是 rust-analyzer 中使用的一个增量计算框架，以确保 IDE 仅重新分析发生变化的代码部分。

技术权衡与考量

语言选择：OCaml

Incremental 是用 OCaml 编写的，提供了强大的类型系统保证，从而确保复杂依赖图中的正确性。虽然有人质疑 OCaml 与 C++ 相比的性能，但也有人指出 OCaml 的速度通常与 Java 相当，并且明显快于解释型语言，使其非常适合高性能计算图。

动态 vs. 静态图

增量系统中的一个挑战是处理动态性——即节点在运行时被添加或删除（例如，UI 窗口弹出并消失）。虽然固定大小的图（如电子表格）比较简单，但动态图需要更更复杂的内存管理和跟踪，以避免缓存问题或扩展瓶颈。

替代方案

一些开发者建议使用 Merkle Trees (hash trees) 作为替代方案。通过为计算节点标记其依赖关系的哈希值和盐值（salt），系统可以通过简单地比较哈希值来识别结果是否需要重新计算，并使用 ID 在缓存中索引结果。