Como “Bloom Filter” pode ser utilizada para melhorar a performance

Elemar Júnior

O código mais rápido que existe é aquele que não precisa ser executado.

Considere, por exemplo, que esteja implementando uma funcionalidade para recuperação de senhas. Nesse caso, é um completo desperdício de recursos fazer uma requisição ao servidor apenas para constatar que o e-mail informado não está cadastrado. Entretanto, como fazer para determinar se um e-mail “existe na base”, sem consultá-la?

Em outro exemplo, considere que esteja implementando a funcionalidade para cadastro de um novo usuário que precisará ter um “nome-de-usuário” único. Seria um total desperdício de recursos fazer requests ao servidor para constatar que o “nome-de-usuário” informado já está cadastrado, associado a outro usuário. Entretanto, como saber se um “nome-de-usuário” já foi utilizado sem consultar o servidor?

Infelizmente, é comum que requisições “inúteis”, como as indicadas nos parágrafos anteriores, ocorram, gerando desperdício de recursos e, muitas vezes, prejuízos de performance. O triste, é que elas poderiam ser evitadas com uso inteligente de estruturas de dados como o Bloom Filter.

Bloom Filter

Um Bloom Filter é uma estrutura de dados probabilística, que demanda pouquíssimo espaço, concebida por Burton Howard Bloom em 1970. Ela é utilizada para testar se um elemento está presente em um conjunto sem necessitar consultar a lista completa de elementos presente nesse conjunto.

Eventualmente, a estrutura pode apontar um falso positivo (indicando que um elemento está em um conjunto quando, na verdade, não está). Entretanto, jamais gera um falso negativo.

Quanto mais elementos são adicionados a uma Bloom filter, maiores são as chances de um falso positivo.

Wikipedia

PS: O paper que apresenta a estrutura de dados está disponível aqui.

Utilizando Bloom Filter, com apenas poucos bits é possível gerar filtros eficientes para milhares de elementos. Um milhão de strings, por exemplo, poderiam ser controladas com apenas 1Mb e 1% de taxa de erro (consultas que geram falsos positivos).

Ou seja, é possível enviar para o “lado cliente” de um software informação suficiente para reduzir dramaticamente requests inócuos e, por consequência, trafego na rede, acessos a “disco” e alocações desnecessárias em memória. Afinal, antes de fazer uma requisição ao servidor para verificar a “presença” de um dado em um conjunto, bastaria o “lado cliente” consultar, antes, ao filtro, podendo prover feedback muito mais rápido sem onerar o backend.

O segredo para a eficiência dessa estrutura de dados é a utilização de hashes de qualidade que são utilizados para ligar ou desligar bits em um mapa. Sempre que um dado é “incluído” no filtro, os bits correspondentes do hash são ligados.

Para verificar se um dado está no filtro, basta verificar se todos os bits correspondentes ao hash estão ligados. Caso estejam, o dado poderá estar no conjunto. Caso contrário, o dado certamente não estará.

A implementação que compartilhamos aqui é baseada em uma versão antiga compartilhada pela Microsoft no Codeplex.

public delegate int HashFunction<T>(T input);

public class BloomFilter<T>
{

    private readonly HashFunction<T> getHashPrimary;
    private readonly HashFunction<T> getHashSecondary;
    private readonly int hashFunctionCount;
    private readonly BitArray hashBits;

    public BloomFilter(
        int capacity, 
        float errorRate,
        HashFunction<T> primaryHashFunction,
        HashFunction<T> secondaryHashFunction
        )
    {
        var m = BestM(capacity, errorRate);
        var k = BestK(capacity, errorRate);
        Debug.WriteLine($"New BloomFilter (k = {k}; m = {m})");

        hashBits = new BitArray(m);
        hashFunctionCount = k;
        getHashPrimary = primaryHashFunction ?? throw new ArgumentNullException(nameof(secondaryHashFunction));
        getHashSecondary = secondaryHashFunction ?? throw new ArgumentNullException(nameof(secondaryHashFunction));
    }

    public void Add(T item)
    {
        // start flipping bits for each hash of item
        int primaryHash = item.GetHashCode();
        int secondaryHash = getHashSecondary(item);
        for (int i = 0; i < hashFunctionCount; i++)
        {
            int hash = ComputeHashUsingDillingerManoliosMethod(primaryHash, secondaryHash, i);
            hashBits[hash] = true;
        }
    }

    public bool MaybeContains(T item)
    {
        int primaryHash = getHashPrimary(item);
        int secondaryHash = getHashSecondary(item);
        for (int i = 0; i < hashFunctionCount; i++)
        {
            int hash = ComputeHashUsingDillingerManoliosMethod(primaryHash, secondaryHash, i);
            if (hashBits[hash] == false)
                return false;
        }
        return true;
    }

    private int ComputeHashUsingDillingerManoliosMethod(int primaryHash, int secondaryHash, int i)
    {
        var resultingHash = (primaryHash + i * secondaryHash) % hashBits.Count;
        return Math.Abs(resultingHash);
    }

