Hoe Roblox de kosten van Spark Join-query's verlaagt met voor machine learning geoptimaliseerde Bloom-filters

Samenvatting

Elke dag zijn er op Roblox 70 miljoen gebruikers die miljoenen ervaringen beleven, wat neerkomt op een totaal van 16 miljard uur per kwartaal. Deze interactie genereert een datameer van petabyteschaal, dat wordt verrijkt voor analyse- en machine learning (ML)-doeleinden. Het samenvoegen van feiten- en dimensietabellen in ons datameer is zeer resource-intensief. Om dit te optimaliseren en het herschikken van gegevens te verminderen, hebben we Learned Bloom Filters [1] geïmplementeerd – slimme datastructuren die gebruikmaken van ML. Door aanwezigheid te voorspellen, verminderen deze filters de hoeveelheid samen te voegen gegevens aanzienlijk, wat de efficiëntie verhoogt en de kosten verlaagt. Tegelijkertijd hebben we ook onze modelarchitecturen verbeterd en aangetoond dat deze aanzienlijke voordelen bieden voor het verminderen van geheugen- en CPU-uren voor verwerking, evenals het verhogen van de operationele stabiliteit.

Inleiding

In ons datameer zijn feitentabellen en datakubussen tijdelijk gepartitioneerd voor efficiënte toegang, terwijl dimensietabellen dergelijke partities missen en het samenvoegen ervan met feitentabellen tijdens updates veel resources kost. De sleutelruimte van de join wordt bepaald door de tijdpartitie van de feitentabel die wordt samengevoegd. De dimensie-entiteiten die in die temporele partitie aanwezig zijn, vormen een kleine subset van die welke in de volledige dimensiedataset aanwezig zijn. Als gevolg hiervan wordt het grootste deel van de geschudde dimensiegegevens in deze koppelingen uiteindelijk weggegooid. Om dit proces te optimaliseren en onnodig schudden te verminderen, hebben we overwogen om Bloom-filters te gebruiken op unieke koppelingssleutels, maar stuitten we op problemen met de filtergrootte en het geheugengebruik.

Om deze op te lossen, hebben we Learned Bloom Filters onderzocht, een op ML gebaseerde oplossing die de omvang van Bloom Filters vermindert met behoud van lage percentages valse positieven. Deze innovatie verhoogt de efficiëntie van join-bewerkingen door de rekenkosten te verlagen en de systeemstabiliteit te verbeteren. Het volgende schema illustreert de conventionele en geoptimaliseerde join-processen in onze gedistribueerde computeromgeving.

Verbetering van de efficiëntie van joins met Learned Bloom Filters

Om de join tussen feiten- en dimensietabellen te optimaliseren, hebben we de implementatie van het Learned Bloom Filter toegepast. We hebben een index samengesteld op basis van de sleutels in de feitentabel en deze vervolgens ingezet om dimensiegegevens vooraf te filteren vóór de join-bewerking. 

Evolutie van traditionele Bloom-filters naar Learned Bloom-filters

Hoewel een traditionele Bloom-filter efficiënt is, voegt deze 15-25% extra geheugen toe per werkknooppunt dat deze moet laden om ons gewenste percentage valse positieven te halen. Maar door gebruik te maken van Learned Bloom-filters hebben we een aanzienlijk kleinere indexgrootte bereikt met behoud van hetzelfde percentage valse positieven. Dit komt door de transformatie van de Bloom-filter naar een binair classificatieprobleem. Positieve labels geven de aanwezigheid van waarden in de index aan, terwijl negatieve labels betekenen dat ze afwezig zijn.

De introductie van een ML-model vergemakkelijkt de eerste controle op waarden, gevolgd door een back-up Bloom-filter voor het elimineren van valse negatieven. De verminderde omvang is het gevolg van de gecomprimeerde weergave van het model en het verminderde aantal sleutels dat nodig is voor het back-up Bloom-filter. Dit onderscheidt het van de conventionele Bloom-filterbenadering. 

Als onderdeel van dit werk hebben we twee maatstaven vastgesteld voor het evalueren van onze Learned Bloom Filter-aanpak: de uiteindelijke grootte van het geserialiseerde object van de index en het CPU-verbruik tijdens de uitvoering van join-query's. 

Omgaan met implementatie-uitdagingen

Onze eerste uitdaging was het aanpakken van een sterk vertekende trainingsdataset met weinig dimensietabel-sleutels in de feitentabel. Daarbij constateerden we een overlap van ongeveer één op de drie sleutels tussen de tabellen. Om dit aan te pakken, maakten we gebruik van de Sandwich Learned Bloom Filter-aanpak [2]. Deze integreert een initieel traditioneel Bloom Filter om de verdeling van de dataset opnieuw in evenwicht te brengen door het merendeel van de sleutels te verwijderen die in de feitentabel ontbraken, waardoor negatieve samples effectief uit de dataset werden geëlimineerd. Vervolgens werden alleen de sleutels die in de initiële Bloom Filter waren opgenomen, samen met de valse positieven, doorgestuurd naar het ML-model, vaak aangeduid als het "learned oracle". Deze aanpak resulteerde in een goed uitgebalanceerde trainingsdataset voor het learned oracle, waardoor het vertekeningsprobleem effectief werd overwonnen.

