Skyframe StateMachines のガイド

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

概要

Skyframe StateMachine は、ヒープ上に存在する「分解された」関数オブジェクトです。すぐには利用できないものの、非同期に計算される場合、1 冗長性なしに柔軟性と評価がサポートされます。StateMachine は待機中にスレッド リソースを結合できませんが、停止して再開する必要があります。そのため、この分解により明示的な再エントリ ポイントが公開されるため、以前の計算がスキップされます。

StateMachine は、シーケンス、分岐、構造化論理同時実行を表すために使用できます。これは特に Skyframe のインタラクションに合わせて調整されています。StateMachine は、より大きな StateMachine に構成し、サブ StateMachine を共有できます。同時実行は、常に階層構造で、純粋に論理的です。すべての同時実行サブタスクは、単一の共有親 SkyFunction スレッドで実行されます。

はじめに

このセクションでは、java.com.google.devtools.build.skyframe.state パッケージにある StateMachine について簡単に説明します。

Skyframe の再起動の概要

Skyframe は依存関係グラフを並行して評価するフレームワークです。グラフの各ノードは、SkyKey がパラメータを指定し、SkyValue が結果を指定する SkyFunction の評価に対応しています。この計算モデルは、SkyFunction が SkyKey を使用して SkyValue を検索することで、追加の SkyFunction の再帰的な並列評価をトリガーできます。ブロックする代わりに、リクエストされた SkyValue がまだ準備できていない場合にスレッドを結合し、リクエスト元の SkyFunction は null getValue レスポンスを監視し、SkyValue ではなく null を返して、入力がないために未完了であることを示します。Skyframe は、リクエストされたすべての SkyValue が使用可能になると SkyFunctions を再起動します。

SkyKeyComputeState が導入されるまでは、再起動を処理する従来の方法は、計算を完全に再実行することでした。これには 2 次的な複雑性がありますが、再実行されるたびに null が返されるルックアップが少なくなるため、この方法で記述された関数は最終的に完了します。SkyKeyComputeState を使用して、手動で指定されたチェックポイント データを SkyFunction に関連付けることで、大幅な再計算を削減できます。

StateMachine は SkyKeyComputeState 内に存在するオブジェクトで、SkyFunction が再起動したときに（SkyKeyComputeState がキャッシュから外れないと仮定して）実質的にすべての再計算を排除するために、一時停止と再開の実行フックを公開します。

SkyKeyComputeState 内のステートフルな計算

オブジェクト指向の設計の観点からは、純粋なデータ値ではなく、計算オブジェクトを SkyKeyComputeState 内に格納することを検討してください。Java では、オブジェクトを保持する動作は最小限の記述で機能インターフェースであり、十分です。StateMachine には、奇妙な形で再帰的な定義があります。2

@FunctionalInterface
public interface StateMachine {
  StateMachine step(Tasks tasks) throws InterruptedException;
}

Tasks インターフェースは SkyFunction.Environment に似ていますが、非同期用に設計されており、論理的に同時実行するサブタスクのサポートが追加されます3。

step の戻り値も別の StateMachine であるため、一連のステップを間接的に指定できます。StateMachine が完了すると、step は DONE を返します。次に例を示します。

class HelloWorld implements StateMachine {
  @Override
  public StateMachine step(Tasks tasks) {
    System.out.println("hello");
    return this::step2;  // The next step is HelloWorld.step2.
  }

  private StateMachine step2(Tasks tasks) {
     System.out.println("world");
     // DONE is special value defined in the `StateMachine` interface signaling
     // that the computation is done.
     return DONE;
  }
}

StateMachine は次の出力を表示します。

hello
world

なお、step2 は StateMachine の関数型インターフェース定義を満たすため、メソッド参照 this::step2 も StateMachine です。メソッド参照は、StateMachine で次の状態を指定する最も一般的な方法です。

一時停止と再開

直観的には、モノリシック関数ではなく StateMachine ステップに計算を分割することで、計算を一時停止して再開するために必要なフックが提供されます。StateMachine.step が返されたときは、明示的な停止ポイントがあります。返された StateMachine 値で指定された継続は、明示的に再開ポイントになります。計算を中断したところから再開できるため、再計算を回避できます。

コールバック、継続、非同期計算

技術的にいうと、StateMachine は継続として機能し、その後で実行される処理を決定します。StateMachine は、ブロックする代わりに step 関数から戻ることで自発的に停止できます。停止すると、制御が Driver インスタンスに戻ります。すると、Driver は準備された StateMachine に切り替えるか、コントロールを放棄して Skyframe に戻すことができます。

従来、コールバックと継続は 1 つのコンセプトにまとめていました。ただし、StateMachine では両者が区別されます。

  • コールバック - 非同期計算の結果を保存する場所を記述します。
  • 継続 - 次の実行状態を指定します。