    private static int BestM(int capacity, float errorRate)
      => (int)Math.Ceiling(capacity * Math.Log(errorRate, 1.0 / Math.Pow(2, Math.Log(2.0))));

    private static int BestK(int capacity, float errorRate)
      => (int)Math.Round(Math.Log(2.0) * BestM(capacity, errorRate) / capacity);
}

O código, aqui escrito em C#, é fácil de transcrever para qualquer linguagem, incluindo Javascript.

A utilidade da Bloom filter também está associada a capacidade de gerar boas chaves hash para os objetos que se quer controlar. Abaixo, implementações para string e int32.

public static class HashFunctions
{
    public static HashFunction<T> FromType<T>() => 
        (obj) => obj.GetHashCode();

    public static int ForStrings(string input)
    {
        var hash = 0;

        for (var i = 0; i < input.Length; i++)
        {
            hash += input[i];
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }
        hash += (hash << 3);
        hash ^= (hash >> 11);
        hash += (hash << 15);
        return hash;
    }

    public static int ForInt32(int input)
    {
        uint x = (uint)input;

        unchecked
        {
            x = ~x + (x << 15); 
            x = x ^ (x >> 12);
            x = x + (x << 2);
            x = x ^ (x >> 4);
            x = x * 2057; 
            x = x ^ (x >> 16);
            return (int)x;
        }
    }
}

Embora existam “acrobacias técnicas” que geram grandes ganhos de desempenho, a forma mais consistente e efetiva de escrever software com performance excelente é fazendo bom uso de algoritmos e estruturas de dados.

Em resumo

O problema
O desconhecimento de algoritmos e estruturas de dados faz com que muitos programadores escrevam códigos com custo computacional muito mais alto do que o necessário.
O insight
Embora existam “acrobacias técnicas” que geram grandes ganhos de desempenho, a forma mais consistente e efetiva de escrever software com performance excelente é fazendo bom uso de algoritmos e estruturas de dados. A utilização de Bloom Filter, por exemplo, pode eliminar a demanda de milhares de consultas a recursos remotos impactando dramaticamente a performance.

Compartilhe este insight:

Comentários

Participe deixando seu comentário sobre este artigo a seguir:

Subscribe
Notify of
guest
0 Comentários
Inline Feedbacks
View all comments

AUTOR

Elemar Júnior
Fundador e CEO da EximiaCo atua como tech trusted advisor ajudando empresas e profissionais a gerar mais resultados através da tecnologia.

NOVOS HORIZONTES PARA O SEU NEGÓCIO

Nosso time está preparado para superar junto com você grandes desafios tecnológicos.

Entre em contato e vamos juntos utilizar a tecnologia do jeito certo para gerar mais resultados.

Insights EximiaCo

Confira os conteúdos de negócios e tecnologia desenvolvidos pelos nossos consultores:

Arquitetura de Dados

Insights de um DBA na análise de um plano de execução

Especialista em performance de Bancos de Dados de larga escala
Arquitetura de Software

Estratégias para modernização do legado

Desenvolvedor .NET/NodeJs e especialista em Kafka com experiência em startups e grandes empresas
Infraestrutura e Nuvem

Migração para a nuvem, mais do que mudança tecnológica, implica em mudança da cultura organizacional

Engenheiro de nuvem, arquiteto de software e especialista em Containers e Devops

Acesse nossos canais

Simplificamos, potencializamos e aceleramos resultados usando a tecnologia do jeito certo

EximiaCo 2022 – Todos os direitos reservados

0
Queremos saber a sua opinião, deixe seu comentáriox
()
x

Como “Bloom Filter” pode ser utilizada para melhorar a performance

Para se candidatar nesta turma aberta, preencha o formulário a seguir:

Condição especial de pré-venda: R$ 14.000,00 - contratando a mentoria até até 31/01/2023 e R$ 15.000,00 - contratando a mentoria a partir de 01/02/2023, em até 12x com taxas.

Tenho interesse nessa capacitação

Para solicitar mais informações sobre essa capacitação para a sua empresa, preencha o formulário a seguir:

Tenho interesse em conversar

Se você está querendo gerar resultados através da tecnologia, preencha este formulário que um de nossos consultores entrará em contato com você:

O seu insight foi excluído com sucesso!

O seu insight foi excluído e não está mais disponível.

O seu insight foi salvo com sucesso!

Ele está na fila de espera, aguardando ser revisado para ter sua publicação programada.

Tenho interesse em conversar

Se você está querendo gerar resultados através da tecnologia, preencha este formulário que um de nossos consultores entrará em contato com você:

Tenho interesse nessa solução

Se você está procurando este tipo de solução para o seu negócio, preencha este formulário que um de nossos consultores entrará em contato com você:

Tenho interesse neste serviço

Se você está procurando este tipo de solução para o seu negócio, preencha este formulário que um de nossos consultores entrará em contato com você:

× Precisa de ajuda?