Como a Roblox reduz os custos das consultas Spark Join com filtros Bloom otimizados por aprendizado de máquina

Resumo

Todos os dias, no Roblox, 70 milhões de usuários interagem com milhões de experiências, totalizando 16 bilhões de horas por trimestre. Essa interação gera um data lake na escala de petabytes, que é enriquecido para fins de análise e aprendizado de máquina (ML). A junção de tabelas de fatos e dimensões em nosso data lake consome muitos recursos; portanto, para otimizar esse processo e reduzir a movimentação de dados, adotamos os Learned Bloom Filters [1] — estruturas de dados inteligentes que utilizam ML. Ao prever a presença, esses filtros reduzem consideravelmente os dados de junção, aumentando a eficiência e reduzindo custos. Ao longo do processo, também aprimoramos nossas arquiteturas de modelo e demonstramos os benefícios substanciais que elas oferecem para reduzir o uso de memória e horas de CPU para processamento, bem como para aumentar a estabilidade operacional.

Introdução

Em nosso data lake, as tabelas de fatos e os cubos de dados são particionados temporalmente para acesso eficiente, enquanto as tabelas de dimensão não possuem tais partições, e juntá-las às tabelas de fatos durante as atualizações consome muitos recursos. O espaço-chave da junção é determinado pela partição temporal da tabela de fatos que está sendo unida. As entidades de dimensão presentes nessa partição temporal são um pequeno subconjunto daquelas presentes em todo o conjunto de dados de dimensão. Como resultado, a maioria dos dados de dimensão reorganizados nessas junções acaba sendo descartada. Para otimizar esse processo e reduzir a reorganização desnecessária, consideramos o uso de Filtros de Bloom em chaves de junção distintas, mas enfrentamos problemas de tamanho de filtro e consumo de memória.

Para resolvê-los, exploramos os Filtros de Bloom Aprendidos, uma solução baseada em ML que reduz o tamanho do Filtro de Bloom enquanto mantém baixas taxas de falsos positivos. Essa inovação aumenta a eficiência das operações de junção, reduzindo os custos computacionais e melhorando a estabilidade do sistema. O esquema a seguir ilustra os processos de junção convencionais e otimizados em nosso ambiente de computação distribuída.

Aumentando a eficiência da junção com filtros Bloom aprendidos

Para otimizar a junção entre as tabelas de fatos e de dimensões, adotamos a implementação do Filtro Bloom Aprendido. Construímos um índice a partir das chaves presentes na tabela de fatos e, posteriormente, implantamos o índice para pré-filtrar os dados de dimensão antes da operação de junção. 

Evolução dos filtros Bloom tradicionais para os filtros Bloom aprendidos

Embora um filtro Bloom tradicional seja eficiente, ele adiciona de 15% a 25% de memória adicional por nó de trabalho que precisa carregá-lo para atingir nossa taxa de falsos positivos desejada. Mas, ao utilizar filtros Bloom aprendidos, conseguimos reduzir consideravelmente o tamanho do índice, mantendo a mesma taxa de falsos positivos. Isso se deve à transformação do filtro Bloom em um problema de classificação binária. Rótulos positivos indicam a presença de valores no índice, enquanto rótulos negativos significam que eles estão ausentes.

A introdução de um modelo de ML facilita a verificação inicial de valores, seguida por um filtro Bloom de backup para eliminar falsos negativos. O tamanho reduzido decorre da representação compactada do modelo e do número reduzido de chaves exigidas pelo filtro Bloom de backup. Isso o distingue da abordagem convencional do filtro Bloom. 

Como parte deste trabalho, estabelecemos duas métricas para avaliar nossa abordagem do Filtro de Bloom Aprendido: o tamanho final do objeto serializado do índice e o consumo de CPU durante a execução de consultas de junção. 

Superando os desafios de implementação

Nosso desafio inicial foi lidar com um conjunto de dados de treinamento altamente tendencioso, com poucas chaves de tabela de dimensão na tabela de fatos. Ao fazer isso, observamos uma sobreposição de aproximadamente uma em cada três chaves entre as tabelas. Para resolver isso, utilizamos a abordagem do Filtro de Bloom Aprendido em Camadas [2]. Isso integra um Filtro de Bloom tradicional inicial para reequilibrar a distribuição do conjunto de dados, removendo a maioria das chaves que estavam faltando na tabela de fatos, eliminando efetivamente amostras negativas do conjunto de dados. Posteriormente, apenas as chaves incluídas no Filtro de Bloom inicial, juntamente com os falsos positivos, foram encaminhadas para o modelo de ML, frequentemente chamado de “oráculo aprendido”. Essa abordagem resultou em um conjunto de dados de treinamento bem equilibrado para o oráculo aprendido, superando o problema de viés de forma eficaz.

