✖

Filtro de Bloom: cómo saber si un elemento está en un conjunto

El filtro de Bloom es una estructura probabilística que nos permite decir, con cierto grado de probabilidad, si un elemento x se encuentra en un conjunto M.

En nuestro sistema, por ejemplo, necesitamos medir cuántas veces han hecho clic los usuarios en un banner publicitario. Después de cada clic nos llega una petición HTTP GET que nos informa de que el usuario XYZ ha hecho clic en el anuncio 123. A veces ocurre que el usuario hace doble clic con el ratón por error y nos llegan dos peticiones. Nos gustaría filtrar esas peticiones y tenerlas registradas en la base de datos como un solo clic.

Necesitamos, por tanto, una aplicación que lea el canal de mensajes sobre clics y elimine los duplicados. ¿Cómo lo haríamos? Cada mensaje tiene un ID, así que no hace falta comparar el mensaje entero; nos basta con averiguar si ya hemos procesado alguna vez un mensaje con el mismo ID. Un código sencillo en JavaScript que eliminara los duplicados de un stream de mensajes (aquí, por simplicidad, de un array) podría ser así:

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" }

Esta solución bastará hasta que se nos acabe la memoria, y se acabará, porque el conjunto processedIds con el tiempo solo crecerá y crecerá. Por supuesto, podemos programar alguna caducidad de los datos: podemos eliminar siempre los mensajes de más de una hora o algo parecido.

Lo malo es cuando ni eso basta. ¿Y si necesitamos tener en el conjunto processedIds los datos de al menos un día y procesamos, digamos, diez mil mensajes por segundo? En el peor de los casos necesitamos guardar hasta 864.000.000 identificadores. Si usamos uuid v4, cada ID tiene longitud 36, lo que significa que al día necesitamos guardar como mínimo 31 GB. Es un poco demasiado. ¿No se podría reducir ese consumo de memoria?

Filtro de Bloom

En lugar de guardar el ID entero, podemos guardar solo su hash. Podemos usar la clásica murmurhash, que para cada string devuelve un número entero de 32 bits y, además, tiene buena distribución:

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" }

A continuación usaremos el truco del vector de bits. Es un array en el que guardaremos solo ceros y unos. Si tenemos una función hash de n bits, necesitamos un vector de tamaño 2n para poder direccionar en el vector todas las salidas posibles de la función hash. La idea es que al principio el vector contiene solo ceros. Si entonces la función hash nos devuelve para la entrada "123" el número 47, simplemente ponemos un uno en el vector, en el índice 47. Así marcamos que ya hemos visto el 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" }

Con el código % numberOfValues solo hemos recortado murmurhash para convertirla en una función hash de n bits, nada más. Y esto es un filtro de Bloom. Aunque en una versión muy degenerada. El problema de este enfoque son, como es lógico, las colisiones, que necesariamente se producirán. Valores de entrada distintos pueden tener el mismo hash de salida. Por eso, para reducir la probabilidad de que haya una colisión, no usaremos una sola función hash, sino varias. Podemos crear varias funciones hash, por ejemplo, añadiendo una sal al valor de entrada. Una función sencilla que creara distintas funciones hash de n bits podría ser así:

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

La clase que representa un filtro de Bloom la podemos escribir así:

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;
}
  • El método add añade un elemento al filtro de Bloom: calcula el hash con todas las funciones hash y en el índice correspondiente guarda true.
  • El método contains averigua si el elemento dado está contenido en el filtro de Bloom.

El filtro de Bloom se puede usar fácilmente:

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" }

Y esa es toda la magia del filtro de Bloom básico. Tiene estas propiedades fundamentales:

  • Si el método contains responde que el elemento no está en el filtro de Bloom, significa que de verdad nunca lo has insertado.
  • Si el método responde que el elemento está presente en el filtro, no tiene por qué significar que de verdad lo hayas guardado: pudo producirse una colisión de las funciones hash.
  • En general, si quieres reducir la probabilidad de una respuesta incorrecta, aumenta el número de funciones hash o aumenta su tamaño (es decir, el tamaño del valor de salida).
  • Cuantas más funciones hash uses, más lento será el filtro de Bloom.
  • Cuanto mayores sean las funciones hash que uses, más espacio ocupará el filtro de Bloom.
  • Una vez que insertas un elemento en el filtro de Bloom, ya no es posible eliminarlo.