Um guia para StateMachines do Skyframe

Informar um problema Ver fonte Nightly · 8.3 · 8.2 · 8.1 · 8.0 · 7.6

Visão geral

Um StateMachine do Skyframe é um objeto de função desconstruído que reside no heap. Ele oferece suporte a avaliação flexível e sem redundância¹ quando os valores necessários não estão disponíveis imediatamente, mas são calculados de forma assíncrona. O StateMachine não pode vincular um recurso de linha de execução enquanto espera, mas precisa ser suspenso e retomado. Assim, a desconstrução expõe pontos de reentrada explícitos para que as computações anteriores possam ser ignoradas.

Os StateMachines podem ser usados para expressar sequências, ramificações, concorrência lógica estruturada e são feitos especificamente para 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 única linha de execução SkyFunction compartilhada.

Introdução

Esta seção apresenta e motiva brevemente os 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 realiza a avaliação paralela de gráficos de dependência. Cada nó no gráfico corresponde à avaliação de uma SkyFunction com uma SkyKey que especifica os parâmetros e uma SkyValue que especifica o resultado. O modelo computacional é tal que uma SkyFunction pode pesquisar SkyValues por SkyKey, acionando a avaliação recursiva e paralela de outras SkyFunctions. Em vez de bloquear, o que ocuparia uma linha de execução, quando um SkyValue solicitado ainda não está pronto porque algum subgrafo de computação está incompleto, a SkyFunction solicitante observa uma resposta null getValue e precisa retornar null em vez de um SkyValue, indicando que ele está incompleto devido a entradas ausentes. O Skyframe reinicia as SkyFunctions quando todos os SkyValues solicitados anteriormente ficam disponíveis.

Antes da introdução do SkyKeyComputeState, a maneira tradicional de lidar com uma reinicialização era executar novamente todo o cálculo. Embora isso tenha complexidade quadrática, as funções escritas dessa forma acabam sendo concluídas porque, a cada nova execução, menos pesquisas retornam null. Com o SkyKeyComputeState, é possível associar dados de ponto de verificação especificados manualmente a uma SkyFunction, economizando uma quantidade significativa de recálculo.

Os StateMachines são objetos que ficam dentro de SkyKeyComputeState e eliminam praticamente todo o recálculo quando uma SkyFunction é reiniciada (supondo que SkyKeyComputeState não saia do cache) ao expor hooks de execução de suspensão e retomada.

Computações com estado em SkyKeyComputeState

Do ponto de vista do design orientado a objetos, faz sentido armazenar objetos computacionais em SkyKeyComputeState em vez de valores de dados puros. Em Java, a descrição mínima de um objeto que carrega um comportamento é uma interface funcional, e isso é suficiente. Um StateMachine tem a seguinte definição recursiva².

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

A interface Tasks é análoga à SkyFunction.Environment, mas foi projetada para assincronia e adiciona suporte a subtarefas logicamente simultâneas³.

O valor de retorno de step é outro StateMachine, permitindo a especificação de uma sequência de etapas, de forma indutiva. step retorna DONE quando o StateMachine é concluído. 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 seguinte saída.

hello
world

Observe que a referência de método this::step2 também é uma StateMachine porque step2 atende à definição de interface funcional de 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 StateMachine etapas, em vez de uma função monolítica, fornece os hooks necessários para suspender e retomar um cálculo. Quando StateMachine.step retorna, há um ponto de suspensão explícito. A continuação especificada pelo valor StateMachine retornado é um ponto de retomada explícito. Assim, é possível evitar a recomputação, já que ela pode ser retomada exatamente de onde parou.

Callbacks, continuações 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, uma 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 devolver o controle ao Skyframe.

Tradicionalmente, callbacks e continuações são combinados em um conceito. No entanto, os 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 de SkyValue. Os callbacks precisam ser o mais simples possível.

Cuidado: um erro comum de callbacks é que a computação assíncrona precisa garantir que o callback seja chamado até o final de cada caminho acessível. É possível ignorar algumas ramificações, e o compilador não emite avisos sobre isso.

As continuações são os valores de retorno StateMachine de StateMachines e encapsulam a execução complexa que segue depois que todos os cálculos assíncronos são resolvidos. Essa abordagem estruturada ajuda a manter a complexidade dos callbacks gerenciável.

