Come Roblox riduce i costi delle query Spark JOIN grazie a filtri Bloom ottimizzati tramite machine learning

Abstract

Ogni giorno su Roblox, 70 milioni di utenti interagiscono con milioni di esperienze, per un totale di 16 miliardi di ore ogni trimestre. Questa interazione genera un data lake su scala petabyte, arricchito a fini di analisi e machine learning (ML). L'unione delle tabelle di fatti e dimensioni nel nostro data lake richiede molte risorse, quindi, per ottimizzare questo processo e ridurre lo spostamento dei dati, abbiamo adottato i Learned Bloom Filters [1], strutture di dati intelligenti che utilizzano il ML. Prevedendo la presenza, questi filtri riducono notevolmente i dati di unione, migliorando l'efficienza e riducendo i costi. Nel corso del processo, abbiamo anche migliorato le nostre architetture di modello e dimostrato i notevoli vantaggi che offrono in termini di riduzione della memoria e delle ore di CPU per l'elaborazione, oltre ad aumentare la stabilità operativa.

Introduzione

Nel nostro data lake, le tabelle dei fatti e i cubi di dati sono partizionati temporalmente per un accesso efficiente, mentre le tabelle delle dimensioni non dispongono di tali partizioni e il loro join con le tabelle dei fatti durante gli aggiornamenti richiede molte risorse. Lo spazio chiave del join è determinato dal partizionamento temporale della tabella dei fatti oggetto del join. Le entità di dimensione presenti in quella partizione temporale sono un piccolo sottoinsieme di quelle presenti nell'intero set di dati delle dimensioni. Di conseguenza, la maggior parte dei dati delle dimensioni rimescolati in questi join viene alla fine scartata. Per ottimizzare questo processo e ridurre il rimescolamento non necessario, abbiamo preso in considerazione l'uso di filtri Bloom su chiavi di join distinte, ma abbiamo dovuto affrontare problemi relativi alle dimensioni del filtro e all'impronta di memoria.

Per risolverli, abbiamo esplorato i filtri Bloom appresi, una soluzione basata sul ML che riduce le dimensioni dei filtri Bloom mantenendo bassi i tassi di falsi positivi. Questa innovazione migliora l’efficienza delle operazioni di join riducendo i costi computazionali e migliorando la stabilità del sistema. Lo schema seguente illustra i processi di join convenzionali e ottimizzati nel nostro ambiente di calcolo distribuito.

Miglioramento dell'efficienza del join con i filtri Bloom appresi

Per ottimizzare il join tra le tabelle dei fatti e delle dimensioni, abbiamo adottato l'implementazione del filtro Bloom appreso. Abbiamo costruito un indice a partire dalle chiavi presenti nella tabella dei fatti e successivamente abbiamo implementato l'indice per pre-filtrare i dati delle dimensioni prima dell'operazione di join. 

Evoluzione dai filtri Bloom tradizionali ai filtri Bloom appresi

Sebbene un filtro Bloom tradizionale sia efficiente, aggiunge il 15-25% di memoria aggiuntiva per ogni nodo di lavoro che deve caricarlo per raggiungere il tasso di falsi positivi desiderato. Ma sfruttando i filtri Bloom appresi, abbiamo ottenuto una dimensione dell'indice notevolmente ridotta, mantenendo lo stesso tasso di falsi positivi. Ciò è dovuto alla trasformazione del filtro Bloom in un problema di classificazione binaria. Le etichette positive indicano la presenza di valori nell'indice, mentre quelle negative indicano la loro assenza.

L'introduzione di un modello di ML facilita il controllo iniziale dei valori, seguito da un filtro Bloom di backup per eliminare i falsi negativi. La dimensione ridotta deriva dalla rappresentazione compressa del modello e dal numero ridotto di chiavi richieste dal filtro Bloom di backup. Questo lo distingue dall'approccio convenzionale del filtro Bloom. 

Nell'ambito di questo lavoro, abbiamo stabilito due metriche per valutare il nostro approccio Learned Bloom Filter: la dimensione finale dell'oggetto serializzato dell'indice e il consumo di CPU durante l'esecuzione delle query di join. 

Affrontare le sfide di implementazione

La nostra sfida iniziale è stata quella di affrontare un set di dati di addestramento altamente sbilanciato con poche chiavi della tabella delle dimensioni nella tabella dei fatti. Nel farlo, abbiamo osservato una sovrapposizione di circa una chiave su tre tra le tabelle. Per affrontare questo problema, abbiamo sfruttato l'approccio del filtro di Bloom appreso a sandwich [2]. Questo integra un filtro di Bloom tradizionale iniziale per riequilibrare la distribuzione del set di dati rimuovendo la maggior parte delle chiavi mancanti dalla tabella dei fatti, eliminando efficacemente i campioni negativi dal set di dati. Successivamente, solo le chiavi incluse nel filtro di Bloom iniziale, insieme ai falsi positivi, sono state inoltrate al modello di ML, spesso indicato come "oracolo appreso". Questo approccio ha portato a un set di dati di addestramento ben bilanciato per l'oracolo appreso, superando efficacemente il problema della distorsione.

