Skyframe

La evaluación paralela y el modelo de incrementalidad de Bazel.

Modelo de datos

El modelo de datos consta de los siguientes elementos:

  • SkyValue: También se denominan nodos. Las SkyValues son objetos inmutables que contienen todos los datos compilados durante la compilación y las entradas de esta. Algunos ejemplos son los archivos de entrada y de salida, y los objetivos y los destinos configurados.
  • SkyKey. Es un nombre inmutable corto para hacer referencia a SkyValue, por ejemplo, FILECONTENTS:/tmp/foo o PACKAGE://foo.
  • SkyFunction. Compila nodos según sus claves y nodos dependientes.
  • Gráfico de nodos Es una estructura de datos que contiene la relación de dependencia entre los nodos.
  • Skyframe: Es el nombre de código del framework de evaluación incremental en el que se basa Bazel.

Evaluación

Una compilación consiste en evaluar el nodo que representa la solicitud de compilación (este es el estado por el que nos esforzamos, pero hay mucho código heredado). Primero, se encuentra su SkyFunction y se lo llama con la clave del SkyKey de nivel superior. Luego, la función solicita la evaluación de los nodos que necesita para evaluar el nodo de nivel superior, lo que, a su vez, genera otras invocaciones de funciones y así sucesivamente hasta llegar a los nodos de hoja (que suelen ser nodos que representan archivos de entrada en el sistema de archivos). Por último, obtenemos el valor del SkyValue de nivel superior, algunos efectos secundarios (como los archivos de salida en el sistema de archivos) y un grafo acíclico dirigido de las dependencias entre los nodos involucrados en la compilación.

Un SkyFunction puede solicitar SkyKeys en varios pases si no puede identificar con anticipación todos los nodos que necesita para hacer su trabajo. Un ejemplo simple es evaluar un nodo de archivo de entrada que resulta ser un symlink: la función intenta leer el archivo, detecta que es un symlink y, por lo tanto, recupera el nodo del sistema de archivos que representa el destino del symlink. Sin embargo, puede ser un symlink, en cuyo caso la función original también necesitará recuperar su destino.

La interfaz SkyFunction representa las funciones en el código y los servicios que se le proporcionan a través de una interfaz llamada SkyFunction.Environment. Estas son las acciones que pueden realizar las funciones:

  • Solicita la evaluación de otro nodo mediante una llamada a env.getValue. Si el nodo está disponible, se muestra su valor; de lo contrario, se muestra null y se espera que la función en sí muestre null. En el último caso, se evalúa el nodo dependiente y, luego, se vuelve a invocar el compilador de nodos original, pero esta vez la misma llamada a env.getValue mostrará un valor que no es null.
  • Llama a env.getValues() para solicitar la evaluación de muchos otros nodos. En esencia, esto hace lo mismo, excepto que los nodos dependientes se evalúan en paralelo.
  • Realizar el procesamiento durante la invocación
  • Tener efectos secundarios, como escribir archivos en el sistema de archivos Hay que tener cuidado de que dos funciones diferentes no pisen el otro. En general, están bien los efectos secundarios de escritura (donde los datos fluyen hacia afuera de Bazel), los efectos secundarios de lectura (donde los datos fluyen hacia Bazel sin una dependencia registrada) no lo están, ya que son una dependencia no registrada y, por lo tanto, pueden causar compilaciones incrementales incorrectas.

Las implementaciones de SkyFunction no deben acceder a los datos de ninguna manera que no sea solicitar dependencias (por ejemplo, leyendo directamente el sistema de archivos), ya que Bazel no registra la dependencia de datos en el archivo que se leyó, lo que genera compilaciones incrementales incorrectas.

Una vez que una función tenga suficientes datos para realizar su trabajo, debe mostrar un valor que no sea null que indique la finalización.

Esta estrategia de evaluación tiene los siguientes beneficios:

  • Hermeticidad. Si las funciones solo solicitan datos de entrada según otros nodos, Bazel puede garantizar que, si el estado de entrada es el mismo, se muestran los mismos datos. Si todas las funciones sky son deterministas, toda la compilación también lo será.
  • Incrementalidad correcta y perfecta Si se registran todos los datos de entrada de todas las funciones, Bazel puede invalidar solo el conjunto exacto de nodos que se debe invalidar cuando cambian los datos de entrada.
  • Paralelismo Dado que las funciones solo pueden interactuar entre sí mediante la solicitud de dependencias, las funciones que no dependen unas de otras pueden ejecutarse en paralelo, y Bazel puede garantizar que el resultado sea el mismo que si se ejecutaran de forma secuencial.

Incrementalidad

Dado que las funciones solo pueden acceder a los datos de entrada según otros nodos, Bazel puede crear un gráfico de flujo de datos completo desde los archivos de entrada hasta los archivos de salida y usar esta información para volver a compilar solo los nodos que realmente necesitan reconstruirse: el cierre transitivo inverso del conjunto de archivos de entrada modificados.

