Um guia sobre máquinas de estado Skyframe

Informar um problemaopen_in_new Ver código-fonteopen_in_new

Informações gerais

Um StateMachine do Skyframe é um objeto de função desconstruído que reside no heap. Ele oferece suporte à avaliação flexível e sem redundância¹ quando os valores necessários não estão imediatamente disponíveis, mas são computados de maneira assíncrona. O StateMachine não pode vincular um recurso da linha de execução enquanto aguarda. Em vez disso, ele precisa ser suspenso e retomado. Assim, a desconstrução expõe pontos de reentrada explícitos para que os cálculos anteriores possam ser ignorados.

Os StateMachines podem ser usados para expressar sequências, ramificações e simultaneidade lógica estruturada e são personalizados especificamente para a interação com o Skyframe. Os StateMachines podem ser compostos em StateMachines maiores e compartilhar sub-StateMachines. A simultaneidade é sempre hierárquica por construção e puramente lógica. Cada subtarefa simultânea é executada na linha de execução pai compartilhada do SkyFunction.

Introdução

Esta seção motiva e apresenta brevemente StateMachines, encontrados no pacote java.com.google.devtools.build.skyframe.state.

Uma breve introdução às reinicializações do Skyframe

O Skyframe é um framework que executa a avaliação paralela de gráficos de dependência. Cada nó no gráfico corresponde à avaliação de uma SkyFunction com uma SkyKey especificando os parâmetros e o SkyValue especificando o resultado. O modelo computacional faz com que uma SkyFunction possa procurar SkyValues pela SkyKey, acionando avaliação recursiva e paralela de SkyFunctions adicionais. Em vez de bloquear, o que vincularia uma linha de execução, quando um SkyValue solicitado ainda não está pronto porque algum subgráfico de computação está incompleto, a SkyFunction solicitante observa uma resposta null getValue e precisa retornar null em vez de um SkyValue, sinalizando que está incompleto devido a entradas ausentes. O Skyframe reinicia o SkyFunctions quando todos os SkyValues solicitados anteriormente ficam disponíveis.

Antes da introdução de SkyKeyComputeState, a maneira tradicional de lidar com uma reinicialização era executar totalmente o cálculo. Embora isso tenha complexidade quadrática, as funções escritas dessa maneira acabam sendo concluídas porque cada nova execução retorna menos null. Com SkyKeyComputeState, é possível associar dados de check-point especificados manualmente a um SkyFunction, economizando uma computação significativa.

StateMachines são objetos que residem em SkyKeyComputeState e eliminam praticamente toda a recomputação quando uma SkyFunction é reiniciada (presumindo que SkyKeyComputeState não esteja fora do cache), expondo ganchos de execução de suspensão e retomada.

Computações com estado em SkyKeyComputeState

Do ponto de vista do design orientado a objetos, faça sentido armazenar objetos computacionais dentro de SkyKeyComputeState em vez de valores de dados puros. Em Java, a descrição mínima de um objeto que comporta um comportamento é uma interface funcional (em inglês) e parece ser suficiente. Um StateMachine tem a seguinte definição curiosamente recursiva².

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

A interface Tasks é análoga a SkyFunction.Environment, mas foi projetada para asynchrony e adiciona suporte a subtarefas simultaneamente lógicas³.

O valor de retorno de step é outro StateMachine, permitindo a especificação de uma sequência de etapas, indutivamente. step retorna DONE quando a StateMachine é concluída. Por exemplo:

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

descreve um StateMachine com a saída a seguir.

hello
world

A referência do método this::step2 também é um StateMachine devido ao step2 que satisfaz a definição de interface funcional do StateMachine. As referências de método são a maneira mais comum de especificar o próximo estado em um StateMachine.

Intuitivamente, dividir um cálculo em etapas StateMachine, em vez de uma função monolítica, fornece os hooks necessários para suspender e retomar uma computação. Quando StateMachine.step retorna, há um ponto explícito de suspensão. A continuação especificada pelo valor StateMachine retornado é um ponto resume explícito. Assim, a computação pode ser evitada porque ela pode ser retomada exatamente de onde parou.

Retornos de chamada, continuação e computação assíncrona