コールバックは、非同期オペレーションを呼び出すときに必要です。つまり、SkyValue ルックアップのように、メソッドを呼び出しても実際のオペレーションが直ちに実行されることはありません。コールバックはできる限りシンプルにする必要があります。

継続とは、StateMachine の StateMachine 戻り値であり、すべての非同期計算が解決された後に続く複雑な実行をカプセル化することです。この構造化されたアプローチにより、コールバックの複雑さを管理しやすくなります。

タスク

Tasks インターフェースには、SkyKey を使用して SkyValue を検索し、同時実行のサブタスクをスケジュール設定するための API が StateMachine に用意されています。

interface Tasks {
  void enqueue(StateMachine subtask);

  void lookUp(SkyKey key, Consumer<SkyValue> sink);

  <E extends Exception>
  void lookUp(SkyKey key, Class<E> exceptionClass, ValueOrExceptionSink<E> sink);

  // lookUp overloads for 2 and 3 exception types exist, but are elided here.
}

SkyValue ルックアップ

StateMachine は、Tasks.lookUp のオーバーロードを使用して SkyValues を検索します。SkyFunction.Environment.getValue と SkyFunction.Environment.getValueOrThrow に類似しており、例外処理のセマンティクスが類似しています。この実装は直ちにルックアップを実行するのではなく、実行する前に可能な限り多くのルックアップをバッチ化します4。この値はすぐに利用できない場合があります。たとえば、Skyframe の再起動が必要であるため、呼び出し元はコールバックを使用して結果の値をどのように処理するかを指定します。

StateMachine プロセッサ（Driver と SkyFrame へのブリッジ）により、次の状態が開始する前に値が利用可能であることが保証されます。以下に例を示します。

class DoesLookup implements StateMachine, Consumer<SkyValue> {
  private Value value;

  @Override
  public StateMachine step(Tasks tasks) {
    tasks.lookUp(new Key(), (Consumer<SkyValue>) this);
    return this::processValue;
  }

  // The `lookUp` call in `step` causes this to be called before `processValue`.
  @Override  // Implementation of Consumer<SkyValue>.
  public void accept(SkyValue value) {
    this.value = (Value)value;
  }

  private StateMachine processValue(Tasks tasks) {
    System.out.println(value);  // Prints the string representation of `value`.
    return DONE;
  }
}

上記の例では、最初のステップで new Key() のルックアップを行い、this をコンシューマとして渡しています。これは、DoesLookup が Consumer<SkyValue> を実装しているために可能です。

契約により、次の状態 DoesLookup.processValue が始まる前に、DoesLookup.step のすべてのルックアップが完了します。したがって、processValue でアクセスされると、value を使用できます。

サブタスク

Tasks.enqueue は、論理的に同時実行するサブタスクの実行をリクエストします。サブタスクも StateMachine であり、繰り返しのサブタスクの作成や SkyValues の検索など、通常の StateMachine で可能なすべての操作を行うことができます。lookUp と同様に、ステートマシンのドライバは、すべてのサブタスクが完了してから次のステップに進みます。以下に例を示します。

class Subtasks implements StateMachine {
  private int i = 0;

  @Override
  public StateMachine step(Tasks tasks) {
    tasks.enqueue(new Subtask1());
    tasks.enqueue(new Subtask2());
    // The next step is Subtasks.processResults. It won't be called until both
    // Subtask1 and Subtask 2 are complete.
    return this::processResults;
  }

  private StateMachine processResults(Tasks tasks) {
    System.out.println(i);  // Prints "3".
    return DONE;  // Subtasks is done.
  }

  private class Subtask1 implements StateMachine {
    @Override
    public StateMachine step(Tasks tasks) {
      i += 1;
      return DONE;  // Subtask1 is done.
    }
  }

  private class Subtask2 implements StateMachine {
    @Override
    public StateMachine step(Tasks tasks) {
      i += 2;
      return DONE;  // Subtask2 is done.
    }
  }
}

Subtask1 と Subtask2 は論理的に同時実行可能ですが、すべてが単一のスレッドで実行されるため、i の「同時」更新で同期を行う必要はありません。

構造化された同時実行

すべての lookUp と enqueue は、次の状態に進む前に解決する必要があるため、同時実行は必然的にツリー構造に制限されます。次の例に示すように、階層型 5 同時実行を作成できます。

構造化された同時実行

UML から、同時実行構造がツリーを形成していることを判断するのは困難です。ツリー構造をより的確に示す代替ビューがあります。

非構造化同時実行

構造化された同時実行は、はるかに簡単に推測できます。

コンポジションと制御のフローパターン

このセクションでは、複数の StateMachine の作成方法と、特定の制御フローに関する問題の解決策の例を示します。

順次状態