De tweede uitdaging had betrekking op de modelarchitectuur en trainingskenmerken. In tegenstelling tot het klassieke probleem van phishing-URL's [1] waren onze koppelingssleutels (die in de meeste gevallen unieke identificatiecodes voor gebruikers/ervaringen zijn) niet inherent informatief. Dit bracht ons ertoe om dimensieattributen te onderzoeken als potentiële modelkenmerken die kunnen helpen voorspellen of een dimensie-entiteit aanwezig is in de feitentabel. Stel je bijvoorbeeld een feitentabel voor die gebruikerssessie-informatie bevat voor ervaringen in een bepaalde taal. De geografische locatie of het attribuut voor taalvoorkeur van de gebruikersdimensie zouden goede indicatoren zijn om te bepalen of een individuele gebruiker al dan niet in de feitentabel aanwezig is.

De derde uitdaging – inferentielatentie – vereiste modellen die zowel valse negatieven minimaliseerden als snelle reacties gaven. Een gradient-boosted tree-model was de optimale keuze voor deze belangrijke statistieken, en we hebben de kenmerkset ervan gesnoeid om precisie en snelheid in evenwicht te brengen.

Onze bijgewerkte join-query met behulp van aangeleerde Bloom-filters ziet er als volgt uit:

Resultaten

Hier zijn de resultaten van onze experimenten met Learned Bloom-filters in ons datameer. We hebben ze geïntegreerd in vijf productieworkloads, die elk verschillende gegevenskenmerken hadden. Het meest rekenintensieve deel van deze workloads is de koppeling tussen een feitentabel en een dimensietabel. De sleutelruimte van de feitentabellen is ongeveer 30% van die van de dimensietabel. Om te beginnen bespreken we hoe de Learned Bloom Filter beter presteerde dan traditionele Bloom Filters wat betreft de uiteindelijke grootte van het geserialiseerde object. Vervolgens laten we de prestatieverbeteringen zien die we hebben waargenomen door Learned Bloom Filters te integreren in onze pijplijnen voor de verwerking van workloads.

Vergelijking van de grootte van het Learned Bloom Filter

Zoals hieronder te zien is, verbeteren de twee varianten van de Learned Bloom Filter bij een gegeven percentage valse positieven de totale objectgrootte met 17-42% in vergelijking met traditionele Bloom Filters.

Bovendien verloren we, door een kleinere subset van kenmerken te gebruiken in ons op gradient boosted tree gebaseerde model, slechts een klein percentage aan optimalisatie, terwijl we de inferentie versnelden.

Resultaten van onderzoek naar het gebruik van Bloom-filters 

In dit gedeelte vergelijken we de prestaties van op Bloom-filters gebaseerde joins met die van reguliere joins aan de hand van verschillende statistieken. 

De onderstaande tabel vergelijkt de prestaties van workloads met en zonder het gebruik van Learned Bloom Filters. Een Learned Bloom Filter met een totale kans op valse positieven van 1% illustreert de onderstaande vergelijking, waarbij voor beide soorten joins dezelfde clusterconfiguratie wordt gehandhaafd. 

Ten eerste hebben we vastgesteld dat de implementatie van het Bloom-filter tot wel 60% beter presteerde dan de reguliere join wat betreft CPU-uren. We zagen een toename in CPU-gebruik tijdens de scanfase voor de Learned Bloom Filter-aanpak vanwege de extra rekenkracht die nodig was voor het evalueren van het Bloom-filter. De voorfiltering die in deze stap werd uitgevoerd, verminderde echter de omvang van de gegevens die werden geschud, wat hielp bij het verminderen van het CPU-gebruik in de daaropvolgende stappen, waardoor het totale aantal CPU-uren daalde.

Ten tweede hebben Learned Bloom Filters ongeveer 80% minder totale gegevensomvang en ongeveer 80% minder totale shuffle-bytes dan een reguliere join. Dit leidt tot stabielere join-prestaties, zoals hieronder wordt besproken. 

We zagen ook een lager resourcegebruik in onze andere productieworkloads die we aan het testen waren. Over een periode van twee weken voor alle vijf de workloads leverde de Learned Bloom Filter-aanpak een gemiddelde dagelijkse kostenbesparing van 25% op, waarbij ook rekening is gehouden met modeltraining en het aanmaken van indexen.

Door de verminderde hoeveelheid gegevens die tijdens het uitvoeren van de join wordt geschud, konden we de operationele kosten van onze analysepijplijn aanzienlijk verlagen en deze tegelijkertijd stabieler maken. De volgende grafiek toont de variabiliteit (met behulp van een variatiecoëfficiënt) in de looptijden (kloktijd) voor een reguliere join-workload en een op Learned Bloom Filters gebaseerde workload over een periode van twee weken voor de vijf workloads waarmee we experimenteerden. De runs met Learned Bloom Filters waren stabieler – consistenter qua duur – wat de mogelijkheid biedt om ze te verplaatsen naar goedkopere, tijdelijke, onbetrouwbare rekenbronnen. 

Referenties

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean en 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.

¹Per 30 juni 2023

²Per 30 juni 2023