Skyframe

O modelo de avaliação paralela e incremental do Bazel.

Modelo de dados

O modelo de dados consiste nos seguintes itens:

• SkyValue. Também chamados de nós. Os SkyValues são objetos imutáveis que contêm todos os dados criados durante a build e as entradas dela. Exemplos: arquivos de entrada, arquivos de saída, destinos e destinos configurados.
• SkyKey. Um nome curto e imutável para referenciar um 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 os nós.
• Skyframe. Codinome para o framework de avaliação incremental em que o Bazel se baseia.

Avaliação

Uma build consiste em avaliar o nó que representa a solicitação de build. Esse é o estado que buscamos, mas há muito código legado 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 folha sejam alcançados (que geralmente são nós que representam arquivos de entrada no sistema de arquivos). Por fim, acabamos com o 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 na build.

Um SkyFunction pode solicitar SkyKeys em várias passagens se não puder informar com antecedência todos os nós necessários para fazer 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, portanto, busca o nó do sistema de arquivos que representa o destino do link simbólico. Mas isso pode ser um link simbólico, caso em que a função original também precisará buscar o destino.

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

• Solicitar a avaliação de outro nó chamando env.getValue. Se o nó estiver disponível, o valor será retornado. Caso contrário, null será retornado e a função deverá retornar null. No último caso, o nó dependente é avaliado e o builder de nó original é invocado novamente, mas dessa vez a mesma chamada env.getValue retornará um valor diferente de null.
• Solicitar a avaliação de vários outros nós chamando env.getValues(). Isso faz essencialmente a mesma coisa, exceto que os nós dependentes são avaliados em paralelo.
• Fazer cálculos durante a invocação
• Ter efeitos colaterais, por exemplo, gravar arquivos no sistema de arquivos. É preciso ter cuidado para que duas funções diferentes não se atrapalhem. Em geral, os efeitos colaterais de gravação (em que os dados fluem para fora do Bazel) são aceitáveis, mas os efeitos colaterais de leitura (em que os dados fluem para dentro do Bazel sem uma dependência registrada) não são, porque são uma dependência não registrada e, como tal, podem causar builds incrementais incorretas.

As implementações de SkyFunction não devem acessar dados de outra forma que não seja solicitando dependências (como ler diretamente o sistema de arquivos), porque isso resulta no Bazel não registrar a dependência de dados no arquivo lido, resultando em builds incrementais incorretas.

Quando uma função tiver dados suficientes para fazer o trabalho, ela deverá retornar um valor diferente de null indicando a conclusão.

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

• Hermeticidade. Se as funções só solicitarem dados de entrada dependendo de outros nós, o Bazel poderá garantir que, se o estado de entrada for o mesmo, os mesmos dados serão retornados. Se todas as funções do Sky forem determinísticas, isso significa que toda a build também será determinística.
• Incrementabilidade correta e perfeita. Se todos os dados de entrada de todas as funções forem registrados, o Bazel poderá invalidar apenas o conjunto exato de nós que precisam ser invalidados quando os dados de entrada mudam.
• 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 elas fossem executadas sequencialmente.

Incrementality

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 delas é ideal depende da aparência do gráfico de dependência.

• 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 que dependem transitivamente de arquivos alterados são invalidados. Isso é ideal se soubermos que o mesmo nó de nível superior será criado novamente. Observe que a invalidação de baixo para cima exige a execução de stat() em todos os arquivos de entrada da build anterior para determinar se eles foram alterados. Isso pode ser melhorado usando inotify ou um mecanismo semelhante para saber sobre arquivos alterados.

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

No momento, só fazemos a invalidação de baixo para cima.

Para aumentar a incrementabilidade, usamos a poda de mudanças: se um nó for invalidado, mas, após a recriação, for descoberto que o novo valor é o mesmo que o antigo, os nós que foram invalidados devido a uma mudança nesse nó serão "ressuscitados".

Isso é útil, por exemplo, se você mudar um comentário em um arquivo C++: o arquivo .o gerado a partir dele será o mesmo. Portanto, não precisamos chamar o vinculador novamente.

Vinculação / compilaçã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 recriado do zero, mesmo que exista um algoritmo melhor que modifique 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, podemos modificar o arquivo .jar em vez de criá-lo do zero novamente.

O motivo pelo qual o Bazel não oferece suporte a essas coisas de maneira fundamentada (temos algum suporte para vinculação incremental, mas não está implementado no Skyframe) é duplo: só tivemos ganhos de performance limitados e era difícil garantir que o resultado da mutação fosse o mesmo de uma recriação limpa, e o Google valoriza builds que são repetíveis bit a bit.

Até agora, sempre conseguimos uma performance boa o suficiente simplesmente decompondo uma etapa de build cara e alcançando uma reavaliação parcial dessa forma: ela divide todas as classes em um app em vários grupos e faz a dexagem separadamente. Dessa forma, se as classes em um grupo não mudarem, a dexagem não precisará ser refeita.

Mapeamento para conceitos do Bazel

Esta é uma visão geral de algumas das implementações de SkyFunction que o Bazel usa para realizar uma build:

• FileStateValue. O resultado de um lstat(). Para arquivos existentes, também calculamos informações adicionais para detectar mudanças no arquivo. Esse é o nó de nível mais baixo no gráfico do Skyframe e não tem dependências.
• FileValue. Usado por qualquer coisa que se preocupe com o conteúdo real e/ou o caminho resolvido de um arquivo. Depende do FileStateValue correspondente e de todos os links simbólicos que precisam ser resolvidos (como 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 (por exemplo, ao avaliar globos do sistema de arquivos, como srcs=glob(["*/*.java"])), o conteúdo do arquivo não é realmente necessário.
• DirectoryListingValue. Essencialmente 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 transitivamente de qualquer DirectoryListingValue usado para resolver os globos no pacote (a estrutura de dados que representa o conteúdo de um arquivo BUILD internamente).
• ConfiguredTargetValue. Representa um destino configurado, que é uma tupla do conjunto de ações geradas durante a análise de um destino e informações fornecidas a destinos configurados que dependem desse. Depende do PackageValue em que o destino correspondente está, dos ConfiguredTargetValues de dependências diretas e de um nó especial que representa a configuração do build.
• ArtifactValue. Representa um arquivo na build, seja uma origem ou um artefato de saída (os 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, ele depende do FileValue do nó associado. Para artefatos de saída, ele depende do ActionExecutionValue de qualquer ação que gere o artefato.
• ActionExecutionValue. Representa a execução de uma ação. Depende dos ArtifactValues dos arquivos de entrada. A ação que ele executa está contida na chave do céu, o que é contrário ao conceito de que as chaves do céu devem 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.