Em termos técnicos, um StateMachine serve como uma continuação, determinando o cálculo subsequente a ser executado. Em vez de bloquear, um StateMachine pode suspender voluntariamente retornando da função step, que transfere o controle de volta para uma instância Driver. O Driver pode mudar para um StateMachine pronto ou renunciar ao controle do Skyframe.

Tradicionalmente, retornos de chamada e continuações são confundidos em um conceito. No entanto, StateMachines mantêm uma distinção entre os dois.

• Callback: descreve onde armazenar o resultado de um cálculo assíncrono.
• Continuação: especifica o próximo estado de execução.

Os callbacks são necessários ao invocar uma operação assíncrona, o que significa que a operação real não ocorre imediatamente ao chamar o método, como no caso de uma pesquisa do SkyValue. Os callbacks devem ser o mais simples possível.

Continuações são os valores de retorno StateMachine de StateMachines e encapsulam a execução complexa que ocorre após a resolução de todas as computações assíncronas. Essa abordagem estruturada ajuda a manter a complexidade dos callbacks.

Tarefas

A interface Tasks fornece StateMachines com uma API para pesquisar SkyValues pela SkyKey e programar subtarefas 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.
}

Pesquisas SkyValue

StateMachines usam sobrecargas Tasks.lookUp para procurar SkyValues. Eles são análogos a SkyFunction.Environment.getValue e SkyFunction.Environment.getValueOrThrow e têm semânticas de processamento de exceções semelhantes. A implementação não realiza a pesquisa imediatamente, mas agrupa em lote⁴ o maior número possível de pesquisas antes de fazer isso. O valor pode não estar imediatamente disponível, por exemplo, exigindo uma reinicialização do Skyframe, para que o autor da chamada especifique o que fazer com o valor resultante usando um callback.

O processador StateMachine (Drivers e ponte para o SkyFrame) garante que o valor esteja disponível antes do início do próximo estado. Veja a seguir um exemplo.

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

No exemplo acima, a primeira etapa faz uma pesquisa por new Key(), transmitindo this como o consumidor. Isso é possível porque DoesLookup implementa Consumer<SkyValue>.

Por contrato, antes que o próximo estado DoesLookup.processValue comece, todas as pesquisas de DoesLookup.step são concluídas. Portanto, value está disponível quando é acessado em processValue.

Subtarefas

Tasks.enqueue solicita a execução de subtarefas simultaneamente simultâneas. Subtarefas também são StateMachines e podem fazer tudo o que StateMachines regulares podem fazer, incluindo a criação recursiva de mais subtarefas ou a pesquisa de SkyValues. Assim como lookUp, o driver de máquina de estado garante que todas as subtarefas estejam concluídas antes de prosseguir para a próxima etapa. Veja a seguir um exemplo.

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

Embora Subtask1 e Subtask2 sejam logicamente simultâneos, tudo é executado em uma única linha de execução para que a atualização "simultânea" de i não precise de sincronização.

Simultaneidade estruturada

Como cada lookUp e enqueue precisam resolver antes de avançar para o próximo estado, isso significa que a simultaneidade é naturalmente limitada a estruturas de árvore. É possível criar uma simultaneidade⁵ hierárquica, conforme mostrado no exemplo a seguir.

É difícil dizer da UML que a estrutura de simultaneidade forma uma árvore. Há uma visualização alternativa que mostra melhor a estrutura da árvore.

A simultaneidade estruturada é muito mais fácil de entender.

Padrões de composição e controle de fluxo

Esta seção apresenta exemplos de como vários StateMachines podem ser compostos e soluções para determinados problemas de fluxo de controle.

Estados sequenciais

Esse é o padrão de fluxo de controle mais comum e direto. Um exemplo é mostrado em Computação com estado dentro de SkyKeyComputeState.

Ramificação

Os estados de ramificação em StateMachines podem ser conseguidos retornando valores diferentes usando o fluxo de controle Java normal, conforme mostrado no exemplo a seguir.

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

É muito comum que determinados branches retornem DONE para conclusão antecipada.

Composição sequencial avançada

