Guía de Skyframe StateMachines

Informa un problemaopen_in_new Ver código fuenteopen_in_new

Descripción general

Un StateMachine de Skyframe es un objeto de función deconstruido que reside en el montón. Admite flexibilidad y evaluación sin redundancia¹ cuando los valores necesarios no están disponibles de inmediato, pero se calculan de forma asíncrona. El StateMachine no puede vincular un recurso de subproceso mientras espera, sino que debe suspenderse y reanudarse. Por lo tanto, la deconstrucción expone puntos de reentrada explícitos para que se puedan omitir los cálculos anteriores.

Los StateMachine se pueden usar para expresar secuencias, ramificaciones y simultaneidad estructurada lógica, y están diseñados específicamente para la interacción de Skyframe. Los StateMachine se pueden componer en objetos StateMachine más grandes y compartir subStateMachine. La simultaneidad siempre es jerárquica por construcción y es totalmente lógica. Cada subtarea simultánea se ejecuta en el subproceso principal de SkyFunction único compartido.

Introducción

En esta sección, se motiva y se presentan brevemente los StateMachine, que se encuentran en el paquete java.com.google.devtools.build.skyframe.state.

Una breve introducción a los reinicios de Skyframe

Skyframe es un framework que realiza una evaluación en paralelo de gráficos de dependencias. Cada nodo del gráfico corresponde a la evaluación de una SkyFunction con una SkyKey que especifica sus parámetros y SkyValue que especifica su resultado. El modelo de procesamiento es tal que una SkyFunction puede buscar SkyValues por SkyKey, lo que activa una evaluación recurrente y paralela de SkyFunctions adicionales. En lugar de bloquear, lo que vincularía un subproceso, cuando un SkyValue solicitado aún no está listo porque algún subgrafo de procesamiento está incompleto, la Skyky que la solicita observa una respuesta null getValue y debería mostrar null en lugar de SkyValue, lo que indica que está incompleto debido a que faltan entradas. Skyframe reinicia SkyFunctions cuando todos los SkyValues solicitados anteriormente están disponibles.

Antes de la introducción de SkyKeyComputeState, la forma tradicional de controlar un reinicio era volver a ejecutar por completo el cálculo. Aunque esto tiene una complejidad cuadrática, las funciones escritas de esta manera finalmente se completan porque cada reejecución, menos búsquedas muestran null. Con SkyKeyComputeState, es posible asociar datos de puntos de control especificados por mano con una SkyFunction, lo que ahorra un cómputo significativo.

Los StateMachine son objetos que se encuentran dentro de SkyKeyComputeState y eliminan de forma virtual todos los cálculos cuando una SkyFunction se reinicia (si suponemos que SkyKeyComputeState no queda fuera de la caché) mediante la exposición de hooks de ejecución y suspensión.

Cálculos con estado dentro de SkyKeyComputeState

Desde el punto de vista del diseño orientado a objetos, tiene sentido considerar el almacenamiento de objetos de computación dentro de SkyKeyComputeState en lugar de valores de datos puros. En Java, la descripción mínima de un comportamiento que contiene un objeto es una interfaz funcional y resulta suficiente. Una StateMachinetiene la siguiente definición, curiosamente recursiva:².

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

La interfaz Tasks es análoga a SkyFunction.Environment, pero está diseñada para la asíncrona y la compatibilidad con subtareas lógicamente simultáneas.³

El valor que se muestra de step es otro StateMachine, lo que permite especificar de forma inductiva una secuencia de pasos. step muestra DONE cuando se completa StateMachine. Por ejemplo:

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;
  }
}

describe un StateMachine con el siguiente resultado.

hello
world

Ten en cuenta que la referencia del método this::step2 también es una StateMachine debido a que step2 satisface la definición de interfaz funcional de StateMachine. Las referencias de métodos son la manera más común de especificar el próximo estado en una StateMachine.

De manera intuitiva, dividir un cálculo en pasos StateMachine, en lugar de una función monolítica, proporciona los hooks necesarios para suspender y reanudar un cálculo. Cuando se muestra StateMachine.step, hay un punto explícito de suspensión. La continuación especificada por el valor StateMachine que se muestra es un punto resumen explícito. Por lo tanto, se puede evitar el procesamiento porque se puede retomar exactamente donde lo dejó.

Devoluciones de llamada, continuaciones y procesamiento asíncrono

