Como o Roblox reduz os custos de consulta do Spark Join com filtros Bloom otimizados para aprendizado de máquina – Roblox Blog

Sumário

Todos os dias no Roblox, 65.5 milhões de usuários se envolvem com milhões de experiências, totalizando 14.0 bilhões de horas trimestralmente. Essa interação gera um data lake em escala de petabytes, que é enriquecido para fins analíticos e de aprendizado de máquina (ML). Unir tabelas de fatos e dimensões em nosso data lake consome muitos recursos. Portanto, para otimizar isso e reduzir o embaralhamento de dados, adotamos filtros Bloom aprendidos [1] - estruturas de dados inteligentes que usam 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 caminho, também melhoramos nossas arquiteturas de modelo e demonstramos os benefícios substanciais que elas oferecem na redução de memória e horas de CPU para processamento, bem como no aumento da estabilidade operacional.

Introdução

Em nosso data lake, as tabelas de fatos e os cubos de dados são particionados temporalmente para um acesso eficiente, enquanto as tabelas de dimensões não possuem essas partições, e juntá-las às tabelas de fatos durante as atualizações consome muitos recursos. O espaço-chave da junção é controlado 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 embaralhados nessas junções é eventualmente descartada. Para otimizar esse processo e reduzir embaralhamentos desnecessários, consideramos usar Filtros Bloom em chaves de junção distintas, mas enfrentou problemas de tamanho de filtro e consumo de memória.

Para abordá-los, exploramos Filtros de saúde aprendidos, uma solução baseada em ML que reduz o tamanho do filtro Bloom enquanto mantém baixas taxas de falsos positivos. Esta 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.

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

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

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

Embora um filtro Bloom tradicional seja eficiente, ele adiciona 15-25% de memória adicional por nó de trabalho, sendo necessário carregá-lo para atingir a taxa de falsos positivos desejada. Mas, ao aproveitar os filtros Bloom aprendidos, alcançamos um tamanho de índice consideravelmente reduzido, mantendo a mesma taxa de falsos positivos. Isto 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 estão ausentes.

A introdução de um modelo ML facilita a verificação inicial dos 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 Learned Bloom Filter: o tamanho final do objeto serializado do índice e o consumo de CPU durante a execução de consultas de junção. 

Navegando pelos desafios de implementação

Nosso desafio inicial foi abordar um conjunto de dados de treinamento altamente tendencioso com poucas chaves de tabela de dimensões 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, aproveitamos a abordagem Sandwich Learned Bloom Filter [2]. Isso integra um filtro 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 Bloom inicial, juntamente com os falsos positivos, foram encaminhadas para o modelo ML, muitas vezes referido como “oráculo aprendido”. Essa abordagem resultou em um conjunto de dados de treinamento bem equilibrado para o oráculo aprendido, superando efetivamente o problema de preconceito.

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 exclusivos para usuários/experiências) não eram inerentemente informativas. Isso nos levou a explorar os atributos de dimensão como recursos potenciais 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 contém informações de sessão do usuário para experiências em um idioma específico. A localização geográfica ou o atributo de preferência de idioma da dimensão do usuário seriam bons indicadores para saber se um usuário individual está presente ou não na tabela de fatos.

O terceiro desafio – latência de inferência – exigia modelos que minimizassem os falsos negativos e fornecessem respostas rápidas. Um modelo de árvore com gradiente aprimorado foi a escolha ideal para essas métricas principais, e reduzimos seu conjunto de recursos para equilibrar precisão e velocidade.

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

Resultados

Aqui estão os resultados de nossos experimentos com filtros Learned Bloom em nosso data lake. Nós os integramos em cinco cargas de trabalho de produção, cada uma com características de dados diferentes. A parte computacionalmente mais cara 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 é aproximadamente 30% 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. A seguir, mostramos as melhorias de desempenho que observamos ao integrar filtros Bloom aprendidos em nossos pipelines de processamento de carga de trabalho.

Comparação aprendida do tamanho do filtro Bloom

Conforme mostrado abaixo, ao observar uma determinada taxa de falsos positivos, as duas variantes do Filtro Bloom aprendido melhoram o tamanho total do objeto entre 17-42% quando comparados aos Filtros Bloom tradicionais.

Além disso, ao usar um subconjunto menor de recursos em nosso modelo baseado em árvore com gradiente aumentado, perdemos apenas uma pequena porcentagem de otimização e tornamos a inferência mais rápida.

Resultados aprendidos do uso do filtro Bloom 

Nesta seção, comparamos o desempenho de junções baseadas em Bloom Filter com o desempenho de junções regulares em diversas métricas. 

A tabela abaixo compara o desempenho de cargas de trabalho com e sem o uso de filtros Bloom aprendidos. Um filtro Bloom aprendido com probabilidade total de falsos positivos de 1% 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 Bloom Filter superou a junção regular em até 60% em horas de CPU. Vimos um aumento no uso da CPU na etapa de varredura para a abordagem do filtro Bloom aprendido devido ao cálculo adicional gasto na avaliação do filtro Bloom. No entanto, a pré-filtragem feita nesta etapa reduziu o tamanho dos dados embaralhados, o que ajudou a reduzir a CPU utilizada pelas etapas downstream, reduzindo 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 total de bytes aleatórios gravados 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 experimentação. Durante um período de duas semanas em todas as cinco cargas de trabalho, a abordagem do Learned Bloom Filter gerou uma média economia de custos diários of % 25 que também é responsável pelo treinamento do modelo e pela criação de índices.

Devido à quantidade reduzida de dados embaralhados durante a execução da junção, conseguimos reduzir significativamente os custos operacionais de nosso pipeline de análise e, ao mesmo tempo, torná-lo mais estável. O gráfico a seguir mostra a variabilidade (usando um coeficiente de variação) nas durações de execução (parede horário do relógio) para uma carga de trabalho de junção regular e uma carga de trabalho baseada no filtro Bloom aprendido durante um período de duas semanas para as cinco cargas de trabalho que testamos. As execuções usando filtros Bloom aprendidos foram mais estáveis ​​– mais consistentes em duração – o que abre a possibilidade de movê-las para recursos de computação transitórios e não confiáveis ​​mais baratos. 

Referências

[1] T. Kraska, A. Beutel, EH Chi, J. Dean e N. Polyzotis. O caso das estruturas de índice aprendidas. https://arxiv.org/abs/1712.01208 2017.

[2] M. Mitzenmacher. Otimizando filtros de saúde aprendidos por meio de sanduíche. 

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

---

¹A partir de 3 meses encerrados em 30 de junho de 2023

²A partir de 3 meses encerrados em 30 de junho de 2023

• Conteúdo com tecnologia de SEO e distribuição de relações públicas. Seja amplificado hoje.
• PlatoData.Network Gerativa Vertical Ai. Capacite-se. Acesse aqui.
• PlatoAiStream. Inteligência Web3. Conhecimento Amplificado. Acesse aqui.
• PlatãoESG. Carbono Tecnologia Limpa, Energia, Ambiente, Solar, Gestão de resíduos. Acesse aqui.
• PlatoHealth. Inteligência em Biotecnologia e Ensaios Clínicos. Acesse aqui.
• Fonte: https://blog.roblox.com/2023/11/roblox-reduces-spark-join-query-costs-machine-learning-optimized-bloom-filters/