Visão geral
O StateMachine
do Skyframe é um objeto de função desconstruído que reside no
heap. Ele é compatível com flexibilidade e avaliação sem redundância1 quando os valores necessários não estão imediatamente disponíveis, 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. Portanto, a desconstrução expõe pontos de reentrada explícitos
para que cálculos anteriores possam ser ignorados.
As StateMachine
s podem ser usadas para expressar sequências, ramificações e simultaneidade lógica estruturada, e são adaptadas especificamente para a interação com o Skyframe.
As StateMachine
s podem ser compostas em StateMachine
s maiores e compartilhar
sub-StateMachine
s. A simultaneidade é sempre hierárquica por construção
e puramente lógica. Cada subtarefa simultânea é executada na única linha de execução mãe compartilhada da SkyFunction.
Introdução
Esta seção motiva e apresenta brevemente as StateMachine
s, encontradas no
pacote
java.com.google.devtools.build.skyframe.state
.
Uma breve introdução às reinicializações do Skyframe
O Skyframe é um framework que faz avaliações paralelas de gráficos de dependência.
Cada nó do gráfico corresponde à avaliação de uma SkyFunction com uma SkyKey especificando os parâmetros e com o SkyValue especificando o resultado. O modelo computacional faz com que uma SkyFunction pesquise o SkyValues pela SkyKey, acionando uma avaliação paralela e recursiva de outras SkyFunctions. Em vez de
bloquear, o que vincularia uma linha de execução, quando um SkyValue solicitado ainda não estiver
pronto porque algum subgráfico de computação está incompleto, o SkyFunction
que fez a solicitação observa uma resposta null
getValue
e precisa retornar null
em vez de um SkyValue, sinalizando que ele está incompleto devido a entradas ausentes.
O Skyframe reinicia (link em inglês) as SkyFunctions quando todos os SkyValues solicitados anteriormente
ficam disponíveis.
Antes da introdução do SkyKeyComputeState
, a maneira tradicional de processar
uma reinicialização era executar novamente o cálculo de novo. Embora ela tenha complexidade quadrática, as funções escritas dessa maneira acabam sendo concluídas, porque a cada nova execução, menos pesquisas retornam null
. Com o SkyKeyComputeState
, é possível
associar dados de check-point especificados manualmente a um SkyFunction, economizando bastante
recomputação.
StateMachine
s são objetos que residem em SkyKeyComputeState
e eliminam
virtualmente toda a recomputação quando uma SkyFunction é reiniciada (supondo que
SkyKeyComputeState
não fique fora do cache) ao expor ganchos de suspensão e
retomada de execução.
Cálculos com estado dentro de SkyKeyComputeState
Do ponto de vista do design orientado a objetos, faz sentido armazenar
objetos computacionais dentro de SkyKeyComputeState
em vez de valores de dados puros.
Em Java, a descrição mínima de um objeto de transporte é uma interface funcional (em inglês) e acaba sendo suficiente. Um StateMachine
tem
esta definição curiosamente recursiva2.
@FunctionalInterface
public interface StateMachine {
StateMachine step(Tasks tasks) throws InterruptedException;
}
A interface Tasks
é análoga a SkyFunction.Environment
, mas é
projetada para assíncrona e adiciona suporte a subtarefas logicamente simultâneas3.
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 a
StateMachine
é concluída. 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 do método this::step2
também é um StateMachine
devido ao
step2
que satisfaz a 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 uma
StateMachine
.
Intuitivamente, dividir um cálculo em etapas StateMachine
, em vez de uma função monolítica, fornece os hooks necessários para suspend e suspend uma computação. Quando StateMachine.step
retorna, há um ponto de suspensão explícito. A continuação especificada pelo valor StateMachine
retornado é um
ponto de retomado explícito. Assim, a recomputação pode ser evitada porque
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 continuation, determinando o
cálculo subsequente a ser executado. Em vez de bloquear, um StateMachine
pode
suspend voluntariamente retornando da função step
, que transfere
o controle de volta para uma instância Driver
. O Driver
pode
alternar para um StateMachine
pronto ou liberar o controle de volta para o Skyframe.
Tradicionalmente, callbacks e continuação são combinados em um conceito.
No entanto, StateMachine
s mantêm uma distinção entre os dois.
- Callback: descreve onde armazenar o resultado de uma computação assíncrona.
- 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 após a chamada do método, como no caso de uma pesquisa do SkyValue. Os retornos de chamada devem ser o mais simples possível.
As continuação são os valores de retorno de StateMachine
de StateMachine
s e
encapsulam a execução complexa que ocorre 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 StateMachine
s com uma API para pesquisar o SkyValues pela SkyKey e agendar 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 do SkyValue
As StateMachine
s usam sobrecargas de Tasks.lookUp
para procurar SkyValues. Elas são
análogas 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 agrupa4 o maior número possível de pesquisas antes disso. O valor pode não estar imediatamente disponível, 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
(Driver
s e a ponte para o
SkyFrame) garante que o valor esteja disponível antes
do início do próximo estado. Confira um exemplo abaixo.
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 do início do próximo estado DoesLookup.processValue
, todas as
pesquisas de DoesLookup.step
estão concluídas. Portanto, value
está disponível quando
é acessado em processValue
.
Subtarefas
Tasks.enqueue
solicita a execução de subtarefas logicamente simultâneas.
As subtarefas também são StateMachine
s e podem realizar as mesmas ações que as StateMachine
s
normais, incluindo a criação recursiva de mais subtarefas ou a pesquisa do SkyValues.
Assim como lookUp
, o driver da máquina de estado garante que todas as subtarefas sejam
concluídas antes de prosseguir para a próxima etapa. Confira um exemplo abaixo.
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
precisam ser resolvidos 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 5 hierárquica, conforme mostrado no exemplo
abaixo.
É difícil dizer na UML que a estrutura de simultaneidade forma uma árvore. Há uma visualização alternativa que mostra melhor a estrutura de árvore.
É muito mais fácil entender a simultaneidade estruturada.
Composição e controle de padrões de fluxo
Esta seção apresenta exemplos de como várias StateMachine
s podem ser compostas
e soluções para determinados problemas de fluxo de controle.
Estados sequenciais
Esse é o padrão de fluxo de controle mais comum e simples. Um exemplo disso
é mostrado em Cálculos com estado dentro de
SkyKeyComputeState
.
Ramificação
Os estados de ramificação em StateMachine
s podem ser alcançados retornando valores
diferentes usando o fluxo de controle Java normal, 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 a 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 pode ser estranho. Permita que M1 e
M2 sejam instâncias StateMachine
que compartilham um StateMachine
, S,
com M1 e M2 sendo as sequências <A, S, B> e
<X, S, Y>, respectivamente. O problema é que S não sabe se precisa continuar para B ou Y após a conclusão, e StateMachine
s 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 apresentado. 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 com certeza serão concluídas antes do próximo estado, às vezes é possível abusar um pouco6 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 que S
seja executado. 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 muito
liberalmente, por exemplo, aninhando vários StateMachine
s com runAfter
, é
o caminho para o Callback Hell. É melhor dividir runAfter
s 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 um runAfterUnlessError
que seria cancelado
antecipadamente em caso de erros. Isso foi motivado pelo fato de que os erros geralmente são verificados duas vezes, uma pelo StateMachine
que tem uma referência runAfter
e outra pela própria máquina runAfter
.
Após algumas deliberações, decidimos que a uniformidade do código é mais importante do que eliminar a duplicação da verificação de erros. Seria confuso se o mecanismo runAfter
não funcionasse de maneira consistente com o mecanismo tasks.enqueue
, que sempre requer a verificação de erros.
Delegação direta
Cada vez que há uma transição formal de estado, a repetição Driver
principal avança.
De acordo com o contrato, "avançar 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 StateMachine
delegado torna um avanço de fase desnecessário ou
contraprodutivo. Por exemplo, se o primeiro step
do delegado executar pesquisas da SkyKey que poderiam ser carregadas em paralelo com pesquisas do estado delegado, então um avanço de fase as tornaria sequenciais. Poderia fazer mais sentido realizar a delegação direta, como 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 do
SkyValue. Esta seção fornece justificativas e sugestões de
abordagens para lidar com vários SkyValues.
Tasks.lookUp
callbacks
O método Tasks.lookUp
recebe 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);
com myValue
sendo uma variável de membro da instância StateMachine
que está fazendo 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
de StateMachine
. A lambda ainda é útil quando há várias pesquisas que
seriam ambíguas.
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 abaixo um exemplo de implementação.
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 processamento de erros, fazer com que a classe StateMachine
implemente diretamente
o callback economiza uma alocação de memória para a lamba.
O tratamento de erros fornece um pouco mais de detalhes, mas, essencialmente, não há muita diferença entre a propagação de erros e os 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. Veja a seguir um exemplo que foi simplificado a partir do código de produção do 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 do callback Consumer<SkyValue>
pode ser compartilhada sem ambiguidade,
porque os tipos de valor são diferentes. Quando esse não for o caso, é viável voltar a
implementações baseadas em lambda ou a instâncias completas de classe interna que implementam os
callbacks adequados.
Propagação de valores entre StateMachine
s
Até agora, este documento só explicou como organizar o trabalho em uma subtarefa, mas as subtarefas também precisam informar valores ao autor da chamada. Como as subtarefas são logicamente assíncronas, os resultados são comunicados ao autor da chamada usando um callback. Para que isso funcione, a subtarefa define uma interface de coletor que é injetada pelo 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;
}
}
Então, o autor da chamada 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 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
depois de aceitar a saída de uma subtarefa ou da pesquisa do SkyValue.
Observe que a implementação de acceptBarError
encaminha o resultado para
Caller.ResultSink
, conforme exigido pelo Bolha de erros.
Alternativas para StateMachine
s de nível superior são descritas em Driver
s e
como fazer a ponte com o SkyFunctions.
Tratamento de erros
Já existem alguns exemplos de tratamento de erros em callbacks
Tasks.lookUp
e em Propagação de valores entre
StateMachines
. Exceções diferentes de
InterruptedException
não são geradas, mas são transmitidas por
callbacks como valores. Esses callbacks geralmente têm semântica exclusiva ou semântica, com
exatamente um de 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.
Balanço de erros (--nokeep_Vamos)
Durante o propagação de erros, um SkyFunction pode ser reiniciado 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
precisa propagar a exceção.
Como a propagação precisa ocorrer independentemente de o próximo estado ser alcançado,
o callback de tratamento de erros precisa executar essa tarefa. Para um StateMachine
interno,
isso é feito invocando o callback pai.
No StateMachine
de nível superior, que interage com a SkyFunction, isso pode ser feito chamando o método setException
de ValueOrExceptionProducer
.
ValueOrExceptionProducer.tryProduceValue
gerará a exceção, mesmo que não haja SkyValues.
Se um Driver
estiver sendo utilizado diretamente, é essencial verificar se há erros propagados no SkyFunction, mesmo que a máquina não tenha concluído o processamento.
Tratamento de eventos
Para SkyFunctions que precisam emitir eventos, um StoredEventHandler
é injetado
no SkyKeyComputeState e injetado ainda mais em StateMachine
s que precisam
deles. Historicamente, o StoredEventHandler
era necessário porque o Skyframe descarta
determinados eventos, a menos que eles sejam repetidos, mas isso foi corrigido posteriormente.
A injeção de StoredEventHandler
é preservada, porque ela simplifica a
implementação de eventos emitidos de callbacks de processamento de erros.
Driver
s e a ponte para o SkyFunctions
Um Driver
é responsável por gerenciar a execução de StateMachine
s,
começando com uma StateMachine
raiz especificada. Como StateMachine
s podem
enfileirar StateMachine
s de subtarefas recursivamente, um único Driver
pode gerenciar
várias subtarefas. Essas subtarefas criam uma estrutura de árvore, um resultado da
simultaneidade estruturada. O Driver
agrupa as pesquisas do SkyValue em subtarefas para melhorar a eficiência.
Há várias classes criadas em torno do 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. Ele retorna verdadeiro quando o StateMachine
é concluído e falso,
caso contrário, indicando que nem todos os valores estavam disponíveis.
Driver
mantém o estado simultâneo do StateMachine
e é
adequado para incorporação em SkyKeyComputeState
.
Como instanciar Driver
diretamente
As implementações de StateMachine
comunicam convencionalmente os resultados usando
callbacks. É possível instanciar diretamente um Driver
, conforme mostrado no
exemplo abaixo.
O Driver
é incorporado à implementação de SkyKeyComputeState
com
uma implementação do ResultSink
correspondente a ser definido um pouco mais abaixo. No nível superior, o objeto State
é um receptor apropriado para o
resultado do cálculo, já que ele persiste ao 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 esboça 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 lentamente o resultado vai ficar assim:
@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 o StateMachine
produzir um valor e não gerar exceções, a incorporação
Driver
será outra implementação possível, conforme mostrado no exemplo abaixo.
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;
}
A incorporação de Driver
na implementação de StateMachine
é uma opção melhor para o estilo de codificação síncrona do Skyframe.
StateMachines que podem produzir exceções
Caso contrário, há classes ValueOrExceptionProducer
e ValueOrException2Producer
incorporáveis SkyKeyComputeState
que têm APIs síncronas para corresponder ao código síncrono SkyFunction.
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. }
}
Ele inclui uma instância Driver
incorporada e se parece muito com a
classe ResultProducer
no driver de incorporação e interage
com o 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
conecta o código de callback assíncrono ao síncrono e gera uma
exceção quando uma é definida.
Conforme observado anteriormente, durante o bolhas 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 qualquer exceção definida, mesmo antes de a
máquina terminar.
Epílogo: remover callbacks
StateMachine
s são uma maneira altamente eficiente, mas que usam bastante código boilerplate para realizar
computação assíncrona. As continuação (especialmente na forma de Runnable
s
passadas para ListenableFuture
) são comuns em algumas partes do código do Bazel,
mas não são predominantes no SkyFunctions de análise. A análise é principalmente vinculada à CPU e
não há APIs assíncronas eficientes para E/S de disco. Seria bom
otimizar os 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 Java. Em vez de
criar 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, deveria ser barato. No entanto, mesmo com linhas de execução virtuais, substituir operações síncronas simples por primitivos de criação e sincronização de linhas de execução é muito caro. Realizamos uma migração de StateMachine
s para linhas de execução virtuais Java, e elas 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 em fase de pré-lançamento, é possível que essa migração possa ser realizada
depois que o desempenho melhorar.
Outra abordagem a ser considerada é aguardar as corrotinas do Loom, se elas ficarem disponíveis. A vantagem aqui é que pode ser possível reduzir a sobrecarga de sincronização usando multitarefa cooperativa.
Se tudo o 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 um desempenho que se aproxime do código de callback escrito à mão.
Apêndice
Inferno do callback
O "inferno do callback" é um problema infame no código assíncrono que usa callbacks. Isso decorre do fato de que a continuação para uma etapa subsequente está aninhada dentro da etapa anterior. Se houver muitas etapas, esse aninhamento pode ser extremamente profundo. Se acoplado ao 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, portanto, o uso dessas variáveis pode ser complicado. O aninhamento profundo é evitado retornando referências de métodos 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;
}
}
Um inferno de callback também pode ocorrer se o padrão de injeção runAfter
for usado muito densamente, mas isso pode ser evitado intercalando injeções
com etapas sequenciais.
Exemplo: pesquisas do SkyValue encadeadas
Muitas vezes, a lógica do aplicativo exige cadeias dependentes de pesquisas do SkyValue, por exemplo, se uma segunda SkyKey depender do primeiro SkyValue. Pensando nisso 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 nas transições de estado: step2
segue step1
. Observe que, aqui, uma
lambda é usada para atribuir value2
. Isso faz com que a ordem do código corresponda à
ordem do cálculo de cima para baixo.
Dicas diversas
Legibilidade: ordem de execução
Para melhorar a legibilidade, mantenha as implementações de StateMachine.step
na ordem de execução e as implementações de callback imediatamente após a transmissão
no código. Isso nem sempre é possível quando o fluxo de controle se ramifica. Comentários adicionais podem ser úteis nesses casos.
Em Exemplo: pesquisas do SkyValue encadeados, uma referência de método intermediária é criada para fazer isso. Isso troca uma pequena quantidade de desempenho pela legibilidade, o que provavelmente vale a pena aqui.
Hipótese geracional
Os objetos Java de média duração quebram a hipótese geracional do coletor de lixo Java, que foi projetado para lidar com objetos que vivem por um período muito curto ou 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 StateMachine
s ainda em execução, enraizados em Driver
, têm
uma vida útil intermediária à medida que são suspensos, aguardando a conclusão dos cálculos
assíncronos.
Isso parece menos ruim no JDK19, mas, ao usar StateMachine
s, às vezes é
possível observar um aumento no tempo de GC, mesmo com reduções drásticas no
lixo real gerado. Como as StateMachine
s têm uma vida útil intermediária,
elas podem ser promovidas para a geração antiga, fazendo com que elas sejam preenchidas mais rapidamente, o que
necessita da limpeza de GCs principais ou completas mais caras.
A precaução inicial é minimizar o uso de variáveis StateMachine
, mas isso nem sempre é viável, por exemplo, se um valor for necessário em vários estados. Sempre que possível, as variáveis step
da pilha local são variáveis de geração mais novas e coletadas de forma eficiente.
Para variáveis StateMachine
, também é útil dividir as coisas em subtarefas e seguir
o padrão recomendado para Propagar valores entre
StateMachine
s. Observe que, ao
seguir o padrão, somente StateMachine
s filhas têm referências a StateMachine
s
pais, e não vice-versa. Isso significa que, à medida que os filhos completam e
atualizam os pais usando callbacks de resultado, os filhos naturalmente saem do
escopo e se tornam qualificados para o GC.
Por fim, em alguns casos, uma variável StateMachine
é necessária em estados anteriores,
mas não em estados posteriores. Pode ser vantajoso anular referências de objetos grandes
quando souber que eles não são mais necessários.
Como nomear estados
Ao nomear um método, geralmente é possível nomear um método para o comportamento
que acontece nesse método. É menos claro como fazer isso em
StateMachine
s porque não há pilha. Por exemplo, suponha que o método foo
chame um submétodo bar
. Em um StateMachine
, isso pode ser convertido na
sequência de estados foo
, seguido 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,
refletindo possivelmente o comportamento local.
Diagrama de árvore de simultaneidade
Confira a seguir uma visualização alternativa do diagrama em Simultaneidade estruturada que descreve melhor a estrutura de árvore. Os blocos formam uma pequena árvore.
-
Diferente da convenção do Skyframe de reiniciar desde o início quando os valores não estão disponíveis. ↩
-
Observe que
step
tem permissão para gerarInterruptedException
, mas os exemplos omitem isso. Há alguns métodos baixos no código do Bazel que geram essa exceção e se propagam até oDriver
, que vai ser descrito posteriormente que executa oStateMachine
. Não há problema em declarar que ele é gerado quando desnecessário.↩ -
As subtarefas simultâneas eram motivadas pela
ConfiguredTargetFunction
, que executa um trabalho independente para cada dependência. Em vez de manipular estruturas de dados complexas que processam todas as dependências de uma vez, introduzindo ineficiências, cada dependência tem o próprioStateMachine
independente.↩ -
Várias chamadas
tasks.lookUp
em uma única etapa são agrupadas. Outros lotes podem ser criados por pesquisas que ocorrem em subtarefas simultâneas. ↩ -
Conceitualmente, isso é semelhante à simultaneidade estruturada de Java jeps/428 (link em inglês). ↩
-
Fazer isso é semelhante a gerar e mesclar uma linha de execução para conseguir composição sequencial. ↩