En términos técnicos, un StateMachine sirve como una continuación, que determina el cálculo que se ejecutará posteriormente. En lugar de bloquear, un StateMachine puede suspenderse de forma voluntaria si regresa de la función step, que transfiere el control de vuelta a una instancia de Driver. Luego, Driver puede cambiar a un StateMachine listo o ceder el control a Skyframe.

Tradicionalmente, las devoluciones de llamada y las continuaciones se combinan en un solo concepto. Sin embargo, los elementos StateMachine mantienen una distinción entre ambos.

• Devolución de llamada: describe dónde almacenar el resultado de un cálculo asíncrono.
• Continuation (Continuación): Especifica el siguiente estado de ejecución.

Las devoluciones de llamada son necesarias cuando se invoca una operación asíncrona, lo que significa que la operación real no se produce inmediatamente después de llamar al método, como en el caso de una búsqueda de SkyValue. Las devoluciones de llamada deben ser lo más sencillas posible.

Las continuaciones son los valores que se muestran de StateMachine de StateMachine y encapsulan la ejecución compleja que sigue una vez que se resuelven todos los cálculos asíncronos. Este enfoque estructurado ayuda a mantener la complejidad de las devoluciones de llamada.

Tareas

La interfaz Tasks proporciona StateMachines con una API para buscar SkyValues por SkyKey y programar subtareas simultáneas.

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.
}

Búsquedas de SkyValue

Los StateMachine usan sobrecargas de Tasks.lookUp para buscar SkyValues. Son similares a SkyFunction.Environment.getValue y SkyFunction.Environment.getValueOrThrow, y tienen una semántica de control de excepciones similar. La implementación no realiza la búsqueda de inmediato, sino que agrupa en lotes⁴ la mayor cantidad posible de búsquedas antes de hacerlo. Es posible que el valor no esté disponible de inmediato, por ejemplo, que requiera un reinicio de Skyframe, por lo que el llamador especifica qué hacer con el valor resultante mediante una devolución de llamada.

El procesador StateMachine (Drivers y la conexión a SkyFrame) garantizan que el valor esté disponible antes de que comience el próximo estado. A continuación, se muestra un ejemplo.

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;
  }
}

En el ejemplo anterior, el primer paso realiza una búsqueda de new Key() y pasa this como el consumidor. Esto es posible porque DoesLookup implementa Consumer<SkyValue>.

Por contrato, antes de que comience el próximo estado DoesLookup.processValue, se completan todas las búsquedas de DoesLookup.step. Por lo tanto, value está disponible cuando se accede a él en processValue.

Subtareas

Tasks.enqueue solicita la ejecución de subtareas de manera lógica. Las subtareas también son StateMachine y pueden hacer lo mismo que StateMachine, como crear más subtareas o buscar SkyValues. Al igual que lookUp, el controlador de máquina de estado garantiza que todas las subtareas estén completas antes de continuar con el siguiente paso. A continuación, se muestra un ejemplo.

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.
    }
  }
}

Aunque Subtask1 y Subtask2 son lógicamente simultáneos, todo se ejecuta en un solo subproceso, por lo que la actualización "simultánea" de i no necesita ninguna sincronización.

Simultaneidad estructurada

Dado que cada lookUp y enqueue deben resolverse antes de avanzar al siguiente estado, significa que la simultaneidad está limitada de forma natural a las estructuras de árbol. Es posible crear simultaneidad⁵ jerárquica, como se muestra en el siguiente ejemplo.

Es difícil saber a partir del UML que la estructura de simultaneidad forma un árbol. Hay una vista alternativa que muestra mejor la estructura de árbol.

La simultaneidad estructurada es mucho más fácil de razonar.

Patrones de flujo de composición y control

En esta sección, se presentan ejemplos de cómo se pueden componer varios StateMachine y soluciones para ciertos problemas de flujo de control.

Estados secuenciales

Este es el patrón de flujo de control más común y directo. Un ejemplo de esto se muestra en Cálculos con estado dentro de SkyKeyComputeState.

Ramificación

Para obtener estados de ramificación en StateMachine, se muestran diferentes valores con el flujo de control normal de Java, como se muestra en el siguiente ejemplo.

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;
  }
  …
}

Es muy común que algunas ramas muestren DONE, para finalización anticipada.

Composición secuencial avanzada

