Una guía para Skyframe StateMachines

Descripción general

Un StateMachine de Skyframe es un objeto-función deconstruido que reside en el montón. Admite la evaluación y la flexibilidad sin redundancia¹ cuando los valores requeridos no están disponibles de inmediato, sino que se calculan de forma asíncrona. El StateMachine no puede ocupar un recurso de subproceso mientras espera, sino que debe suspenderse y reanudarse. De esta manera, se exponen puntos de reingreso explícitos para que se puedan omitir los cálculos previos.

Los StateMachines se pueden usar para expresar secuencias, ramificaciones y simultaneidad lógica estructurada, y se adaptan específicamente para la interacción con Skyframe. Los StateMachines se pueden componer en StateMachines más grandes y compartir sub-StateMachines. La simultaneidad siempre es jerárquica por construcción y puramente lógica. Cada subtarea simultánea se ejecuta en el único subproceso compartido de SkyFunction principal.

Introducción

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

Breve introducción a los reinicios de Skyframe

Skyframe es un framework que realiza la evaluación paralela de los grafos de dependencias. Cada nodo del gráfico corresponde a la evaluación de una SkyFunction con una SkyKey que especifica sus parámetros y una SkyValue que especifica su resultado. El modelo computacional es tal que una SkyFunction puede buscar SkyValues por SkyKey, lo que activa la evaluación recursiva y paralela de SkyFunctions adicionales. En lugar de bloquear, lo que inmovilizaría un subproceso, cuando un SkyValue solicitado aún no está listo porque algún subgrafo de procesamiento está incompleto, la SkyFunction solicitante observa una respuesta null getValue y debe devolver null en lugar de un SkyValue, lo que indica que está incompleto debido a la falta de entradas. Skyframe reinicia las 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 el cálculo por completo. Si bien esto tiene una complejidad cuadrática, las funciones escritas de esta manera se completan con el tiempo porque, en cada nueva ejecución, menos búsquedas devuelven null. Con SkyKeyComputeState, es posible asociar datos de puntos de control especificados manualmente con una SkyFunction, lo que ahorra una gran cantidad de recompilación.

Los StateMachine son objetos que residen dentro de SkyKeyComputeState y eliminan prácticamente todos los recálculos cuando se reinicia una SkyFunction (suponiendo que SkyKeyComputeState no se quite de la caché) exponiendo hooks de ejecución de suspensión y reanudació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 computacionales dentro de SkyKeyComputeState en lugar de valores de datos puros. En Java, la descripción mínima de un objeto que lleva un comportamiento es una interfaz funcional, y resulta ser suficiente. Un StateMachine tiene la siguiente definición recursiva curiosa².

@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 asincronía y agrega compatibilidad con subtareas lógicamente simultáneas³.

El valor de retorno de step es otro StateMachine, lo que permite especificar una secuencia de pasos de forma inductiva. step devuelve 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 un StateMachine porque step2 satisface la definición de la interfaz funcional de StateMachine. Las referencias a métodos son la forma más común de especificar el siguiente estado en un StateMachine.

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

Devoluciones de llamada, continuaciones y procesamiento asíncrono

En términos técnicos, un StateMachine sirve como una continuación, ya que determina el cálculo posterior que se ejecutará. En lugar de bloquearse, una StateMachine puede suspenderse voluntariamente devolviendo la función step, que transfiere el control a una instancia de Driver. Luego, el 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 StateMachines mantienen una distinción entre ambos.

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

Se requieren devoluciones de llamada 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 simples posible.

Las continuaciones son los valores de retorno de StateMachine de los StateMachines 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 bajo control.

Tasks

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 StateMachines usan sobrecargas de Tasks.lookUp para buscar SkyValues. Son análogos a SkyFunction.Environment.getValue y SkyFunction.Environment.getValueOrThrow, y tienen una semántica similar de control de excepciones. La implementación no realiza la búsqueda de inmediato, sino que, en cambio, agrupa⁴ tantas búsquedas como sea posible antes de hacerlo. Es posible que el valor no esté disponible de inmediato, por ejemplo, si se requiere un reinicio de Skyframe, por lo que el llamador especifica qué hacer con el valor resultante a través de una devolución de llamada.

El procesador StateMachine (Drivers y puente a SkyFrame) garantiza que el valor esté disponible antes de que comience el siguiente 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 consumidor. Esto es posible porque DoesLookup implementa Consumer<SkyValue>.

Según el contrato, antes de que comience el siguiente 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 lógicamente simultáneas. Las subtareas también son StateMachines y pueden hacer todo lo que hacen los StateMachines normales, lo que incluye crear más subtareas de forma recursiva o buscar SkyValues. Al igual que lookUp, el controlador de la máquina de estados garantiza que todas las subtareas se completen 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.
    }
  }
}

