Jane Street Incremental: 増分計算のためのライブラリ

Incremental は計算グラフ内の依存関係を追跡することで再計算を最小限に抑えます

Jane Street の Incremental は、ソースデータが変更された際に計算グラフを部分的に更新（hydrating）するという問題を解決するために設計されたライブラリです。入力が変更されたときに計算パイプライン全体を再実行するのではなく、Incremental は計算間の依存関係を追跡し、変更の影響を受ける特定のノードのみを更新します。このアプローチにより、計算オーバーヘッドを理論上の最小値まで削減し、複雑で相互依存的なデータ変換において非常に高い効率を実現します。

コアコンセプトと実装

Incremental は計算のためのビルドシステムとして機能し、データの入力と出力の関係を指向性非巡回グラフ（DAG）として扱います。

依存関係の追跡と伝播

• 自動グラフ構築: ライブラリは、実行中に依存関係を内省することで、計算グラフを自動的に構築します。
• 変更の伝播: ソース値が更新されると、ライブラリはその変更をグラフ全体に伝播させます。このパターンのいくつかの実装では、評価の順序を決定し、冗長な更新を避けるために、高さベースのアルゴリズムが使用されます。
• バッチ処理: stabilize コマンドを使用すると、開発者は複数の変更をまとめてバッチ処理することができ、一連の更新が完了した後に計算グラフが一度だけ再評価されるようにします。

Observable パターンの比較

入力がリスナーに値を公開する Observable パターンと似ていますが、Incremental は変更検知の最適化と、ノードが再計算される回数の最小化に焦点を当てています。入力が変更されたにもかかわらず計算結果が変わらない場合、伝播を停止させることで、単純なプッシュベースのシステムの欠陥を回避します。

業界での応用とエコシステム

増分計算は、金融モデリングから現代的なユーザーインターフェースまで、さまざまなドメインで使用される基礎的なパターンです。

金融ワークロードとハイパフォーマンス・コンピューティング

増分計算は、金融業界において長い歴史を持っています。例えば、Goldman Sachs のような企業におけるデリバティブ価格設定システムは、数十年前から、高コストな微分計算を最小限に抑えるために同様のグラフベースのアプローチを利用していました。現代的な反復版には、Differential Dataflow、Timely Dataflow、および DBSP (Feldera によって使用) などのシステムがあり、これらは大規模な金融データワークロード向けに最適化されています。

UI フレームワークと「Signals"

JavaScript エコシステムでは、このパターンは現在「Signals」として普及しています。Vue, SolidJS, Svelte, Ember, and Angular などのフレームワークは、きめ細かなリアクティビティを実現するために signals を使用しています。

• SolidJS は、特に Incremental と同様の、DAG 評価のための高さベースのアルゴリズムを利用しています。
• Bonsai は、Jane Street が開発した UI ライブラリであり、Incremental の上に直接構築されています。これは、Virtual DOM（React で使用）のアプローチを改善し、VDOM 自体を増分的に扱うことで、ツリー構築に費やされる時間を削減します。

コンパイラとビルドシステム

増分計算は、現代的なビルドシステムやコンパイラの中核をなしています。例えば、Salsa は、rust-analyzer で使用されている増分計算フレームワークであり、IDE が変更されたコードの部分のみを再解析するようにします。

技術的なトレードオフと検討事項

言語の選択: OCaml

Incremental は OCaml で書かれており、複雑な依存関係グラフにおける正確性を保証する強力な型システムによる保証を提供します。OCaml の性能について C++ と比較して疑問を呈する声もありますが、他の開発者は OCaml の速度が Java と同等であり、解釈型言語よりも大幅に速いことに注目しています。これは、ハイパフォーマンス・コンピューティング・グラフにとって適しています。

動的 vs. 静的グラフ

増分計算システムにおける課題の一つは、動態性（runtime でノードがノードが追加または削除されること、例えば UI ウィンドウがポップアップしたり消えたりすること）の扱いです。固定サイズのグラフ（スプレッドシートなど）は単純ですが、動的グラフは、キャッシュの問題やスケーリングのボトルネックを避けるために、より洗練されたメモリ管理と追跡が必要です。

代替アプローチ

一部の開発者は、代替案として Merkle Trees (hash trees) の使用を提案しています。依存関係のハッシュとソルトを用いて計算ノードにタグを付けることで、システムは、単にハッシュを比較することで結果が再計算される必要があるかどうかを識別できます。また、ID を使用してキャッシュ内の結果をインデックスし、結果を管理します。