Como la estructura de control de StateMachine no tiene memoria, compartir las definiciones de StateMachine como subtareas a veces puede ser incómodo. Supongamos que M₁ y M₂ son instancias StateMachine que comparten StateMachine, S, donde M₁ y M₂ son las secuencias <A, S, B> y <X, S, Y> respectivamente. El problema es que S no sabe si continuar con B o Y después de que se completa, y los StateMachine no mantienen una pila de llamadas. En esta sección, se revisan algunas técnicas para lograrlo.

StateMachine como elemento de secuencia de la terminal

Esto no soluciona el problema inicial que se plantea. Solo muestra la composición secuencial cuando el StateMachine compartido es terminal en la secuencia.

// 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();
  }
}

Esto funciona incluso si S es una máquina de estado compleja.

Subtarea para composición secuencial

Dado que se garantiza que las subtareas en cola se completarán antes del próximo estado, a veces es posible hacer un abuso abusivo del⁶ mecanismo de subtareas.

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;
  }
}

Inserción de runAfter

En ocasiones, es abusivo usar Tasks.enqueue porque hay otras subtareas o llamadas a Tasks.lookUp que se deben completar antes de que se ejecute S. En este caso, puedes insertar un parámetro runAfter en S para informar a S qué hacer a continuación.

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;
  }
}

Este enfoque es más sencillo que abusar de las subtareas. Sin embargo, aplicarlo demasiado, por ejemplo, si anidas varios StateMachine con runAfter, es la ruta hacia Callback Hell. En su lugar, es mejor dividir los runAfter secuenciales con estados secuenciales comunes.

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

se puede reemplazar por lo siguiente:

  private StateMachine step1(Tasks tasks) {
     doStep1();
     return new S(/* runAfter= */ this::intermediateStep);
  }

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

Alternativa prohibida: runAfterUnlessError

En un borrador anterior, habíamos considerado un runAfterUnlessError que se anularía temprano en los errores. Esto se vio motivado por el hecho de que los errores a menudo terminan siendo verificados dos veces, una por el StateMachine que tiene una referencia runAfter y otra por la propia máquina runAfter.

Después de un poco de discusión, decidimos que la uniformidad del código es más importante que anular el duplicado de la comprobación de errores. Sería confuso confundir el mecanismo runAfter con el mecanismo tasks.enqueue, que siempre requiere comprobación de errores.

Delegación directa

Cada vez que hay una transición de estado formal, el bucle Driver principal avanza. Según el contrato, el avance de estados significa que todas las búsquedas y subtareas de SkyValue que se pusieron en cola se resuelven antes de que se ejecute el siguiente estado. A veces, la lógica de un delegado StateMachine hace que un avance de fase sea innecesario o contraproducente. Por ejemplo, si el primer step del delegado realiza búsquedas de SkyKey que se pueden paralelizar con búsquedas del estado de delegación, un avance de fase los haría secuenciales. Puede tener más sentido realizar la delegación directa, como se muestra en el siguiente ejemplo.

class Parent implements StateMachine {
  @Override
  public StateMachine step(Tasks tasks ) {
    tasks.lookUp(new Key1(), this);
    // Directly delegates to `Delegate`.
    //
    // The (valid) alternative:
    //   return new Delegate(this::afterDelegation);
    // would cause `Delegate.step` to execute after `step` completes which would
    // cause lookups of `Key1` and `Key2` to be sequential instead of parallel.
    return new Delegate(this::afterDelegation).step(tasks);
  }

  private StateMachine afterDelegation(Tasks tasks) {
    …
  }
}

class Delegate implements StateMachine {
  private final StateMachine runAfter;

  Delegate(StateMachine runAfter) {
    this.runAfter = runAfter;
  }

  @Override
  public StateMachine step(Tasks tasks) {
    tasks.lookUp(new Key2(), this);
    return …;
  }

  // Rest of implementation.
  …

  private StateMachine complete(Tasks tasks) {
    …
    return runAfter;
  }
}

Flujo de datos

El enfoque de la discusión anterior ha sido centrarse en la administración del flujo de control. En esta sección, se describe la propagación de los valores de datos.

Cómo implementar devoluciones de llamada de Tasks.lookUp

Hay un ejemplo de cómo implementar una devolución de llamada Tasks.lookUp en las búsquedas de SkyValue. En esta sección, se proporcionan los motivos y se sugieren enfoques para manejar varios SkyValues.

Tasks.lookUp devoluciones de llamada

El método Tasks.lookUp toma una devolución de llamada, sink, como parámetro.

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

El enfoque idiomático sería usar una lambda de Java para implementar esto:

  tasks.lookUp(key, value -> myValue = (MyValueClass)value);