O segundo desafio centrou-se na arquitetura do modelo e nos recursos de treinamento. Ao contrário do problema clássico de URLs de phishing [1], nossas chaves de junção (que, na maioria dos casos, são identificadores únicos para usuários/experiências) não eram inerentemente informativas. Isso nos levou a explorar atributos de dimensão como possíveis recursos do modelo que podem ajudar a prever se uma entidade de dimensão está presente na tabela de fatos. Por exemplo, imagine uma tabela de fatos que contenha informações de sessão do usuário para experiências em um determinado idioma. A localização geográfica ou o atributo de preferência de idioma da dimensão do usuário seriam bons indicadores da presença ou não de um usuário individual na tabela de fatos.

O terceiro desafio — a latência de inferência — exigia modelos que minimizassem os falsos negativos e fornecessem respostas rápidas. Um modelo de árvore com reforço de gradiente foi a escolha ideal para essas métricas-chave, e nós podamos seu conjunto de características para equilibrar precisão e velocidade.

Nossa consulta de junção atualizada, utilizando filtros Bloom aprendidos, é mostrada abaixo:

Resultados

Aqui estão os resultados de nossos experimentos com filtros Bloom aprendidos em nosso data lake. Nós os integramos a cinco cargas de trabalho de produção, cada uma com características de dados diferentes. A parte mais dispendiosa em termos computacionais dessas cargas de trabalho é a junção entre uma tabela de fatos e uma tabela de dimensões. O espaço-chave das tabelas de fatos é de aproximadamente 30% do da tabela de dimensões. Para começar, discutimos como o Filtro Bloom Aprendido superou os Filtros Bloom tradicionais em termos de tamanho final do objeto serializado. Em seguida, mostramos as melhorias de desempenho que observamos ao integrar os Filtros Bloom Aprendidos em nossos pipelines de processamento de cargas de trabalho.

Comparação de tamanho do Filtro Bloom Aprendido

Conforme mostrado abaixo, ao analisar uma determinada taxa de falsos positivos, as duas variantes do Filtro Bloom Aprendido melhoram o tamanho total do objeto em 17% a 42% quando comparadas aos Filtros Bloom tradicionais.

Além disso, ao usar um subconjunto menor de características em nosso modelo baseado em árvore com reforço de gradiente, perdemos apenas uma pequena porcentagem da otimização, ao mesmo tempo em que tornamos a inferência mais rápida.

Resultados do uso do filtro de Bloom 

Nesta seção, comparamos o desempenho de junções baseadas em filtro Bloom com o de junções regulares em várias métricas. 

A tabela abaixo compara o desempenho de cargas de trabalho com e sem o uso de Filtros de Bloom Aprendidos. Um Filtro de Bloom Aprendido com 1% de probabilidade total de falsos positivos demonstra a comparação abaixo, mantendo a mesma configuração de cluster para ambos os tipos de junção. 

Primeiro, descobrimos que a implementação do Filtro de Bloom superou a junção regular em até 60% em horas de CPU. Observamos um aumento no uso da CPU na etapa de varredura para a abordagem do Filtro de Bloom Aprendido devido ao tempo de computação adicional gasto na avaliação do Filtro de Bloom. No entanto, a pré-filtragem realizada nessa etapa reduziu o tamanho dos dados que estavam sendo reorganizados, o que ajudou a reduzir o uso da CPU nas etapas posteriores, diminuindo assim o total de horas de CPU.

Em segundo lugar, os Filtros Bloom Aprendidos têm cerca de 80% menos tamanho total de dados e cerca de 80% menos bytes de reorganização escritos do que uma junção regular. Isso leva a um desempenho de junção mais estável, conforme discutido abaixo. 

Também observamos uma redução no uso de recursos em nossas outras cargas de trabalho de produção em fase de experimentação. Ao longo de um período de duas semanas em todas as cinco cargas de trabalho, a abordagem do Filtro Bloom Aprendido gerou uma economia média diária de 25%, o que também leva em conta o treinamento do modelo e a criação de índices.

Devido à redução da quantidade de dados reorganizados durante a execução da junção, conseguimos reduzir significativamente os custos operacionais de nosso pipeline de análise, ao mesmo tempo em que o tornamos mais estável. O gráfico a seguir mostra a variabilidade (usando um coeficiente de variação) nas durações de execução (tempo de relógio) para uma carga de trabalho de junção regular e uma carga de trabalho baseada em filtros Bloom aprendidos ao longo de um período de duas semanas para as cinco cargas de trabalho com as quais fizemos a experiência. As execuções que utilizaram os Filtros de Bloom Aprendidos foram mais estáveis — mais consistentes em termos de duração —, o que abre a possibilidade de transferi-las para recursos de computação transitórios, mais baratos e menos confiáveis. 

Referências

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean e N. Polyzotis. The Case for Learned Index Structures. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. Otimização de filtros Bloom aprendidos por meio do método “sandwiching”. 

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

¹No trimestre encerrado em 30 de junho de 2023

²No trimestre encerrado em 30 de junho de 2023