Hur Roblox minskar kostnaderna för Spark Join-fråga med maskininlärning Optimerade blomfilter - Roblox-blogg

Hur Roblox minskar kostnaderna för Spark Join Query med maskininlärning optimerade blomfilter – Roblox Blog

Tidsstämpel: 28 november 2023 12:23
Källnod: 2983061

Abstrakt

Varje dag på Roblox, 65.5 miljoner användare engagerar sig i miljontals upplevelser, totalt 14.0 miljarder timmar kvartalsvis. Denna interaktion genererar en petabyte-skala datasjö, som är berikad för analys- och maskininlärningsändamål (ML). Det är resurskrävande att sammanfoga fakta- och dimensionstabeller i vår datasjö, så för att optimera detta och minska datablandningen anammade vi Learned Bloom Filters [1] – smarta datastrukturer med ML. Genom att förutsäga närvaro trimmar dessa filter avsevärt sammanfogningsdata, vilket ökar effektiviteten och sänker kostnaderna. På vägen har vi också förbättrat våra modellarkitekturer och demonstrerat de betydande fördelarna de erbjuder för att minska minne och CPU-timmar för bearbetning, samt öka driftstabiliteten.

Beskrivning

I vår datasjö är faktatabeller och datakuber temporärt 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 sammanfogningen drivs av den tidsmässiga partitionen av faktatabellen som sammanfogas. 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 majoriteten av den blandade dimensionsdatan i dessa kopplingar så småningom. För att optimera denna process och minska onödig blandning övervägde vi att använda Blomfilter på distinkta kopplingsnycklar men stötte på problem med filterstorlek och minnesavtryck.

För att ta itu med dem utforskade vi Lärde blomfilter, en ML-baserad lösning som minskar storleken på Bloom Filter samtidigt som den bibehåller låga falska positiva frekvenser. Denna innovation förbättrar effektiviteten i sammanfogningsverksamheten 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ättra föreningseffektiviteten med inlärda blomfilter

För att optimera kopplingen mellan fakta- och dimensionstabeller använde vi implementeringen Learned Bloom Filter. Vi konstruerade ett index från nycklarna som finns i faktatabellen och distribuerade sedan indexet för att förfiltrera dimensionsdata innan sammanfogningsoperationen. 

Evolution från traditionella blomfilter till inlärda blomfilter

Medan ett traditionellt blomfilter är effektivt lägger det till 15-25 % extra minne per arbetarnod som behöver ladda det för att nå vår önskade falska positiva frekvens. Men genom att använda Learned Bloom Filters, 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 anger förekomsten av värden i indexet, medan negativa etiketter betyder att de saknas.

Introduktionen av en ML-modell underlättar den första kontrollen av värden, följt av ett backup-bloom-filter för att eliminera falska negativ. Den reducerade storleken härrör från modellens komprimerade representation och reducerade antal nycklar som krävs av backup-bloomfiltret. Detta skiljer den från den konventionella Bloom Filter-metoden. 

Som en del av detta arbete har vi etablerat två mätvärden för att utvärdera vår Learned Bloom Filter-metod: indexets slutliga serialiserade objektstorlek och CPU-förbrukning under körningen av kopplingsfrågor. 

Navigera i implementeringsutmaningar

Vår första utmaning var att ta itu med en mycket partisk 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 tackla detta använde vi Sandwich Learned Bloom Filter-metoden [2]. Detta integrerar ett initialt traditionellt Bloom-filter för att balansera om datauppsättningsdistributionen genom att ta bort majoriteten av nycklar som saknades från faktatabellen, vilket effektivt eliminerar negativa prover från datauppsättningen. Därefter vidarebefordrades endast nycklarna 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, som effektivt överkom biasproblemet.

Den andra utmaningen fokuserade på modellarkitektur och träningsfunktioner. Till skillnad från det klassiska problemet med nätfiske-URL:er [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. Den geografiska platsen eller språkpreferensattributet för användardimensionen skulle vara bra indikatorer på om en enskild användare finns i faktatabellen eller inte.

Den tredje utmaningen – slutledningslatens – krävde modeller som både minimerade falska negativa och gav snabba svar. En gradientförstärkt trädmodell var det optimala valet för dessa nyckelmått, och vi beskärde dess funktionsuppsättning för att balansera precision och hastighet.

Vår uppdaterade anslutningsfråga med inlärda blomfilter visas nedan:

Resultat

Här är resultaten av våra experiment med Learned Bloom-filter i 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 diskuterar vi hur Learned Bloom Filter överträffade traditionella Bloom Filter när det gäller slutlig serialiserade objektstorlek. Därefter visar vi prestandaförbättringar som vi observerade 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 man tittar på en given falsk positiv frekvens, förbättrar de två varianterna av det inlärda Bloom-filtret den totala objektstorleken med mellan 17-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 samtidigt som vi gjorde slutsatser snabbare.

Lärda resultat för användning av blomfilter 

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

Tabellen nedan jämför prestandan för arbetsbelastningar med och utan användning av inlärda blomfilter. Ett inlärt blomfilter med 1 % total falsk positiv sannolikhet visar jämförelsen nedan samtidigt som man bibehåller samma klusterkonfiguration för båda jointyperna. 

Först upptäckte vi att implementeringen av Bloom Filter överträffade den vanliga anslutningen med så mycket som 60 % i CPU-timmar. Vi såg en ökning av CPU-användningen av skanningssteget för Learned Bloom Filter-metoden på grund av den extra beräkning som spenderades på att utvärdera Bloom-filtret. Förfiltreringen som gjordes i det här steget minskade dock storleken på data som blandas, vilket bidrog till att minska CPU-användningen av nedströmsstegen, vilket minskade det totala antalet CPU-timmar.

För det andra har Learned Bloom Filters cirka 80 % mindre total datastorlek och cirka 80 % mindre totala shuffle-byte skrivna än en vanlig join. Detta leder till mer stabil kopplingsprestanda som diskuteras nedan. 

Vi såg också minskad resursanvändning i våra andra produktionsbelastningar under experiment. Under en period av två veckor över alla fem arbetsbelastningar genererade metoden Learned Bloom Filter ett genomsnitt dagliga kostnadsbesparingar of 25% som också står för modellträning och indexskapande.

På grund av den minskade mängden data som blandas när vi utförde sammanfogningen, kunde vi avsevärt minska driftskostnaderna för vår analyspipeline samtidigt som den gjorde den mer stabil. Följande diagram visar variabilitet (med en variationskoefficient) i körlängder (vägg). klocktid) för en vanlig arbetsbelastning och en Learned Bloom Filter-baserad arbetsbelastning under en tvåveckorsperiod för de fem arbetsbelastningar vi experimenterade med. Körningarna med Learned Bloom Filters var mer stabila – mer konsekventa i varaktighet – vilket öppnar för möjligheten att flytta dem till billigare tillfälliga opålitliga beräkningsresurser. 

Referensprojekt

[1] T. Kraska, A. Beutel, EH Chi, J. Dean och N. Polyzotis. Fallet för inlärda indexstrukturer. https://arxiv.org/abs/1712.012082017

[2] M. Mitzenmacher. Optimera inlärda blomfilter genom smörgås. 

https://arxiv.org/abs/1803.014742018

¹Från och med 3 månader som slutade 30 juni 2023

²Från och med 3 månader som slutade 30 juni 2023

Tidsstämpel:

Mer från Roblox