Envision VM (parte 3), Atomi e Archiviazione dei Dati

Victor Nicollet

Questo articolo è il terzo di una serie di quattro parti sulle dinamiche interne della macchina virtuale Envision: il software che esegue gli script Envision. Vedi parte 1, parte 2 e parte 4. Questa serie non copre il compilatore Envision (forse in futuro), quindi assumiamo semplicemente che lo script sia stato convertito in bytecode che la macchina virtuale Envision prende in input.

Durante l’esecuzione, le thunk leggono dati di input e scrivono dati di output, spesso in grandi quantità.

• Un miliardo di booleani (un bit per valore) occupa 125 MB.
• Un miliardo di numeri in virgola mobile (precisione a 32 bit) occupa 4 GB.
• Un miliardo di righe di vendita minime (data, posizione, EAN-13, quantità) occupa tra 14 GB e 33 GB (o più!) a seconda di come i valori sono codificati.

Ciò crea due sfide: come preservare questi dati dal momento in cui vengono creati fino al momento in cui vengono utilizzati (parte della risposta è: su unità NVMe distribuite su più macchine) e come ridurre al minimo la quantità di dati che passa attraverso canali più lenti della RAM (rete e archiviazione persistente).

Livello dei Metadati

Una parte della soluzione consiste nell’avere due livelli di dati separati, con i dati che vengono inseriti in uno dei due livelli in base alla loro natura. Il livello dei metadati contiene informazioni sui dati effettivi e sugli script in esecuzione:

• Quando una thunk ha restituito con successo dei dati, l’identificatore univoco di tali dati viene conservato in questo livello.
• Quando una thunk ha fallito, i messaggi di errore prodotti dalla thunk vengono conservati in questo livello.
• Quando una thunk ha restituito una nuova thunk (e il DAG dei suoi genitori), il DAG serializzato viene conservato in questo livello.
• Una thunk può salvare checkpoint nel livello dei metadati (di solito costituito da un blocco di identificatori dei dati); se una thunk viene interrotta prima di essere completata, può quindi caricare il suo checkpoint dal livello dei metadati e riprendere il lavoro da quella posizione.

In altre parole, il livello dei metadati può essere visto come un dizionario che mappa le thunk ai risultati, dove la natura esatta del risultato dipende da ciò che la thunk ha effettivamente restituito.

Il livello dei metadati può anche contenere informazioni aggiuntive sulla struttura dei dati a cui si fa riferimento. Ad esempio, se una thunk ha restituito una coppia di vettori, allora i metadati conterranno l’identificatore univoco di ciascun vettore. Ciò consente ai consumatori di accedere a un vettore senza dover caricare entrambi.

Ci sono due limiti sui valori memorizzati nel livello dei metadati: una voce non può superare i 10 MB (quindi un DAG serializzato non può superare questa quantità!) e lo spazio di archiviazione totale per il livello dei metadati è di 1,5 GB. Di solito, in questo livello ci sono circa un milione di valori, per una dimensione media delle voci di 1,5 KB.

Il livello dei metadati vive sempre nella RAM per garantire un accesso rapido. Agisce come la fonte di verità per l’esecuzione delle thunk: una thunk è stata eseguita se e solo se c’è un risultato associato a quella thunk nel livello dei metadati, anche se ciò non garantisce che i dati a cui fa riferimento quel risultato siano disponibili.

Ogni worker nel cluster mantiene la propria copia del livello dei metadati. Il worker trasmette ogni modifica a questo livello (causata dall’esecuzione delle thunk locali) a tutti gli altri worker nel cluster e anche allo scheduler. Questo avviene su base “best effort”: se un messaggio di trasmissione non raggiunge la sua destinazione, viene scartato¹ senza un nuovo tentativo.

Ogni secondo, il livello dei metadati viene salvato su disco in modo incrementale. In caso di arresto anomalo o riavvio, il worker impiegherà uno o due secondi per ricaricare l’intero livello da disco per ricordare cosa stava facendo.

