Wie Roblox die Kosten für Spark-Join-Abfragen mit für maschinelles Lernen optimierten Bloom-Filtern senkt – Roblox-Blog

Wie Roblox die Kosten für Spark-Join-Abfragen mit für maschinelles Lernen optimierten Bloom-Filtern senkt – Roblox-Blog

Zeitstempel: 28. November 2023, 12:23 Uhr
Quellknoten: 2983061

Abstrakt

Jeden Tag auf Roblox, 65.5 Millionen Benutzer interagieren mit Millionen von Erlebnissen, insgesamt 14.0 Milliarden Stunden vierteljährlich. Durch diese Interaktion entsteht ein Datensee im Petabyte-Bereich, der für Analyse- und maschinelle Lernzwecke (ML) angereichert wird. Das Zusammenführen von Fakten- und Dimensionstabellen in unserem Datensee ist ressourcenintensiv. Um dies zu optimieren und die Datenverschiebung zu reduzieren, haben wir Learned Bloom Filters [1] eingeführt – intelligente Datenstrukturen mithilfe von ML. Durch die Vorhersage der Anwesenheit reduzieren diese Filter die Verbindungsdaten erheblich, wodurch die Effizienz gesteigert und die Kosten gesenkt werden. Im Zuge dessen haben wir auch unsere Modellarchitekturen verbessert und die erheblichen Vorteile demonstriert, die sie hinsichtlich der Reduzierung von Arbeitsspeicher und CPU-Stunden für die Verarbeitung sowie einer 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 über solche Partitionen verfügen und ihre Verknüpfung mit Faktentabellen bei Aktualisierungen ressourcenintensiv ist. Der Schlüsselraum des Joins wird durch die zeitliche Partition der zu verbindenden Faktentabelle bestimmt. Die in dieser zeitlichen Partition vorhandenen Dimensionsentitäten sind eine kleine Teilmenge derjenigen, 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, haben wir über die Verwendung nachgedacht Blütenfilter auf unterschiedlichen Join-Schlüsseln, hatte jedoch Probleme mit der Filtergröße und dem Speicherbedarf.

Um sie anzugehen, haben wir nachgeforscht Bloom-Filter gelernt, eine ML-basierte Lösung, die die Größe des Bloom-Filters reduziert und gleichzeitig niedrige Falsch-Positiv-Raten beibehält. Diese Innovation steigert die Effizienz von Join-Vorgängen, indem sie die Rechenkosten senkt und die Systemstabilität verbessert. Das folgende Schema veranschaulicht die herkömmlichen und optimierten Join-Prozesse in unserer verteilten Computerumgebung.

Verbesserung der Verbindungseffizienz mit erlernten Bloom-Filtern

Um die Verbindung zwischen Fakten- und Dimensionstabellen zu optimieren, haben wir die Implementierung des Learned Bloom Filters übernommen. Wir haben aus den in der Faktentabelle vorhandenen Schlüsseln einen Index erstellt und den Index anschließend bereitgestellt, um Dimensionsdaten vor dem Join-Vorgang vorzufiltern. 

Entwicklung von traditionellen Bloom-Filtern zu erlernten Bloom-Filtern

Während ein herkömmlicher Bloom-Filter effizient ist, fügt er 15–25 % zusätzlichen Speicher pro Worker-Knoten hinzu, der geladen werden muss, um unsere gewünschte Falsch-Positiv-Rate zu erreichen. Aber durch die Nutzung von Learned-Bloom-Filtern haben wir eine erheblich reduzierte Indexgröße bei gleichbleibender Falsch-Positiv-Rate erreicht. Dies liegt an der Umwandlung des Bloom-Filters in ein binäres Klassifizierungsproblem. Positive Bezeichnungen zeigen das Vorhandensein von Werten im Index an, während negative Bezeichnungen bedeuten, dass sie nicht vorhanden sind.

Die Einführung eines ML-Modells erleichtert die anfängliche Überprüfung der Werte, gefolgt von einem Backup-Bloom-Filter zur Eliminierung falsch-negativer Ergebnisse. Die reduzierte Größe ergibt sich aus der komprimierten Darstellung des Modells und der reduzierten Anzahl von Schlüsseln, die für den Backup-Bloom-Filter erforderlich sind. 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 serialisierte Objektgröße des Index und den CPU-Verbrauch während der Ausführung von Join-Abfragen. 

Herausforderungen bei der Umsetzung meistern

Unsere anfängliche Herausforderung bestand darin, einen stark verzerrten Trainingsdatensatz mit wenigen Dimensionstabellenschlüsseln in der Faktentabelle zu bearbeiten. Dabei beobachteten wir eine Überlappung von etwa jedem dritten Schlüssel zwischen den Tabellen. Um dieses Problem anzugehen, haben wir den Sandwich Learned Bloom Filter-Ansatz [2] genutzt. Dies integriert einen anfänglichen traditionellen Bloom-Filter, um die Datensatzverteilung neu auszubalancieren, indem die Mehrheit der Schlüssel, die in der Faktentabelle fehlten, entfernt wird, wodurch negative Stichproben effektiv aus dem Datensatz entfernt werden. Anschließend wurden nur die im ursprünglichen Bloom-Filter enthaltenen Schlüssel zusammen mit den falsch positiven Ergebnissen 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 Bias-Problem effektiv.

