Wie Roblox die Kosten für Spark-Join-Abfragen mit maschinell lernoptimierten Bloom-Filtern senkt

Zusammenfassung

Jeden Tag nutzen 70 Millionen Nutzer auf Roblox Millionen von Erlebnissen, was vierteljährlich insgesamt 16 Milliarden Stunden ergibt. Diese Interaktion erzeugt einen Data Lake im Petabyte-Bereich, der für Analyse- und Machine-Learning-Zwecke (ML) angereichert wird. Das Verknüpfen von Fakten- und Dimensionstabellen in unserem Data Lake ist ressourcenintensiv. Um dies zu optimieren und den Datenaustausch zu reduzieren, haben wir Learned Bloom Filters [1] eingesetzt – intelligente Datenstrukturen, die ML nutzen. Durch die Vorhersage der Anwesenheit reduzieren diese Filter die zu verknüpfenden Daten erheblich, was die Effizienz steigert und Kosten senkt. Dabei haben wir auch unsere Modellarchitekturen verbessert und die erheblichen Vorteile aufgezeigt, die sie hinsichtlich der Reduzierung von Speicher- und CPU-Ressourcen für die Verarbeitung sowie der Erhöhung der Betriebsstabilität bieten.

Einleitung

In unserem Data Lake sind Faktentabellen und Datenwürfel für einen effizienten Zugriff zeitlich partitioniert, während Dimensionstabellen keine solchen Partitionen aufweisen und ihre Verknüpfung mit Faktentabellen bei Aktualisierungen ressourcenintensiv ist. Der Schlüsselraum der Verknüpfung wird durch die zeitliche Partition der zu verknüpfenden Faktentabelle bestimmt. Die in dieser zeitlichen Partition vorhandenen Dimensionsentitäten stellen nur eine kleine Teilmenge derjenigen dar, die im gesamten Dimensionsdatensatz vorhanden sind. Infolgedessen wird der Großteil der gemischten Dimensionsdaten in diesen Verknüpfungen letztendlich verworfen. Um diesen Prozess zu optimieren und unnötiges Mischen zu reduzieren, erwogen wir den Einsatz von Bloom-Filtern auf eindeutigen Verknüpfungsschlüsseln, stießen jedoch auf Probleme hinsichtlich Filtergröße und Speicherbedarf.

Um diese zu lösen, haben wir uns mit „Learned Bloom Filters“ befasst, einer ML-basierten Lösung, die die Größe der Bloom-Filter reduziert und gleichzeitig niedrige Falsch-Positiv-Raten beibehält. Diese Innovation steigert die Effizienz von Join-Operationen, indem sie den Rechenaufwand senkt und die Systemstabilität verbessert. Das folgende Schema veranschaulicht die herkömmlichen und optimierten Join-Prozesse in unserer verteilten Rechenumgebung.

Verbesserung der Join-Effizienz mit Learned Bloom Filters

Um die Verknüpfung zwischen Fakt- und Dimensionstabellen zu optimieren, haben wir die Implementierung des „Learned Bloom Filter“ übernommen. Wir haben einen Index aus den in der Faktentabelle vorhandenen Schlüsseln erstellt und diesen anschließend eingesetzt, um die Dimensionsdaten vor der Verknüpfungsoperation vorzufiltern. 

Entwicklung von traditionellen Bloom-Filtern zu gelernten Bloom-Filtern

Ein traditioneller Bloom-Filter ist zwar effizient, benötigt jedoch 15–25 % zusätzlichen Speicher pro Worker-Knoten, der ihn laden muss, um unsere gewünschte Falsch-Positiv-Rate zu erreichen. Durch den Einsatz von Learned Bloom Filters konnten wir jedoch eine deutlich reduzierte Indexgröße erzielen und gleichzeitig die gleiche Falsch-Positiv-Rate beibehalten. Dies liegt an der Umwandlung des Bloom-Filters in ein binäres Klassifizierungsproblem. Positive Labels zeigen das Vorhandensein von Werten im Index an, während negative Labels bedeuten, dass sie fehlen.