Tarefas

A interface Tasks fornece StateMachines com uma API para pesquisar SkyValues por 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.
}

Dica: quando um estado usa a interface Tasks para realizar pesquisas ou criar subtarefas, essas pesquisas e subtarefas são concluídas antes do início do próximo estado.

Dica: (corolário) se as subtarefas forem StateMachines complexos ou criarem subtarefas recursivamente, todas elas serão concluídas transitoriamente antes do início do próximo estado.

Pesquisas de SkyValue

Os StateMachines usam sobrecargas de Tasks.lookUp para pesquisar SkyValues. Eles são análogos a SkyFunction.Environment.getValue e SkyFunction.Environment.getValueOrThrow e têm semântica semelhante de tratamento de exceções. A implementação não realiza a pesquisa imediatamente, mas, em vez disso, agrupa⁴ o máximo de pesquisas possível antes de fazer isso. O valor pode não estar disponível imediatamente, por exemplo, exigindo uma reinicialização do Skyframe. Portanto, o autor da chamada especifica o que fazer com o valor resultante usando um callback.

O processador StateMachine (Drivers e ponte para SkyFrame) garante que o valor esteja disponível antes do início do próximo estado. Confira 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 de new Key(), transmitindo this como o consumidor. Isso é possível porque DoesLookup implementa Consumer<SkyValue>.

Dica: ao transmitir this como um coletor de valores, é útil para os leitores fazer upcast dele para o tipo de receptor e restringir a finalidade da transmissão de this. O exemplo transmite (Consumer<SkyValue>) this.

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

Subtarefas

O Tasks.enqueue solicita a execução de subtarefas logicamente simultâneas. As subtarefas também são StateMachines e podem fazer tudo o que os StateMachines regulares fazem, incluindo criar mais subtarefas de forma recursiva ou pesquisar SkyValues. Assim como o lookUp, o driver de máquina de estado garante que todas as subtarefas sejam concluídas antes de prosseguir para a próxima etapa. Confira 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. Portanto, a atualização "simultânea" de i não precisa de nenhuma sincronização.

Simultaneidade estruturada

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

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

É muito mais fácil entender a simultaneidade estruturada.

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

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 disso é mostrado em Computações com estado em SkyKeyComputeState.

Ramificação

É possível ramificar estados em StateMachines retornando valores diferentes usando o fluxo de controle Java regular, como 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 algumas ramificações retornem DONE para conclusão antecipada.

Composição sequencial avançada

Como a estrutura de controle StateMachine não tem memória, compartilhar definições de StateMachine como subtarefas às vezes pode ser complicado. Sejam M₁ e M₂ instâncias de StateMachine que compartilham um StateMachine, S, sendo M₁ e M₂ as sequências <A, S, B> e <X, S, Y>, respectivamente. O problema é que S não sabe se deve continuar para B ou Y depois que ele for concluído, e StateMachines não mantêm uma pilha de chamadas. Esta seção analisa algumas técnicas para fazer isso.

StateMachine como elemento de sequência terminal

Isso não resolve o problema inicial. Ele só demonstra 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 subtarefas⁶.

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 execução de S. Nesse caso, injetar um parâmetro runAfter em S pode ser usado para informar S sobre 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 abusar de subtarefas. No entanto, aplicar isso de forma muito liberal, por exemplo, aninhando vários StateMachines com runAfter, é o caminho para o 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);
  }

Observação: é possível transmitir DONE como o parâmetro runAfter quando não há nada para executar depois.

Dica: ao usar runAfter, sempre anote o parâmetro com /* runAfter= */ para informar ao leitor o significado no site de chamada.

Alternativa Forbidden: runAfterUnlessError

Em um rascunho anterior, consideramos um runAfterUnlessError que seria interrompido 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 deliberar, decidimos que a uniformidade do código é mais importante do que a remoção de duplicações na verificação de erros. Seria confuso se o mecanismo runAfter não funcionasse de maneira consistente com o mecanismo tasks.enqueue, que sempre exige verificação de erros.

Aviso: ao usar runAfter, a máquina que tem o runAfter injetado precisa invocar incondicionalmente na conclusão, mesmo em caso de erro, para manter a consistência.

