スカイフレーム

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 以外の値を返す必要があります。

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

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

インクリメンタリティ

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

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

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

  • トップダウンの無効化の際には、トップレベル ノードの推移的閉鎖がチェックされ、推移的閉鎖がクリーンであるノードのみが保持されます。これは、現在のノードグラフが大きいことがわかっていても、次のビルドではそのごく一部しか必要ないという場合に役立ちます。ボトムアップの無効化では、最初のビルドの大きなグラフが無効になります。これとは異なり、トップダウンの無効化は 2 番目のビルドの小さなグラフを歩くだけになります。

現在のところ、ボトムアップの無効化のみが行われています。

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

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

増分リンク / コンパイル

このモデルの主な制限は、ノードの無効化がオール オア ナッシングであることです。つまり、依存関係が変更された場合、変更に基づいてノードの古い値を変更する優れたアルゴリズムが存在しても、依存するノードは常にゼロから再構築されます。次のような方法をおすすめします。

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

Bazel が現在、これらのことを原則的にサポートしていない理由（増分リンクについてはある程度のサポートはあるが、Skyframe には実装されていません）が 2 つあります。パフォーマンスの向上は限定的であり、ミューテーションの結果がクリーンな再ビルドの結果と同じになることを保証することは困難です。また、Google は、ビット単位で再現可能なビルドを評価しています。

これまでは、費用のかかるビルドステップを分解して部分的な再評価を行うだけで、常に十分なパフォーマンスを達成できました。つまり、アプリ内のすべてのクラスを複数のグループに分割し、個別に dex 変換する必要がありました。こうすることで、グループ内のクラスが変更されなければ dex を再度実行する必要がなくなります。

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 キーを小さくする必要があるという概念とは矛盾しています。Google では現在、この不一致の解決に取り組んでいます（Skyframe で実行フェーズを実行しない場合、ActionExecutionValue と ArtifactValue は使用されません）。