Uso de Estruturas de Dados Probabilísticas na Movile: Bloom filters

Revisores: Lucy Narita, Mauro Takeda e Henrique Shiraiwa.

Um dos tópicos mais importantes da Computação é, com certeza, o estudo de estruturas de dados.

O uso de uma estrutura de dados adequada para o algoritmo pode tanto ajudar a obter uma performance ótima, assim como o uso de uma não adequada pode fazer o algoritmo rodar de forma muito mais lenta do que deveria.

Um dos tópicos mais discutidos recentemente nessa área trata-se de estruturas de dados probabilísticas. Há várias definições para o que elas são. Uma definição particularmente boa e genérica é que estruturas de dados probabilísticas são estruturas de dados que, ao contrário das tradicionais, só conseguem dar respostas aproximadas quando consultadas. Esse resultado aproximado está correto com uma probabilidade X, daí o nome dado a elas.O principal motivo que levou este tópico a ganhar forças nos últimos anos foi o incrível aumento da quantidade de dados que temos disponíveis atualmente, tornando o processamento e armazenamento em desafios imensos. É por isso que, considerando os grandes volumes de dados que temos aqui na Movile, as estruturas probabilísticas são tão eficientes.

Bloom filter

Umas das estruturas de dados probabilísticas mais famosas é o Bloom filter. Criada por Burton Bloom na década de 70, ela se propõe a responder uma única pergunta: dada uma chave, ela pode fazer parte do conjunto representado por esse Bloom filter?

Bloom filters são extremamente eficientes no uso de memória, podendo armazenar algo na ordem de 100 milhões de chaves com menos de 200Mb de memória. Como desvantagem, eles podem retornar falsos-positivos, ou seja, a consulta pode retornar que a chave pode pertencer, quando ela, na verdade, não faz parte do conjunto representado pelo Bloom filter. Apesar de haver falsos-positivos, um Bloom filter jamais retornará um falso-negativo, ou seja, ele jamais dirá que uma chave não faz parte do conjunto quando, na verdade, ela faz.

A grande sacada por trás dos Bloom filters é de como ele codifica a existência das chaves. Suponha que você gostaria de consultar se um número inteiro pertence a um conjunto. A solução simples e evidente para esse problema seria armazenar todos os números que pertencem a esse conjunto na memória, talvez usando Set ou Hash Map. A questão é: cada número long ocupa, na grande maioria das linguagens, 8 bytes, ou seja, 64 bits. Um Bloom filter, por sua vez, não representa o número usando todos os 64 bits da representação normal dele, eles usam muito menos: normalmente 10 bits já são mais que suficientes para termos uma porcentagem extremamente baixa de falso-positivos.

A maneira que ele faz essa codificação é através de funções de hash que são aplicadas na chave. Cada uma das funções de hash gera um valor que é usado como índice de um vetor de bits. Para cada um dos índices, o bit naquela posição passa a ter o valor de 1. Para a consulta, o mesmo procedimento é aplicado: se todos os bits nas posições geradas pelas funções de hash estiverem como 1 é possível que a chave exista no conjunto, se qualquer um dos bits estiver com 0 a chave não existirá no conjunto.

(David Eppstein — self-made, originally for a talk at WADS 2007)

Bloom filters na sua versão tradicional, ao contrário da maioria das estruturas de dados, não suportam exclusão de elementos: uma vez que um elemento foi adicionado no conjunto, ele ficará para sempre lá. Isso não é um grande problema: chaves que não são mais úteis gerarão falsos-positivos, o que é completamente aceitável e se a taxa de falsos-positivos for muito alta, basta gerar novamente ele do zero e inserir novamente os números que ainda fazem parte do conjunto.

Uso de Bloom filter na Movile

Um dos usos que fazemos de Bloom filters na Movile é na parte de envio de SMS. Um dos passos cruciais nesse fluxo é identificar qual a operadora do celular de destino da mensagem. Uma das etapas para verificar a operadora de destino consiste em verificar se o número foi portado da operadora original para uma outra. Basicamente, essa informação é representada como uma lista com todos os números portados de todos os países que atuamos, sendo que precisamos consultá-la para cada uma das milhões de mensagens que enviamos por dia.