La seconda sfida riguardava l'architettura del modello e le caratteristiche di addestramento. A differenza del classico problema degli URL di phishing [1], le nostre chiavi di join (che nella maggior parte dei casi sono identificatori univoci per utenti/esperienze) non erano intrinsecamente informative. Questo ci ha portato a esplorare gli attributi delle dimensioni come potenziali caratteristiche del modello in grado di aiutare a prevedere se un'entità di dimensione è presente nella tabella dei fatti. Ad esempio, immaginiamo una tabella dei fatti che contenga informazioni sulle sessioni degli utenti per esperienze in una lingua specifica. La posizione geografica o l'attributo di preferenza linguistica della dimensione utente sarebbero buoni indicatori della presenza o meno di un singolo utente nella tabella dei fatti.

La terza sfida, la latenza di inferenza, richiedeva modelli che minimizzassero i falsi negativi e fornissero risposte rapide. Un modello ad albero potenziato da gradiente era la scelta ottimale per queste metriche chiave e ne abbiamo potato l'insieme di caratteristiche per bilanciare precisione e velocità.

La nostra query di join aggiornata che utilizza i filtri di Bloom appresi è mostrata di seguito:

Risultati

Ecco i risultati dei nostri esperimenti con i filtri Bloom appresi nel nostro data lake. Li abbiamo integrati in cinque carichi di lavoro di produzione, ciascuno dei quali presentava caratteristiche dei dati diverse. La parte più onerosa dal punto di vista computazionale di questi carichi di lavoro è il join tra una tabella dei fatti e una tabella delle dimensioni. Lo spazio chiave delle tabelle dei fatti è circa il 30% di quello della tabella delle dimensioni. Per cominciare, discutiamo di come il filtro Bloom appreso abbia superato i filtri Bloom tradizionali in termini di dimensione finale dell'oggetto serializzato. Successivamente, mostriamo i miglioramenti delle prestazioni che abbiamo osservato integrando i filtri Bloom appresi nelle nostre pipeline di elaborazione dei carichi di lavoro.

Confronto delle dimensioni dei filtri Bloom appresi

Come mostrato di seguito, considerando un dato tasso di falsi positivi, le due varianti del filtro Bloom appreso migliorano la dimensione totale degli oggetti tra il 17 e il 42% rispetto ai filtri Bloom tradizionali.

Inoltre, utilizzando un sottoinsieme più piccolo di caratteristiche nel nostro modello basato su alberi con potenziamento del gradiente, abbiamo perso solo una piccola percentuale di ottimizzazione, rendendo al contempo più veloce l'inferenza.

Risultati sull'utilizzo del filtro di Bloom 

In questa sezione, confrontiamo le prestazioni dei join basati su Bloom Filter con quelle dei join regolari in base a diverse metriche. 

La tabella sottostante mette a confronto le prestazioni dei carichi di lavoro con e senza l'uso dei filtri Bloom appresi. Un filtro Bloom appreso con una probabilità totale di falsi positivi dell'1% illustra il confronto riportato di seguito, mantenendo la stessa configurazione di cluster per entrambi i tipi di join. 

In primo luogo, abbiamo riscontrato che l'implementazione del filtro di Bloom ha superato il join regolare fino al 60% in termini di ore di CPU. Abbiamo osservato un aumento dell'utilizzo della CPU nella fase di scansione per l'approccio del filtro di Bloom appreso a causa della potenza di calcolo aggiuntiva impiegata nella valutazione del filtro di Bloom. Tuttavia, il prefiltraggio effettuato in questa fase ha ridotto la dimensione dei dati da rimescolare, il che ha contribuito a ridurre la CPU utilizzata dalle fasi a valle, riducendo così le ore totali di CPU.

In secondo luogo, i filtri Bloom appresi hanno una dimensione totale dei dati inferiore di circa l'80% e circa l'80% in meno di byte di rimescolamento scritti rispetto a un join standard. Ciò porta a prestazioni di join più stabili, come discusso di seguito. 

Abbiamo inoltre riscontrato un utilizzo ridotto delle risorse in altri nostri carichi di lavoro di produzione sottoposti a sperimentazione. In un periodo di due settimane su tutti e cinque i carichi di lavoro, l'approccio Learned Bloom Filter ha generato un risparmio medio giornaliero sui costi del 25%, che tiene conto anche dell'addestramento del modello e della creazione dell'indice.

Grazie alla riduzione della quantità di dati rimescolati durante l'esecuzione del join, siamo stati in grado di ridurre significativamente i costi operativi della nostra pipeline di analisi, rendendola al contempo più stabile. Il grafico seguente mostra la variabilità (utilizzando un coefficiente di variazione) nelle durate di esecuzione (tempo di clock) per un carico di lavoro di join regolare e un carico di lavoro basato su filtri Bloom appresi su un periodo di due settimane per i cinque carichi di lavoro con cui abbiamo sperimentato. Le esecuzioni che utilizzavano i filtri Bloom appresi erano più stabili — più costanti in termini di durata — il che apre la possibilità di trasferirle su risorse di calcolo transitorie, meno affidabili ma più economiche. 

Riferimenti

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean e N. Polyzotis. The Case for Learned Index Structures. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. Optimizing Learned Bloom Filters by Sandwiching. 

https://arxiv.org/abs/1803.01474, 2018.

¹Al 30 giugno 2023

²Al 30 giugno 2023