Envision VM (parte 3), Átomos y Almacenamiento de Datos

Victor Nicollet

Este artículo es el tercero de una serie de cuatro partes sobre el funcionamiento interno de la máquina virtual Envision: el software que ejecuta los scripts de Envision. Consulta parte 1, parte 2 y parte 4. Esta serie no cubre el compilador de Envision (tal vez en otro momento), así que supongamos que el script se ha convertido de alguna manera en el bytecode que la máquina virtual de Envision toma como entrada.

Durante la ejecución, los thunks leen datos de entrada y escriben datos de salida, a menudo en grandes cantidades.

• Mil millones de booleanos (un bit por valor) ocupan 125 MB.
• Mil millones de números de punto flotante (precisión de 32 bits) ocupan 4 GB.
• Mil millones de líneas de ventas mínimas (fecha, ubicación, EAN-13, cantidad) ocupan entre 14 GB y 33 GB (¡o más!) dependiendo de cómo se codifiquen los valores.

Esto crea dos desafíos: cómo preservar estos datos desde el momento en que se crean hasta que se utilizan (parte de la respuesta es: en unidades NVMe distribuidas en varias máquinas) y cómo minimizar la cantidad de datos que pasan por canales más lentos que la RAM (red y almacenamiento persistente).

Capa de Metadatos

Una parte de la solución es tener dos capas de datos separadas, donde los datos se empujan a una de las dos capas según su naturaleza. La capa de metadatos contiene información sobre los datos reales y sobre los scripts que se están ejecutando:

• Cuando un thunk ha devuelto datos correctamente, se guarda el identificador único de esos datos en esta capa.
• Cuando un thunk ha fallado, los mensajes de error producidos por el thunk se guardan en esta capa.
• Cuando un thunk ha devuelto un nuevo thunk (y el DAG de sus padres), el DAG serializado se guarda en esta capa.
• Un thunk puede guardar puntos de control en la capa de metadatos (generalmente consiste en el identificador de un bloque de datos); si un thunk se interrumpe antes de completarse, puede cargar su punto de control desde la capa de metadatos y reanudar el trabajo desde esa posición.

En otras palabras, la capa de metadatos se puede ver como un diccionario que asigna thunks a resultados, donde la naturaleza exacta del resultado depende de lo que el thunk haya devuelto en realidad.

La capa de metadatos también puede contener información adicional sobre la estructura de los datos a los que se hace referencia. Por ejemplo, si un thunk ha devuelto un par de vectores, entonces los metadatos contendrán el identificador único de cada vector. Esto permite que los consumidores accedan a un vector sin tener que cargar ambos.

Hay dos límites en los valores almacenados en la capa de metadatos: una entrada no puede superar los 10 MB (por lo que un DAG serializado tampoco puede superar esta cantidad) y el espacio total de almacenamiento para la capa de metadatos es de 1.5 GB. Por lo general, hay alrededor de un millón de valores en esta capa, con un tamaño promedio de entrada de 1.5 KB.

La capa de metadatos siempre reside en la RAM para garantizar un acceso rápido. Actúa como la fuente de verdad para la ejecución de thunks: un thunk se ha ejecutado si, y solo si, hay un resultado asociado a ese thunk en la capa de metadatos, aunque esto no garantiza que los datos a los que hace referencia ese resultado estén disponibles.

Cada trabajador en el clúster mantiene su propia copia de la capa de metadatos. El trabajador transmite cada cambio en esta capa (causado por la ejecución de thunks locales) a todos los demás trabajadores en el clúster, así como al planificador. Esto se hace de manera “mejor esfuerzo”: si un mensaje de transmisión no llega a su destino, se descarta¹ sin intentar de nuevo.

Cada segundo, la capa de metadatos se guarda en disco de forma incremental. En caso de un fallo o reinicio, el trabajador tardará uno o dos segundos en volver a cargar toda la capa desde el disco para recordar lo que estaba haciendo.

Mantener grandes bases de datos en memoria

Como se mencionó anteriormente, la capa de metadatos puede contener un millón de entradas. Cada DAG individual puede contener cientos de miles de nodos. Todos estos tienen largas vidas, desde minutos hasta horas. Mantener millones de objetos de larga duración en memoria es bastante difícil para el recolector de basura de .NET.

La recolección de basura en .NET es un tema complejo (aunque hay una excelente serie de Konrad Kokosa para profundizar en los detalles de bajo nivel), pero el problema general es una combinación de tres hechos:

