Skyframe

A avaliação paralela e o modelo de incrementabilidade do Bazel.

Modelo de dados

O modelo de dados consiste nos seguintes itens:

  • SkyValue. Também chamados de nós. SkyValues são objetos imutáveis que contêm todos os dados criados ao longo do build e as entradas dele. Exemplos: arquivos de entrada, arquivos de saída, destinos e destinos configurados.
  • SkyKey. Um nome curto imutável para referenciar SkyValue, por exemplo, FILECONTENTS:/tmp/foo ou PACKAGE://foo.
  • SkyFunction. Cria nós com base nas chaves e nos nós dependentes.
  • Gráfico de nós. Uma estrutura de dados que contém a relação de dependência entre nós.
  • Skyframe. O nome do codinome do framework de avaliação incremental em que o Bazel é baseado.

Avaliação

Um build consiste em avaliar o nó que representa a solicitação de build. Esse é o estado pelo qual estamos nos esforçando, mas há muitos códigos legados no caminho. Primeiro, o SkyFunction é encontrado e chamado com a chave do SkyKey de nível superior. Em seguida, a função solicita a avaliação dos nós necessários para avaliar o nó de nível superior, o que, por sua vez, resulta em outras invocações de função e assim por diante, até que os nós de folha sejam alcançados (que geralmente são nós que representam arquivos de entrada no sistema de arquivos). Por fim, chegamos ao valor do SkyValue de nível superior, alguns efeitos colaterais (como arquivos de saída no sistema de arquivos) e um gráfico acíclico direcionado das dependências entre os nós envolvidos no build.

Um SkyFunction poderá solicitar SkyKeys em vários cartões se não puder informar com antecedência todos os nós necessários para realizar o trabalho. Um exemplo simples é avaliar um nó de arquivo de entrada que acaba sendo um link simbólico: a função tenta ler o arquivo, percebe que é um link simbólico e busca o nó do sistema de arquivos que representa o destino do link simbólico. Mas ele pode ser um link simbólico. Nesse caso, a função original também vai precisar buscar o destino.

As funções são representadas no código pela interface SkyFunction e os serviços fornecidos a ela por uma interface chamada SkyFunction.Environment. As funções podem fazer o seguinte:

  • Solicite a avaliação de outro nó chamando env.getValue. Se o nó estiver disponível, o valor dele vai ser retornado. Caso contrário, null vai ser retornado, e a própria função vai retornar null. No último caso, o nó dependente é avaliado e, em seguida, o builder de nós original é invocado novamente, mas desta vez a mesma chamada env.getValue retornará um valor diferente de null.
  • Solicite a avaliação de vários outros nós chamando env.getValues(). Isso faz basicamente o mesmo, exceto que os nós dependentes são avaliados em paralelo.
  • Faça computação durante a invocação
  • têm efeitos colaterais, como gravação de arquivos no sistema de arquivos; É preciso ter cuidado para que duas funções diferentes não pisem no pé da outra. Em geral, efeitos colaterais de gravação (em que os dados fluem para fora do Bazel) são aceitáveis. Já os efeitos colaterais de leitura (quando os dados fluem para o Bazel sem uma dependência registrada) não são, porque são uma dependência não registrada e, assim, podem causar builds incrementais incorretos.

As implementações de SkyFunction não podem acessar dados de outra forma que não seja solicitando dependências (como lendo diretamente o sistema de arquivos), porque isso faz com que o Bazel não registre a dependência de dados no arquivo que foi lido, resultando em builds incrementais incorretos.

Depois que uma função tem dados suficientes para fazer seu trabalho, ela precisa retornar um valor não null indicando a conclusão.

Essa estratégia de avaliação tem vários benefícios:

  • Hermeticidade. Se as funções solicitam apenas dados de entrada dependentes de outros nós, o Bazel garante que, se o estado de entrada for o mesmo, os mesmos dados serão retornados. Se todas as funções do Sky forem deterministas, isso significa que todo o build também será determinístico.
  • Incrementabilidade correta e perfeita. Se todos os dados de entrada de todas as funções forem gravados, o Bazel poderá invalidar apenas o conjunto exato de nós que precisa ser invalidado quando os dados de entrada forem alterados.
  • Paralelismo. Como as funções só podem interagir entre si solicitando dependências, as funções que não dependem umas das outras podem ser executadas em paralelo, e o Bazel pode garantir que o resultado seja o mesmo que se fossem executadas em sequência.

Incrementabilidade

Como as funções só podem acessar dados de entrada dependendo de outros nós, o Bazel pode criar um gráfico de fluxo de dados completo dos arquivos de entrada para os arquivos de saída e usar essas informações para recriar apenas os nós que realmente precisam ser recriados: o fechamento transitivo reverso do conjunto de arquivos de entrada alterados.