En particular, existen dos estrategias de incrementalidad posibles: la de arriba abajo y la de arriba abajo. El óptimo dependerá de cómo se vea el gráfico de dependencia.

  • Durante la invalidación ascendente, después de que se compila un grafo y se conoce el conjunto de entradas modificadas, se invalidan todos los nodos que dependen de manera transitiva de los archivos modificados. Esto es óptimo si sabemos que se volverá a compilar el mismo nodo de nivel superior. Ten en cuenta que la invalidación de abajo hacia arriba requiere que se ejecute stat() en todos los archivos de entrada de la compilación anterior para determinar si se modificaron. Esto se puede mejorar usando inotify o un mecanismo similar para aprender sobre los archivos modificados.

  • Durante la invalidación de arriba abajo, se verifica el cierre transitivo del nodo de nivel superior y solo se conservan los nodos cuyo cierre transitivo está limpio. Esto es mejor si sabemos que el gráfico de nodos actual es grande, pero solo necesitamos un pequeño subconjunto de él en la próxima compilación: la invalidación ascendente invalidaría el grafo más grande de la primera compilación, a diferencia de la invalidación de arriba hacia abajo, que simplemente recorre el grafo pequeño de la segunda compilación.

Por el momento, solo realizamos la invalidación de abajo hacia arriba.

Para obtener una mayor incrementalidad, usamos la reducción de cambios: si se invalida un nodo, pero se vuelve a compilar, se descubre que su valor nuevo es el mismo que el anterior, se “resucitan” los nodos que se invalidaron debido a un cambio en este nodo.

Esto resulta útil, por ejemplo, si se cambia un comentario en un archivo C++: el archivo .o generado a partir de ese archivo será el mismo y, por lo tanto, no es necesario volver a llamar al vinculador.

Compilación o vinculación incremental

La principal limitación de este modelo es que la invalidación de un nodo es todo o nada: cuando cambia una dependencia, el nodo dependiente siempre se vuelve a compilar desde cero, incluso si existiera un mejor algoritmo que mutaría el valor anterior del nodo en función de los cambios. Estos son algunos ejemplos en los que podría ser útil:

  • Vinculación incremental
  • Cuando un solo archivo .class cambia en un .jar, en teoría, podríamos modificar el archivo .jar en lugar de volver a compilarlo desde cero.

El motivo por el que Bazel actualmente no admite estas funciones con principios (ya que tenemos cierto grado de compatibilidad con la vinculación incremental, pero no se implementa dentro de Skyframe) es doble: solo tuvimos ganancias de rendimiento limitadas y era difícil garantizar que el resultado de la mutación sea el mismo que el de una recompilación limpia, y las compilaciones de valores de Google se repiten un poco por bits.

Hasta ahora, siempre podíamos lograr un rendimiento lo suficientemente bueno con solo descomponer un paso de compilación costoso y realizar una reevaluación parcial de esa manera: divide todas las clases de una app en varios grupos y realiza la conversión a DEX en ellas por separado. De esta manera, si las clases de un grupo no cambian, no es necesario volver a realizar la conversión a dex.

Asigna a conceptos de Bazel

Esta es una descripción general de algunas de las implementaciones de SkyFunction que Bazel usa para realizar una compilación:

  • FileStateValue. Es el resultado de un elemento lstat(). En el caso de los archivos existentes, también procesamos información adicional para detectar cambios en el archivo. Este es el nodo de nivel más bajo del gráfico de Skyframe y no tiene dependencias.
  • FileValue Lo usa todo lo que tenga interés en el contenido real o la ruta resuelta de un archivo. Depende del FileStateValue correspondiente y de cualquier symlink que se deban resolver (como FileValue para a/b, necesita la ruta resuelta de a y la ruta resuelta de a/b). La distinción entre FileStateValue es importante porque, en algunos casos (por ejemplo, evaluar los globs del sistema de archivos (como srcs=glob(["*/*.java"])) el contenido del archivo no es realmente necesario).
  • DirectoryListingValue En esencia, es el resultado de readdir(). Depende del FileValue asociado con el directorio.
  • PackageValue. Representa la versión analizada de un archivo BUILD. Depende del FileValue del archivo BUILD asociado y, de forma transitiva, de cualquier DirectoryListingValue que se use para resolver los globs en el paquete (la estructura de datos que representa el contenido de un archivo BUILD de forma interna)
  • ConfiguredTargetValue Representa un destino configurado, que es una tupla del conjunto de acciones generadas durante el análisis de un objetivo y la información proporcionada a los destinos configurados que dependen de este. Depende del PackageValue en el que se encuentra el destino correspondiente, del ConfiguredTargetValues de las dependencias directas y de un nodo especial que representa la configuración de compilación.
  • ArtifactValue. Representa un archivo de la compilación, ya sea una fuente o un artefacto de salida (los artefactos son casi equivalentes a los archivos y se usan para hacer referencia a ellos durante la ejecución real de los pasos de compilación). En el caso de los archivos de origen, depende del FileValue del nodo asociado. En el caso de los artefactos de salida, depende del ActionExecutionValue de la acción que genere el artefacto.
  • ActionExecutionValue Representa la ejecución de una acción. Depende del ArtifactValues de sus archivos de entrada. La acción que ejecuta está actualmente dentro de su clave de cielo, lo que contradice el concepto de que las claves de cielo deben ser pequeñas. Estamos trabajando para resolver esta discrepancia (ten en cuenta que ActionExecutionValue y ArtifactValue no se usan si no ejecutamos la fase de ejecución en Skyframe).