• El costo de rendimiento de un pase de recolección de basura es proporcional al número de objetos vivos en el área de memoria que se está recolectando. Procesar millones de objetos, a menudo con miles de millones de referencias para seguir entre ellos, llevará varios segundos al recolector de basura para procesar.
• Para evitar pagar este costo, el recolector de basura de .NET trabaja con áreas separadas de memoria, llamadas generaciones, dependiendo de la edad de los objetos que contienen. La generación más joven, Gen0, se somete a recolección de basura con frecuencia, pero solo contiene objetos asignados desde el último pase (es decir, solo unos pocos). La generación más antigua, Gen2, solo se recolecta si tanto Gen1 como Gen0 se recolectaron pero no se obtuvo suficiente memoria libre. Esto será bastante raro siempre y cuando la mayoría de las asignaciones de objetos sean pequeñas y de corta duración.
• Sin embargo, una operación de thunk normal implica grandes matrices de valores, que se asignan en el montón de objetos grandes (Large Object Heap), un área separada de Gen0, Gen1 y Gen2. Cuando el montón de objetos grandes se queda sin espacio, se realiza una recolección de basura completa, que también recoge Gen2.

Y Gen2 es donde se encuentran los millones de objetos de los DAG y la capa de metadatos.

Para evitar esto, hemos construido tanto los DAG como la capa de metadatos para que utilicen muy pocos objetos.

Cada DAG consta solo de dos asignaciones: una matriz de nodos y una matriz de aristas, ambas de las cuales son tipos de valor no administrados, por lo que el recolector de basura ni siquiera necesita recorrer su contenido para seguir cualquier referencia que puedan contener. Cuando se necesita un thunk para ser ejecutado, se deserializa a partir de la representación binaria del DAG², que está presente en la capa de metadatos.

La capa de metadatos tiene contenido de longitud variable, por lo que se construye tallando fragmentos de un gran byte[], utilizando ref struct y MemoryMarshal.Cast para manipular los datos sin copiarlos.

Espacio de rascado

Un clúster tiene entre 512GiB y 1.5TiB de RAM, y entre 15.36TB y 46.08TB de almacenamiento NVMe. La mayor parte de este espacio se dedica a almacenar los resultados intermedios de la evaluación de los thunks.

La RAM es un bien inmueble valioso: representa solo el 3% del espacio de almacenamiento disponible, pero es entre 100 y 1000 veces más rápido para leer y escribir. Existe un beneficio significativo en asegurarse de que los datos que están a punto de ser leídos por un thunk ya estén presentes en la memoria (o que nunca hayan salido de la memoria en primer lugar).

Además, es casi imposible utilizar el 100% de la RAM disponible en .NET, ya que el sistema operativo tiene necesidades de memoria variables y no tiene una forma confiable de comunicarse con el proceso de .NET para indicarle que debe liberar algo de memoria, lo que resulta en que el proceso sea asesinado por falta de memoria (out-of-memory).

Envision resuelve este problema delegando la gestión de las transferencias de RAM a NVMe al sistema operativo. Hemos publicado este código como Lokad.ScratchSpace. Esta biblioteca asigna memoria a todo el espacio de almacenamiento disponible en las unidades NVMe y lo expone como un almacén de blobs que la aplicación puede utilizar para:

1. escribir bloques de datos (hasta 2GB cada uno) en el espacio de rascado, ya sea directamente o mediante la serialización desde un objeto administrado. Esta operación devuelve un identificador de bloque.
2. leer bloques de datos utilizando sus identificadores. Esta operación fija el bloque y lo expone a la aplicación como un ReadOnlySpan<byte>, que la aplicación debe copiar (o deserializar) a la memoria administrada.

Una vez que el espacio de rascado está lleno, los bloques más antiguos se descartan para dejar espacio para nuevos datos. Esto significa que es posible que una operación de lectura falle si el identificador apunta a un bloque que ha sido eliminado, pero esto es una ocurrencia rara durante la ejecución de un script de Envision. Rara vez una sola ejecución produce decenas de terabytes. Por otro lado, esto puede evitar que una nueva ejecución reutilice los resultados de una ejecución anterior.

La clave para utilizar un espacio de rascado mapeado en memoria es que la RAM disponible se distribuye entre tres tipos de páginas³: memoria que pertenece a procesos (como el proceso .NET de Envision), memoria que es una copia exacta byte a byte de una porción de un archivo en disco y memoria que está destinada a ser escrita en un archivo en disco.

La memoria que es una copia de un archivo en disco puede ser liberada en cualquier momento por el sistema operativo y utilizada para otro propósito, ya sea para ser entregada a un proceso para su propio uso o para convertirse en una copia de otra porción de un archivo en disco. Si bien no es instantáneo, estas páginas actúan como un búfer de memoria que se puede reasignar rápidamente para otro uso. Y hasta que se vuelvan a asignar, el sistema operativo sabe que contienen una copia de una región específica de memoria persistente, por lo que cualquier solicitud de lectura para esa región se redirigirá a la página existente, lo que no requerirá ninguna carga desde el disco.

La memoria que está destinada a ser escrita en disco eventualmente será escrita y se convertirá en una copia de la región donde se escribió. Esta conversión está limitada por la velocidad de escritura de las unidades NVMe (del orden de 1GB/s).

La memoria asignada al proceso no se puede convertir de nuevo en los otros dos tipos sin ser liberada por el proceso (lo cual el GC de .NET a veces hace después de que una recolección haya liberado una gran cantidad de memoria). Toda la memoria asignada a través de .NET, incluidos todos los objetos administrados y todo lo que supervisa el GC, debe pertenecer a este tipo de memoria.

