Jak Roblox obniża koszty zapytań Spark Join dzięki filtrom Bloom zoptymalizowanym pod kątem uczenia maszynowego

Streszczenie

Każdego dnia w serwisie Roblox 70 milionów użytkowników korzysta z milionów doświadczeń, co daje łącznie 16 miliardów godzin w ciągu kwartału. Interakcja ta generuje jezioro danych o wielkości petabajta, które jest wzbogacane do celów analitycznych i uczenia maszynowego (ML). Łączenie tabel faktów i wymiarów w naszym jeziorze danych wymaga dużych zasobów, więc aby to zoptymalizować i ograniczyć przetasowywanie danych, zastosowaliśmy filtry Learned Bloom [1] — inteligentne struktury danych wykorzystujące ML. Dzięki przewidywaniu obecności filtry te znacznie ograniczają ilość danych do połączenia, zwiększając wydajność i obniżając koszty. Jednocześnie ulepszyliśmy architekturę naszych modeli i wykazaliśmy, że oferują one znaczne korzyści w zakresie zmniejszenia zużycia pamięci i czasu pracy procesora podczas przetwarzania, a także zwiększenia stabilności operacyjnej.

Wprowadzenie

W naszym jeziorze danych tabele faktów i kostki danych są partycjonowane czasowo w celu zapewnienia wydajnego dostępu, podczas gdy tabele wymiarów nie posiadają takich partycji, a ich łączenie z tabelami faktów podczas aktualizacji jest procesem wymagającym dużych zasobów. Przestrzeń klucza połączenia jest determinowana przez partycję czasową łączonej tabeli faktów. Entities wymiarów obecne w tej partycji czasowej stanowią niewielki podzbiór tych obecnych w całym zbiorze danych wymiarów. W rezultacie większość przetasowanych danych wymiarów w tych połączeniach jest ostatecznie odrzucana. Aby zoptymalizować ten proces i ograniczyć niepotrzebne przetasowywanie, rozważaliśmy zastosowanie filtrów Blooma na odrębnych kluczach połączeń, ale napotkaliśmy problemy związane z rozmiarem filtrów i zajmowaną pamięcią.

Aby je rozwiązać, zbadaliśmy filtry Bloom typu „Learned”, rozwiązanie oparte na uczeniu maszynowym, które zmniejsza rozmiar filtrów Bloom przy zachowaniu niskiego wskaźnika fałszywych alarmów. Ta innowacja zwiększa wydajność operacji dołączania poprzez zmniejszenie kosztów obliczeniowych i poprawę stabilności systemu. Poniższy schemat ilustruje konwencjonalne i zoptymalizowane procesy dołączania w naszym środowisku obliczeniowym.

Zwiększanie wydajności połączeń za pomocą filtrów Bloom opartych na uczeniu

Aby zoptymalizować łączenie tabel faktów i wymiarów, wdrożyliśmy filtry Bloom typu „Learned”. Stworzyliśmy indeks na podstawie kluczy obecnych w tabeli faktów, a następnie wdrożyliśmy go w celu wstępnego filtrowania danych wymiarowych przed operacją łączenia. 

Ewolucja od tradycyjnych filtrów Bloom do filtrów Bloom opartych na uczeniu

Chociaż tradycyjny filtr Blooma jest wydajny, wymaga on 15–25% dodatkowej pamięci na każdy węzeł roboczy, który musi go załadować, aby osiągnąć pożądany wskaźnik fałszywych alarmów. Jednak dzięki wykorzystaniu filtrów Blooma opartych na uczeniu się udało nam się znacznie zmniejszyć rozmiar indeksu przy zachowaniu tego samego wskaźnika fałszywych alarmów. Wynika to z przekształcenia filtra Blooma w problem klasyfikacji binarnej. Etykiety pozytywne wskazują na obecność wartości w indeksie, natomiast etykiety negatywne oznaczają ich brak.