Si bien 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 sincronización.

Simultaneidad estructurada

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

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

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

Patrones de composición y flujo de control

En esta sección, se presentan ejemplos de cómo se pueden componer varios StateMachines 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 sencillo. En Cálculos con estado dentro de SkyKeyComputeState, se muestra un ejemplo de esto.

Ramificación

Los estados de bifurcación en StateMachines se pueden lograr devolviendo diferentes valores con el flujo de control Java normal, 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 ciertas ramas devuelvan DONE para una finalización anticipada.

Composición secuencial avanzada

Dado que la estructura de control StateMachine no tiene memoria, compartir definiciones de StateMachine como subtareas a veces puede ser incómodo. Sean M₁ y M₂ dos instancias de StateMachine que comparten un StateMachine, S, con M₁ y M₂ como 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 terminal

Esto no resuelve el problema inicial planteado. Solo demuestra 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 en sí misma una máquina de estados compleja.

Subtarea para la composición secuencial

Dado que se garantiza que las subtareas en cola se completarán antes del siguiente estado, a veces es posible abusar un poco⁶ 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;
  }
}

Inyección de runAfter

A veces, abusar de Tasks.enqueue es imposible porque hay otras subtareas paralelas o llamadas a Tasks.lookUp que deben completarse antes de que se ejecute S. En este caso, se puede insertar un parámetro runAfter en S para informarle a S qué debe 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 limpio que abusar de las subtareas. Sin embargo, aplicar esto con demasiada libertad, por ejemplo, anidando varios StateMachine con runAfter, es el camino al Callback Hell. En cambio, es mejor dividir las runAfters 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 abortaría los errores de forma anticipada. Esto se debió al hecho de que, a menudo, los errores terminan verificándose dos veces: una vez por el StateMachine que tiene una referencia runAfter y otra vez por la propia máquina runAfter.

Después de deliberar, decidimos que la uniformidad del código es más importante que la deduplicación de la verificación de errores. Sería confuso si el mecanismo runAfter no funcionara de manera coherente con el mecanismo tasks.enqueue, que siempre requiere una verificación de errores.

Delegación directa

Cada vez que hay una transición de estado formal, avanza el bucle Driver principal. Según el contrato, el avance de estados significa que todas las búsquedas y subtareas de SkyValue 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 podrían paralelizarse con las búsquedas del estado de delegación, un avance de fase las haría secuenciales. Podría 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 se centró en la administración del flujo de control. En esta sección, se describe la propagación de los valores de datos.

Implementa devoluciones de llamada de Tasks.lookUp

En Búsquedas de SkyValue, se incluye un ejemplo de implementación de una devolución de llamada de Tasks.lookUp. En esta sección, se proporciona una explicación y se sugieren enfoques para controlar varios SkyValues.

Devoluciones de llamada de Tasks.lookUp

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 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 expresión lambda sigue siendo útil cuando hay varias búsquedas que serían ambiguas.

También hay sobrecargas de manejo 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 control de errores, hacer que la clase StateMachine implemente directamente la devolución de llamada ahorra una asignación de memoria para la lambda.

El control de errores proporciona un poco más de detalles, pero, básicamente, no hay mucha diferencia entre la propagación de errores y los valores normales.

Cómo consumir 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 la devolución de llamada Consumer<SkyValue> se puede compartir de forma inequívoca porque los tipos de valores son diferentes. Cuando no es así, es viable recurrir a implementaciones basadas en lambda o instancias completas de clases internas que implementen las devoluciones de llamada adecuadas.

Propagación de valores entre StateMachines

Hasta ahora, este documento solo explicó cómo organizar el trabajo en una subtarea, pero las subtareas también deben informar valores al llamador. Dado que las subtareas son lógicamente asíncronas, sus resultados se comunican al llamador a través de una devolución de llamada. Para que esto funcione, la subtarea define una interfaz de receptor que se inyecta a través de 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ía 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 muestran algunos aspectos. Caller debe propagar sus resultados y definir su propio Caller.ResultSink. Caller implementa las devoluciones de llamada de BarProducer.ResultSink. Cuando se reanuda, 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 la salida de una subtarea o una búsqueda de SkyValue.

Ten en cuenta que la implementación de acceptBarError reenvía el resultado de forma anticipada al Caller.ResultSink, según lo requiere el Error bubbling.

Las alternativas para los StateMachine de nivel superior se describen en Drivers y en la vinculación a SkyFunctions.

Manejo de errores