Die zweite Herausforderung konzentrierte sich auf Modellarchitektur und Trainingsfunktionen. Im Gegensatz zum klassischen Problem der Phishing-URLs [1] waren unsere Verbindungsschlüssel (bei denen es sich in den meisten Fällen um eindeutige Kennungen für Benutzer/Erfahrungen handelt) nicht von Natur aus informativ. 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 Benutzersitzungsinformationen für Erlebnisse in einer bestimmten Sprache enthält. Der geografische Standort oder das Sprachpräferenzattribut der Benutzerdimension wären gute Indikatoren dafür, ob ein einzelner Benutzer in der Faktentabelle vorhanden ist oder nicht.

Die dritte Herausforderung – die Inferenzlatenz – erforderte Modelle, die sowohl falsch-negative Ergebnisse minimierten als auch schnelle Antworten lieferten. Für diese Schlüsselmetriken war ein verlaufsverstärktes Baummodell die optimale Wahl, und wir haben seinen Funktionsumfang beschnitten, um Präzision und Geschwindigkeit in Einklang zu bringen.

Unsere aktualisierte Join-Abfrage mit erlernten Bloom-Filtern sieht wie folgt aus:

Die Ergebnisse

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

Größenvergleich der erlernten Bloom-Filter

Wie unten gezeigt, verbessern die beiden Varianten des erlernten Bloom-Filters bei Betrachtung einer bestimmten Falsch-Positiv-Rate die Gesamtobjektgröße im Vergleich zu herkömmlichen Bloom-Filtern um 17–42 %.

Darüber hinaus haben wir durch die Verwendung einer kleineren Teilmenge von Funktionen in unserem baumbasierten Modell mit Gradientenverstärkung nur einen kleinen Prozentsatz der Optimierung verloren und gleichzeitig die Schlussfolgerung beschleunigt.

Erlernte Ergebnisse der Bloom-Filternutzung 

In diesem Abschnitt vergleichen wir die Leistung von Bloom-Filter-basierten Verknüpfungen mit der Leistung regulärer Verknüpfungen anhand mehrerer Metriken. 

Die folgende Tabelle vergleicht die Leistung von Workloads mit und ohne Verwendung von Learned Bloom Filters. Ein erlernter Bloom-Filter mit einer Falsch-Positiv-Gesamtwahrscheinlichkeit von 1 % zeigt den folgenden Vergleich, wobei für beide Verknüpfungstypen die gleiche Clusterkonfiguration beibehalten wird. 

Erstens haben wir herausgefunden, dass die Bloom-Filter-Implementierung den regulären Join um bis zu 60 % bei den CPU-Stunden übertrifft. Aufgrund der zusätzlichen Rechenleistung, die für die Auswertung des Bloom-Filters aufgewendet wurde, konnten wir einen Anstieg der CPU-Auslastung des Scanschritts für den Learned-Bloom-Filter-Ansatz feststellen. Die in diesem Schritt durchgeführte Vorfilterung reduzierte jedoch die Größe der gemischten Daten, was dazu beitrug, die von den nachgelagerten Schritten beanspruchte CPU zu reduzieren und somit die Gesamt-CPU-Stunden zu reduzieren.

Zweitens haben Learned-Bloom-Filter etwa 80 % weniger Gesamtdatengröße und etwa 80 % weniger insgesamt geschriebene Shuffle-Bytes als ein regulärer Join. Dies führt zu einer stabileren Join-Leistung, wie unten erläutert. 

Auch bei unseren anderen getesteten Produktions-Workloads konnten wir einen geringeren Ressourcenverbrauch feststellen. Über einen Zeitraum von zwei Wochen generierte der Learned-Bloom-Filter-Ansatz für alle fünf Workloads einen Durchschnitt tägliche Kosteneinsparungen of 25%, Dies berücksichtigt auch das Modelltraining und die Indexerstellung.

Aufgrund der geringeren Datenmenge, die während der Verknüpfung gemischt wird, konnten wir die Betriebskosten unserer Analysepipeline erheblich senken und sie gleichzeitig stabiler machen. Das folgende Diagramm zeigt die Variabilität (unter Verwendung eines Variationskoeffizienten) in der Laufdauer (Wall). Uhrzeit) für eine reguläre Join-Arbeitslast und eine auf dem Learned Bloom Filter basierende Arbeitslast über einen Zeitraum von zwei Wochen für die fünf Arbeitslasten, mit denen wir experimentiert haben. Die Läufe mit Learned-Bloom-Filtern waren stabiler – konsistenter in der Dauer – was die Möglichkeit eröffnet, sie auf günstigere, vorübergehend unzuverlässige Rechenressourcen zu verlagern. 

Bibliographie

[1] T. Kraska, A. Beutel, EH Chi, J. Dean und N. Polyzotis. Das Argument für erlernte Indexstrukturen. https://arxiv.org/abs/1712.01208 2017.

[2] M. Mitzenmacher. Optimierung erlernter Bloom-Filter durch Sandwiching. 

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

¹Stand: 3 Monate bis zum 30. Juni 2023

²Stand: 3 Monate bis zum 30. Juni 2023

Zeitstempel:

Mehr von Roblox