How Roblox Reduces Spark Join Query Costs With Machine Learning Optimized Bloom Filters - Roblox Blog

Ponovno objavil Platon

Spremljevalci: 0

Minimalizem

Vsak dan na Robloxu, 65.5 milijonov uporabnikov sodeluje z milijoni izkušenj, skupaj 14.0 milijard ur na četrtletje. Ta interakcija ustvari petabajtno podatkovno jezero, ki je obogateno za namene analitike in strojnega učenja (ML). Združevanje tabel dejstev in razsežnosti v našem podatkovnem jezeru zahteva veliko virov, zato smo za optimizacijo tega in zmanjšanje mešanja podatkov sprejeli naučene Bloomove filtre [1] – pametne podatkovne strukture, ki uporabljajo ML. S predvidevanjem prisotnosti ti filtri znatno skrajšajo združene podatke, izboljšajo učinkovitost in zmanjšajo stroške. Na tej poti smo tudi izboljšali naše arhitekture modelov in prikazali bistvene prednosti, ki jih ponujajo za zmanjšanje pomnilnika in CPE ur za obdelavo, kot tudi povečanje stabilnosti delovanja.

Predstavitev

V našem podatkovnem jezeru so tabele dejstev in podatkovne kocke časovno particionirane za učinkovit dostop, medtem ko dimenzijske tabele nimajo takšnih particij, njihovo združevanje s tabelami dejstev med posodobitvami pa zahteva veliko virov. Ključni prostor združevanja poganja časovna particija tabele dejstev, ki se združuje. Entitete dimenzije, prisotne v tej časovni particiji, so majhna podmnožica tistih, ki so prisotne v celotnem naboru podatkov dimenzije. Posledično je večina premešanih dimenzijskih podatkov v teh spojih sčasoma zavrženih. Da bi optimizirali ta postopek in zmanjšali nepotrebno mešanje, smo razmislili o uporabi Bloom Filtri na različnih ključih za združevanje, vendar je imel težave z velikostjo filtra in pomnilniškim odtisom.

Da bi jih obravnavali, smo raziskali Naučeni Bloomovi filtri, rešitev, ki temelji na ML, ki zmanjša velikost filtra Bloom in hkrati ohranja nizke stopnje lažno pozitivnih rezultatov. Ta inovacija povečuje učinkovitost povezovalnih operacij z zmanjšanjem računskih stroškov in izboljšanjem stabilnosti sistema. Naslednja shema ponazarja običajne in optimizirane postopke združevanja v našem porazdeljenem računalniškem okolju.

Izboljšanje učinkovitosti spajanja z naučenimi filtri Bloom

Za optimizacijo združevanja med tabelami dejstev in dimenzijami smo sprejeli implementacijo Learned Bloom Filter. Konstruirali smo indeks iz ključev, ki so prisotni v tabeli dejstev, in nato razmestili indeks za predhodno filtriranje podatkov dimenzij pred operacijo združevanja.

Evolucija od tradicionalnih Bloom filtrov do naučenih Bloom filtrov

Medtem ko je tradicionalni filter Bloom učinkovit, doda 15–25 % dodatnega pomnilnika na delovno vozlišče, ki ga mora naložiti, da doseže želeno stopnjo lažno pozitivnih rezultatov. Toda z uporabo naučenih filtrov Bloom smo dosegli znatno zmanjšano velikost indeksa, hkrati pa ohranili enako lažno pozitivno stopnjo. To je zaradi preoblikovanja Bloomovega filtra v problem binarne klasifikacije. Pozitivne oznake kažejo na prisotnost vrednosti v indeksu, medtem ko negativne oznake pomenijo, da jih ni.

Uvedba modela ML olajša začetno preverjanje vrednosti, ki mu sledi rezervni Bloomov filter za odpravo lažno negativnih rezultatov. Zmanjšana velikost izhaja iz stisnjene predstavitve modela in zmanjšanega števila ključev, ki jih zahteva rezervni Bloomov filter. To ga razlikuje od običajnega pristopa Bloom Filter.

Kot del tega dela smo vzpostavili dve metriki za vrednotenje našega pristopa Learned Bloom Filter: končno serializirano velikost objekta indeksa in porabo procesorja med izvajanjem poizvedb za združevanje.

Krmarjenje z izzivi implementacije

Naš začetni izziv je bil obravnava zelo pristranskega nabora podatkov o usposabljanju z nekaj ključi tabele dimenzij v tabeli dejstev. Pri tem smo opazili prekrivanje približno enega od treh ključev med tabelami. Da bi se tega lotili, smo uporabili pristop Sandwich Learned Bloom Filter [2]. To integrira začetni tradicionalni Bloomov filter za ponovno uravnoteženje distribucije nabora podatkov z odstranitvijo večine ključev, ki manjkajo v tabeli dejstev, s čimer učinkovito odstrani negativne vzorce iz nabora podatkov. Kasneje so bili le ključi, vključeni v začetni Bloomov filter, skupaj z lažnimi pozitivnimi rezultati, posredovani modelu ML, ki se pogosto imenuje "naučeni orakelj". Rezultat tega pristopa je bil dobro uravnotežen nabor podatkov za usposabljanje naučenega orakulja, s čimer je učinkovito odpravljen problem pristranskosti.