Die Einführung eines ML-Modells erleichtert die anfängliche Überprüfung auf Werte, gefolgt von einem Backup-Bloom-Filter zur Eliminierung von Falsch-Negativen. Die reduzierte Größe resultiert aus der komprimierten Darstellung des Modells und der geringeren Anzahl von Schlüsseln, die der Backup-Bloom-Filter benötigt. Dies unterscheidet ihn vom herkömmlichen Bloom-Filter-Ansatz. 

Im Rahmen dieser Arbeit haben wir zwei Metriken zur Bewertung unseres „Learned Bloom Filter“-Ansatzes festgelegt: die endgültige Größe des serialisierten Indexobjekts und den CPU-Verbrauch während der Ausführung von Join-Abfragen. 

Bewältigung von Implementierungsherausforderungen

Unsere anfängliche Herausforderung bestand darin, einen stark verzerrten Trainingsdatensatz mit wenigen Dimensionsschlüsseln in der Faktentabelle zu bewältigen. Dabei stellten wir eine Überschneidung von etwa einem Drittel der Schlüssel zwischen den Tabellen fest. Um dies zu lösen, nutzten wir den „Sandwich Learned Bloom Filter“-Ansatz [2]. Dieser integriert einen anfänglichen traditionellen Bloom-Filter, um die Verteilung des Datensatzes neu auszubalancieren, indem er die Mehrheit der Schlüssel entfernt, die in der Faktentabelle fehlten, wodurch negative Samples effektiv aus dem Datensatz eliminiert werden. Anschließend wurden nur die im anfänglichen Bloom-Filter enthaltenen Schlüssel zusammen mit den Falsch-Positiven an das ML-Modell weitergeleitet, das oft als „gelerntes Orakel“ bezeichnet wird. Dieser Ansatz führte zu einem ausgewogenen Trainingsdatensatz für das gelernte Orakel und überwand das Verzerrungsproblem effektiv.

Die zweite Herausforderung betraf die Modellarchitektur und die Trainingsmerkmale. Im Gegensatz zum klassischen Problem der Phishing-URLs [1] waren unsere Verknüpfungsschlüssel (die in den meisten Fällen eindeutige Identifikatoren für Benutzer/Erlebnisse sind) an sich nicht aussagekräftig. Dies veranlasste uns, Dimensionsattribute als potenzielle Modellmerkmale zu untersuchen, die dabei helfen können, vorherzusagen, ob eine Dimensionsentität in der Faktentabelle vorhanden ist. Stellen Sie sich beispielsweise eine Faktentabelle vor, die Informationen zu Benutzersitzungen für Erlebnisse in einer bestimmten Sprache enthält. Der geografische Standort oder das Attribut zur Sprachpräferenz der Benutzerdimension wären gute Indikatoren dafür, ob ein einzelner Benutzer in der Faktentabelle vorhanden ist oder nicht.

Die dritte Herausforderung – die Latenz bei der Inferenz – erforderte Modelle, die sowohl Falsch-Negative minimierten als auch schnelle Antworten lieferten. Ein Gradient-Boosted-Tree-Modell war die optimale Wahl für diese Schlüsselkennzahlen, und wir haben dessen Merkmalsatz bereinigt, um Präzision und Geschwindigkeit in Einklang zu bringen.

Unsere aktualisierte Join-Abfrage unter Verwendung gelernter Bloom-Filter sieht wie folgt aus:

Ergebnisse

Hier sind die Ergebnisse unserer Experimente mit Learned Bloom-Filtern in unserem Data Lake. Wir haben sie in fünf Produktions-Workloads integriert, von denen jede unterschiedliche Datenmerkmale aufwies. Der rechenintensivste Teil dieser Workloads ist die Verknüpfung zwischen einer Faktentabelle und einer Dimensionstabelle. Der Schlüsselraum der Faktentabellen beträgt etwa 30 % desjenigen der Dimensionstabelle. Zunächst diskutieren wir, wie der Learned Bloom Filter herkömmliche Bloom-Filter hinsichtlich der endgültigen Größe des serialisierten Objekts übertraf. Als Nächstes zeigen wir Leistungsverbesserungen auf, die wir durch die Integration von Learned Bloom Filtern in unsere Workload-Verarbeitungspipelines beobachtet haben.

