Cómo Roblox reduce los costos de consultas de Spark Join con filtros Bloom optimizados para aprendizaje automático - Blog de Roblox

Cómo Roblox reduce los costos de consultas de Spark Join con filtros Bloom optimizados para aprendizaje automático – Blog de Roblox

Marca de tiempo: 28 de noviembre de 2023 12:23 p.m.
Nodo de origen: 2983061

Resumen

Todos los días en Roblox, 65.5 millones de usuarios interactúan con millones de experiencias, totalizando 14.0 mil millones de horas trimestrales. 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). Unir tablas de hechos y dimensiones en nuestro lago de datos requiere muchos recursos, por lo que para optimizar esto y reducir la mezcla de datos, adoptamos los filtros Learned Bloom [1]: estructuras de datos inteligentes que utilizan ML. Al predecir la presencia, estos filtros recortan considerablemente los datos de unión, lo que mejora la eficiencia y reduce los costos. En el camino, también mejoramos las arquitecturas de nuestros modelos y demostramos los beneficios sustanciales que ofrecen para reducir la memoria y las horas de CPU para el procesamiento, además de aumentar la estabilidad operativa.

Introducción

En nuestro lago de datos, las tablas de hechos y los cubos de datos están particionados temporalmente para un acceso eficiente, mientras que las tablas de dimensiones carecen de dichas particiones, y unirlas con tablas de hechos durante las actualizaciones requiere muchos recursos. El espacio clave de la unión está determinado por la partición temporal de la tabla de hechos que se une. 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 dimensión. Como resultado, la mayoría de los datos de dimensiones mezcladas en estas uniones finalmente se descartan.. Para optimizar este proceso y reducir la mezcla innecesaria, consideramos usar Filtros de floración en distintas claves de unión, pero enfrentó problemas con el tamaño del filtro y la huella de memoria.

Para abordarlos, exploramos Filtros de floración aprendidos, una solución basada en ML que reduce el tamaño del filtro Bloom y al mismo tiempo mantiene bajas tasas de falsos positivos. Esta innovación mejora la eficiencia de las operaciones conjuntas al reducir los costos computacionales y mejorar la estabilidad del sistema. El siguiente esquema ilustra los procesos de unión convencionales y optimizados en nuestro entorno informático distribuido.

Mejora de la eficiencia de la unión con filtros Bloom aprendidos

Para optimizar la unión entre tablas de hechos y dimensiones, adoptamos la implementación del filtro Learned Bloom. Construimos un índice a partir de las claves presentes en la tabla de hechos y posteriormente implementamos el índice para filtrar previamente los datos de dimensión antes de la operación de unión. 

Evolución de los filtros de floración tradicionales a los filtros de floración aprendidos

Si bien un filtro Bloom tradicional es eficiente, agrega entre un 15% y un 25% de memoria adicional por cada nodo trabajador que necesita cargarlo para alcanzar la tasa de falsos positivos deseada. Pero al aprovechar los filtros Learned Bloom, logramos un tamaño de índice considerablemente reducido y al mismo tiempo mantuvimos 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 etiquetas negativas significan que están ausentes.

La introducción de un modelo ML facilita la verificación inicial de los valores, seguida de un filtro Bloom de respaldo para eliminar falsos negativos. El tamaño reducido se debe a la representación comprimida del modelo y a la reducción del número de claves requeridas por el filtro Bloom de respaldo. Esto lo distingue del enfoque convencional de Bloom Filter. 

Como parte de este trabajo, establecimos dos métricas para evaluar nuestro enfoque de filtro 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. 

Navegando los desafíos de la implementación

Nuestro desafío inicial fue abordar un conjunto de datos de entrenamiento altamente sesgado con pocas claves de tabla de dimensiones en la tabla de hechos. Al hacerlo, observamos una superposición de aproximadamente una de cada tres claves entre las tablas. Para abordar esto, aprovechamos el enfoque Sandwich Learned Bloom Filter [2]. Esto integra un filtro 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, eliminando efectivamente las muestras negativas del conjunto de datos. Posteriormente, solo las claves incluidas en el filtro Bloom inicial, junto con los falsos positivos, se enviaron al modelo ML, a menudo denominado el "oráculo aprendido". Este enfoque dio como resultado un conjunto de datos de entrenamiento bien equilibrado para el oráculo aprendido, superando eficazmente el problema del sesgo.