Wprowadzenie modelu uczenia maszynowego ułatwia wstępną kontrolę wartości, a następnie filtr Bloom służy jako zabezpieczenie w celu wyeliminowania wyników fałszywie negatywnych. Zmniejszony rozmiar wynika ze skompresowanej reprezentacji modelu oraz zmniejszonej liczby kluczy wymaganych przez filtr Bloom służący jako zabezpieczenie. To odróżnia go od konwencjonalnego podejścia opartego na filtrze Bloom. 

W ramach tej pracy ustaliliśmy dwa wskaźniki do oceny naszego podejścia opartego na filtru Bloom z uczeniem maszynowym: końcowy rozmiar zserializowanego obiektu indeksu oraz zużycie procesora podczas wykonywania zapytań typu join. 

Radzenie sobie z wyzwaniami związanymi z wdrożeniem

Naszym początkowym wyzwaniem było poradzenie sobie z wysoce stronniczym zbiorem danych szkoleniowych, zawierającym niewiele kluczy tabel wymiarowych w tabeli faktów. Zauważyliśmy przy tym, że około jedna trzecia kluczy w tabelach się pokrywała. Aby temu zaradzić, wykorzystaliśmy podejście typu „Sandwich Learned Bloom Filter” [2]. Polega ono na zintegrowaniu początkowego tradycyjnego filtra Blooma w celu zrównoważenia rozkładu zbioru danych poprzez usunięcie większości kluczy, których brakowało w tabeli faktów, co skutecznie eliminuje negatywne próbki z zbioru danych. Następnie do modelu ML, często nazywanego „wyuczonym wyrocznią”, przekazywano tylko klucze zawarte w początkowym filtrze Blooma wraz z fałszywymi alarmami. Podejście to zaowocowało dobrze zbilansowanym zbiorem danych szkoleniowych dla wyuczonej wyroczni, skutecznie rozwiązując problem stronniczości.

Drugie wyzwanie dotyczyło architektury modelu i cech szkoleniowych. W przeciwieństwie do klasycznego problemu adresów URL służących do phishingu [1], nasze klucze łączące (które w większości przypadków są unikalnymi identyfikatorami użytkowników/doświadczeń) nie były z natury rzeczy informacyjne. To skłoniło nas do zbadania atrybutów wymiarów jako potencjalnych cech modelu, które mogą pomóc w przewidywaniu, czy dana jednostka wymiaru występuje w tabeli faktów. Wyobraźmy sobie na przykład tabelę faktów zawierającą informacje o sesjach użytkowników dotyczących doświadczeń w określonym języku. Lokalizacja geograficzna lub atrybut preferencji językowych wymiaru użytkownika byłyby dobrymi wskaźnikami tego, czy dany użytkownik występuje w tabeli faktów, czy nie.

Trzecie wyzwanie — opóźnienie wnioskowania — wymagało modeli, które zarówno minimalizowałyby liczbę wyników fałszywie ujemnych, jak i zapewniałyby szybkie odpowiedzi. Model drzewa wzmocnionego gradientem był optymalnym wyborem dla tych kluczowych wskaźników, a my ograniczyliśmy jego zestaw cech, aby zrównoważyć precyzję i szybkość.

Nasze zaktualizowane zapytanie łączące wykorzystujące wyuczone filtry Blooma przedstawiono poniżej:

Wyniki

Oto wyniki naszych eksperymentów z filtrami Learned Bloom w naszym jeziorze danych. Zintegrowaliśmy je z pięcioma obciążeniami produkcyjnymi, z których każde miało inne cechy danych. Najbardziej obciążającą obliczeniowo częścią tych obciążeń jest połączenie tabeli faktów z tabelą wymiarów. Przestrzeń kluczy tabel faktów stanowi około 30% tabeli wymiarów. Na początek omówimy, w jaki sposób filtry Learned Bloom Filter przewyższały tradycyjne filtry Bloom pod względem końcowego rozmiaru obiektu zserializowanego. Następnie pokażemy poprawę wydajności, którą zaobserwowaliśmy po zintegrowaniu filtrów Learned Bloom Filter z naszymi potokami przetwarzania obciążeń.

