Spel

Hur Roblox minskar Spark Join-frågor med maskininlärningsoptimerade Bloom-filter

Abstrakt

Varje dag i Roblox, 70 miljontals användare interagerar med miljontals upplevelser, med totalt 16 miljarder kvartalstimmar. Denna interaktion genererar en petabyte-skala datasjö, som är berikad för analys- och maskininlärningsändamål (ML). Att sammanfoga fakta- och dimensionstabeller i vår datasjö är resurskrävande, så för att optimera detta och minska datablandningen använde vi Learned Bloom-filter (1) – intelligenta datastrukturer som använder ML. Genom att förutsäga närvaro trimmar dessa filter avsevärt sammanfogningsdata, vilket förbättrar effektiviteten och minskar kostnaderna. Längs vägen har vi också förbättrat våra modellarkitekturer och visat de betydande fördelarna de erbjuder genom att minska minnet och CPU-timmar för bearbetning, samt öka driftstabiliteten.

Introduktion

I vår datasjö är faktatabeller och datakuber tillfälligt partitionerade för effektiv åtkomst, medan dimensionstabeller saknar sådana partitioner, och att sammanfoga dem med faktatabeller under uppdateringar är resurskrävande. Nyckelutrymmet för kopplingen bestäms av den tillfälliga partitionen av faktatabellen som ansluts. Dimensionsentiteterna som finns i den temporala partitionen är en liten delmängd av de som finns i hela dimensionsdatauppsättningen. Som ett resultat förkastas det mesta av data för blandade dimensioner i dessa kopplingar så småningom.. För att optimera denna process och minska onödig blandning övervägde vi att använda Bloom filter på olika kopplingsnycklar, men stötte på problem med filterstorlek och minnesfotavtryck.

För att ta itu med dem utforskar vi Lärde blomfilter, en ML-baserad lösning som minskar Bloom-filterstorleken samtidigt som den bibehåller låga falska positiva frekvenser. Denna innovation förbättrar effektiviteten i gemensamma operationer genom att minska beräkningskostnaderna och förbättra systemstabiliteten. Följande schema illustrerar de konventionella och optimerade sammanfogningsprocesserna i vår distribuerade datormiljö.

Förbättrad sammanfogningseffektivitet med inlärda blomfilter

För att optimera kopplingen mellan fakta- och dimensionstabeller använder vi implementeringen av Learned Bloom-filtret. Vi bygger ett index från nycklarna som finns i faktatabellen och implementerar därefter indexet för att förfiltrera dimensionsdatan före joinoperationen.

Evolution från traditionella blomfilter till inlärda blomfilter

Medan ett traditionellt Bloom-filter är effektivt lägger det till 15 % till 25 % extra minne för varje arbetarnod som behöver ladda det för att uppnå önskad falsk positiv frekvens. Men genom att utnyttja Learned Bloom-filter, uppnådde vi en avsevärt reducerad indexstorlek samtidigt som vi bibehöll samma falska positiva frekvens. Detta beror på omvandlingen av Bloom-filtret till ett binärt klassificeringsproblem. Positiva etiketter indikerar närvaron av värden i indexet, medan negativa etiketter betyder att de saknas.

Introduktionen av en ML-modell underlättar den första verifieringen av värden, följt av ett stödjande Bloom-filter för att eliminera falska negativ. Den minskade storleken beror på den komprimerade representationen av modellen och minskningen av antalet nycklar som krävs av det stödjande Bloom-filtret. Detta skiljer den från den konventionella Bloom Filter-metoden.

Som en del av detta arbete upprättade vi två mätvärden för att utvärdera vår inlärda Bloom-filtermetod: den slutliga storleken på det serialiserade indexobjektet och CPU-förbrukningen under exekveringen av kopplingsfrågor.

Navigera i implementeringsutmaningar

Vår första utmaning var att ta itu med en mycket skev träningsdatauppsättning med få dimensionstabellnycklar i faktatabellen. När vi gjorde det observerade vi en överlappning av ungefär en av tre nycklar mellan tabellerna. För att ta itu med detta använder vi Sandwich Learned Bloom Filter-metoden (2). Detta integrerar ett initialt traditionellt Bloom-filter för att balansera om fördelningen av datamängden genom att ta bort de flesta nycklar som saknades i faktatabellen, vilket effektivt tar bort negativa sampel från datamängden. Därefter skickades endast nycklarna som ingick i det initiala Bloom-filtret, tillsammans med de falska positiva, till ML-modellen, ofta kallad det “lärda oraklet”. Detta tillvägagångssätt resulterade i en välbalanserad träningsdatauppsättning för det lärda oraklet, vilket effektivt överkom problemet med partiskhet.