Mantenere grandi database in memoria

Come accennato in precedenza, il livello dei metadati può contenere un milione di voci. Ciascun DAG individuale può contenere centinaia di migliaia di nodi. Tutti questi hanno una lunga durata—da minuti a ore. Mantenere milioni di oggetti a lunga durata in memoria è abbastanza difficile per il garbage collector di .NET.

La garbage collection in .NET è un argomento complesso (anche se c’è una serie eccellente di Konrad Kokosa per approfondire i dettagli a basso livello), ma il problema generale è una combinazione di tre fatti:

• Il costo delle prestazioni di un passaggio di garbage collection è proporzionale al numero di oggetti vivi nell’area di memoria in cui viene eseguita la garbage collection. Elaborare milioni di oggetti, spesso con miliardi di riferimenti da seguire tra di loro, richiederà al garbage collector diversi secondi per essere elaborato.
• Per evitare di pagare questo costo, il garbage collector di .NET lavora con aree separate di memoria, chiamate generazioni, a seconda dell’età degli oggetti al loro interno. La generazione più giovane, Gen0, viene sottoposta frequentemente a garbage collection ma contiene solo gli oggetti allocati dall’ultimo passaggio (quindi, solo pochi). La generazione più vecchia, Gen2, viene raccolta solo se sia Gen1 che Gen0 sono state raccolte ma non sono riuscite a restituire memoria sufficiente. Questo sarà piuttosto raro fintanto che la maggior parte delle allocazioni di oggetti sono di piccole dimensioni e di breve durata.
• Tuttavia, un’operazione di thunk normale coinvolge grandi array di valori, che vengono allocati nell’Large Object Heap, un’area separata da Gen0, Gen1 e Gen2. Quando l’Large Object Heap si esaurisce, viene eseguita una garbage collection completa, che raccoglie anche Gen2.

E Gen2 è dove sono situati i milioni di oggetti dei DAG e del livello dei metadati.

Per evitare ciò, abbiamo costruito sia i DAG che il livello dei metadati in modo da utilizzare solo pochissimi oggetti.

Ogni DAG è composto solo da due allocazioni—un array di nodi e un array di archi, entrambi di tipo valore non gestito, in modo che il GC non debba nemmeno attraversare il loro contenuto per seguire eventuali riferimenti che possono contenere. Quando una thunk è necessaria per essere eseguita, viene deserializzata dalla rappresentazione binaria del DAG², che è presente nel livello dei metadati.

Il livello dei metadati ha contenuti di lunghezza variabile, quindi viene costruito intagliando porzioni di un grande byte[], utilizzando ref struct e MemoryMarshal.Cast per manipolare i dati senza copiarli.

Spazio di lavoro temporaneo

Un cluster dispone di una RAM compresa tra 512GiB e 1,5TiB e di uno spazio di archiviazione NVMe compreso tra 15,36TB e 46,08TB. La maggior parte di questo spazio è dedicata alla memorizzazione dei risultati intermedi della valutazione del thunk.

La RAM è una risorsa preziosa: rappresenta solo il 3% dello spazio di archiviazione disponibile, ma è tra 100 e 1000 volte più veloce da leggere e scrivere. È vantaggioso assicurarsi che i dati che stanno per essere letti da una thunk siano già presenti in memoria (o non abbiano mai lasciato la memoria in primo luogo).

Inoltre, è quasi impossibile utilizzare il 100% della RAM disponibile in .NET—il sistema operativo ha esigenze di memoria variabili e non ha un modo affidabile per comunicare al processo .NET che dovrebbe rilasciare parte della memoria, il che comporta l’uccisione del processo per mancanza di memoria (out-of-memory).

Envision risolve questo problema delegando la gestione dei trasferimenti RAM-NVMe al sistema operativo. Abbiamo reso open source questo codice come Lokad.ScratchSpace. Questa libreria mappa in memoria tutto lo spazio di archiviazione disponibile sui dischi NVMe e lo espone come un archivio di blob che l’applicazione può utilizzare per:

1. scrivere blocchi di dati (fino a 2GB ciascuno) nello spazio di lavoro temporaneo, direttamente o serializzando da un oggetto gestito. Questa operazione restituisce un identificatore di blocco.
2. leggere blocchi di dati utilizzando i loro identificatori. Questa operazione blocca il blocco e lo espone all’applicazione come un ReadOnlySpan<byte>, che l’applicazione dovrebbe quindi copiare (o deserializzare) nella memoria gestita.

Una volta che lo spazio di lavoro temporaneo è pieno, i blocchi più vecchi vengono eliminati per fare spazio ai nuovi dati. Ciò significa che è possibile che un’operazione di lettura fallisca se l’identificatore punta a un blocco che è stato eliminato, ma questo è un evento raro durante l’esecuzione di uno script Envision—raramente una singola esecuzione produce decine di terabyte. D’altra parte, ciò potrebbe impedire a una nuova esecuzione di riutilizzare i risultati di una precedente.

La chiave per utilizzare uno spazio di lavoro temporaneo mappato in memoria è che la RAM disponibile è distribuita tra tre tipi di pagine³: memoria che appartiene ai processi (come il processo .NET di Envision), memoria che è una copia esatta byte per byte di una porzione di un file su disco e memoria che è destinata a essere scritta su un file su disco.

La memoria che è una copia di un file su disco può essere rilasciata in qualsiasi momento dal sistema operativo e utilizzata per un altro scopo—per essere data a un processo per il suo utilizzo o per diventare una copia di un’altra porzione di un file su disco. Sebbene non sia istantaneo, queste pagine agiscono come un buffer di memoria che può essere rapidamente riassegnato a un altro utilizzo. E finché non vengono riassegnate, il sistema operativo sa che contengono una copia di una specifica regione di memoria persistente e quindi qualsiasi richiesta di lettura per quella regione verrà reindirizzata alla pagina esistente, evitando così di dover caricare i dati dal disco.

La memoria destinata a essere scritta su disco verrà alla fine scritta e diventerà una copia della regione in cui è stata scritta. Questa conversione è limitata dalla velocità di scrittura delle unità NVMe (dell’ordine di 1 GB/s).

La memoria assegnata al processo non può essere convertita nuovamente nei due altri tipi senza essere rilasciata dal processo (cosa che il GC di .NET farà a volte, dopo che una raccolta ha rilasciato una grande quantità di memoria). Tutta la memoria allocata tramite .NET, inclusi tutti gli oggetti gestiti e tutto ciò che il GC supervisiona, deve appartenere a questo tipo di memoria.

In un lavoratore tipico, il 25% della memoria è assegnato direttamente al processo .NET, il 70% è una copia in sola lettura delle regioni dei file e il 5% è in fase di scrittura.

Strato Atom

Il principio generale è che ogni thunk scrive il suo output nello spazio di lavoro temporaneo come uno o più atom, quindi memorizza gli identificatori di questi atom nello strato dei metadati. I thunk successivi caricano quindi questi identificatori dallo strato dei metadati e li utilizzano per interrogare lo spazio di lavoro temporaneo per gli atom di cui hanno bisogno.

Il nome «Atom» è stato scelto perché non è possibile leggere solo una parte di un atom: possono essere recuperati solo nella loro interezza. Se una struttura dati deve supportare la richiesta di solo una parte dei suoi contenuti, la salviamo invece come più atom, che possono poi essere recuperati indipendentemente.

Alcuni atom sono compressi; ad esempio, la maggior parte dei vettori booleani non è rappresentata come bool[], che consuma un byte per elemento, ma è invece compattata a 1 bit per valore e quindi compressa per eliminare lunghe sequenze di valori identici.