Drugi izziv je bil osredotočen na arhitekturo modela in značilnosti usposabljanja. Za razliko od klasične težave URL-jev z lažnim predstavljanjem [1] naši ključi za pridružitev (ki so v večini primerov edinstveni identifikatorji za uporabnike/izkušnje) sami po sebi niso bili informativni. To nas je vodilo k raziskovanju atributov razsežnosti kot potencialnih funkcij modela, ki lahko pomagajo napovedati, ali je entiteta razsežnosti prisotna v tabeli dejstev. Na primer, predstavljajte si tabelo dejstev, ki vsebuje informacije o uporabniški seji za izkušnje v določenem jeziku. Geografska lokacija ali atribut jezikovnih preferenc uporabniške dimenzije bi bil dober pokazatelj, ali je posamezni uporabnik prisoten v tabeli dejstev ali ne.

Tretji izziv – zakasnitev sklepanja – je zahteval modele, ki so minimizirali lažne negative in zagotavljali hitre odzive. Drevesni model s prelivom je bil optimalna izbira za te ključne metrike, zato smo zmanjšali njegov nabor funkcij, da bi uravnotežili natančnost in hitrost.

Naša posodobljena poizvedba za pridružitev z uporabo naučenih Bloomovih filtrov je prikazana spodaj:

Rezultati

Tukaj so rezultati naših poskusov s filtri Learned Bloom v našem podatkovnem jezeru. Integrirali smo jih v pet produkcijskih delovnih obremenitev, od katerih je vsaka imela različne podatkovne lastnosti. Računalniško najdražji del teh delovnih obremenitev je povezava med tabelo dejstev in tabelo dimenzij. Ključni prostor tabel dejstev je približno 30 % dimenzijske tabele. Za začetek razpravljamo o tem, kako je naučeni filter Bloom presegel tradicionalne filtre Bloom v smislu končne serializirane velikosti objekta. Nato prikazujemo izboljšave zmogljivosti, ki smo jih opazili z integracijo naučenih Bloomovih filtrov v naše cevovode za obdelavo delovne obremenitve.

Naučena primerjava velikosti filtra Bloom

Kot je prikazano spodaj, če pogledamo dano lažno pozitivno stopnjo, obe različici naučenega Bloomovega filtra izboljšata skupno velikost predmeta za 17–42 % v primerjavi s tradicionalnimi Bloomovimi filtri.

Poleg tega smo z uporabo manjše podmnožice funkcij v našem modelu, ki temelji na drevesu s povečanim gradientom, izgubili le majhen odstotek optimizacije, medtem ko je bilo sklepanje hitrejše.

Naučeni rezultati uporabe filtra Bloom

V tem razdelku primerjamo uspešnost združevanj, ki temeljijo na filtru Bloom, z uspešnostjo običajnih združevanj v več meritvah.

Spodnja tabela primerja zmogljivost delovnih obremenitev z in brez uporabe naučenih Bloomovih filtrov. Naučeni Bloomov filter z 1-odstotno skupno lažno pozitivno verjetnostjo prikazuje spodnjo primerjavo, medtem ko ohranja isto konfiguracijo gruče za obe vrsti združevanja.

Najprej smo ugotovili, da je implementacija filtra Bloom prekašala običajno združevanje za kar 60 % v urah procesorja. Opazili smo povečanje uporabe procesorja pri koraku skeniranja za pristop naučenega Bloomovega filtra zaradi dodatnega računanja, porabljenega za ocenjevanje Bloomovega filtra. Vendar pa je predhodno filtriranje, opravljeno v tem koraku, zmanjšalo velikost podatkov, ki se mešajo, kar je pomagalo zmanjšati CPE, ki ga uporabljajo spodnji koraki, s čimer se je zmanjšalo skupno število ur CPE.

Drugič, naučeni Bloomovi filtri imajo približno 80 % manjšo skupno velikost podatkov in približno 80 % manj skupnih naključnih bajtov zapisanih kot običajno združevanje. To vodi do stabilnejšega delovanja združevanja, kot je opisano spodaj.

Opazili smo tudi zmanjšano porabo virov pri drugih proizvodnih delovnih obremenitvah, ki smo jih preizkušali. V obdobju dveh tednov pri vseh petih delovnih obremenitvah je pristop Learned Bloom Filter ustvaril povprečje dnevni prihranek stroškov of 25% kar upošteva tudi usposabljanje modela in ustvarjanje indeksa.

Zaradi zmanjšane količine podatkov, premešanih med izvajanjem združevanja, smo lahko znatno zmanjšali operativne stroške našega analitičnega cevovoda, hkrati pa ga naredili bolj stabilnega. Naslednja tabela prikazuje variabilnost (z uporabo koeficienta variacije) v trajanju izvajanja (stena ura) za običajno delovno obremenitev združevanja in delovno obremenitev na podlagi naučenega Bloomovega filtra v obdobju dveh tednov za pet delovnih obremenitev, s katerimi smo eksperimentirali. Zagoni z uporabo naučenih Bloomovih filtrov so bili bolj stabilni – bolj dosledni v trajanju – kar odpira možnost, da jih premaknete na cenejše prehodne nezanesljive računalniške vire.