Delegação direta

Sempre que há uma transição de estado formal, o loop Driver principal avança. De acordo com o contrato, o avanço de estados significa que todas as pesquisas e subtarefas do SkyValue enfileiradas anteriormente são resolvidas antes da execução do próximo estado. Às vezes, a lógica de um delegado StateMachine torna um avanço de fase desnecessário ou contraproducente. Por exemplo, se o primeiro step do delegado realizar pesquisas do SkyKey que podem ser paralelizadas com pesquisas do estado de delegação então um avanço de fase os tornaria sequenciais. Pode ser mais interessante fazer 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 foi o gerenciamento do fluxo de controle. Esta seção descreve a propagação de valores de dados.

Implementar callbacks de Tasks.lookUp

Há um exemplo de implementação de um callback Tasks.lookUp em Pesquisas de SkyValue. Esta seção apresenta a lógica e sugere abordagens para processar vários SkyValues.

Callbacks de Tasks.lookUp

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 Java para implementar isso:

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

em que myValue é 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.

Observação: aviso sobre o bikeshedding. Há uma diferença perceptível de aproximadamente 1% no uso da CPU de ponta a ponta ao implementar callbacks de forma sistemática em implementações de StateMachine em comparação com o uso de lambdas, o que torna essa recomendação questionável. Para evitar debates desnecessários, deixe a decisão a cargo da pessoa que está implementando a solução.

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

Confira um exemplo de implementação 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, ter a classe StateMachine implementando diretamente o callback economiza uma alocação de memória para o lambda.

O tratamento de erros oferece 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 vezes, são necessárias várias pesquisas do SkyValue. Uma abordagem que funciona na maior parte do tempo é ativar o tipo de SkyValue. Confira a seguir um exemplo simplificado de código de produção de protótipo.

  @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 Consumer<SkyValue> pode ser compartilhada sem ambiguidade porque os tipos de valor são diferentes. Quando não é o caso, é viável usar implementações baseadas em lambda ou instâncias completas de classes internas que implementam os callbacks adequados.

Propagação de valores entre StateMachines

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

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

Dica: seria tentador usar a assinatura mais concisa void accept(Bar value) em vez da void acceptBarValue(Bar value) acima. No entanto, Consumer<SkyValue> é uma sobrecarga comum de void accept(Bar value), e fazer isso geralmente leva a violações da regra do guia de estilo Sobrecargas: nunca dividir.

Dica: usar um tipo ResultSink personalizado em vez de um genérico de java.util.function facilita a localização de implementações na base de código, melhorando a legibilidade.

Um caller StateMachine teria esta 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 e definir o próprio Caller.ResultSink. Caller implementa os callbacks BarProducer.ResultSink. Ao retomar, processResult verifica se value é nulo para determinar se ocorreu um erro. Esse é um padrão de comportamento comum depois de aceitar a saída de uma subatividade ou pesquisa do SkyValue.

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

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

Tratamento de erros

Há alguns exemplos de tratamento de erros já em callbacks Tasks.lookUp e Propagating values between StateMachines. Exceções, além de InterruptedException, não são geradas, mas transmitidas por callbacks como valores. Esses callbacks geralmente têm semântica de OR exclusivo, com exatamente um valor ou erro sendo transmitido.

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

Propagação de erros (--nokeep_going)

Aviso: os erros precisam ser propagados de volta para a SkyFunction para que a propagação de erros funcione corretamente.

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á atingido devido ao contrato da API Tasks. No entanto, o StateMachine ainda precisa propagar a exceção.

Como a propagação precisa ocorrer independente de o próximo estado ser alcançado, o callback de tratamento de erros precisa realizar essa tarefa. Para um StateMachine interno, isso é feito invocando o callback principal.

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

Se um Driver estiver sendo usado diretamente, é essencial verificar se há erros propagados da SkyFunction, mesmo que a máquina não tenha terminado o processamento.

Manipulação de eventos

