スカイフレーム

問題を報告する ソースを表示

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

データモデル

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

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

評価

ビルドは、ビルド リクエストを表すノードの評価で構成されます（Google が取り組んでいる状態ですが、多くのレガシーコードが用意されています）。まず、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 では実装されていません）があります。パフォーマンスの向上は限られており、ミューテーションの結果がクリーンな再ビルドの結果と同じであることを確認することは困難であり、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 は未使用です）。