スカイフレーム

Bazel の並列評価とインクリメンタリティ モデル。

データモデル

データモデルは次の項目で構成されます。

• SkyValue。ノードとも呼ばれます。SkyValues は、ビルドの過程で作成されたすべてのデータとビルドの入力を格納する不変オブジェクトです。例: 入力ファイル、出力ファイル、ターゲット、構成済み ターゲット。
• SkyKey。SkyValue を参照するための短い不変の名前（例: FILECONTENTS:/tmp/foo、PACKAGE://foo）。
• SkyFunction。キーと依存ノードに基づいてノードをビルドします。
• ノードグラフ。ノード間の依存関係を含むデータ構造 。
• Skyframe。Bazel のベースとなる増分評価フレームワークのコード名。

評価

ビルドは、ビルド リクエストを表すノードの評価で構成されます（これが目指す状態ですが、多くのレガシーコードが邪魔になっています）。まず、SkyFunction が見つかり、最上位の SkyKey のキーを使用して呼び出されます。次に、この関数は最上位ノードを評価するために必要なノードの評価をリクエストします。これにより、他の関数呼び出しが発生し、リーフノードに到達するまで続きます（通常、リーフノードはファイル システム内の入力ファイルを表すノードです）。最終的に、最上位の SkyValue の値、いくつかの副作用（ファイル システム内の出力ファイルなど）、ビルドに関与したノード間の依存関係の有向非巡回グラフが得られます。

SkyFunction は、ジョブに必要なすべてのノードを事前に把握できない場合、複数のパスで SkyKeys をリクエストできます。簡単な例として、入力ファイル ノードを評価した結果、シンボリック リンクであることが判明した場合を考えてみましょう。関数はファイルの読み取りを試み、シンボリック リンクであることを認識し、シンボリック リンクのターゲットを表すファイル システム ノードを取得します。ただし、そのノード自体がシンボリック リンクである可能性もあります。その場合、元の関数もターゲットを取得する必要があります。

コードでは、関数はインターフェース SkyFunction と、SkyFunction.Environment というインターフェースによって提供されるサービスで表されます。関数でできることは次のとおりです。

• env.getValue を呼び出して、別のノードの評価をリクエストします。ノードが使用可能な場合はその値が返されます。使用できない場合は null が返され、関数自体も null を返すことが想定されます。後者の場合、依存ノードが評価され、元のノードビルダーが再度呼び出されますが、今回は同じ env.getValue 呼び出しで null 以外の値が返されます。
• env.getValues() を呼び出して、複数の他のノードの評価をリクエストします。基本的には同じですが、依存ノードが並行して評価される点が異なります。
• 呼び出し中に計算を行う
• 副作用がある（例: ファイル システムへのファイルの書き込み）。2 つの異なる関数が互いに干渉しないように注意する必要があります。一般に、書き込みの副作用（データが Bazel から外部に流れる場合）は問題ありませんが、読み取りの副作用（登録された依存関係なしにデータが Bazel に流入する場合）は問題があります。これは、登録されていない依存関係であるため、増分ビルドが正しく行われない可能性があるためです。

SkyFunction の実装では、依存関係のリクエスト（ファイル システムの直接読み取りなど）以外の方法でデータにアクセスしないでください。これにより、Bazel が読み取られたファイルに対するデータ依存関係を登録せず、増分ビルドが正しく行われなくなります。

関数がジョブを実行するのに十分なデータを持っている場合は、完了を示す null 以外の値を返す必要があります。

この評価戦略には次のようなメリットがあります。

• 密閉性。関数が他のノードに依存することで入力データのみをリクエストする場合、Bazel は入力状態が同じであれば同じデータが返されることを保証できます。すべての Sky 関数が決定論的である場合、ビルド全体も決定論的になります。
• 正確で完全なインクリメンタリティ。すべての関数の入力データが記録されている場合、Bazel は入力データが変更されたときに無効にする必要があるノードの正確なセットのみを無効にできます。
• 並列処理。関数は依存関係をリクエストすることでのみ相互にやり取りできるため、互いに依存しない関数は並行して実行できます。Bazel は、順次実行した場合と同じ結果になることを保証できます。

インクリメンタリティ

関数は他のノードに依存することでのみ入力データにアクセスできるため、Bazel は入力ファイルから出力ファイルまでの完全なデータフロー グラフを作成し、この情報を使用して、実際に再ビルドする必要があるノード（変更された入力ファイルのセットの逆推移閉包）のみを再ビルドできます。

特に、インクリメンタリティ戦略には、ボトムアップとトップダウンの 2 つがあります。どちらが最適かは、依存関係グラフの形状によって異なります。