Para SkyFunctions que precisam emitir eventos, um StoredEventHandler é injetado em SkyKeyComputeState e depois em StateMachines que exigem isso. Antes, o StoredEventHandler era necessário porque o Skyframe descartava determinados eventos, a menos que fossem reproduzidos novamente, mas isso foi corrigido depois. 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 os StateMachines podem enfileirar recursivamente subtarefas StateMachines, um único Driver pode gerenciar várias subtarefas. Essas subtarefas criam uma estrutura de árvore, resultado da simultaneidade estruturada. O Driver agrupa pesquisas do SkyValue em subtarefas para melhorar a eficiência.

Há várias classes criadas em torno do Driver, com a seguinte API.

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

Driver usa um único StateMachine raiz como parâmetro. Chamar Driver.drive executa o StateMachine até onde for possível sem um reinicio do Skyframe. Ele retorna "true" quando o StateMachine é concluído e "false" caso contrário, indicando que nem todos os valores estavam disponíveis.

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

Instanciar Driver diretamente

As implementações de StateMachine geralmente comunicam os resultados por callbacks. É possível instanciar diretamente um Driver, como mostrado no exemplo a seguir.

O Driver está incorporado na implementação do SkyKeyComputeState junto com uma implementação do ResultSink correspondente, que será definida mais adiante. No nível superior, o objeto State é um receptor adequado para o resultado da computação, já que tem uma vida útil maior 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 descreve o 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;
  }
}

O código para calcular o resultado de forma lenta pode ser parecido com o 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;
}

Incorporação Driver

Se o StateMachine produzir 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 da 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;
}

Incorporar Driver na implementação de StateMachine é mais adequado para o estilo de programação síncrona do Skyframe.

StateMachines que podem gerar exceções

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

A classe abstrata ValueOrExceptionProducer inclui os seguintes 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. }
}

Ele inclui uma instância Driver incorporada e se assemelha muito à classe ResultProducer no driver de incorporação e interage com a SkyFunction de maneira semelhante. Em vez de definir um ResultSink, as implementações chamam setValue ou setException quando qualquer uma dessas situações ocorre. Quando os dois ocorrem, a exceção tem prioridade. O método tryProduceValue faz a ponte entre o código de callback assíncrono e o síncrono e gera uma exceção quando um deles é definido.

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

Epílogo: remoção eventual de callbacks

Os StateMachines são uma maneira altamente eficiente, mas repetitiva, de realizar computação assíncrona. As continuações (principalmente na forma de Runnables transmitidos para ListenableFuture) são comuns em algumas partes do código do Bazel, mas não são predominantes nas SkyFunctions de análise. A análise é principalmente vinculada à CPU, e não há APIs assíncronas eficientes para E/S de disco. Com o tempo, é bom otimizar os callbacks, já que eles têm uma curva de aprendizado e prejudicam a legibilidade.

Uma das alternativas mais promissoras são as linhas de execução virtuais do Java. Em vez de ter que escrever callbacks, tudo é substituído por chamadas síncronas e de bloqueio. Isso é possível porque vincular um recurso de linha de execução virtual, ao contrário de uma linha de execução de plataforma, é barato. No entanto, mesmo com linhas de execução virtuais, substituir operações síncronas simples por criação de linhas de execução e primitivos de sincronização é muito caro. Fizemos uma migração de StateMachines para threads virtuais Java, e elas ficaram muito mais lentas, o que levou a um aumento de quase três vezes na latência da análise de ponta a ponta. Como as linhas de execução virtuais ainda são um recurso de prévia, é possível que essa migração seja realizada em uma data posterior, quando o desempenho melhorar.

Outra abordagem a ser considerada é esperar pelas corrotinas do Loom, se elas ficarem disponíveis. A vantagem é que pode ser possível reduzir a sobrecarga de sincronização usando a multitarefa cooperativa.

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

Apêndice

Callback Hell

O callback hell é um problema famoso em códigos assíncronos que usam callbacks. Isso ocorre porque a continuação de uma etapa subsequente está aninhada na etapa anterior. Se houver muitas etapas, esse aninhamento poderá ser extremamente profundo. Se combinado com o fluxo de controle, o código se torna incontrolá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 da pilha da etapa externa pode ser preservado. Em Java, as variáveis lambda capturadas precisam ser efetivamente finais, o que pode ser complicado. O aninhamento profundo é evitado retornando referências de método como continuações em vez de lambdas, conforme mostrado abaixo.

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 callback hell também pode ocorrer se o padrão de injeção de runAfter for usado de forma muito densa, mas isso pode ser evitado intercalando injeções com etapas sequenciais.