Ya hay algunos ejemplos de control de errores en las devoluciones de llamada de Tasks.lookUp y en la propagación de valores entre StateMachines. No se arrojan excepciones, aparte de InterruptedException, sino que se pasan a través de devoluciones de llamada como valores. Estas devoluciones de llamada suelen tener semántica de OR exclusiva, con exactamente un valor o un error que se pasa.

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

Propagación de errores (--nokeep_going)

Durante la propagación de errores, es posible que se reinicie una SkyFunction 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 de Tasks. Sin embargo, StateMachine 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. En el caso de un StateMachine interno, esto se logra invocando la devolución de llamada principal.

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 utiliza un Driver directamente, es fundamental verificar si hay errores propagados desde SkyFunction, incluso si la máquina no terminó de procesar.

Control de eventos

Para las SkyFunctions que necesitan emitir eventos, se inyecta un StoredEventHandler en SkyKeyComputeState y, luego, se inyecta en los StateMachines que los requieren. Históricamente, se necesitaba el StoredEventHandler debido a que Skyframe descartaba ciertos eventos, a menos que se reprodujeran, pero esto se corrigió posteriormente. Se conserva la inyección de StoredEventHandler porque simplifica la implementación de eventos emitidos desde devoluciones de llamada de control de errores.

Drivers y vinculación a SkyFunctions

Un Driver es responsable de administrar la ejecución de StateMachines, comenzando con un StateMachine raíz especificado. Como los StateMachines pueden poner en cola de forma recursiva los StateMachines de subtareas, un solo Driver puede administrar numerosas subtareas. Estas subtareas crean una estructura de árbol, resultado de la simultaneidad estructurada. Driver procesa por lotes las búsquedas de SkyValue en las subtareas para mejorar la eficiencia.

Hay varias clases compiladas en torno a Driver, con la siguiente API.

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

Driver toma un solo StateMachine raíz como parámetro. La llamada a Driver.drive ejecuta StateMachine hasta donde puede llegar sin un reinicio de Skyframe. Devuelve verdadero cuando se completa StateMachine y falso en caso contrario, lo que indica que no todos los valores estaban disponibles.

Driver mantiene el estado simultáneo de StateMachine y es adecuado para la incorporación en SkyKeyComputeState.

Creación de instancias de Driver directamente

Las implementaciones de StateMachine suelen comunicar sus resultados a través de devoluciones de llamada. Es posible crear una instancia de Driver directamente, como se muestra en el siguiente ejemplo.

El Driver se incorpora en la implementación de SkyKeyComputeState junto con una implementación del ResultSink correspondiente que se definirá un poco más adelante. En el nivel superior, el objeto State es un receptor adecuado para el resultado del cálculo, ya que se garantiza que sobrevivirá a 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;
  }
}

El siguiente código describe 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;
  }
}

Entonces, el código para calcular el resultado de forma diferida 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;
}

Incorporación Driver

Si StateMachine produce un valor y no genera excepciones, incorporar Driver es otra posible implementación, 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 SkyFunction puede tener código similar al siguiente (en el que State es el tipo específico de 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;
}

Incorporar Driver en la implementación de StateMachine se adapta mejor al estilo de codificación síncrona de Skyframe.

Máquinas de estado que pueden producir excepciones

De lo contrario, hay clases SkyKeyComputeState insertables ValueOrExceptionProducer y ValueOrException2Producer que tienen APIs síncronas para que coincidan 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 integrada y se parece mucho a la clase ResultProducer en Embedding driver y se comunica con SkyFunction de manera similar. En lugar de definir un ResultSink, las implementaciones llaman a setValue o setException cuando ocurre cualquiera de esos eventos. Cuando ocurren ambos, la excepción tiene prioridad. El método tryProduceValue conecta el código de devolución de llamada asíncrono con el código síncrono y arroja una excepción cuando se establece una.

Como se mencionó anteriormente, durante la propagación de errores, es posible que se produzca un error incluso si la máquina aún no terminó, ya que no todos los datos de entrada están disponibles. Para adaptarse a esto, tryProduceValue arroja cualquier excepción establecida, incluso antes de que la máquina termine.

Epílogo: Cómo quitar las devoluciones de llamada con el tiempo

Los StateMachine son una forma muy eficiente, pero con mucha repetición, de realizar cálculos asíncronos. Las continuaciones (en particular, en forma de Runnables que se pasan a ListenableFuture) son comunes en ciertas partes del código de Bazel, pero no son frecuentes en las SkyFunctions de análisis. El análisis se limita principalmente a la CPU, y no hay APIs 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, todo se reemplaza por llamadas síncronas de bloqueo. Esto es posible porque vincular un recurso de subproceso virtual, a diferencia de un subproceso de plataforma, debería ser económico. Sin embargo, incluso con los subprocesos virtuales, reemplazar las operaciones síncronas simples por primitivas de creación y sincronización de subprocesos es demasiado costoso. Realizamos una migración de StateMachine a subprocesos virtuales de Java, y estos fueron órdenes de magnitud más lentos, lo que provocó un aumento de casi 3 veces en la latencia del análisis de extremo a extremo. Dado que los subprocesos virtuales aún son una función en versión preliminar, es posible que esta migración se realice en una fecha posterior cuando mejore el rendimiento.