これは、最も一般的でわかりやすい制御フロー パターンです。SkyKeyComputeState 内のステートフルな計算の例をご覧ください。

ブランチ

StateMachine の分岐状態は、次の例に示すように、通常の Java 制御フローを使用して異なる値を返すことで実現できます。

class Branch implements StateMachine {
  @Override
  public StateMachine step(Tasks tasks) {
    // Returns different state machines, depending on condition.
    if (shouldUseA()) {
      return this::performA;
    }
    return this::performB;
  }
  …
}

一部のブランチでは、早期の完了に DONE を返すのが一般的です。

高度な順次合成

StateMachine コントロール構造はメモリレスであるため、StateMachine 定義をサブタスクとして共有すると、不自然になることがあります。M1 と M22 は、それぞれ StateMachine と StateMachine の共有 StateMachine になります。M2 は、それぞれ <A, S, B> と <X, S, Y> となります。問題は、完了後に S が B と Y のどちらを続行するかを認識せず、StateMachine がコールスタックを完全に保持しないことです。このセクションでは、その方法を紹介します。

StateMachine を終端とするシーケンス要素

この方法で解決できませんでした。共有 StateMachine がシーケンスの終端である場合にのみ、シーケンシャル構成を示します。

// S is the shared state machine.
class S implements StateMachine { … }

class M1 implements StateMachine {
  @Override
  public StateMachine step(Tasks tasks) {
    performA();
    return new S();
  }
}

class M2 implements StateMachine {
  @Override
  public StateMachine step(Tasks tasks) {
    performX();
    return new S();
  }
}

これは、S 自体が複雑なステートマシンであっても機能します。

連続した構成のサブタスク

キューに登録されたサブタスクは、次の状態になる前に完了することが保証されているため、サブタスクのメカニズムをわずかに悪用する6場合もあります。

class M1 implements StateMachine {
  @Override
  public StateMachine step(Tasks tasks) {
    performA();
    // S starts after `step` returns and by contract must complete before `doB`
    // begins. It is effectively sequential, inducing the sequence < A, S, B >.
    tasks.enqueue(new S());
    return this::doB;
  }

  private StateMachine doB(Tasks tasks) {
    performB();
    return DONE;
  }
}

class M2 implements StateMachine {
  @Override
  public StateMachine step(Tasks tasks) {
    performX();
    // Similarly, this induces the sequence < X, S, Y>.
    tasks.enqueue(new S());
    return this::doY;
  }

  private StateMachine doY(Tasks tasks) {
    performY();
    return DONE;
  }
}

runAfter インジェクション

Tasks.enqueue の乱用ができない場合もあります。これは、S の実行前に完了する必要がある、他の並列サブタスクまたは Tasks.lookUp 呼び出しがあるためです。この場合、runAfter パラメータを S に挿入すると、処理内容を S に通知できます。

class S implements StateMachine {
  // Specifies what to run after S completes.
  private final StateMachine runAfter;

  @Override
  public StateMachine step(Tasks tasks) {
    … // Performs some computations.
    return this::processResults;
  }

  @Nullable
  private StateMachine processResults(Tasks tasks) {
    … // Does some additional processing.

    // Executes the state machine defined by `runAfter` after S completes.
    return runAfter;
  }
}

class M1 implements StateMachine {
  @Override
  public StateMachine step(Tasks tasks) {
    performA();
    // Passes `this::doB` as the `runAfter` parameter of S, resulting in the
    // sequence < A, S, B >.
    return new S(/* runAfter= */ this::doB);
  }

  private StateMachine doB(Tasks tasks) {
    performB();
    return DONE;
  }
}

class M2 implements StateMachine {
  @Override
  public StateMachine step(Tasks tasks) {
    performX();
    // Passes `this::doY` as the `runAfter` parameter of S, resulting in the
    // sequence < X, S, Y >.
    return new S(/* runAfter= */ this::doY);
  }

  private StateMachine doY(Tasks tasks) {
    performY();
    return DONE;
  }
}

この方法は、サブタスクを乱用するよりもクリーンです。ただし、複数の StateMachine を runAfter にネストするなどして、これを制限なく適用することは、Callback Hell への道のりです。代わりに、連続した runAfter を通常の連続した状態に分割することをおすすめします。

  return new S(/* runAfter= */ new T(/* runAfter= */ this::nextStep))

{0/} は次のものに置き換えることができます。

ヒント: runAfter を使用する場合は、常にパラメータに /* runAfter= */ アノテーションを付けて、呼び出しサイトの意味をリーダーに知らせます。
  private StateMachine step1(Tasks tasks) {
     doStep1();
     return new S(/* runAfter= */ this::intermediateStep);
  }

  private StateMachine intermediateStep(Tasks tasks) {
    return new T(/* runAfter= */ this::nextStep);
  }