Em particular, existem duas estratégias de incrementabilidade possíveis: a de baixo para cima e a de cima para baixo. Qual é a ideal depende da aparência do gráfico de dependências.

  • Durante a invalidação de baixo para cima, depois que um gráfico é criado e o conjunto de entradas alteradas é conhecido, todos os nós são invalidados e dependem transitivamente dos arquivos alterados. Isso é ideal se soubermos que o mesmo nó de nível superior será criado novamente. A invalidação de baixo para cima exige a execução de stat() em todos os arquivos de entrada do build anterior para determinar se eles foram modificados. Isso pode ser melhorado com o uso de inotify ou um mecanismo semelhante para saber mais sobre os arquivos modificados.

  • Durante a invalidação de cima para baixo, o fechamento transitivo do nó de nível superior é verificado e apenas os nós são mantidos cujo fechamento transitivo está limpo. Isso é melhor se soubermos que o gráfico de nós atual é grande, mas precisamos apenas de um pequeno subconjunto dele no próximo build: a invalidação de baixo para cima invalidaria o gráfico maior do primeiro build, ao contrário da invalidação de cima para baixo, que apenas percorre o pequeno gráfico do segundo build.

No momento, fazemos apenas invalidação de baixo para cima.

Para aumentar a incrementabilidade, usamos a remoção de mudanças: se um nó for invalidado, mas for recriado, o novo valor será o mesmo que o antigo, os nós que foram invalidados devido a uma mudança nele serão "restabelecidos".

Isso é útil, por exemplo, se alguém modificar um comentário em um arquivo C++: o arquivo .o gerado com base nele será o mesmo, não sendo necessário chamar o vinculador novamente.

Compilação / vinculação incremental

A principal limitação desse modelo é que a invalidação de um nó é uma questão de tudo ou nada: quando uma dependência muda, o nó dependente sempre é reconstruído do zero, mesmo que exista um algoritmo melhor para modificar o valor antigo do nó com base nas mudanças. Alguns exemplos em que isso seria útil:

  • Vinculação incremental
  • Quando um único arquivo .class muda em um .jar, teoricamente podemos modificar o arquivo .jar em vez de criá-lo do zero novamente.

O motivo pelo qual o Bazel atualmente não oferece suporte a essas coisas de forma baseada em princípios (temos um pouco de suporte para vinculação incremental, mas não é implementado no Skyframe) é duplo: tínhamos apenas ganhos de desempenho limitados e era difícil garantir que o resultado da mutação fosse o mesmo de uma recompilação limpa e os builds de valores do Google que são repetíveis bit por bit.

Até agora, sempre poderíamos alcançar um bom desempenho o suficiente simplesmente decompondo uma etapa de build cara e fazendo uma reavaliação parcial dessa maneira: ele divide todas as classes de um app em vários grupos e faz a dexação delas separadamente. Dessa forma, se as classes de um grupo não mudarem, a dexação não precisará ser refeita.

Mapeamento para conceitos do Bazel

Esta é uma visão geral rápida de algumas das implementações de SkyFunction que o Bazel usa para executar um build:

  • FileStateValue. O resultado de uma lstat(). Para arquivos existentes, também computamos informações adicionais para detectar alterações no arquivo. É o nó de nível mais baixo no gráfico do Skyframe e não tem dependências.
  • FileValue. Usado por qualquer elemento que se importe com o conteúdo real e/ou o caminho resolvido de um arquivo. Depende do FileStateValue correspondente e dos links simbólicos que precisam ser resolvidos. Por exemplo, o FileValue para a/b precisa do caminho resolvido de a e do caminho resolvido de a/b. A distinção entre FileStateValue é importante porque, em alguns casos, como na avaliação de globs do sistema de arquivos (como srcs=glob(["*/*.java"])), o conteúdo do arquivo não é realmente necessário.
  • DirectoryListingValue (em inglês). Basicamente, o resultado de readdir(). Depende do FileValue associado ao diretório.
  • PackageValue. Representa a versão analisada de um arquivo BUILD. Depende do FileValue do arquivo BUILD associado e também de forma transitiva de qualquer DirectoryListingValue usado para resolver os globs no pacote (a estrutura de dados que representa internamente o conteúdo de um arquivo BUILD).
  • ConfiguredTargetValue. Representa um destino configurado, que é uma tupla do conjunto de ações geradas durante a análise de um destino e das informações fornecidas aos destinos configurados que dependem dele. Depende do PackageValue em que o destino correspondente está, o ConfiguredTargetValues das dependências diretas e um nó especial que representa a configuração do build.
  • ArtifactValue (em inglês). Representa um arquivo no build, seja ele um artefato de origem ou de saída (artefatos são quase equivalentes a arquivos e são usados para se referir a arquivos durante a execução real das etapas de build). Para arquivos de origem, isso depende do FileValue do nó associado. Para artefatos de saída, isso depende do ActionExecutionValue de qualquer ação que gere o artefato.
  • ActionExecutionValue. Representa a execução de uma ação. Depende do ArtifactValues dos arquivos de entrada. A ação executada está atualmente contida na chave do céu, o que é contrário ao conceito de que as teclas precisam ser pequenas. Estamos trabalhando para resolver essa discrepância. Observe que ActionExecutionValue e ArtifactValue não são usados se não executarmos a fase de execução no Skyframe.