Como a estrutura de controle StateMachine não tem memória, às vezes o compartilhamento de definições StateMachine como subtarefas pode ser desagradável. Permita que M₁ e M₂ sejam instâncias StateMachine que compartilham um StateMachine, S, com M₁ e M₂ sendo as sequências <A, S, B> e <X, S, Y>, respectivamente. O problema é que S não sabe se continua em B ou Y após a conclusão, e StateMachines não mantêm uma pilha de chamadas. Esta seção analisa algumas técnicas para fazer isso.

StateMachine como elemento da sequência do terminal

Isso não resolve o problema inicial. Ele demonstra apenas a composição sequencial quando o StateMachine compartilhado é terminal na sequência.

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

Isso funciona mesmo que S seja uma máquina de estado complexa.

Subtarefa para composição sequencial

Como as subtarefas enfileiradas têm garantia de conclusão antes do próximo estado, às vezes é possível abusar um pouco do mecanismo de subtarefa⁶.

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

Injeção de runAfter

Às vezes, abusar de Tasks.enqueue é impossível porque há outras subtarefas paralelas ou chamadas de Tasks.lookUp que precisam ser concluídas antes da S ser executada. Nesse caso, injetar um parâmetro runAfter em S para informar ao S o que fazer em seguida.

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

Essa abordagem é mais limpa do que o abuso de subtarefas. No entanto, aplicar isso de forma muito liberal, por exemplo, aninhando vários StateMachines com runAfter, é o caminho para Callback Hell. É melhor dividir runAfters sequenciais com estados sequenciais comuns.

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

pode ser substituído pelo seguinte.

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

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

Alternativa proibida: runAfterUnlessError

Em um rascunho anterior, consideramos uma runAfterUnlessError que seria cancelada no início dos erros. Isso foi motivado pelo fato de que os erros geralmente acabam sendo verificados duas vezes: uma pelo StateMachine, que tem uma referência runAfter, e outra pela própria máquina runAfter.

Depois de algumas deliberações, decidimos que a uniformidade do código é mais importante do que desduplicar a verificação de erros. Seria confuso se o mecanismo runAfter não funcionasse de maneira consistente com o mecanismo tasks.enqueue, o que sempre exige a verificação de erros.

Delegação direta

Sempre que há uma transição de estado formal, o loop principal Driver avança. De acordo com o contrato, o avanço de estados significa que todas as buscas e subtarefas SkyValue enfileiradas antes são resolvidas antes da execução do próximo estado. Às vezes, a lógica de um StateMachine delegado torna a fase avançada desnecessária ou contraprodutiva. Por exemplo, se a primeira step do delegado realizar pesquisas SkyKey que podem ser carregadas em paralelo com pesquisas do estado delegado, um avanço de fase os tornará sequenciais. Pode fazer mais sentido realizar a delegação direta, conforme mostrado no exemplo abaixo.

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

Fluxo de dados

O foco da discussão anterior tem sido o gerenciamento do fluxo de controle. Esta seção descreve a propagação de valores de dados.

Como implementar callbacks Tasks.lookUp

Há um exemplo de implementação de um callback Tasks.lookUp nas pesquisas Skyky. Esta seção fornece uma justificativa e sugere abordagens para lidar com vários SkyValues.

Tasks.lookUp callbacks

O método Tasks.lookUp usa um callback, sink, como parâmetro.

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

A abordagem idiomática seria usar uma lambda em Java para implementar isso:

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

com myValue sendo uma variável de membro da instância StateMachine que faz a pesquisa. No entanto, a lambda exige uma alocação de memória extra em comparação com a implementação da interface Consumer<SkyValue> na implementação StateMachine. O lambda ainda é útil quando há várias pesquisas que seriam ambíguas.

Também há sobrecargas de tratamento de erros de Tasks.lookUp, que são análogos 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);
  }

Um exemplo de implementação é mostrado abaixo.

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

Assim como nas pesquisas sem tratamento de erros, fazer com que a classe StateMachine implemente diretamente o callback economiza uma alocação de memória para a lamba.

O gerenciamento de erros fornece um pouco mais de detalhes, mas, essencialmente, não há muita diferença entre a propagação de erros e valores normais.

Como consumir vários SkyValues

Muitas pesquisas do SkyValue geralmente são necessárias. Uma abordagem que funciona muito é ativar o tipo de SkyValue. Veja a seguir um exemplo simplificado em relação ao código de produção de protótipos.

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