Den andra utmaningen fokuserade på modellarkitekturen och träningsfunktionerna. Till skillnad från det klassiska nätfiske-URL-problemet (1), var våra anslutningsnycklar (som i de flesta fall är unika identifierare för användare/upplevelser) inte i sig informativa. Detta fick oss att utforska dimensionsattribut som potentiella modellfunktioner som kan hjälpa till att förutsäga om en dimensionsentitet finns i faktatabellen. Föreställ dig till exempel en faktatabell som innehåller användarsessionsinformation för upplevelser på ett visst språk. Användardimensionens geografiska plats eller språkpreferensattribut skulle vara bra indikatorer på om en enskild användare finns i faktatabellen eller inte.

Den tredje utmaningen, slutledningslatens, krävde modeller som minimerar falska negativa svar och ger snabba svar. En gradientdriven trädmodell var det optimala valet för dessa nyckelmått, och vi beskärde dess funktionsuppsättning för att balansera noggrannhet och hastighet.

Vår uppdaterade sökfråga med hjälp av de inlärda Bloom-filtren visas nedan:

Resultat

Det här är resultatet av våra experiment med Learned Bloom-filter på vår datasjö. Vi integrerade dem i fem produktionsbelastningar, som var och en hade olika dataegenskaper. Den beräkningsmässigt dyraste delen av dessa arbetsbelastningar är kopplingen mellan en faktatabell och en dimensionstabell. Faktatabellernas nyckelutrymme är cirka 30 % av dimensionstabellen. Till att börja med analyserade vi hur det inlärda Bloom-filtret överträffade traditionella Bloom-filter när det gäller den slutliga storleken på det serialiserade objektet. Nedan visar vi de prestandaförbättringar vi ser genom att integrera Learned Bloom Filters i våra pipelines för bearbetning av arbetsbelastning.

Lärt Bloom-filterstorleksjämförelse

Som visas nedan, när en given falsk positiv frekvens observeras, förbättrar de två varianterna av det inlärda Bloom-filtret den totala objektstorleken med 17 % till 42 % jämfört med traditionella Bloom-filter.

Dessutom, genom att använda en mindre delmängd av funktioner i vår gradientförstärkta trädbaserade modell, förlorade vi bara en liten andel av optimeringen och gjorde slutsatser snabbare.

Bloom-filteranvändningsresultat lärde sig

I det här avsnittet jämför vi prestandan för Bloom Filter-baserade kopplingar med vanliga kopplingar över flera mätvärden.

Följande tabell jämför prestandan för arbetsbelastningar med och utan användning av inlärda Bloom-filter. Ett Bloom-filter som lärts in med en total falsk positiv sannolikhet på 1 % visar följande jämförelse samtidigt som man bibehåller samma klusterkonfiguration för båda typerna av kopplingar.

Först upptäckte vi att implementeringen av Bloom Filter överträffade regelbunden bindning med upp till 60 % i CPU-timmar. Vi såg en ökning av CPU-användningen av skanningssteget för den inlärda Bloom-filtermetoden på grund av den extra beräkning som ägnades åt att utvärdera Bloom-filtret. Förfiltreringen som utfördes i det här steget minskade dock storleken på data som blandas, vilket bidrog till att minska CPU-användningen av efterföljande steg, vilket minskade det totala antalet CPU-timmar.

För det andra har Learned Bloom-filter cirka 80 % mindre total datastorlek och cirka 80 % färre slumpmässiga byte skrivna än en vanlig join. Detta leder till mer stabil bindningsprestanda, som diskuteras nedan.

Vi såg också minskad resursanvändning i våra andra produktionsbelastningar under experiment. Under en tvåveckorsperiod över de fem arbetsbelastningarna genererade filtermetoden Learned Bloom ett genomsnitt dagliga kostnadsbesparingar av 25 %, som också representerar modellutbildning och indexskapande.

På grund av den mindre mängden data som blandas ihop när vi utförde sammanfogningen kunde vi avsevärt minska driftskostnaderna för vår analysprocess samtidigt som vi gjorde den mer stabil. Följande graf visar variabiliteten (med användning av en variationskoefficient) i exekveringslängd (väggklocktid) för en vanlig arbetsbelastning och en Learned Bloom Filter-baserad arbetsbelastning under en tvåveckorsperiod för fem arbetsbelastningar som vi experimenterade med. Körningar med Learned Bloom-filter var mer stabila (mer konsekvent i varaktighet), vilket öppnar möjligheten att flytta dem till billigare transienta och opålitliga datorresurser.

Referenser

(1) T. Kraska, A. Beutel, EH Chi, J. Dean och N. Polyzotis. Fallet med inlärda indexstrukturer. https://arxiv.org/abs/1712.012082017.

(2) M. Mitzenmacher. Optimering av blomfilter lärt sig med sandwich.

https://arxiv.org/abs/1803.014742018.


¹Vid 3 månader som slutar 30 juni 2023

²Vid 3 månader som slutar 30 juni 2023