Comment Roblox réduit les coûts des requêtes Spark Join grâce aux filtres Bloom optimisés pour l'apprentissage automatique - Roblox Blog

Republié par Platon

Suiveurs: 0

Abstract

Chaque jour sur Roblox, 65.5 millions d'utilisateurs participent à des millions d'expériences, pour un total de 14.0 milliards d’heures par trimestre. Cette interaction génère un lac de données à l'échelle du pétaoctet, qui est enrichi à des fins d'analyse et d'apprentissage automatique (ML). La jonction de tables de faits et de dimensions dans notre lac de données nécessite beaucoup de ressources. Pour optimiser cela et réduire le brassage des données, nous avons adopté les filtres Learned Bloom [1], des structures de données intelligentes utilisant le ML. En prédisant la présence, ces filtres réduisent considérablement les données de jointure, améliorant ainsi l'efficacité et réduisant les coûts. En cours de route, nous avons également amélioré nos architectures de modèles et démontré les avantages substantiels qu'elles offrent en matière de réduction des heures de mémoire et de processeur pour le traitement, ainsi qu'en augmentant la stabilité opérationnelle.

Introduction

Dans notre lac de données, les tables de faits et les cubes de données sont partitionnés temporellement pour un accès efficace, tandis que les tables de dimensions ne disposent pas de telles partitions, et les joindre aux tables de faits lors des mises à jour nécessite beaucoup de ressources. L'espace clé de la jointure est déterminé par la partition temporelle de la table de faits à joindre. Les entités dimensionnelles présentes dans cette partition temporelle constituent un petit sous-ensemble de celles présentes dans l'ensemble de données dimensionnelles. En conséquence, la majorité des données de dimension mélangées dans ces jointures sont finalement supprimées.. Pour optimiser ce processus et réduire les brassages inutiles, nous avons envisagé d'utiliser Filtres Bloom sur des clés de jointure distinctes, mais confronté à des problèmes de taille de filtre et d'empreinte mémoire.

Pour y répondre, nous avons exploré Filtres de floraison appris, une solution basée sur le ML qui réduit la taille du filtre Bloom tout en maintenant de faibles taux de faux positifs. Cette innovation améliore l'efficacité des opérations de jointure en réduisant les coûts de calcul et en améliorant la stabilité du système. Le schéma suivant illustre les processus de jointure conventionnels et optimisés dans notre environnement informatique distribué.

Améliorer l'efficacité des jointures grâce aux filtres Bloom appris

Pour optimiser la jointure entre les tables de faits et de dimensions, nous avons adopté l'implémentation du Learned Bloom Filter. Nous avons construit un index à partir des clés présentes dans la table de faits et avons ensuite déployé l'index pour pré-filtrer les données de dimension avant l'opération de jointure.

Evolution des filtres de floraison traditionnels aux filtres de floraison appris

Bien qu'un filtre Bloom traditionnel soit efficace, il ajoute 15 à 25 % de mémoire supplémentaire par nœud de travail devant le charger pour atteindre le taux de faux positifs souhaité. Mais en exploitant les filtres Learned Bloom, nous avons obtenu une taille d’index considérablement réduite tout en conservant le même taux de faux positifs. Cela est dû à la transformation du filtre Bloom en un problème de classification binaire. Les étiquettes positives indiquent la présence de valeurs dans l'index, tandis que les étiquettes négatives signifient qu'elles sont absentes.

L'introduction d'un modèle ML facilite la vérification initiale des valeurs, suivie d'un filtre Bloom de secours pour éliminer les faux négatifs. La taille réduite provient de la représentation compressée du modèle et du nombre réduit de clés requises par le filtre Bloom de sauvegarde. Cela la distingue de l’approche conventionnelle du Bloom Filter.

Dans le cadre de ce travail, nous avons établi deux métriques pour évaluer notre approche Learned Bloom Filter : la taille finale de l'objet sérialisé de l'index et la consommation CPU lors de l'exécution des requêtes de jointure.

Relever les défis de mise en œuvre

Notre défi initial consistait à traiter un ensemble de données de formation très biaisé avec peu de clés de table de dimensions dans la table de faits. Ce faisant, nous avons observé un chevauchement d’environ une clé sur trois entre les tables. Pour résoudre ce problème, nous avons exploité l’approche Sandwich Learned Bloom Filter [2]. Celui-ci intègre un filtre Bloom traditionnel initial pour rééquilibrer la distribution de l'ensemble de données en supprimant la majorité des clés manquantes de la table de faits, éliminant ainsi efficacement les échantillons négatifs de l'ensemble de données. Par la suite, seules les clés incluses dans le filtre Bloom initial, ainsi que les faux positifs, ont été transmises au modèle ML, souvent appelé « l'oracle érudit ». Cette approche a abouti à un ensemble de données de formation bien équilibré pour l'oracle érudit, surmontant efficacement le problème de biais.