A implementação de callback de Consumer<SkyValue> pode ser compartilhada sem ambiguidade, porque os tipos de valor são diferentes. Quando não for esse o caso, é possível recorrer a implementações baseadas em lambda ou instâncias completas de classe interna que implementam os callbacks adequados.

Propagando valores entre StateMachines

Até agora, este documento explicou apenas como organizar o trabalho em uma subtarefa, mas as subtarefas também precisam informar um valor de volta para o autor da chamada. Como as subtarefas são logicamente assíncronas, os resultados são comunicados de volta ao autor da chamada usando um callback. Para que isso funcione, a subtarefa define uma interface de coletor que é injetada por meio do construtor.

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

O autor da chamada StateMachine teria a seguinte aparência:

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

O exemplo anterior demonstra algumas coisas. Caller precisa propagar os resultados de volta e define o próprio Caller.ResultSink. Caller implementa os callbacks BarProducer.ResultSink. Após a retomada, processResult verifica se value é nulo para determinar se ocorreu um erro. Esse é um padrão de comportamento comum após aceitar a saída de uma pesquisa de subtarefa ou SkyValue.

A implementação de acceptBarError encaminha o resultado para o Caller.ResultSink, conforme exigido pelo Erro de propagação.

As alternativas para StateMachines de nível superior são descritas em Drivers e como fazer a ponte para SkyFunctions.

Tratamento de erros

Há alguns exemplos de tratamento de erros em callbacks Tasks.lookUp e Propagação de valores entre StateMachines. Exceções, diferentes de InterruptedException não são geradas, mas transmitidas pelos callbacks como valores. Esses callbacks geralmente têm semântica exclusiva ou, com exatamente um valor ou erro sendo passado.

A próxima seção descreve uma interação sutil, mas importante, com o tratamento de erros do Skyframe.

Erro borbulhante (--nokeep_going)

Durante a propagação de erros, uma SkyFunction pode ser reiniciada, mesmo que nem todos os SkyValues solicitados estejam disponíveis. Nesses casos, o estado subsequente nunca será alcançado devido ao contrato da API Tasks. No entanto, o StateMachine ainda propagará a exceção.

Como a propagação precisa ocorrer independentemente de o próximo estado ser atingido, o callback de tratamento de erros precisa executar essa tarefa. Para uma StateMachine interna, isso é feito ao invocar o callback pai.

No StateMachine de nível superior, que interage com o SkyFunction, isso pode ser feito chamando o método setException de ValueOrExceptionProducer. ValueOrExceptionProducer.tryProduceValue gerará a exceção mesmo que não haja SkyValues ausentes.

Se um Driver estiver sendo utilizado diretamente, é essencial verificar se há erros propagados do SkyFunction, mesmo que a máquina não tenha concluído o processamento.

Tratamento de eventos

Para o SkyFunctions que precisam emitir eventos, um StoredEventHandler é injetado no SkyKeyComputeState e injetado nos StateMachines que o exigem. Historicamente, o StoredEventHandler era necessário devido à queda do Skyframe em determinados eventos, a menos que eles sejam repetidos, mas isso foi corrigido posteriormente. A injeção de StoredEventHandler é preservada porque simplifica a implementação de eventos emitidos por callbacks de tratamento de erros.

Drivers e ponte para SkyFunctions

Um Driver é responsável por gerenciar a execução de StateMachines, começando com um StateMachine raiz especificado. Como StateMachines podem enfileirar recursivamente subtarefas StateMachine, uma única Driver pode gerenciar várias subtarefas. Essas subtarefas criam uma estrutura de árvore, um resultado da simultaneidade estruturada. O Driver agrupa as pesquisas SkyValue em subtarefas para melhorar a eficiência.

Há várias classes criadas em torno de Driver, com a API a seguir.

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

Driver usa uma única raiz StateMachine como parâmetro. Chamar Driver.drive executa o StateMachine o máximo possível sem uma reinicialização do Skyframe. Ela retorna "true" quando StateMachine é concluída, e "false" para indicar que nem todos os valores estavam disponíveis.

Driver mantém o estado simultâneo do StateMachine e é adequado para incorporação em SkyKeyComputeState.