donde myValue es una variable de miembro de la instancia StateMachine que realiza la búsqueda. Sin embargo, la lambda requiere una asignación de memoria adicional en comparación con la implementación de la interfaz Consumer<SkyValue> en la implementación de StateMachine. La lambda sigue siendo útil cuando hay varias búsquedas que serían ambiguas.

También hay sobrecargas de control de errores de Tasks.lookUp, que son análogas a SkyFunction.Environment.getValueOrThrow.

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

  interface ValueOrExceptionSink<E extends Exception> {
    void acceptValueOrException(@Nullable SkyValue value, @Nullable E exception);
  }

A continuación, se muestra un ejemplo de implementación.

class PerformLookupWithError extends StateMachine, ValueOrExceptionSink<MyException> {
  private MyValue value;
  private MyException error;

  @Override
  public StateMachine step(Tasks tasks) {
    tasks.lookUp(new MyKey(), MyException.class, ValueOrExceptionSink<MyException>) this);
    return this::processResult;
  }

  @Override
  public acceptValueOrException(@Nullable SkyValue value, @Nullable MyException exception) {
    if (value != null) {
      this.value = (MyValue)value;
      return;
    }
    if (exception != null) {
      this.error = exception;
      return;
    }
    throw new IllegalArgumentException("Both parameters were unexpectedly null.");
  }

  private StateMachine processResult(Tasks tasks) {
    if (exception != null) {
      // Handles the error.
      …
      return DONE;
    }
    // Processes `value`, which is non-null.
    …
  }
}

Al igual que con las búsquedas sin manejo de errores, que la clase StateMachine implemente directamente la devolución de llamada guarda una asignación de memoria para la lamba.

El manejo de errores proporciona un poco más de detalle, pero, en esencia, no hay mucha diferencia entre la propagación de errores y los valores normales.

Consuma varios SkyValues

A menudo, se requieren varias búsquedas de SkyValue. Un enfoque que funciona la mayor parte del tiempo es activar el tipo de SkyValue. El siguiente es un ejemplo que se simplificó a partir del código de producción del prototipo.

  @Nullable
  private StateMachine fetchConfigurationAndPackage(Tasks tasks) {
    var configurationKey = configuredTarget.getConfigurationKey();
    if (configurationKey != null) {
      tasks.lookUp(configurationKey, (Consumer<SkyValue>) this);
    }

    var packageId = configuredTarget.getLabel().getPackageIdentifier();
    tasks.lookUp(PackageValue.key(packageId), (Consumer<SkyValue>) this);

    return this::constructResult;
  }

  @Override  // Implementation of `Consumer<SkyValue>`.
  public void accept(SkyValue value) {
    if (value instanceof BuildConfigurationValue) {
      this.configurationValue = (BuildConfigurationValue) value;
      return;
    }
    if (value instanceof PackageValue) {
      this.pkg = ((PackageValue) value).getPackage();
      return;
    }
    throw new IllegalArgumentException("unexpected value: " + value);
  }

La implementación de devolución de llamada Consumer<SkyValue> se puede compartir inequívocamente porque los tipos de valores son diferentes. Cuando no sea el caso, podrás recurrir a las implementaciones basadas en lambda o a las instancias de clase interna completas que implementan las devoluciones de llamada adecuadas.

Propagar valores entre StateMachine

Hasta ahora, en este documento, solo se explica cómo organizar el trabajo en una subtarea, pero las subtareas también deben informar un valor al emisor. Como las subtareas son lógicamente asíncronas, sus resultados se comunican al emisor con una devolución de llamada. Para que esto funcione, la subtarea define una interfaz de receptor que se incorpora mediante su constructor.

class BarProducer implements StateMachine {
  // Callers of BarProducer implement the following interface to accept its
  // results. Exactly one of the two methods will be called by the time
  // BarProducer completes.
  interface ResultSink {
    void acceptBarValue(Bar value);
    void acceptBarError(BarException exception);
  }

  private final ResultSink sink;

  BarProducer(ResultSink sink) {
     this.sink = sink;
  }

  … // StateMachine steps that end with this::complete.

  private StateMachine complete(Tasks tasks) {
    if (hasError()) {
      sink.acceptBarError(getError());
      return DONE;
    }
    sink.acceptBarValue(getValue());
    return DONE;
  }
}

Un llamador StateMachine se verá de la siguiente manera.