È possibile che gli atom scompaiano, anche se questo è un evento raro. Le due principali situazioni in cui ciò può accadere sono quando lo strato dei metadati ricorda un risultato da una precedente esecuzione, ma l’atom corrispondente è stato eliminato dallo spazio di lavoro temporaneo nel frattempo, e quando l’atom era memorizzato su un diverso lavoratore che non risponde più alle richieste. Meno frequentemente, un errore di checksum rivela che i dati memorizzati non sono più validi e devono essere eliminati.

Quando un atom scompare, il thunk che lo ha richiesto viene interrotto e entra in modalità di ripristino:

1. Il sistema verifica la presenza (ma non i checksum) di tutti gli altri atom a cui il thunk fa riferimento come input. Questo perché gli atom sono probabilmente generati contemporaneamente e sullo stesso lavoratore, e la scomparsa di un atom è correlata alla scomparsa di altri atom dello stesso periodo e luogo.
2. Il sistema esamina lo strato dei metadati per i riferimenti a uno qualsiasi degli atom scoperti come mancanti durante il passaggio precedente. Ciò farà sì che alcuni thunk tornino da “eseguiti” a “non ancora eseguiti” perché il loro risultato è stato scartato. Il kernel lo rileverà quindi e li pianificherà nuovamente.

I thunk ri-eseguiti produrranno quindi nuovamente l’atom e l’esecuzione può riprendere.

Array di Atom

Un aspetto particolare dello strato degli atomi è il modo in cui vengono eseguite le shuffle: uno strato iniziale di $M$ thunk produce ciascuno diversi milioni di righe di dati, e poi uno strato successivo di $N$ thunk legge l’output dello strato precedente per eseguire un’altra operazione (di solito una forma di riduzione), ma ogni singola riga dello strato iniziale viene letta solo da un thunk dello strato successivo.

Sarebbe molto spregevole che ogni thunk dello strato successivo leggesse tutti i dati dello strato iniziale (ogni riga verrebbe letta $N$ volte, di cui $N-1$ sarebbero superflue), ma questo è esattamente ciò che accadrebbe se ogni thunk dello strato iniziale producesse esattamente un atom.

D’altra parte, se ogni thunk dello strato iniziale producesse un atom per ogni thunk dello strato successivo, l’operazione di shuffle coinvolgerebbe un totale di $M\cdot N$ atomi, ovvero un milione di atomi per $M = N = 1000$. Sebbene il sovraccarico sugli atomi non sia eccessivo, sommando un identificatore di atomi, un identificatore di tenant, un tipo di dato di atomi, una dimensione e un po’ di contabilità, può ancora raggiungere qualche centinaio di byte per atomi. Mentre 100MB possono sembrare un prezzo piccolo da pagare per spostare circa 4GB di dati effettivi, quei dati effettivi vivono nello strato degli atomi (che è progettato per dati di grandi dimensioni), mentre 100MB rappresentano una parte considerevole del budget totale di 1.5GB dello strato dei metadati.

Per aggirare questo problema, Envision supporta gli array di atomi:

• Tutti gli atomi in un array di atomi vengono scritti contemporaneamente e vengono mantenuti insieme sia in memoria che su disco.
• Dato l’identificatore dell’array di atomi, è facile derivare l’identificatore dell’i-esimo atomo nell’array.

Grazie a questo, un array di atomi ha lo stesso sovraccarico di un singolo atomo. In una shuffle, i thunk dello strato iniziale produrrebbero $M$ array di $N$ atomi ciascuno. I thunk dello strato successivo richiederebbero ciascuno $M$ atomi, uno da ciascun array, nella posizione corrispondente al rango di quel thunk nella shuffle.

In conclusione, alcune statistiche di produzione! In un’ora, un lavoratore tipico eseguirà 150 000 thunk e scriverà 200 000 atomi (gli array di atomi vengono contati solo una volta) che rappresentano 750GiB di dati intermedi.

Nel prossimo e ultimo articolo di questa serie, discuteremo degli strati che consentono l’esecuzione distribuita.

Pubblicità sfacciata: stiamo assumendo ingegneri del software. È possibile lavorare in remoto.