En un trabajador típico, el 25% de la memoria se asigna directamente al proceso .NET, el 70% es una copia de solo lectura de las regiones de archivos y el 5% se está escribiendo.

Capa de Átomos

El principio general es que cada thunk escribe su salida en el espacio de rascado como uno o más átomos, luego almacena los identificadores de esos átomos en la capa de metadatos. Los thunks subsiguientes luego cargan estos identificadores desde la capa de metadatos y los utilizan para consultar el espacio de rascado en busca de los átomos que necesitan.

El nombre «Átomo» se eligió porque no es posible leer solo una parte de un átomo: solo se pueden recuperar en su totalidad. Si una estructura de datos necesita admitir la solicitud de solo una parte de su contenido, en su lugar la guardamos como múltiples átomos, que luego se pueden recuperar de forma independiente.

Algunos átomos están comprimidos; por ejemplo, la mayoría de los vectores booleanos no se representan como bool[], que consume un byte por elemento, sino que se compactan a 1 bit por valor y luego se comprimen para eliminar secuencias largas de valores idénticos.

Es posible que los átomos desaparezcan, aunque esto es una ocurrencia rara. Las dos situaciones principales en las que esto puede ocurrir es cuando la capa de metadatos recuerda un resultado de una ejecución anterior, pero el átomo correspondiente fue expulsado del espacio de rascado en el ínterin, y cuando el átomo se almacenó en un trabajador diferente que ya no responde a las solicitudes. Con menos frecuencia, un error de suma de comprobación revela que los datos almacenados ya no son válidos y deben descartarse.

Cuando un átomo desaparece, el thunk que lo solicitó se interrumpe y entra en modo de recuperación:

1. El sistema verifica la presencia (pero no las sumas de comprobación) de todos los demás átomos a los que hace referencia la entrada del thunk. Esto se debe a que es probable que los átomos se generen al mismo tiempo y en el mismo trabajador, y la desaparición de un átomo está correlacionada con la desaparición de otros átomos de alrededor del mismo tiempo y lugar.
2. El sistema busca exhaustivamente en la capa de metadatos referencias a cualquiera de los átomos que se descubrieron como faltantes durante el paso anterior. Esto hará que algunos thunks vuelvan a “no ejecutados” porque su resultado fue descartado. El kernel detectará esto y los programará nuevamente.

Los thunks que se vuelven a ejecutar producirán nuevamente el átomo y la ejecución puede continuar.

Arrays de átomos

Un aspecto particular de la capa de átomos es la forma en que se realizan las mezclas: una primera capa de $M$ thunks produce varias millones de líneas de datos, y luego una segunda capa de $N$ thunks lee la salida de la capa anterior para realizar otra operación (generalmente, alguna forma de reducción), pero cada línea de la primera capa solo es leída por un thunk de la segunda capa.

Sería muy ineficiente que cada thunk de la segunda capa leyera todos los datos de la primera capa (cada línea se leería $N$ veces, de las cuales $N-1$ serían innecesarias), pero esto es exactamente lo que sucedería si cada thunk de la primera capa produjera exactamente un átomo.

Por otro lado, si cada thunk de la primera capa produce un átomo para cada thunk de la segunda capa, la operación de mezcla implicará un total de $M\cdot N$ átomos, es decir, un millón de átomos para $M = N = 1000$. Si bien el costo adicional de los átomos no es excesivo, sumando un identificador de átomo, un identificador de inquilino, un tipo de datos de átomo, tamaño y un poco de contabilidad, aún puede alcanzar unos cientos de bytes por átomo. Si bien 100MB pueden parecer un precio pequeño a pagar para mezclar alrededor de 4GB de datos reales, esos datos reales viven en la capa de átomos (que está diseñada para datos grandes), mientras que 100MB representan una parte considerable del presupuesto total de 1.5GB de la capa de metadatos.

Para solucionar esto, Envision admite arrays de átomos:

• Todos los átomos en un array de átomos se escriben al mismo tiempo y se mantienen juntos tanto en la memoria como en el disco.
• Dado el identificador del array de átomos, es fácil derivar el identificador del átomo i-ésimo en el array.

Gracias a esto, un array de átomos tiene el mismo costo adicional que un solo átomo. En una mezcla, los thunks de la primera capa producirían $M$ arrays de $N$ átomos cada uno. Los thunks de la segunda capa solicitarían cada uno $M$ átomos, uno de cada array, en la posición correspondiente al rango de ese thunk en la mezcla.

En resumen, ¡algunas estadísticas de producción! En una hora, un trabajador típico ejecutará 150 000 thunks y escribirá 200 000 átomos (los arrays de átomos se cuentan solo una vez) que representan 750GiB de datos intermedios.

En el próximo y último artículo de esta serie, discutiremos las capas que permiten que la ejecución distribuida ocurra.

Autopromoción descarada: estamos contratando ingenieros de software. El trabajo remoto es posible.