Otro enfoque que se puede considerar es esperar las corrutinas de Loom, si alguna vez están disponibles. La ventaja aquí es que podría ser posible reducir la sobrecarga de sincronización con la realización de varias tareas a la vez de forma cooperativa.

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

Apéndice

Infierno de devoluciones de llamada

El infierno de las devoluciones de llamada es un problema infame en el código asíncrono que usa devoluciones de llamada. Esto se debe a que la continuación de un paso posterior está anidada dentro del paso anterior. Si hay muchos pasos, este anidamiento puede ser extremadamente profundo. Si se combina con el flujo de control, el código se vuelve inmanejable.

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 efectivamente finales, por lo que usar esas variables puede ser engorroso. Para evitar el anidamiento profundo, se devuelven referencias de métodos como continuaciones 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 las devoluciones de llamada también puede ocurrir si el patrón de inyección de runAfter se usa con demasiada densidad, pero esto se puede evitar intercalando inyecciones con pasos secuenciales.

Ejemplo: Búsquedas encadenadas de SkyValue

A menudo, la lógica de la aplicación requiere cadenas dependientes de búsquedas de SkyValue, por ejemplo, si una segunda SkyKey depende de la primera SkyValue. Si pensamos en esto de forma ingenua, se generaría 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, dado que las continuaciones se especifican como referencias de métodos, el código parece procedural en las transiciones de estado: step2 sigue a step1. Ten en cuenta que, aquí, se usa una expresión 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, procura mantener las implementaciones de StateMachine.step en orden de ejecución y las implementaciones de devolución de llamada inmediatamente después de donde se pasan en el código. Esto no siempre es posible cuando el flujo de control se bifurca. Los comentarios adicionales pueden ser útiles en estos casos.

En Ejemplo: Búsquedas encadenadas de SkyValue, se crea una referencia de método intermedia para lograr esto. Esto sacrifica una pequeña cantidad de rendimiento en pos de la legibilidad, lo que probablemente valga la pena en este caso.

Hipótesis generacional

Los objetos Java de vida media incumplen la hipótesis generacional del recolector de basura de Java, que está diseñado para controlar objetos que existen durante un período muy corto o de forma permanente. Por definición, los objetos en SkyKeyComputeState incumplen esta hipótesis. Estos objetos, que contienen el árbol construido de todos los StateMachine que aún se están ejecutando, con raíz en Driver, tienen una vida útil intermedia, ya que se suspenden mientras esperan que se completen los cálculos asíncronos.

Parece menos grave en JDK19, pero cuando se usan StateMachines, a veces es posible observar un aumento en el tiempo de GC, incluso con disminuciones drásticas en la basura real generada. Dado que los objetos StateMachine tienen una vida útil intermedia, se podrían promover a la generación anterior, lo que haría que se llenara más rápido y, por lo tanto, requeriría GC principales o completas más costosas para limpiar.

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

Para las variables StateMachine, también es útil dividir las tareas en subtareas y seguir el patrón recomendado para propagar valores entre StateMachines. Observa que, cuando se sigue el patrón, solo los StateMachine secundarios tienen referencias a los StateMachine principales, y no al revés. Esto significa que, a medida que los elementos secundarios completan y actualizan los elementos principales con devoluciones de llamada de resultados, los elementos secundarios quedan naturalmente fuera del alcance y se vuelven aptos para la recolección de basura.

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 sabe que ya no son necesarios.

Estados de nombres

Cuando se nombra un método, suele ser posible nombrarlo según el comportamiento que se produce dentro de él. No es tan claro cómo hacerlo en StateMachines porque no hay una pila. Por ejemplo, supongamos que el método foo llama a un submétodo bar. En un StateMachine, esto se podría traducir en la secuencia de estados foo, seguida de bar. foo ya no incluye el comportamiento bar. Como resultado, los nombres de los métodos para los estados tienden a tener un alcance más limitado, lo que podría reflejar el comportamiento local.

Diagrama de árbol de simultaneidad

A continuación, se muestra una vista alternativa del diagrama en Concurrencia estructurada que representa mejor la estructura del árbol. Los bloques forman un árbol pequeño.