El segundo desafío 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 inherentemente informativas. Esto nos llevó a explorar los atributos de dimensión como características potenciales del modelo que pueden ayudar a predecir si una entidad de dimensión está presente en la tabla de hechos. Por ejemplo, imagine una tabla de hechos que contiene información de la sesión del usuario para experiencias en un idioma en particular. La ubicación geográfica o el atributo de preferencia de idioma de la dimensión del usuario serían buenos indicadores de si un usuario individual está presente en la tabla de hechos o no.

El tercer desafío, la latencia de inferencia, requería modelos que minimizaran los falsos negativos y proporcionaran respuestas rápidas. Un modelo de árbol impulsado por gradiente fue la opción óptima para estas métricas clave, y podamos su conjunto de características para equilibrar la precisión y la velocidad.

Nuestra consulta de unión actualizada utilizando los filtros Bloom aprendidos se muestra a continuación:

Resultados

Estos son los resultados de nuestros experimentos con filtros Learned Bloom en nuestro lago de datos. Los integramos en cinco cargas de trabajo de producción, cada una de las cuales poseía diferentes características de datos. 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 clave de las tablas de hechos es aproximadamente el 30% de la tabla de dimensiones. Para empezar, analizamos cómo el filtro Bloom aprendido superó a los filtros Bloom tradicionales en términos del tamaño final del objeto serializado. A continuación, mostramos las mejoras de rendimiento que observamos al integrar Learned Bloom Filters en nuestras canalizaciones de procesamiento de cargas de trabajo.

Comparación de tamaños de filtros Bloom aprendidos

Como se muestra a continuación, al observar una determinada tasa de falsos positivos, 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 árbol potenciado por gradiente, perdimos solo un pequeño porcentaje de optimización y agilizamos la inferencia.

Resultados de uso del filtro Bloom aprendidos 

En esta sección, comparamos el rendimiento de las uniones basadas en Bloom Filter con el de las uniones normales a través de varias métricas. 

La siguiente tabla 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 falso positivo del 1 % demuestra la siguiente comparación mientras se mantiene la misma configuración de clúster para ambos tipos de unión. 

En primer lugar, descubrimos que la implementación de Bloom Filter superó la unión normal hasta en un 60 % en horas de CPU. Vimos un aumento en el uso de CPU del paso de escaneo para el enfoque del filtro Bloom aprendido debido al cálculo adicional gastado en la evaluación del filtro Bloom. Sin embargo, el filtrado previo realizado en este paso redujo el tamaño de los datos que se mezclaban, lo que ayudó a reducir la CPU utilizada por los pasos posteriores, reduciendo así el total de horas de CPU.

En segundo lugar, los filtros Learned Bloom tienen aproximadamente un 80 % menos de tamaño total de datos y aproximadamente un 80 % menos de bytes aleatorios escritos que una unión normal. Esto conduce a un rendimiento de unión más estable, como se analiza a continuación. 

También vimos un uso reducido de recursos en nuestras otras cargas de trabajo de producción bajo experimentación. Durante un período de dos semanas en las cinco cargas de trabajo, el enfoque del filtro Learned Bloom generó un promedio ahorro de costos diario of 25%, lo que también representa el entrenamiento de modelos y la creación de índices.

Debido a la menor cantidad de datos mezclados al realizar la unión, pudimos reducir significativamente los costos operativos de nuestro proceso de análisis y al mismo tiempo hacerlo más estable. El siguiente gráfico muestra la variabilidad (usando un coeficiente de variación) en las duraciones de ejecución (muro hora del reloj) para una carga de trabajo de unión regular y una carga de trabajo basada en Learned Bloom Filter durante un período de dos semanas para las cinco cargas de trabajo con las que experimentamos. Las ejecuciones que utilizaron filtros Learned Bloom fueron más estables (más consistentes en duración), lo que abre la posibilidad de trasladarlos a recursos informáticos transitorios y poco confiables más baratos. 

Referencias

[1] T. Kraska, A. Beutel, EH Chi, J. Dean y N. Polyzotis. El caso de las estructuras de índices aprendidos. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. Optimización de filtros de floración aprendidos mediante sándwich. 

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

¹A los 3 meses finalizados el 30 de junio de 2023

²A los 3 meses finalizados el 30 de junio de 2023

Sello de tiempo:

Mas de Roblox