class Caller implements StateMachine, BarProducer.ResultSink {
  interface ResultSink {
    void acceptCallerValue(Bar value);
    void acceptCallerError(BarException error);
  }

  private final ResultSink sink;

  private Bar value;

  Caller(ResultSink sink) {
    this.sink = sink;
  }

  @Override
  @Nullable
  public StateMachine step(Tasks tasks) {
    tasks.enqueue(new BarProducer((BarProducer.ResultSink) this));
    return this::processResult;
  }

  @Override
  public void acceptBarValue(Bar value) {
    this.value = value;
  }

  @Override
  public void acceptBarError(BarException error) {
    sink.acceptCallerError(error);
  }

  private StateMachine processResult(Tasks tasks) {
    // Since all enqueued subtasks resolve before `processResult` starts, one of
    // the `BarResultSink` callbacks must have been called by this point.
    if (value == null) {
      return DONE;  // There was a previously reported error.
    }
    var finalResult = computeResult(value);
    sink.acceptCallerValue(finalResult);
    return DONE;
  }
}

En el ejemplo anterior, se demuestran algunos aspectos. Caller debe propagar sus resultados y definir su propio Caller.ResultSink. Caller implementa las devoluciones de llamada BarProducer.ResultSink. Después de la reanudación, processResult verifica si value es nulo para determinar si se produjo un error. Este es un patrón de comportamiento común después de aceptar los resultados de una subtarea o una búsqueda de SkyValue.

Ten en cuenta que la implementación de acceptBarError reenvía el resultado con anticipación a Caller.ResultSink, según lo requiera la burbuja de errores.

Las alternativas para los StateMachine de nivel superior se describen en Driver y se vinculan a SkyFunctions.

Manejo de errores

Ya hay algunos ejemplos de manejo de errores en las devoluciones de llamada de Tasks.lookUp y la propagación de valores entre StateMachines. No se muestran excepciones, excepto InterruptedException, sino que se pasan por valores como valores de las devoluciones de llamada. Estas devoluciones de llamada suelen tener una semántica exclusiva o exclusiva, y se pasa exactamente un valor o error.

En la siguiente sección, se describe una interacción sutil, pero importante, con el manejo de errores de Skyframe.

Error al burbujear (--nokeep_going)

Durante la burbuja de error, una SkyFunction puede reiniciarse incluso si no están disponibles todos los SkyValues solicitados. En esos casos, nunca se alcanzará el estado posterior debido al contrato de la API Tasks. Sin embargo, StateMachine aún debe propagar la excepción.

Dado que la propagación debe ocurrir independientemente de si se alcanza el siguiente estado, la devolución de llamada de control de errores debe realizar esta tarea. Para un StateMachine interno, esto se logra invocando la devolución de llamada superior.

En el StateMachine de nivel superior, que interactúa con SkyFunction, esto se puede hacer llamando al método setException de ValueOrExceptionProducer. Luego, ValueOrExceptionProducer.tryProduceValue arrojará la excepción, incluso si faltan SkyValues.

Si se usa un Driver directamente, es esencial verificar si hay errores propagados desde SkyFunction, incluso si la máquina no terminó de procesarse.

Manejo de eventos

Para SkyFunctions que necesiten emitir eventos, se insertará una StoredEventHandler en SkyKeyComputeState y, luego, se insertará en StateMachine que las requieren. Históricamente, se necesitaba StoredEventHandler porque Skyframe descartaba ciertos eventos, a menos que se volvieran a reproducir, pero esto se corrigió posteriormente. La inyección de StoredEventHandler se conserva porque simplifica la implementación de eventos emitidos desde devoluciones de llamada de control de errores.

Driver y cómo conectar SkyFunctions

Un Driver es responsable de administrar la ejecución de StateMachine, y comienza con un StateMachine raíz especificado. Como los elementos StateMachine pueden poner en cola las subtareas StateMachine de forma recurrente, un solo Driver puede administrar varias subtareas. Estas subtareas crean una estructura de árbol, un resultado de simultaneidad estructurada. Driver agrupa en lotes las búsquedas de SkyValue en subtareas para mejorar la eficiencia.

Hay varias clases creadas en torno al Driver con la siguiente API.

public final class Driver {
  public Driver(StateMachine root);
  public boolean drive(SkyFunction.Environment env) throws InterruptedException;
}