Porównanie rozmiarów filtra Bloom typu Learned

Jak pokazano poniżej, przy danym wskaźniku fałszywych alarmów dwa warianty filtra Bloom typu „learned” zmniejszają całkowity rozmiar obiektu o 17–42% w porównaniu z tradycyjnymi filtrami Bloom.

Ponadto, dzięki zastosowaniu mniejszego podzbioru cech w naszym modelu opartym na drzewach z wzmocnieniem gradientowym, straciliśmy tylko niewielki procent optymalizacji, jednocześnie przyspieszając wnioskowanie.

Wyniki badań nad wykorzystaniem filtrów Blooma 

W tej sekcji porównujemy wydajność połączeń opartych na filtrze Blooma z wydajnością zwykłych połączeń w oparciu o kilka wskaźników. 

Poniższa tabela porównuje wydajność obciążeń z wykorzystaniem filtrów Bloom Filter opartych na uczeniu się oraz bez nich. Filtr Bloom Filter oparty na uczeniu się z całkowitym prawdopodobieństwem fałszywie pozytywnych wyników wynoszącym 1% ilustruje poniższe porównanie przy zachowaniu tej samej konfiguracji klastra dla obu typów połączeń. 

Po pierwsze, stwierdziliśmy, że implementacja filtra Blooma przewyższała zwykłe połączenie nawet o 60% pod względem godzin pracy procesora. Zaobserwowaliśmy wzrost wykorzystania procesora na etapie skanowania w przypadku podejścia opartego na filtrze Blooma z uczeniem się, co wynikało z dodatkowych obliczeń związanych z oceną filtra Blooma. Jednak wstępne filtrowanie przeprowadzone na tym etapie zmniejszyło rozmiar danych podlegających przetasowaniu, co pomogło zmniejszyć wykorzystanie procesora na kolejnych etapach, a tym samym skrócić łączną liczbę godzin pracy procesora.

Po drugie, filtry Bloom typu Learned mają o około 80% mniejszy całkowity rozmiar danych i o około 80% mniej zapisanych bajtów przetasowania niż zwykłe połączenie. Prowadzi to do bardziej stabilnej wydajności połączeń, jak omówiono poniżej. 

Zauważyliśmy również zmniejszone zużycie zasobów w innych naszych obciążeniach produkcyjnych objętych eksperymentem. W ciągu dwóch tygodni we wszystkich pięciu obciążeniach podejście oparte na filtru Bloom Filter wygenerowało średnie dzienne oszczędności kosztów na poziomie 25%, co uwzględnia również szkolenie modelu i tworzenie indeksów.

Dzięki zmniejszeniu ilości danych przetasowywanych podczas wykonywania połączenia udało nam się znacznie obniżyć koszty operacyjne naszego potoku analitycznego, jednocześnie zwiększając jego stabilność. Poniższy wykres przedstawia zmienność (przy użyciu współczynnika zmienności) czasów trwania przebiegów (czasu zegara systemowego) dla obciążenia z typowym połączeniem oraz obciążenia opartego na filtrach Bloom typu Learned w okresie dwóch tygodni dla pięciu obciążeń, na których przeprowadzaliśmy eksperymenty. Przebiegi z wykorzystaniem filtrów Bloomowych opartych na uczeniu się były bardziej stabilne — bardziej spójne pod względem czasu trwania — co otwiera możliwość przeniesienia ich na tańsze, tymczasowe i mniej niezawodne zasoby obliczeniowe. 

Bibliografia

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean i N. Polyzotis. The Case for Learned Index Structures. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. Optymalizacja wyuczonych filtrów Blooma poprzez stosowanie metody „sandwiching”. 

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

¹Na dzień 30 czerwca 2023 r.

²Na dzień 30 czerwca 2023 r.