✖

Bloom filter: um elemento está no conjunto?

O Bloom filter é uma estrutura probabilística que nos permite dizer, com certo grau de probabilidade, se um elemento x está em um conjunto M.

No nosso sistema, por exemplo, precisamos medir quantas vezes os usuários clicaram em um banner de publicidade. Depois de cada clique, chega até nós uma requisição HTTP GET informando que o usuário XYZ clicou no anúncio 123. De vez em quando acontece de o usuário dar um clique duplo por engano com o mouse e, assim, chegarem duas requisições. Gostaríamos de filtrar essas requisições e tê-las registradas no banco de dados como um único clique.

Precisamos, então, de uma aplicação que leia o canal de mensagens sobre cliques e filtre as duplicações. Como faríamos isso? Cada mensagem dessas tem algum ID, então não precisamos comparar a mensagem inteira; basta descobrir se já processamos alguma vez uma mensagem com o mesmo ID. Um código simples em JavaScript que removeria duplicações de um stream (aqui, por simplicidade, de um vetor) de mensagens poderia ser assim:

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}]
var processedIds = {};

messages.forEach(function(message) {
    if (!processedIds[message.id]) {
        processedIds[message.id] = true;
        console.log(message);
    }
});

// Imprime: { id: "123" } { id: "456" } { id: "789" }

Essa solução vai bastar até a memória acabar — e ela vai acabar, porque o conjunto processedIds com o tempo só vai crescer e crescer. Podemos, é claro, programar algum tipo de expiração dos dados — podemos sempre remover as mensagens com mais de uma hora ou algo parecido.

O pior é quando nem isso basta. E se precisamos ter no conjunto processedIds os dados de pelo menos um dia e processamos, digamos, dez mil mensagens por segundo? No pior caso, precisamos guardar até 864.000.000 IDs. Se usamos uuid v4, cada ID tem comprimento 36, o que significa que por dia precisamos guardar no mínimo 31 GB. É um pouco demais. Não dá para reduzir esse consumo de memória?

Bloom filter

Em vez de guardar o ID inteiro, podemos guardar apenas o seu hash. Podemos usar a clássica murmurhash, que devolve para cada string um número inteiro de 32 bits e, além disso, tem boa distribuição:

var murmurhash = require("murmurhash");

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var processedHashedIds = {};

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id);
    if (!processedHashedIds[hashedId]) {
        processedHashedIds[hashedId] = true;
        console.log(message);
    }
});

// Imprime: { id: "123" } { id: "456" } { id: "789" }

Em seguida usamos o truque do vetor de bits. É um vetor em que vamos guardar apenas zeros e uns. Se temos uma função hash de n bits, precisamos de um vetor de tamanho 2n, para sermos capazes de endereçar no vetor todas as saídas possíveis da função hash. A ideia é que, no começo, o vetor contém só zeros. Se a função hash devolver para a entrada "123" o número 47, simplesmente colocamos 1 no vetor, no índice 47. Assim marcamos que já vimos o hash de valor 47.

var n = 8;
var numberOfValues = Math.pow(2, n);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var bitVector = new Array(numberOfValues);

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id) % numberOfValues;
    if (!bitVector[hashedId]) {
        bitVector[hashedId] = true;
        console.log(message);
    }
});

// Imprime: { id: "123" } { id: "456" } { id: "789" }

Com aquele código % numberOfValues apenas cortamos o murmurhash de modo que ele se torne uma função hash de n bits, nada mais. E isso é o Bloom filter. Ainda que uma versão bem degenerada. O problema dessa abordagem são, naturalmente, as colisões, que necessariamente ocorrem. Valores de entrada diferentes podem ter o mesmo hash de saída. Por isso, para reduzir a probabilidade de ocorrer uma colisão, não usamos apenas uma função hash, mas várias. Podemos criar várias funções hash, por exemplo, acrescentando um sal ao valor de entrada. Uma função simples que criaria diferentes funções hash de n bits poderia ser assim:

var murmurhash = require("murmurhash");

function createNBitHashFunction(n, salt) {
    var upperBound = Math.pow(2, n);
    return function(inputString) {
        return murmurhash.v2(inputString + salt) % upperBound;
    }
}

var firstHashFunction = createNBitHashFunction(8, "nejakaSul");
var secondHashFunction = createNBitHashFunction(8, "nejakaJinaSul");

console.log(firstHashFunction("123")); // 42
console.log(secondHashFunction("123")); // 174

Podemos escrever a classe que representa o Bloom filter assim:

function BloomFilter(numberOfHashFunctions, numberOfBits) {
    this.reset(numberOfHashFunctions, numberOfBits);
}

BloomFilter.prototype.reset = function(numberOfHashFunctions, numberOfBits) {
    this.bitVector = new Array(Math.pow(2, numberOfBits));
    this.hashFunctions = [];

    for (var i = 0; i < numberOfHashFunctions; i++) {
        this.hashFunctions.push(createNBitHashFunction(numberOfBits, i.toString()));
    }
}

BloomFilter.prototype.add = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        if (!this.bitVector[checksum]) {
            return false;
        }
    }
    return true;
}
  • O método add adiciona um elemento ao Bloom filter: calcula o hash com todas as funções hash e guarda true no índice correspondente.
  • O método contains verifica se o elemento dado está contido no Bloom filter.

O Bloom filter pode ser usado com facilidade:

var bloomFilter = new BloomFilter(3, 8);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];

messages.forEach(function(message) {
    if (!bloomFilter.contains(message.id)) {
        bloomFilter.add(message.id);
        console.log(message);
    }
});

// Imprime: { id: "123" } { id: "456" } { id: "789" }

E essa é toda a mágica do Bloom filter básico. Ele tem estas propriedades básicas:

  • Se o método contains responde que o elemento dado não está no Bloom filter, isso significa que você realmente nunca inseriu esse elemento nele.
  • Se o método responde que o elemento dado está presente no Bloom filter, isso não significa necessariamente que você realmente guardou esse elemento nele — pode ter ocorrido uma colisão das funções hash.
  • Em geral, se você quer reduzir a probabilidade de uma resposta incorreta, aumente o número de funções hash ou aumente o tamanho delas (isto é, o tamanho do valor de saída).
  • Quanto mais funções hash você usar, mais lento o Bloom filter será.
  • Quanto maiores as funções hash que você usar, mais espaço o Bloom filter ocupará.
  • Depois que você insere um elemento no Bloom filter, não é mais possível removê-lo.