El modelo de evaluación y incrementalidad en paralelo de Bazel.
Modelo de datos
El modelo de datos consta de los siguientes elementos:
SkyValue
. También se denominan nodos.SkyValues
son objetos inmutables que contienen todos los datos compilados durante el transcurso de la compilación y las entradas de la compilación. Algunos ejemplos son los archivos de entrada, los archivos de salida, los objetivos y los objetivos configurados.SkyKey
. Un nombre inmutable y corto para hacer referencia a unSkyValue
, por ejemplo,FILECONTENTS:/tmp/foo
oPACKAGE://foo
.SkyFunction
. Crea nodos basados en sus claves y nodos dependientes.- Gráfico de nodos. Una estructura de datos que contiene la relación de dependencia entre nodos.
Skyframe
. Nombre en código para el marco de trabajo 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 que nos esforzamos, pero hay mucho código heredado en el camino). 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, 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, terminamos con el valor de SkyValue
de nivel superior, algunos efectos secundarios (como archivos de salida en el sistema de archivos) y un grafo acíclico dirigido de las dependencias entre los nodos que participaron en la compilación.
Un SkyFunction
puede solicitar SkyKeys
en varios pases si no puede decir con anticipación todos los nodos que necesita para hacer su trabajo. Un ejemplo simple es evaluar un nodo del archivo de entrada que resulta ser un symlink: la función intenta leer el archivo, se da cuenta de que es un symlink y, por lo tanto, recupera el nodo del sistema de archivos que representa el destino del symlink. Pero ese puede ser un symlink, en cuyo caso la función original también deberá recuperar su objetivo.
Las funciones se representan en el código con la interfaz SkyFunction
y los servicios que proporciona 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 muestranull
y se espera que la función en sí muestrenull
. En el último caso, se evalúa el nodo dependiente y, luego, se invoca nuevamente al compilador de nodos original, pero esta vez la misma llamada aenv.getValue
mostrará un valor distinto denull
. - Llama a
env.getValues()
para solicitar la evaluación de varios otros nodos. Básicamente, hace lo mismo, excepto que los nodos dependientes se evalúan en paralelo. - Haz cálculos durante su invocación
- Tienen efectos secundarios, por ejemplo, escribir archivos en el sistema de archivos. Debes tener cuidado de que dos funciones diferentes no se interpongan entre sí. En general, los efectos secundarios de escritura (donde los datos fluyen hacia afuera de Bazel) son correctos; los efectos secundarios de lectura (que los datos fluyen hacia adentro sin Bazel) no lo son, 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 otra manera que no sea solicitar dependencias (como leer directamente el sistema de archivos), ya que eso hace que Bazel no registre la dependencia de datos en el archivo leído, lo que genera compilaciones incrementales incorrectas.
Una vez que una función tiene suficientes datos para hacer su trabajo, debe mostrar un valor que no sea null
que indique la finalización.
Esta estrategia de evaluación tiene una serie de beneficios:
- Hermeticidad. Si las funciones solo solicitan datos de entrada por medio de otros nodos, Bazel puede garantizar que, si el estado de la entrada es el mismo, se muestren los mismos datos. Si todas las funciones del cielo son deterministas, esto significa que toda la construcción también será determinista.
- 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 deben invalidarse 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.
Incrementality
Dado que las funciones solo pueden acceder a los datos de entrada en función de otros nodos, Bazel puede compilar un gráfico de flujo de datos completo de los archivos de entrada a los archivos de salida y usar esta información para volver a compilar los nodos que deban volver a compilarse: el cierre transitivo inverso del conjunto de archivos de entrada modificados.
En particular, existen dos estrategias de incrementalidad posibles: la de arriba hacia abajo y la de arriba hacia abajo. La forma óptima para cada caso dependerá de cómo se vea el gráfico de dependencias.
Durante la invalidación de arriba hacia abajo, después de compilar un grafo y de conocer el conjunto de entradas modificadas, se invalidan todos los nodos que dependen de forma 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 coninotify
o un mecanismo similar para obtener información sobre los archivos modificados.Durante la invalidación de arriba a 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 en la próxima compilación: la invalidación de abajo hacia arriba invalidaría el grafo más grande de la primera compilación, a diferencia de la invalidación de arriba hacia abajo, que solo camina por el pequeño gráfico de la segunda compilación.
Actualmente, solo invalidamos de abajo hacia arriba.
Para lograr una incrementalidad mayor, usamos la reducción de cambios: si se invalida un nodo, pero cuando se vuelve a compilar, se descubre que su valor nuevo es el mismo que el anterior, los nodos que se invalidaron debido a un cambio en este nodo son “resucitados”.
Esto resulta útil, por ejemplo, si se modifica un comentario en un archivo C++, entonces el archivo .o
generado a partir de este será el mismo, por lo que no es necesario volver a llamar al vinculador.
Vinculación o compilación incremental
La principal limitación de este modelo es que la invalidación de un nodo es un asunto de todo o nada: cuando una dependencia cambia, el nodo dependiente siempre se reconstruye desde cero, aunque exista un algoritmo mejor que mute el valor anterior del nodo según los cambios. Estos son algunos ejemplos útiles:
- Vinculación incremental
- Cuando cambia un solo archivo
.class
en un.jar
, podríamos, en teoría, modificar el archivo.jar
en lugar de compilarlo desde cero de nuevo.
La razón por la que Bazel actualmente no admite estas cosas de acuerdo con los principios (tenemos alguna medida de compatibilidad para la vinculación incremental, pero no se implementa dentro de Skyframe) es doble: solo obtuvimos mejoras de rendimiento limitadas y era difícil garantizar que el resultado de la mutación fuera el mismo que el de una reconstrucción limpia, y Google valora las compilaciones que se repiten bits por bit.
Hasta ahora, siempre podíamos lograr un rendimiento lo suficientemente bueno tan solo descomponiendo un paso de compilación costoso y volviendo a realizar una reevaluación parcial de esa manera: divide todas las clases de una aplicación en varios grupos y realiza la conversión a dex por separado. De esta manera, si no cambian las clases de un grupo, no es necesario rehacer la conversión a dex.
Asigna los conceptos a Bazel
Esta es una descripción general de algunas de las implementaciones de SkyFunction
que Bazel usa para realizar una compilación:
- FileStateValue. El resultado de una
lstat()
En los archivos existentes, también se procesa información adicional para detectar los cambios en el archivo. Este es el nodo de nivel más bajo en el gráfico de Skyframe y no tiene dependencias. - FileValue Lo usa cualquier cosa que le importe el contenido real o la ruta resuelta de un archivo. Depende de la
FileStateValue
correspondiente y de los symlinks que se deban resolver (comoFileValue
paraa/b
necesita la ruta resuelta dea
y la ruta resuelta dea/b
). La distinción entreFileStateValue
es importante porque, en algunos casos (por ejemplo, evaluar los globs de sistema de archivos (comosrcs=glob(["*/*.java"])
) no es necesario en realidad el contenido del archivo. - DirectoryListingValue Básicamente, el resultado de
readdir()
. Depende delFileValue
asociado con el directorio. - PackageValue. Representa la versión analizada de un archivo BUILD. Depende del
FileValue
del archivoBUILD
asociado y, de forma transitiva, de cualquierDirectoryListingValue
que se use para resolver los globs en el paquete (la estructura de datos que representa el contenido de un archivoBUILD
de forma interna). - ConfiguredTargetValue estándar. Representa un objetivo 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 encuentre el destino correspondiente, elConfiguredTargetValues
de las dependencias directas y un nodo especial que represente la configuración de compilación. - ArtifactValue. Representa un archivo en 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 estos durante la ejecución real de los pasos de la compilación). Para los archivos de origen, depende del
FileValue
del nodo asociado y, para los artefactos de salida, depende delActionExecutionValue
de la acción que genere el artefacto. - ActionExecutionValue predeterminada. Representa la ejecución de una acción. Depende del
ArtifactValues
de sus archivos de entrada. La acción que ejecuta actualmente se encuentra dentro de su clave de firma, lo cual es contrario al concepto de que las claves de firma deben ser pequeñas. Estamos trabajando para resolver esta discrepancia (ten en cuenta queActionExecutionValue
yArtifactValue
no se usan si no ejecutamos la fase de ejecución en Skyframe).