Hvordan Roblox reduserer kostnadene for Spark Join Query med maskinlæring Optimaliserte blomstringsfiltre - Roblox Blog

Hvordan Roblox reduserer kostnadene for gnist-samarbeid med maskinlæring, optimaliserte blomstringsfiltre – Roblox-bloggen

Tidsstempel: 28. november 2023 12:23
Kilde node: 2983061

Abstrakt

Hver dag på Roblox, 65.5 millioner brukere engasjerer seg i millioner av opplevelser, totalt 14.0 milliarder timer kvartalsvis. Denne interaksjonen genererer en datainnsjø i petabyte-skala, som er beriket for analyse- og maskinlæringsformål (ML). Det er ressurskrevende å slå sammen fakta- og dimensjonstabeller i datainnsjøen vår, så for å optimalisere dette og redusere stokking av data, tok vi i bruk Learned Bloom Filters [1] – smarte datastrukturer ved hjelp av ML. Ved å forutsi tilstedeværelse trimmer disse filtrene betraktelig sammenføyningsdata, noe som øker effektiviteten og reduserer kostnadene. Underveis har vi også forbedret modellarkitekturene våre og demonstrert de betydelige fordelene de tilbyr for å redusere minne og CPU-timer for prosessering, samt øke driftsstabiliteten.

Introduksjon

I vår datainnsjø er faktatabeller og datakuber midlertidig partisjonert for effektiv tilgang, mens dimensjonstabeller mangler slike partisjoner, og å slå dem sammen med faktatabeller under oppdateringer er ressurskrevende. Nøkkelrommet til sammenføyningen er drevet av den tidsmessige partisjonen til faktatabellen som sammenføyes. Dimensjonsenhetene som er tilstede i den tidsmessige partisjonen er en liten delmengde av de som er tilstede i hele dimensjonsdatasettet. Som et resultat blir flertallet av de stokkede dimensjonsdataene i disse sammenføyningene til slutt forkastet. For å optimalisere denne prosessen og redusere unødvendig stokking, vurderte vi å bruke Bloom filtre på distinkte join-nøkler, men møtte problemer med filterstørrelse og minneavtrykk.

For å ta tak i dem utforsket vi Lærte blomstringsfiltre, en ML-basert løsning som reduserer Bloom Filter-størrelsen samtidig som den opprettholder lave falske positive rater. Denne innovasjonen forbedrer effektiviteten av sammenføyningsoperasjoner ved å redusere beregningskostnader og forbedre systemstabiliteten. Følgende skjema illustrerer de konvensjonelle og optimaliserte sammenføyningsprosessene i vårt distribuerte datamiljø.

Forbedrer sammenføyningseffektiviteten med lærde blomstringsfiltre

For å optimalisere sammenføyningen mellom fakta- og dimensjonstabeller, tok vi i bruk Learned Bloom Filter-implementeringen. Vi konstruerte en indeks fra nøklene i faktatabellen og distribuerte deretter indeksen for å forhåndsfiltrere dimensjonsdata før sammenføyningsoperasjonen. 

Evolusjon fra tradisjonelle blomstringsfiltre til lærde blomstringsfiltre

Selv om et tradisjonelt blomstringsfilter er effektivt, legger det til 15-25 % ekstra minne per arbeidernode som trenger å laste det for å oppnå ønsket falsk positiv rate. Men ved å bruke Learned Bloom Filters, oppnådde vi en betydelig redusert indeksstørrelse samtidig som vi opprettholdt samme falske positive rate. Dette er på grunn av transformasjonen av Bloom-filteret til et binært klassifiseringsproblem. Positive etiketter indikerer tilstedeværelsen av verdier i indeksen, mens negative etiketter betyr at de mangler.

Introduksjonen av en ML-modell letter den første sjekken for verdier, etterfulgt av et backup-bloom-filter for å eliminere falske negativer. Den reduserte størrelsen stammer fra modellens komprimerte representasjon og reduserte antall nøkler som kreves av backup-bloomfilteret. Dette skiller den fra den konvensjonelle Bloom Filter-tilnærmingen. 

Som en del av dette arbeidet etablerte vi to beregninger for å evaluere vår Learned Bloom Filter-tilnærming: indeksens endelige serialiserte objektstørrelse og CPU-forbruk under utførelsen av sammenføyningsspørringer. 

Navigere gjennom implementeringsutfordringer

Vår første utfordring var å adressere et svært partisk opplæringsdatasett med få dimensjonstabellnøkler i faktatabellen. Ved å gjøre dette observerte vi en overlapping på omtrent en av tre nøkler mellom tabellene. For å takle dette brukte vi Sandwich Learned Bloom Filter-tilnærmingen [2]. Dette integrerer et innledende tradisjonelt Bloom-filter for å rebalansere datasettfordelingen ved å fjerne flertallet av nøklene som manglet fra faktatabellen, og effektivt eliminere negative prøver fra datasettet. Deretter ble bare nøklene inkludert i det innledende Bloom-filteret, sammen med de falske positive, videresendt til ML-modellen, ofte referert til som det "lærte oraklet." Denne tilnærmingen resulterte i et velbalansert opplæringsdatasett for det lærde oraklet, som effektivt overkom bias-problemet.