Driver toma una única raíz StateMachine como parámetro. Llamar a Driver.drive ejecuta el elemento StateMachine en cuanto puede llegar sin un reinicio de Skyframe. El resultado es verdadero cuando StateMachine se completa y, de lo contrario, es falso, lo que indica que no todos los valores estaban disponibles.

Driver mantiene el estado simultáneo de StateMachine y es adecuado para incorporarlo en SkyKeyComputeState.

Creando una instancia directa de Driver

Las implementaciones de StateMachine comunican sus resultados de forma convencional a través de devoluciones de llamada. Es posible crear una instancia directa de Driver, como se muestra en el siguiente ejemplo.

Driver está incorporado en la implementación de SkyKeyComputeState junto con una implementación del ResultSink correspondiente que se definirá un poco más abajo. En el nivel superior, el objeto State es un receptor adecuado para el resultado del cálculo, ya que se garantiza que durará más que Driver.

class State implements SkyKeyComputeState, ResultProducer.ResultSink {
  // The `Driver` instance, containing the full tree of all `StateMachine`
  // states. Responsible for calling `StateMachine.step` implementations when
  // asynchronous values are available and performing batched SkyFrame lookups.
  //
  // Non-null while `result` is being computed.
  private Driver resultProducer;

  // Variable for storing the result of the `StateMachine`
  //
  // Will be non-null after the computation completes.
  //
  private ResultType result;

  // Implements `ResultProducer.ResultSink`.
  //
  // `ResultProducer` propagates its final value through a callback that is
  // implemented here.
  @Override
  public void acceptResult(ResultType result) {
    this.result = result;
  }
}

En el siguiente código, se esboza el ResultProducer.

class ResultProducer implements StateMachine {
  interface ResultSink {
    void acceptResult(ResultType value);
  }

  private final Parameters parameters;
  private final ResultSink sink;

  … // Other internal state.

  ResultProducer(Parameters parameters, ResultSink sink) {
    this.parameters = parameters;
    this.sink = sink;
  }

  @Override
  public StateMachine step(Tasks tasks) {
    …  // Implementation.
    return this::complete;
  }

  private StateMachine complete(Tasks tasks) {
    sink.acceptResult(getResult());
    return DONE;
  }
}

Luego, el código para calcular de manera diferida el resultado podría verse de la siguiente manera.

@Nullable
private Result computeResult(State state, Skyfunction.Environment env)
    throws InterruptedException {
  if (state.result != null) {
    return state.result;
  }
  if (state.resultProducer == null) {
    state.resultProducer = new Driver(new ResultProducer(
      new Parameters(), (ResultProducer.ResultSink)state));
  }
  if (state.resultProducer.drive(env)) {
    // Clears the `Driver` instance as it is no longer needed.
    state.resultProducer = null;
  }
  return state.result;
}

Incorporando Driver

Si el StateMachine produce un valor y no genera excepciones, la incorporación de Driver es otra implementación posible, como se muestra en el siguiente ejemplo.

class ResultProducer implements StateMachine {
  private final Parameters parameters;
  private final Driver driver;

  private ResultType result;

  ResultProducer(Parameters parameters) {
    this.parameters = parameters;
    this.driver = new Driver(this);
  }

  @Nullable  // Null when a Skyframe restart is needed.
  public ResultType tryProduceValue( SkyFunction.Environment env)
      throws InterruptedException {
    if (!driver.drive(env)) {
      return null;
    }
    return result;
  }