Exemplo: pesquisas encadeadas de SkyValue

Muitas vezes, a lógica do aplicativo exige cadeias dependentes de pesquisas do SkyValue. Por exemplo, se uma segunda SkyKey depende do primeiro SkyValue. Pensando de forma ingênua, 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ções são especificadas como referências de método, o código parece procedural em transições de estado: step2 segue step1. Observe que, aqui, uma lambda é usada para atribuir value2. Isso faz com que a ordenação do código corresponda à ordenação do cálculo de cima para baixo.

Dicas gerais

Legibilidade: ordem de execução

Para melhorar a legibilidade, tente manter as implementações de StateMachine.step em ordem de execução e as implementações de callback imediatamente após o local em que elas são transmitidas no código. Isso nem sempre é possível quando o fluxo de controle tem ramificações. Comentários adicionais podem ser úteis nesses casos.

Em Exemplo: pesquisas encadeadas de SkyValue, uma referência de método intermediário é criada para isso. Isso troca uma pequena quantidade de performance por legibilidade, o que provavelmente vale a pena aqui.

Hipótese geracional

Objetos Java de vida média violam a hipótese geracional do coletor de lixo Java, que foi projetado para processar objetos que duram muito pouco ou 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 ainda em execução, com raiz em Driver, têm um ciclo de vida intermediário, já que são suspensos enquanto aguardam a conclusão dos cálculos assíncronos.

Parece menos ruim no JDK19, mas ao usar StateMachines, às vezes é possível observar um aumento no tempo de GC, mesmo com diminuições drásticas no lixo real gerado. Como os StateMachines têm um ciclo de vida intermediário, eles podem ser promovidos para a geração antiga, fazendo com que ela se preencha mais rapidamente e exigindo GCs principais ou completos mais caros para limpeza.

A precaução inicial é minimizar o uso de variáveis StateMachine, mas isso nem sempre é possível, por exemplo, se um valor for necessário em vários estados. Quando possível, as variáveis de pilha local step são variáveis de geração jovem e têm coleta de lixo eficiente.

Para variáveis StateMachine, também é útil dividir as coisas em subtarefas e seguir o padrão recomendado para Propagação de valores entre StateMachines. Observe que, ao seguir o padrão, apenas os StateMachines filhos têm referências aos StateMachines principais, e não o contrário. Isso significa que, à medida que as crianças concluem e atualizam os pais usando callbacks de resultado, elas naturalmente saem do escopo e ficam qualificadas para a coleta de lixo.

Por fim, em alguns casos, uma variável StateMachine é necessária em estados anteriores, mas não em estados posteriores. É recomendável definir como nulas as referências de objetos grandes quando eles não forem mais necessários.

Como nomear estados

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

Diagrama de árvore de simultaneidade

A seguir, uma visão alternativa do diagrama em Concorrência estruturada que descreve melhor a estrutura de árvore. Os blocos formam uma pequena árvore.

---

1. Em contraste com a convenção do Skyframe de reiniciar do início quando os valores não estão disponíveis. ↩

2. Observe que step pode gerar InterruptedException, mas os exemplos omitem isso. Há alguns métodos de baixo nível no código Bazel que geram essa exceção e a propagam até o Driver, que será descrito mais tarde e executa o StateMachine. Não é necessário declarar que ele será gerado quando não for necessário. ↩

3. As subtarefas simultâneas foram motivadas pelo ConfiguredTargetFunction, que realiza trabalho independente para cada dependência. Em vez de manipular estruturas de dados complexas que processam todas as dependências de uma só vez, introduzindo ineficiências, cada dependência tem seu próprio StateMachine independente. ↩

4. Várias chamadas tasks.lookUp em uma única etapa são agrupadas. Outros agrupamentos em lote podem ser criados por pesquisas que ocorrem em subtarefas simultâneas. ↩

5. Isso é conceitualmente semelhante à simultaneidade estruturada do Java jeps/428. ↩

6. Isso é semelhante a gerar uma thread e juntá-la para alcançar composição sequencial. ↩