Den andre utfordringen sentrerte seg om modellarkitektur og treningsfunksjoner. I motsetning til det klassiske problemet med nettfisking-URL-er [1], var sammenkoblingsnøklene våre (som i de fleste tilfeller er unike identifikatorer for brukere/opplevelser) ikke i seg selv informative. Dette førte til at vi utforsket dimensjonsattributter som potensielle modellfunksjoner som kan bidra til å forutsi om en dimensjonsenhet er til stede i faktatabellen. Tenk deg for eksempel en faktatabell som inneholder informasjon om brukerøkter for opplevelser på et bestemt språk. Den geografiske plasseringen eller språkpreferanseattributtet til brukerdimensjonen vil være gode indikatorer på om en individuell bruker er til stede i faktatabellen eller ikke.

Den tredje utfordringen – slutningsforsinkelse – krevde modeller som både minimerte falske negativer og ga raske svar. En gradientforsterket tremodell var det optimale valget for disse nøkkelberegningene, og vi beskjærte funksjonssettet for å balansere presisjon og hastighet.

Vår oppdaterte søk med innlærte blomstringsfiltre er som vist nedenfor:

Resultater

Her er resultatene av våre eksperimenter med Learned Bloom-filtre i datainnsjøen vår. Vi integrerte dem i fem produksjonsarbeidsmengder, som hver hadde forskjellige dataegenskaper. Den mest beregningsmessig kostbare delen av disse arbeidsbelastningene er sammenføyningen mellom en faktatabell og en dimensjonstabell. Nøkkelrommet til faktatabellene er omtrent 30 % av dimensjonstabellen. Til å begynne med diskuterer vi hvordan Learned Bloom-filteret overgikk tradisjonelle Bloom-filtre når det gjelder endelig serialisert objektstørrelse. Deretter viser vi ytelsesforbedringer som vi observerte ved å integrere Learned Bloom-filtre i pipelines for arbeidsbelastningsbehandling.

Lært Bloom Filter Størrelse Sammenligning

Som vist nedenfor, når man ser på en gitt falsk positiv rate, forbedrer de to variantene av det innlærte Bloom Filter den totale objektstørrelsen med mellom 17-42 % sammenlignet med tradisjonelle Bloom-filtre.

I tillegg, ved å bruke et mindre delsett av funksjoner i vår gradientforsterkede trebaserte modell, mistet vi bare en liten prosentandel av optimaliseringen samtidig som vi gjorde konklusjoner raskere.

Lærte resultater for bruk av blomstringsfilter 

I denne delen sammenligner vi ytelsen til Bloom Filter-baserte sammenføyninger med ytelsen til vanlige sammenføyninger på tvers av flere beregninger. 

Tabellen nedenfor sammenligner ytelsen til arbeidsbelastninger med og uten bruk av Learned Bloom-filtre. Et lært blomstringsfilter med 1 % total falsk positiv sannsynlighet demonstrerer sammenligningen nedenfor samtidig som den opprettholder samme klyngekonfigurasjon for begge sammenføyningstypene. 

For det første fant vi ut at implementeringen av Bloom Filter overgikk den vanlige sammenføyningen med så mye som 60 % i CPU-timer. Vi så en økning i CPU-bruk av skannetrinnet for Learned Bloom Filter-tilnærmingen på grunn av den ekstra beregningen som ble brukt på å evaluere Bloom-filteret. Imidlertid reduserte forhåndsfiltreringen som ble utført i dette trinnet størrelsen på data som ble stokket, noe som bidro til å redusere CPU-en som ble brukt av nedstrømstrinnene, og dermed reduserte de totale CPU-timene.

For det andre har Learned Bloom-filtre omtrent 80 % mindre total datastørrelse og omtrent 80 % færre totale shuffle-byte skrevet enn en vanlig sammenføyning. Dette fører til mer stabil sammenføyningsytelse som diskutert nedenfor. 

Vi så også redusert ressursbruk i våre andre produksjonsarbeidsmengder under eksperimentering. Over en periode på to uker på tvers av alle fem arbeidsmengdene genererte Learned Bloom Filter-tilnærmingen et gjennomsnitt daglige kostnadsbesparelser of 25%, som også står for modelltrening og indeksoppretting.

På grunn av den reduserte mengden data som ble blandet mens vi utførte sammenføyningen, klarte vi å redusere driftskostnadene for analysepipeline vår betydelig, samtidig som vi gjorde den mer stabil. Tabellen nedenfor viser variasjon (ved bruk av en variasjonskoeffisient) i kjøringsvarighet (vegg). klokketid) for en vanlig arbeidsbelastning og en Learned Bloom Filter-basert arbeidsbelastning over en to-ukers periode for de fem arbeidsmengdene vi eksperimenterte med. Kjøringene med Learned Bloom Filters var mer stabile – mer konsistente i varighet – noe som åpner for muligheten for å flytte dem til billigere forbigående upålitelige dataressurser. 

Referanser

[1] T. Kraska, A. Beutel, EH Chi, J. Dean og N. Polyzotis. Saken for lærte indeksstrukturer. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. Optimalisering av lærte blomstringsfiltre ved å legge sammen. 

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

¹Fra og med 3 måneder som ble avsluttet 30. juni 2023

²Fra og med 3 måneder avsluttet 30. juni 2023

Tidstempel:

Mer fra Roblox