• ボトムアップの無効化では、グラフが作成され、変更された入力のセットが判明した後、変更されたファイルに推移的に依存するすべてのノードが無効になります。同じ最上位ノードが再度ビルドされることがわかっている場合は、これが最適です。ボトムアップの無効化では、変更されたかどうかを判断するために、前のビルドのすべての入力ファイルで stat() を実行する必要があります。これは、inotify などのメカニズムを使用して、変更されたファイルについて学習することで改善できます。

• トップダウンの無効化では、最上位ノードの推移閉包がチェックされ、推移閉包がクリーンなノードのみが保持されます。現在のノードグラフが大きいが、次のビルドで必要なのはそのサブセットのみであることがわかっている場合は、この方法が適しています。ボトムアップの無効化では、2 回目のビルドの小さなグラフを走査するだけのトップダウンの無効化とは異なり、最初のビルドの大きなグラフが無効になります。

現在、ボトムアップの無効化のみを行っています。

インクリメンタリティをさらに高めるために、変更のプルーニングを使用します。ノードが無効になったが、再ビルド時に新しい値が古い値と同じであることが判明した場合、このノードの変更によって無効になったノードは「復活」します。

これは、たとえば C++ ファイルのコメントを変更した場合に便利です。このファイルから生成される .o ファイルは同じになるため、リンカーを再度呼び出す必要はありません。

増分リンク / コンパイル

このモデルの主な制限は、ノードの無効化がオール オア ナッシングであることです。依存関係が変更されると、ノードの古い値を変更するより優れたアルゴリズムが存在する場合でも、依存ノードは常に最初から再ビルドされます。この方法が役立つ例をいくつか示します。

• 増分リンク
• .jar 内の 1 つの .class ファイルが変更された場合、理論的には、最初から再ビルドするのではなく、.jar ファイルを変更できます。

Bazel が現在、これらの機能を原則的な方法でサポートしていない理由（増分リンクはある程度サポートしていますが、Skyframe 内には実装されていません）は 2 つあります。パフォーマンスの向上は限定的であり、変更後の結果がクリーンな再ビルドの結果と同じになることを保証するのが難しかったためです。また、Google はビット単位で再現可能なビルドを重視しています。

これまで、高コストのビルドステップを分解し、部分的な再評価を行うことで、常に十分なパフォーマンスを実現できました。アプリ内のすべてのクラスを複数のグループに分割し、それぞれで dexing を行います。これにより、グループ内のクラスが変更されない場合、dexing をやり直す必要はありません。

Bazel のコンセプトへのマッピング

Bazel がビルドの実行に使用する SkyFunction の実装の概要を以下に示します。

• FileStateValue。lstat() の結果。既存のファイルについては、ファイルの変更を検出するために追加情報も計算します。これは Skyframe グラフの最下位レベルのノードであり、依存関係はありません。
• FileValue 。ファイルの内容や解決されたパスを重視するすべてのものに使用されます。対応する FileStateValue と、解決する必要があるシンボリック リンク（a/b の FileValue には a の解決されたパスと a/b の解決されたパスが必要です）に依存します。FileStateValue の区別が重要なのは、ファイル システムの glob（srcs=glob(["*/*.java"]) など）を評価する場合など、ファイルの内容が実際に必要ない場合があるためです。
• DirectoryListingValue。基本的には readdir() の結果です。ディレクトリに関連付けられた FileValue に依存します。
• PackageValue 。BUILD ファイルの解析済みバージョンを表します。関連付けられた BUILD ファイルの FileValue に依存し、パッケージ内の glob を解決するために使用される DirectoryListingValue にも推移的に依存します（BUILD ファイルの内容を表すデータ構造）。
• ConfiguredTargetValue。構成済みターゲットを表します。これは、ターゲットの分析中に生成されたアクションのセットと、このターゲットに依存する構成済みターゲットに提供される情報のタプルです。対応するターゲットが存在する PackageValue、直接依存関係の ConfiguredTargetValues、ビルド構成を表す特別なノードに依存します。
• ArtifactValue。ビルド内のファイルを表します。ソース アーティファクトまたは出力アーティファクトです（アーティファクトはファイルとほぼ同じで、ビルドステップの実際の実行中にファイルを参照するために使用されます）。ソースファイルの場合、関連付けられたノードの FileValue に依存します。出力アーティファクトの場合、アーティファクトを生成するアクションの ActionExecutionValue に依存します。
• ActionExecutionValue。アクションの実行を表します。入力ファイルの ArtifactValues に依存します。現在、実行するアクションは Sky キーに含まれています。これは、Sky キーは小さくすべきであるというコンセプトに反しています。この不一致の解決に取り組んでいます（Skyframe で実行フェーズを実行しない場合、ActionExecutionValue と ArtifactValue は使用されません）。