Le deuxième défi était centré sur l'architecture du modèle et les fonctionnalités de formation. Contrairement au problème classique des URL de phishing [1], nos clés de jointure (qui dans la plupart des cas sont des identifiants uniques pour les utilisateurs/expériences) n'étaient pas intrinsèquement informatives. Cela nous a amené à explorer les attributs de dimension en tant que fonctionnalités potentielles du modèle qui peuvent aider à prédire si une entité de dimension est présente dans la table de faits. Par exemple, imaginez une table de faits contenant des informations sur la session utilisateur pour les expériences dans une langue particulière. L'emplacement géographique ou l'attribut de préférence linguistique de la dimension utilisateur seraient de bons indicateurs pour savoir si un utilisateur individuel est présent ou non dans la table de faits.

Le troisième défi – la latence d’inférence – nécessitait des modèles capables à la fois de minimiser les faux négatifs et de fournir des réponses rapides. Un modèle d'arbre amélioré par le gradient était le choix optimal pour ces mesures clés, et nous avons élagué son ensemble de fonctionnalités pour équilibrer précision et vitesse.

Notre requête de jointure mise à jour à l'aide des filtres Bloom appris est la suivante :

Résultats

Voici les résultats de nos expériences avec les filtres Learned Bloom dans notre lac de données. Nous les avons intégrés dans cinq charges de travail de production, chacune possédant des caractéristiques de données différentes. La partie la plus coûteuse en calcul de ces charges de travail est la jointure entre une table de faits et une table de dimensions. L'espace clé des tables de faits représente environ 30 % de la table de dimensions. Pour commencer, nous expliquons comment le filtre Bloom appris a surpassé les filtres Bloom traditionnels en termes de taille finale de l'objet sérialisé. Nous montrons ensuite les améliorations de performances que nous avons observées en intégrant les filtres Learned Bloom dans nos pipelines de traitement de charge de travail.

Comparaison de la taille du filtre Bloom appris

Comme indiqué ci-dessous, lorsque l'on examine un taux de faux positifs donné, les deux variantes du filtre Bloom appris améliorent la taille totale de l'objet entre 17 et 42 % par rapport aux filtres Bloom traditionnels.

De plus, en utilisant un sous-ensemble plus petit de fonctionnalités dans notre modèle basé sur un arbre amélioré par gradient, nous n'avons perdu qu'un petit pourcentage d'optimisation tout en accélérant l'inférence.

Résultats d'utilisation du filtre Bloom appris

Dans cette section, nous comparons les performances des jointures basées sur Bloom Filter à celles des jointures régulières sur plusieurs métriques.

Le tableau ci-dessous compare les performances des charges de travail avec et sans l'utilisation des filtres Learned Bloom. Un filtre Bloom appris avec une probabilité totale de faux positifs de 1 % démontre la comparaison ci-dessous tout en conservant la même configuration de cluster pour les deux types de jointure.

Premièrement, nous avons constaté que la mise en œuvre de Bloom Filter surpassait la jointure régulière jusqu'à 60 % en heures CPU. Nous avons constaté une augmentation de l'utilisation du processeur lors de l'étape d'analyse pour l'approche du filtre Bloom appris en raison du calcul supplémentaire consacré à l'évaluation du filtre Bloom. Cependant, le préfiltrage effectué au cours de cette étape a réduit la taille des données mélangées, ce qui a contribué à réduire le processeur utilisé par les étapes en aval, réduisant ainsi le nombre total d'heures de processeur.

Deuxièmement, les filtres Bloom appris ont environ 80 % de taille de données totale en moins et environ 80 % d'octets de lecture aléatoire en moins qu'une jointure classique. Cela conduit à des performances de jointure plus stables, comme indiqué ci-dessous.

Nous avons également constaté une réduction de l’utilisation des ressources dans nos autres charges de travail de production en cours d’expérimentation. Sur une période de deux semaines pour les cinq charges de travail, l'approche Learned Bloom Filter a généré en moyenne économies de coûts quotidiennes of % 25, qui prend également en compte la formation du modèle et la création d'index.

En raison de la quantité réduite de données mélangées lors de l'exécution de la jointure, nous avons pu réduire considérablement les coûts opérationnels de notre pipeline d'analyse tout en le rendant plus stable. Le graphique suivant montre la variabilité (à l'aide d'un coefficient de variation) des durées d'exécution (mur horloge) pour une charge de travail de jointure régulière et une charge de travail basée sur le filtre Bloom appris sur une période de deux semaines pour les cinq charges de travail que nous avons expérimentées. Les exécutions utilisant les filtres Learned Bloom étaient plus stables (durée plus constante), ce qui ouvre la possibilité de les déplacer vers des ressources de calcul peu fiables, transitoires et moins chères.

Bibliographie

[1] T. Kraska, A. Beutel, EH Chi, J. Dean et N. Polyzotis. Les arguments en faveur des structures d’index apprises. https://arxiv.org/abs/1712.01208 2017.

[2] M. Mitzenmacher. Optimisation des filtres de floraison appris par sandwich.

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

¹Période de 3 mois terminée le 30 juin 2023

²Au 3 mois clos le 30 juin 2023