Größenvergleich des Learned Bloom Filters

Wie unten dargestellt, verbessern die beiden Varianten des Learned Bloom Filters bei einer gegebenen Falsch-Positiv-Rate die Gesamtgröße der Objekte im Vergleich zu herkömmlichen Bloom-Filtern um 17 bis 42 %.

Darüber hinaus haben wir durch die Verwendung einer kleineren Teilmenge von Merkmalen in unserem auf Gradient Boosted Trees basierenden Modell nur einen geringen Prozentsatz an Optimierung eingebüßt, während die Inferenz schneller wurde.

Ergebnisse zur Verwendung von Bloom-Filtern 

In diesem Abschnitt vergleichen wir die Leistung von Bloom-Filter-basierten Joins mit der von regulären Joins anhand verschiedener Metriken. 

Die folgende Tabelle vergleicht die Leistung von Workloads mit und ohne Verwendung von Learned Bloom Filters. Ein Learned Bloom Filter mit einer Gesamt-Falsch-Positiv-Wahrscheinlichkeit von 1 % veranschaulicht den folgenden Vergleich, wobei für beide Join-Typen die gleiche Clusterkonfiguration beibehalten wird. 

Erstens stellten wir fest, dass die Bloom-Filter-Implementierung den regulären Join in Bezug auf die CPU-Stunden um bis zu 60 % übertraf. Wir beobachteten einen Anstieg der CPU-Auslastung im Scan-Schritt beim Learned-Bloom-Filter-Ansatz, der auf den zusätzlichen Rechenaufwand bei der Auswertung des Bloom-Filters zurückzuführen war. Die in diesem Schritt durchgeführte Vorfilterung reduzierte jedoch die Größe der zu sortierenden Daten, was dazu beitrug, die CPU-Auslastung in den nachfolgenden Schritten zu senken und somit die Gesamtzahl der CPU-Stunden zu verringern.

Zweitens weisen Learned Bloom Filter eine um etwa 80 % geringere Gesamtdatenmenge und etwa 80 % weniger geschriebene Shuffle-Bytes auf als ein regulärer Join. Dies führt zu einer stabileren Join-Leistung, wie weiter unten erläutert wird. 

Wir konnten auch bei unseren anderen Produktions-Workloads, die im Rahmen des Experiments getestet wurden, einen geringeren Ressourcenverbrauch feststellen. Über einen Zeitraum von zwei Wochen erzielte der „Learned Bloom Filter“-Ansatz bei allen fünf Workloads durchschnittliche tägliche Kosteneinsparungen von 25 %, wobei auch das Modelltraining und die Indexerstellung berücksichtigt wurden.

Aufgrund der geringeren Menge an Daten, die während der Durchführung des Joins verschoben wurden, konnten wir die Betriebskosten unserer Analyse-Pipeline deutlich senken und sie gleichzeitig stabiler machen. Die folgende Grafik zeigt die Variabilität (unter Verwendung eines Variationskoeffizienten) der Laufzeiten (Wall-Clock-Zeit) für eine reguläre Join-Workload und eine auf Learned Bloom Filters basierende Workload über einen Zeitraum von zwei Wochen für die fünf Workloads, mit denen wir experimentiert haben. Die Läufe mit Learned Bloom Filters waren stabiler – d. h. konsistenter in der Dauer –, was die Möglichkeit eröffnet, sie auf kostengünstigere, vorübergehend unzuverlässige Rechenressourcen zu verlagern. 

Referenzen

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

[2] M. Mitzenmacher. Optimizing Learned Bloom Filters by Sandwiching. 

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

¹Stand: 3-Monats-Periode zum 30. Juni 2023

²Stand: 3 Monate bis zum 30. Juni 2023