Cómo Roblox reduce los costes de las consultas Spark Join con filtros Bloom optimizados mediante aprendizaje automático
Resumen
Cada día, en Roblox, 70 millones de usuarios interactúan con millones de experiencias, lo que suma un total de 16 000 millones de horas al trimestre. Esta interacción genera un lago de datos a escala de petabytes, que se enriquece con fines de análisis y aprendizaje automático (ML). La unión de tablas de hechos y dimensiones en nuestro lago de datos consume muchos recursos, por lo que, para optimizar este proceso y reducir la reorganización de datos, hemos adoptado los filtros Bloom aprendidos [1], unas estructuras de datos inteligentes que utilizan el aprendizaje automático. Al predecir la presencia, estos filtros reducen considerablemente los datos de unión, lo que mejora la eficiencia y reduce los costes. Al mismo tiempo, también hemos mejorado nuestras arquitecturas de modelos y hemos demostrado los importantes beneficios que ofrecen para reducir la memoria y las horas de CPU necesarias para el procesamiento, así como para aumentar la estabilidad operativa.
Introducción
En nuestro lago de datos, las tablas de hechos y los cubos de datos se particionan temporalmente para un acceso eficiente, mientras que las tablas de dimensiones carecen de tales particiones, y unirlos con las tablas de hechos durante las actualizaciones consume muchos recursos. El espacio clave de la unión viene determinado por la partición temporal de la tabla de hechos que se está uniendo. Las entidades de dimensión presentes en esa partición temporal son un pequeño subconjunto de las presentes en todo el conjunto de datos de dimensiones. Como resultado, la mayoría de los datos de dimensión reorganizados en estas uniones acaba descartándose. Para optimizar este proceso y reducir la reorganización innecesaria, consideramos el uso de filtros Bloom en claves de unión distintas, pero nos enfrentamos a problemas de tamaño de filtro y de huella de memoria.
Para abordarlos, exploramos los filtros de Bloom aprendidos, una solución basada en el aprendizaje automático que reduce el tamaño del filtro de Bloom al tiempo que mantiene bajas las tasas de falsos positivos. Esta innovación mejora la eficiencia de las operaciones de unión al reducir los costes computacionales y mejorar la estabilidad del sistema. El siguiente esquema ilustra los procesos de unión convencionales y optimizados en nuestro entorno de computación distribuida.
Mejora de la eficiencia de las uniones con filtros Bloom aprendidos
Para optimizar la unión entre las tablas de hechos y de dimensiones, adoptamos la implementación del filtro Bloom aprendido. Construimos un índice a partir de las claves presentes en la tabla de hechos y, posteriormente, implementamos el índice para prefiltrar los datos de las dimensiones antes de la operación de unión.
Evolución de los filtros Bloom tradicionales a los filtros Bloom aprendidos
Aunque un filtro Bloom tradicional es eficiente, añade entre un 15 % y un 25 % de memoria adicional por cada nodo de trabajo que necesita cargarlo para alcanzar nuestra tasa de falsos positivos deseada. Sin embargo, al aprovechar los filtros Bloom aprendidos, logramos reducir considerablemente el tamaño del índice manteniendo la misma tasa de falsos positivos. Esto se debe a la transformación del filtro Bloom en un problema de clasificación binaria. Las etiquetas positivas indican la presencia de valores en el índice, mientras que las negativas significan que están ausentes.
La introducción de un modelo de aprendizaje automático facilita la comprobación inicial de los valores, seguida de un filtro Bloom de respaldo para eliminar los falsos negativos. La reducción del tamaño se debe a la representación comprimida del modelo y al menor número de claves que requiere el filtro Bloom de respaldo. Esto lo distingue del enfoque convencional del filtro Bloom.
Como parte de este trabajo, establecimos dos métricas para evaluar nuestro enfoque del filtro de Bloom aprendido: el tamaño final del objeto serializado del índice y el consumo de CPU durante la ejecución de consultas de unión.
Superar los retos de implementación
Nuestro reto inicial fue abordar un conjunto de datos de entrenamiento muy sesgado con pocas claves de tabla de dimensiones en la tabla de hechos. Al hacerlo, observamos un solapamiento de aproximadamente una de cada tres claves entre las tablas. Para abordar esto, aprovechamos el enfoque del filtro de Bloom aprendido tipo sándwich [2]. Este integra un filtro de Bloom tradicional inicial para reequilibrar la distribución del conjunto de datos eliminando la mayoría de las claves que faltaban en la tabla de hechos, lo que elimina de manera efectiva las muestras negativas del conjunto de datos. Posteriormente, solo las claves incluidas en el filtro de Bloom inicial, junto con los falsos positivos, se remitieron al modelo de aprendizaje automático, a menudo denominado «oráculo aprendido». Este enfoque dio como resultado un conjunto de datos de entrenamiento bien equilibrado para el oráculo aprendido, superando el problema del sesgo de manera eficaz.
El segundo reto se centró en la arquitectura del modelo y las características de entrenamiento. A diferencia del problema clásico de las URL de phishing [1], nuestras claves de unión (que en la mayoría de los casos son identificadores únicos para usuarios/experiencias) no eran intrínsecamente informativas. Esto nos llevó a explorar los atributos de dimensión como posibles características del modelo que pueden ayudar a predecir si una entidad de dimensión está presente en la tabla de hechos. Por ejemplo, imaginemos una tabla de hechos que contiene información de sesiones de usuario para experiencias en un idioma concreto. La ubicación geográfica o el atributo de preferencia de idioma de la dimensión de usuario serían buenos indicadores de si un usuario concreto está presente en la tabla de hechos o no.
El tercer reto —la latencia de la inferencia— requería modelos que minimizaran los falsos negativos y proporcionaran respuestas rápidas. Un modelo de árbol con refuerzo de gradiente fue la elección óptima para estas métricas clave, y recortamos su conjunto de características para equilibrar la precisión y la velocidad.
Nuestra consulta de unión actualizada, que utiliza filtros Bloom aprendidos, es la que se muestra a continuación:
Resultados
A continuación se muestran los resultados de nuestros experimentos con filtros Bloom aprendidos en nuestro lago de datos. Los integramos en cinco cargas de trabajo de producción, cada una de las cuales presentaba características de datos diferentes. La parte más costosa desde el punto de vista computacional de estas cargas de trabajo es la unión entre una tabla de hechos y una tabla de dimensiones. El espacio de claves de las tablas de hechos es aproximadamente el 30 % del de la tabla de dimensiones. Para empezar, analizamos cómo el filtro Bloom aprendido superó a los filtros Bloom tradicionales en términos de tamaño final del objeto serializado. A continuación, mostramos las mejoras de rendimiento que observamos al integrar los filtros Bloom aprendidos en nuestras canalizaciones de procesamiento de cargas de trabajo.
Comparación del tamaño del filtro Bloom aprendido
Como se muestra a continuación, al analizar una tasa de falsos positivos determinada, las dos variantes del filtro Bloom aprendido mejoran el tamaño total del objeto entre un 17 % y un 42 % en comparación con los filtros Bloom tradicionales.
Además, al utilizar un subconjunto más pequeño de características en nuestro modelo basado en árboles con refuerzo de gradiente, solo perdimos un pequeño porcentaje de optimización, al tiempo que aceleramos la inferencia.
Resultados del uso del filtro de Bloom
En esta sección, comparamos el rendimiento de las uniones basadas en filtros Bloom con el de las uniones normales en varias métricas.
La tabla siguiente compara el rendimiento de las cargas de trabajo con y sin el uso de filtros Bloom aprendidos. Un filtro Bloom aprendido con una probabilidad total de falsos positivos del 1 % muestra la comparación siguiente, manteniendo la misma configuración de clúster para ambos tipos de unión.
En primer lugar, observamos que la implementación del filtro de Bloom superaba al join normal en hasta un 60 % en horas de CPU. Se observó un aumento en el uso de la CPU durante la fase de escaneo del enfoque del filtro de Bloom aprendido, debido al esfuerzo computacional adicional dedicado a evaluar el filtro de Bloom. Sin embargo, el prefiltrado realizado en esta fase redujo el tamaño de los datos que se barajan, lo que contribuyó a reducir la CPU utilizada por las fases posteriores, reduciendo así el total de horas de CPU.
En segundo lugar, los filtros Bloom aprendidos tienen un tamaño total de datos aproximadamente un 80 % menor y escriben aproximadamente un 80 % menos de bytes de reordenación que una unión normal. Esto conduce a un rendimiento de unión más estable, como se explica a continuación.
También observamos una reducción en el uso de recursos en nuestras otras cargas de trabajo de producción sometidas a experimentación. Durante un periodo de dos semanas en las cinco cargas de trabajo, el enfoque del filtro de Bloom aprendido generó un ahorro medio diario del 25 %, lo que también tiene en cuenta el entrenamiento del modelo y la creación de índices.
Debido a la menor cantidad de datos reorganizados durante la ejecución de la unión, pudimos reducir significativamente los costes operativos de nuestro canal de análisis, al tiempo que lo hicimos más estable. El siguiente gráfico muestra la variabilidad (utilizando un coeficiente de variación) en las duraciones de las ejecuciones (tiempo real) para una carga de trabajo de unión normal y una basada en filtros Bloom aprendidos durante un periodo de dos semanas para las cinco cargas de trabajo con las que experimentamos. Las ejecuciones que utilizaban filtros de Bloom aprendidos fueron más estables —más consistentes en cuanto a duración—, lo que abre la posibilidad de trasladarlas a recursos de computación transitorios, menos fiables y más económicos.
Referencias
[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean y N. Polyzotis. The Case for Learned Index Structures. https://arxiv.org/abs/1712.01208, 2017.
[2] M. Mitzenmacher. Optimización de filtros Bloom aprendidos mediante sándwich.
https://arxiv.org/abs/1803.01474, 2018.
¹A 30 de junio de 2023
²A 30 de junio de 2023