Instanciando Driver diretamente

As implementações de StateMachine comunicam os resultados de modo convencional usando callbacks. É possível instanciar diretamente um Driver, conforme mostrado no exemplo a seguir.

O Driver é incorporado na implementação de SkyKeyComputeState junto com uma implementação do ResultSink correspondente para ser definido um pouco mais abaixo. No nível superior, o objeto State é um receptor apropriado para o resultado do cálculo, porque garante que ele durará mais 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;
  }
}

O código abaixo mostra o esboço do 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;
  }
}

Então, o código para calcular lentamente o resultado pode ser semelhante ao seguinte.

@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

Se StateMachine gerar um valor e não gerar exceções, a incorporação de Driver será outra implementação possível, conforme mostrado no exemplo a seguir.

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

A SkyFunction pode ter um código semelhante ao seguinte, em que State é o tipo específico de função 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;
}

A incorporação de Driver na implementação de StateMachine é mais adequada para o estilo de codificação síncrona do Skyframe.

StateMachines que podem produzir exceções

Caso contrário, há classes SkyKeyComputeState-incorporáveis ValueOrExceptionProducer e ValueOrException2Producer que têm APIs síncronas para corresponder ao código SkyFunction síncrono.

A classe abstrata ValueOrExceptionProducer inclui os métodos a seguir.

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

Ela inclui uma instância Driver incorporada e muito parecida com a classe ResultProducer em Como incorporar drivers e interage com a SkyFunction de maneira semelhante. Em vez de definir um ResultSink, as implementações chamam setValue ou setException quando uma delas ocorre. Quando ambos ocorrem, a exceção tem prioridade. O método tryProduceValue vincula o código de callback assíncrono ao código síncrono e gera uma exceção quando um é definido.

Conforme observado anteriormente, durante a propagação de erros, é possível que ocorra um erro mesmo que a máquina ainda não tenha sido concluída porque nem todas as entradas estão disponíveis. Para acomodar isso, tryProduceValue gera todas as exceções definidas, mesmo antes da conclusão da máquina.

Epílogo: eventualmente remoção de retornos de chamada

StateMachines são uma maneira altamente eficiente, mas intensiva de boilerplate para executar a computação assíncrona. As contínuas (especialmente na forma de Runnables transmitidas para ListenableFuture) são espalhadas em determinadas partes do código do Bazel, mas não são predominantes na análise de SkyFunctions. A análise é vinculada principalmente à CPU e não há APIs assíncronas eficientes para E/S de disco. Por fim, seria bom otimizar callbacks, porque eles têm uma curva de aprendizado e impedem a legibilidade.

Uma das alternativas mais promissoras são as linhas de execução virtuais do Java. Em vez de gravar callbacks, tudo é substituído por chamadas síncronas e de bloqueio. Isso é possível porque a vinculação de um recurso de linha de execução virtual, ao contrário de uma linha de execução de plataforma, precisa ser barata. No entanto, mesmo com linhas de execução virtuais, substituir operações síncronas simples pela criação de linhas de execução e primitivas de sincronização é muito caro. Realizamos uma migração de StateMachines para linhas de execução virtuais Java, que eram ordens de magnitude mais lentas, levando a um aumento de quase três vezes na latência de análise de ponta a ponta. Como as linhas de execução virtuais ainda são um recurso de visualização, é possível que essa migração possa ser realizada posteriormente quando o desempenho melhorar.

Outra abordagem a ser considerada é aguardar as corrotinas do Loom, se elas estiverem disponíveis. A vantagem, nesse caso, é que é possível reduzir a sobrecarga de sincronização usando a multitarefa cooperativa.

Se tudo mais falhar, a regravação de bytecode de baixo nível também pode ser uma alternativa viável. Com otimização suficiente, pode ser possível alcançar o desempenho que se aproxima do código de retorno de chamada escrito à mão.

Apêndice

Inferno de retorno de chamada

O inferno de callback é um problema conhecido em código assíncrono que usa callbacks. Isso ocorre porque a continuação de uma etapa subsequente está aninhada na etapa anterior. Se houver muitas etapas, esse aninhamento pode ser extremamente profundo. Se aliado ao fluxo de controle, o código se tornará não gerenciável.

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