A primeira solução que tentamos usar para esse problema foi armazenar os números portados na memória, num mapa com o número, representado por um Long, e a operadora dele, representado por um inteiro. Porém, com o passar do tempo e com o crescimento de nossas operações, começamos a ter sérios problemas de performance e custos devido ao alto uso de memória e alto tempo de inicialização da solução: precisávamos carregar todos os números portados, várias dezenas de milhões de valores, a cada vez que o sistema fosse inicializado.

Precisávamos de outra solução e achamos que usar um Bloom filter poderia nos ajudar nisso! Passamos então, ao invés de armazenar todos os números na memória da aplicação, usar um banco de dados externo e usar o Bloom filter como um primeiro filtro para saber se haveria chance, ou não, do número ter sido portado. Essa solução nos deu vantagens importantes: mantivemos a latência extremamente baixa para a grande maioria dos casos (algo perto de 2 ordens de grandeza, se considerarmos uma solução apenas com o banco de dados) e também a aplicação passou a carregar somente o Bloom filter, cujo uso de memória é pequeno. Como banco de dados escolhemos utilizar um banco de dados não-relacional: Redis.

O Redis é um banco de dados não-relacional que atua também como um cachê persistido chave-valor, o que se encaixa perfeitamente no nosso problema: nossa chave é o telefone e o valor é a operadora para qual o número foi portado. Além do modelo de dados se encaixar perfeitamente com o nosso case, também obtemos vantagens interessantes ao utilizar o Redis: como ele armazena todos os dados em memória, suas operações são extremamente rápidas, o que nos deixa com uma latência ainda baixa mesmo nos casos que precisamos consultá-lo! Um diagrama simplificado da nossa arquitetura pode ser encontrado na figura abaixo:

Resultados

Obtivemos ótimos resultados com a aplicação do Bloom filter na nossa arquitetura. Em comparação com nossa primeira solução, economizamos no total cerca de 2.5GB de memória por instância dos nossos sistemas de envios, o que totalizou cerca de 100GB de memória economizada. O tempo de inicialização das nossas plataformas caiu de cerca de 300s para menos de 15s, já que passamos a carregar somente o Bloom filter durante o processo de load. Por último, só consultamos o Redis para cerca de 12% do total dos nossos envios, sendo que, destes somente cerca de 5% foram consultas causadas por falsos-positivos, ou seja, números que o Bloom filter retornou que poderiam ter sido portados, porém a consulta no Redis revelou que o número na verdade não tinha sido este. A tabela abaixo mostra um exemplos desses dados de uma de nossas instâncias, desde o momento que ela foi iniciada:

Conclusões

Uma das lições mais importante que tiramos desse case é que ele nos fez lembrar, mais uma vez, o quão úteis boas estruturas de dados são.

É legal lembrar também que — além das estruturas de dados probabilísticas que resolveram tão bem nosso problema — existem diversos tipos de estruturas para outros problemas mais específicos. Para citar alguns exemplos, temos as CRDT (Conflict-free Replicated Data Type — que estão aos poucos se tornando relevantes para evitar conflitos em sistemas distribuídos) e as estruturas de dados persistentes (como as presentes em algumas linguagens de programação, especialmente as funcionais, e.g. Clojure e Scala)

Algumas Referências:

http://llimllib.github.io/bloomfilter-tutorial/ : Uma boa referência sobre o funcionamento de Bloom filter

https://dl.acm.org/citation.cfm?id=362686.362692 : Paper original sobre Bloom filters.

https://bravenewgeek.com/stream-processing-and-probabilistic-methods/ : Uma boa explicação sobre Bloom filter

https://gist.github.com/hellerbarde/2843375 : Alguns dados sobre latência de recursos.

https://redis.io/ : Site Redis