Comment Roblox réduit les coûts des requêtes Spark JOIN grâce à des filtres Bloom optimisés par apprentissage automatique

Résumé

Chaque jour sur Roblox, 70 millions d'utilisateurs interagissent avec des millions d'expériences, pour un total de 16 milliards d'heures par trimestre. Cette interaction génère un lac de données de l'ordre du pétaoctet, enrichi à des fins d'analyse et d'apprentissage automatique (ML). La jointure des tables de faits et de dimensions dans notre lac de données est très gourmande en ressources ; afin d'optimiser ce processus et de réduire le brassage des données, nous avons adopté les filtres de Bloom appris [1] — des structures de données intelligentes utilisant l'apprentissage automatique. En prédisant la présence, ces filtres réduisent considérablement le volume de données à joindre, ce qui améliore l'efficacité et réduit les coûts. Ce faisant, nous avons également amélioré nos architectures de modèles et démontré les avantages substantiels qu'elles offrent en termes de réduction de la mémoire et des heures de CPU nécessaires au traitement, ainsi que d'augmentation de 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 leur jointure avec les tables de faits lors des mises à jour est gourmande en ressources. L'espace clé de la jointure est déterminé par la partition temporelle de la table de faits à joindre. Les entités de dimension présentes dans cette partition temporelle ne constituent qu'un petit sous-ensemble de celles présentes dans l'ensemble de données de dimension complet. Par conséquent, la majorité des données de dimension remaniées dans ces jointures finit par être écartée. Afin d'optimiser ce processus et de réduire les remaniements inutiles, nous avons envisagé d'utiliser des filtres de Bloom sur des clés de jointure distinctes, mais nous avons rencontré des problèmes liés à la taille des filtres et à l'empreinte mémoire.

Pour y remédier, nous avons exploré les filtres de Bloom appris, une solution basée sur l'apprentissage automatique qui réduit la taille des filtres de 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 de calcul distribué.

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

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

Évolution des filtres Bloom traditionnels vers les filtres Bloom appris

Bien qu'un filtre de 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 de Bloom appris, nous avons considérablement réduit la taille de l'index tout en conservant le même taux de faux positifs. Cela s'explique par la transformation du filtre de 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 d'apprentissage automatique facilite la vérification initiale des valeurs, suivie d'un filtre de Bloom de secours pour éliminer les faux négatifs. La réduction de la taille résulte de la représentation compressée du modèle et du nombre réduit de clés requises par le filtre de Bloom de secours. C'est ce qui le distingue de l'approche classique du filtre de Bloom. 

Dans le cadre de ce travail, nous avons établi deux indicateurs pour évaluer notre approche du filtre de Bloom appris : la taille finale de l'objet sérialisé de l'index et la consommation de CPU pendant l'exécution des requêtes de jointure. 

Relever les défis de la mise en œuvre

Notre premier défi consistait à traiter un ensemble de données d'apprentissage fortement biaisé, comportant 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 y remédier, nous avons exploité l'approche du filtre de Bloom appris en sandwich [2]. Celle-ci intègre un filtre de Bloom traditionnel initial afin de rééquilibrer la distribution de l'ensemble de données en supprimant la majorité des clés manquantes dans 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 de Bloom initial, ainsi que les faux positifs, ont été transmises au modèle d'apprentissage automatique, souvent appelé « oracle appris ». Cette approche a permis d'obtenir un ensemble de données d'entraînement bien équilibré pour l'oracle appris, surmontant ainsi efficacement le problème de biais.

Le deuxième défi concernait l'architecture du modèle et les caractéristiques d'apprentissage. 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és à explorer les attributs de dimension comme caractéristiques potentielles du modèle pouvant 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 les sessions utilisateur pour des expériences dans une langue particulière. L'emplacement géographique ou l'attribut de préférence linguistique de la dimension utilisateur constitueraient de bons indicateurs permettant de déterminer 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 qui minimisaient les faux négatifs tout en fournissant des réponses rapides. Un modèle d'arbre à gradient boosté s'est avéré le choix optimal pour ces indicateurs clés, et nous avons allégé son ensemble de caractéristiques afin d'équilibrer précision et vitesse.

Notre requête de jointure mise à jour utilisant des filtres de Bloom appris est présentée ci-dessous :

Résultats

Voici les résultats de nos expériences avec les filtres Bloom appris dans notre lac de données. Nous les avons intégrés à cinq charges de travail en production, chacune présentant des caractéristiques de données différentes. La partie la plus coûteuse en termes de 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 celui de la table de dimensions. Pour commencer, nous examinons en quoi le filtre Bloom appris a surpassé les filtres Bloom traditionnels en termes de taille finale des objets sérialisés. Ensuite, nous présentons les gains de performances que nous avons observés en intégrant des filtres Bloom appris dans nos pipelines de traitement des charges de travail.

Comparaison de la taille des filtres de Bloom appris

Comme le montre le tableau ci-dessous, pour un taux de faux positifs donné, les deux variantes du filtre de Bloom appris réduisent la taille totale des objets de 17 à 42 % par rapport aux filtres de Bloom traditionnels.

De plus, en utilisant un sous-ensemble plus restreint de caractéristiques dans notre modèle basé sur un arbre à gradient boosté, nous n'avons perdu qu'un faible pourcentage d'optimisation tout en accélérant l'inférence.

Résultats de l'utilisation du filtre de Bloom 

Dans cette section, nous comparons les performances des jointures basées sur des filtres de Bloom à celles des jointures classiques à l'aide de plusieurs indicateurs. 

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

Tout d'abord, nous avons constaté que la mise en œuvre du filtre de Bloom surpassait la jointure classique de près de 60 % en termes d'heures CPU. Nous avons observé une augmentation de l'utilisation du CPU lors de l'étape de balayage pour l'approche du filtre de Bloom appris, en raison du temps de calcul supplémentaire consacré à l'évaluation du filtre de Bloom. Cependant, le préfiltrage effectué lors de cette étape a réduit la taille des données à réorganiser, ce qui a contribué à réduire l'utilisation du CPU par les étapes en aval, réduisant ainsi le nombre total d'heures CPU.

Deuxièmement, les filtres Bloom appris présentent une taille totale de données réduite d'environ 80 % et un nombre total d'octets de réorganisation écrits réduit d'environ 80 % par rapport à une jointure classique. Cela se traduit par des performances de jointure plus stables, comme expliqué ci-dessous. 

Nous avons également constaté une réduction de l'utilisation des ressources dans nos autres charges de travail de production soumises à l'expérimentation. Sur une période de deux semaines pour l'ensemble des cinq charges de travail, l'approche du filtre de Bloom appris a généré une économie quotidienne moyenne de 25 %, ce qui tient également compte de l'entraînement du modèle et de la création d'index.

Grâce à la réduction de la quantité de données remanié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 (temps réel) pour une charge de travail de jointure classique et une charge de travail basée sur les filtres de Bloom appris sur une période de deux semaines pour les cinq charges de travail que nous avons testées. Les exécutions utilisant des filtres de Bloom appris étaient plus stables — plus régulières en termes de durée —, ce qui ouvre la possibilité de les transférer vers des ressources de calcul transitoires, moins fiables mais moins coûteuses. 

Références

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean et 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.

¹Au 30 juin 2023

²Au 30 juin 2023