  @Override
  public StateMachine step(Tasks tasks) {
    …  // Implementation.
}

La CloudFunction puede tener un código similar al siguiente (donde State es el tipo específico de la función de SkyKeyComputeState).

@Nullable  // Null when a Skyframe restart is needed.
Result computeResult(SkyFunction.Environment env, State state)
    throws InterruptedException {
  if (state.result != null) {
    return state.result;
  }
  if (state.resultProducer == null) {
    state.resultProducer = new ResultProducer(new Parameters());
  }
  var result = state.resultProducer.tryProduceValue(env);
  if (result == null) {
    return null;
  }
  state.resultProducer = null;
  return state.result = result;
}

La incorporación de Driver en la implementación de StateMachine es más adecuada para el estilo de codificación síncrona de Skyframe.

StateMachines que pueden producir excepciones

De lo contrario, hay clases SkyKeyComputeState-incorporables ValueOrExceptionProducer y ValueOrException2Producer que tienen API síncronas que coinciden con el código síncrono de SkyFunction.

La clase abstracta ValueOrExceptionProducer incluye los siguientes métodos.

public abstract class ValueOrExceptionProducer<V, E extends Exception>
    implements StateMachine {
  @Nullable
  public final V tryProduceValue(Environment env)
      throws InterruptedException, E {
    …  // Implementation.
  }

  protected final void setValue(V value)  {  … // Implementation. }
  protected final void setException(E exception) {  … // Implementation. }
}

Incluye una instancia de Driver incorporada y se parece mucho a la clase ResultProducer en el controlador de incorporación; además, interactúa con SkyFunction de manera similar. En lugar de definir un ResultSink, las implementaciones llaman a setValue o setException cuando se produce cualquiera de esas situaciones. Cuando se producen ambos, la prioridad tiene prioridad. El método tryProduceValue une el código de devolución de llamada asíncrono al código síncrono y arroja una excepción cuando se establece uno.

Como se señaló antes, durante la generación de errores, es posible que se produzca un error incluso si la máquina aún no se completó porque no todas las entradas están disponibles. Para adaptarse a esto, tryProduceValue arroja cualquier excepción establecida, incluso antes de que la máquina esté lista.

Epílogo: Eliminación eventual de devoluciones de llamada

Las StateMachine son una forma muy eficiente, pero estándar intensiva para realizar cálculos asíncronos. Las continuaciones (particularmente en la forma de Runnable que se pasan a ListenableFuture) son generalizadas en ciertas partes del código de Bazel, pero no prevalecen en el análisis de SkyFunctions. El análisis está ligado principalmente a la CPU y no hay API asíncronas eficientes para la E/S del disco. Con el tiempo, sería bueno optimizar las devoluciones de llamada, ya que tienen una curva de aprendizaje y dificultan la legibilidad.

Una de las alternativas más prometedoras son los subprocesos virtuales de Java. En lugar de tener que escribir devoluciones de llamada, se reemplaza todo por llamadas de bloqueo síncronas. Esto es posible porque vincular un recurso de subproceso virtual es un recurso económico, a diferencia de un subproceso de la plataforma. Sin embargo, incluso con los subprocesos virtuales, reemplazar operaciones síncronas simples por las primitivas de creación y sincronización de subprocesos es demasiado costoso. Realizamos una migración de subprocesos virtuales de StateMachine a Java y su orden de magnitud era más lento, lo que generó casi un triple de latencia de análisis de extremo a extremo. Debido a que los subprocesos virtuales aún son una función de vista previa, es posible que esta migración se pueda realizar más adelante, cuando mejore el rendimiento.

Otro enfoque que debes considerar es esperar las corrutinas de Loom, si alguna vez están disponibles. La ventaja es que es posible reducir la sobrecarga de sincronización mediante el uso de varias tareas cooperativas.

Si todo lo demás falla, la reescritura de código de bytes de bajo nivel también podría ser una alternativa viable. Con una optimización suficiente, es posible lograr un rendimiento que se acerque al código de devolución de llamada escrito a mano.

Apéndice

Demonio de la devolución de llamada

El infierno de devolución de llamada es un problema infame en el código asíncrono que usa devoluciones de llamada. Se debe a que la continuación de un paso siguiente se anida en el paso anterior. Si hay muchos pasos, este anidado puede ser muy profundo. Si se combina con el flujo de control, el código deja de ser manejable.

class CallbackHell implements StateMachine {
  @Override
  public StateMachine step(Tasks task) {
    doA();
    return (t, l) -> {
      doB();
      return (t1, l2) -> {
        doC();
        return DONE;
      };
    };
  }
}

Una de las ventajas de las implementaciones anidadas es que se puede conservar el marco de pila del paso externo. En Java, las variables lambda capturadas deben ser definitivas, por lo que usar esas variables puede ser engorroso. Para evitar el anidamiento, se muestran referencias de métodos como continuas en lugar de lambdas, como se muestra a continuación.

class CallbackHellAvoided implements StateMachine {
  @Override
  public StateMachine step(Tasks task) {
    doA();
    return this::step2;
  }

  private StateMachine step2(Tasks tasks) {
    doB();
    return this::step3;
  }

  private StateMachine step3(Tasks tasks) {
    doC();
    return DONE;
  }
}

El infierno de devolución de llamada también puede ocurrir si el patrón inyección runAfter se usa de manera demasiado densa, pero se puede evitar mediante la intercalación de inyecciones con pasos secuenciales.

Ejemplo: Búsquedas de SkyValue encadenadas

A menudo, la lógica de la aplicación requiere cadenas dependientes de las búsquedas de SkyValue, por ejemplo, si una segunda SkyKey depende del primer SkyValue. Si se piensa de manera simple, esto dará como resultado una estructura de devolución de llamada compleja y profundamente anidada.

private ValueType1 value1;
private ValueType2 value2;

private StateMachine step1(...) {
  tasks.lookUp(key1, (Consumer<SkyValue>) this);  // key1 has type KeyType1.
  return this::step2;
}

@Override
public void accept(SkyValue value) {
  this.value1 = (ValueType1) value;
}

private StateMachine step2(...) {
  KeyType2 key2 = computeKey(value1);
  tasks.lookup(key2, this::acceptValueType2);
  return this::step3;
}

private void acceptValueType2(SkyValue value) {
  this.value2 = (ValueType2) value;
}

Sin embargo, como las continuaciones se especifican como referencias de métodos, el código parece ser de procedimiento en todas las transiciones de estado: step2 sigue step1. Ten en cuenta que aquí se usa una lambda para asignar value2. Esto hace que el orden del código coincida con el orden del cálculo de arriba abajo.

Sugerencias varias

Legibilidad: Orden de ejecución

Para mejorar la legibilidad, intenta mantener las implementaciones StateMachine.step en el orden de ejecución y las implementaciones de devolución de llamada inmediatamente después de que se pasen en el código. Esto no siempre es posible cuando el flujo de control se ramifica. Los comentarios adicionales pueden ser útiles en esos casos.

En Ejemplo: Búsquedas de SkyValue encadenadas, se crea una referencia de método intermedia para lograrlo. Esto cambia un poco el rendimiento por la legibilidad, lo que probablemente valga la pena aquí.

Hipótesis generacional

Los objetos Java de corta duración rompen la hipótesis generacional del recolector de elementos no utilizados de Java, que está diseñado para controlar los objetos que permanecen por un tiempo muy corto o los que viven para siempre. Por definición, los objetos de SkyKeyComputeState infringen esta hipótesis. Estos objetos, que contienen el árbol construido de todos los StateMachine en ejecución, con permisos de administrador en Driver, tienen una vida útil intermedia cuando se suspenden, a la espera de que se completen los cálculos asíncronos.

Parece menos deficiente en JDK19, pero, cuando se usan StateMachine, a veces es posible observar un aumento en el tiempo de recolección de elementos no utilizados, incluso con drásticas disminuciones en la recolección de elementos no utilizados reales. Dado que las StateMachine tienen una vida útil intermedia, podrían ascenderse a la generación anterior, lo que haría que se llenen más rápido, por lo que se necesitarán recolecciones más importantes o completas de mayor costo.

La precaución inicial es minimizar el uso de variables StateMachine, pero no siempre es posible, por ejemplo, si se necesita un valor en varios estados. Cuando es posible, las variables step de pila local son variables de generación joven y se recogen de manera eficiente mediante GC.

Para las variables StateMachine, puede ser útil desglosar las tareas en subtareas y seguir el patrón recomendado en Propagar valores entre StateMachines. Ten en cuenta que, cuando sigues el patrón, solo los elementos secundarios StateMachines tienen referencias a elementos superiores StateMachine y no al revés. Esto significa que, a medida que los elementos secundarios completan y actualizan los elementos superiores mediante devoluciones de llamada de resultados, estos quedan naturalmente fuera del alcance y son aptos para la recolección de elementos no utilizados.

Por último, en algunos casos, se necesita una variable StateMachine en estados anteriores, pero no en estados posteriores. Puede ser beneficioso anular las referencias de objetos grandes una vez que se sepa que ya no son necesarias.

Estados de nombres

Cuando nombras un método, por lo general, es posible nombrar un método para el comportamiento que ocurre dentro de ese método. Es menos claro cómo hacerlo en los StateMachine porque no hay pila. Por ejemplo, supongamos que el método foo llama a un submétodo bar. En un StateMachine, esto se puede traducir a la secuencia de estado foo, seguida de bar. foo ya no incluye el comportamiento bar. Como resultado, los nombres de los métodos para los estados suelen tener un alcance más limitado, lo que podría reflejar un comportamiento local.

Diagrama de árbol de simultaneidad

La siguiente es una vista alternativa del diagrama en Simultaneidad estructurada, que describe mejor la estructura de árbol. Los bloques forman un pequeño árbol.