Filtre de Bloom : un élément est-il dans l’ensemble ?

Le filtre de Bloom est une structure probabiliste qui nous permet de dire, avec une certaine probabilité, si un élément x se trouve dans un ensemble M.

Dans notre système, par exemple, nous devons compter combien de fois les utilisateurs ont cliqué sur une bannière publicitaire. À chaque clic, nous recevons une requête HTTP GET qui nous informe que l’utilisateur XYZ a cliqué sur la publicité 123. Il arrive parfois qu’un utilisateur fasse un double clic par erreur avec sa souris et que nous recevions donc deux requêtes. Nous aimerions filtrer ces requêtes et n’enregistrer qu’un seul clic dans la base de données.

Il nous faut donc une application qui lise le flux de messages sur les clics et élimine les doublons. Comment nous y prendre ? Chaque message a un identifiant (ID), donc nous n’avons pas besoin de comparer le message entier : il nous suffit de savoir si nous avons déjà traité un message avec le même ID. Un code simple en JavaScript qui supprimerait les doublons d’un flux de messages (ici, pour simplifier, d’un tableau) pourrait ressembler à ceci :

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);
    }
});

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

Cette solution suffira jusqu’à ce que la mémoire soit saturée, et elle le sera un jour, car l’ensemble processedIds ne fera que grossir avec le temps. Nous pouvons bien sûr ajouter une expiration des données : par exemple, supprimer tous les messages vieux de plus d’une heure.

C’est plus embêtant quand même cela ne suffit pas. Que faire si nous devons garder dans l’ensemble processedIds les données d’au moins une journée et que nous traitons, disons, dix mille messages par seconde ? Dans le pire des cas, il faut stocker jusqu’à 864 000 000 identifiants. Si nous utilisons des UUID v4, chaque ID a une longueur de 36 caractères, ce qui veut dire qu’il faut stocker au moins 31 Go par jour. C’est un peu beaucoup. Ne pourrait-on pas réduire cette consommation de mémoire ?

Filtre de Bloom

Au lieu de stocker l’ID en entier, nous pouvons stocker seulement son empreinte (en anglais « hash »), c’est-à-dire un nombre court calculé à partir de l’ID. Nous pouvons utiliser la fonction classique murmurhash, qui renvoie pour chaque chaîne de caractères un entier de 32 bits et qui, de plus, répartit bien les valeurs :

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);
    }
});

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

Nous utilisons ensuite l’astuce du tableau de bits. C’est un tableau dans lequel nous ne stockons que des zéros et des uns. Si nous avons une fonction de hachage sur n bits, il nous faut un tableau de taille 2ⁿ pour pouvoir y adresser toutes les sorties possibles de la fonction de hachage. L’idée est qu’au début le tableau ne contient que des zéros. Si la fonction de hachage nous renvoie ensuite le nombre 47 pour l’entrée "123", nous mettons simplement un 1 à l’indice 47 du tableau. Nous marquons ainsi que nous avons déjà vu l’empreinte de valeur 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);
    }
});

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

Avec le code % numberOfValues, nous avons simplement tronqué murmurhash pour en faire une fonction de hachage sur n bits, rien de plus. Et voilà un filtre de Bloom, même s’il s’agit d’une version très dégénérée. Le problème de cette approche, ce sont évidemment les collisions, qui se produiront forcément : des entrées différentes peuvent avoir la même empreinte. Pour réduire la probabilité d’une collision, nous n’utilisons donc pas une seule fonction de hachage, mais plusieurs. Nous pouvons créer plusieurs fonctions de hachage, par exemple, en ajoutant un sel à la valeur d’entrée. Une fonction simple qui créerait différentes fonctions de hachage sur n bits pourrait ressembler à ceci :

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, "unSel");
var secondHashFunction = createNBitHashFunction(8, "unAutreSel");

console.log(firstHashFunction("123")); // 246
console.log(secondHashFunction("123")); // 14

Nous pouvons écrire la classe qui représente un filtre de Bloom ainsi :

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

La méthode add ajoute un élément au filtre de Bloom : elle calcule l’empreinte avec toutes les fonctions de hachage et stocke true à l’indice correspondant.
La méthode contains vérifie ensuite si l’élément donné est contenu dans le filtre de Bloom.

Utiliser le filtre de Bloom est facile :

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);
    }
});

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

Voilà toute la magie du filtre de Bloom de base. Il a les propriétés fondamentales suivantes :

Si la méthode contains répond que l’élément n’est pas dans le filtre de Bloom, c’est que tu ne l’y as vraiment jamais ajouté.
Si la méthode répond que l’élément est présent dans le filtre de Bloom, cela ne signifie pas forcément que tu l’y as réellement ajouté : il a pu se produire une collision entre fonctions de hachage.
En général, pour réduire la probabilité d’une réponse erronée, augmente le nombre de fonctions de hachage ou augmente leur taille (c’est-à-dire la taille de la valeur de sortie).
Plus tu utilises de fonctions de hachage, plus le filtre de Bloom sera lent.
Plus les fonctions de hachage que tu utilises sont grandes, plus le filtre de Bloom occupera de place.
Une fois qu’un élément a été ajouté au filtre de Bloom, il n’est plus possible de le retirer.

« Précédent: HyperLogLog : comment estimer avec précision le nombre de valeurs distinctes

Suivant: Chiffrement de César »

Filtre de Bloom : un élément est-il dans l’ensemble ?

Filtre de Bloom

Filtre de Bloom : un élément est-il dans l’ensemble ?