Uma das vantagens das implementações aninhadas é que o frame de pilha da etapa externa pode ser preservado. Em Java, as variáveis lambda capturadas precisam ser efetivamente finais. Portanto, o uso dessas variáveis pode ser complicado. O aninhamento profundo é evitado ao retornar referências de método como continuação, em vez de lambdas, conforme mostrado a seguir.

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

O inferno de callback também poderá ocorrer se o padrão de injeção runAfter for usado muito densamente, mas isso pode ser evitado ao intercalar injeções com etapas sequenciais.

Exemplo: pesquisas do ChaValue encadeadas

Muitas vezes, é necessário que a lógica do aplicativo exija cadeias dependentes de pesquisas SkyValue, por exemplo, se uma segunda SkyKey depende do primeiro SkyValue. Pensando nisso de forma simples, isso resultaria em uma estrutura de callback complexa e profundamente aninhada.

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

No entanto, como as continuaçãos são especificadas como referências de método, o código parece procedível em transições de estado: step2 segue step1. Aqui, um lambda é usado para atribuir value2. Isso faz com que a ordenação do código corresponda à ordem da computação de cima para baixo.

Dicas diversas

Legibilidade: ordem de execução

Para melhorar a legibilidade, procure manter as implementações de StateMachine.step na ordem de execução e nas implementações de callback imediatamente depois de transmitir no código. Nem sempre isso é possível quando o fluxo de controle é ramificado. Comentários adicionais podem ser úteis nesses casos.

Em Exemplo: pesquisas encadeadas do SkyValue, uma referência de método intermediária é criada para isso. Isso gera uma pequena quantidade de desempenho pela legibilidade, o que provavelmente vale a pena aqui.

Hipótese geracional

Objetos Java de duração média quebram a hipótese geracional do coletor de lixo Java, projetado para lidar com objetos que vivem por um período muito curto ou com objetos que vivem para sempre. Por definição, os objetos em SkyKeyComputeState violam essa hipótese. Esses objetos, que contêm a árvore construída de todos os StateMachines em execução, com raiz em Driver têm uma vida útil intermediária à medida que são suspensos, aguardando a conclusão de cálculos assíncronos.

Parece menos ruim no JDK19, mas ao usar StateMachines, às vezes é possível observar um aumento no tempo de coleta de lixo, mesmo com reduções significativas no lixo gerado. Como os StateMachines têm vida útil intermediária, eles podem ser promovidos para a geração antiga, fazendo com que eles sejam preenchidos mais rapidamente, o que torna as GCs mais caras ou completas mais limpas.

A precaução inicial é minimizar o uso de variáveis StateMachine, mas nem sempre é viável, por exemplo, se um valor for necessário em vários estados. Sempre que possível, as variáveis step de pilha local são variáveis de geração jovem e são coletadas com eficiência.

Para variáveis StateMachine, também é útil dividir as coisas em subtarefas e seguir o padrão recomendado para Propagar valores entre StateMachines. Ao seguir o padrão, somente StateMachines filhos têm referências a StateMachines pais, e não vice-versa. Isso significa que, à medida que os filhos concluem e atualizam os pais usando callbacks de resultado, eles ficam naturalmente fora do escopo e se qualificam para a GC.

Por fim, em alguns casos, uma variável StateMachine é necessária em estados anteriores, mas não em estados posteriores. Pode ser útil anular referências de objetos grandes quando se sabe que eles não são mais necessários.

Estados de nomenclatura

Ao nomear um método, geralmente é possível nomear um método para o comportamento que acontece nesse método. Não é tão claro como fazer isso em StateMachines porque não há pilha. Por exemplo, suponha que o método foo chame um submétodo bar. Em uma StateMachine, isso pode ser traduzido na sequência de estado foo, seguida por bar. foo não inclui mais o comportamento bar. Como resultado, os nomes de métodos para estados tendem a ser mais restritos no escopo, refletindo potencialmente o comportamento local.

Diagrama da árvore de simultaneidade

Veja a seguir uma visualização alternativa do diagrama em Simultaneidade estruturada que melhor descreve a estrutura da árvore. Os blocos formam uma pequena árvore.