Filtres de Bloom : appartenance probabiliste à un ensemble, sans faux négatifs

Ce que c'est

Un filtre de Bloom est un tableau de bits de m bits et de k fonctions de hachage. Insérer un élément met à 1 les k bits sélectionnés par ses empreintes ; interroger le filtre vérifie ces bits. Si un seul bit est à 0, l'élément n'a jamais été inséré ; si tous sont à 1, il a été inséré, ou bien les bits ont été mis à 1 par d'autres éléments — un faux positif. La documentation PostgreSQL de son index bloom décrit la structure comme économe en espace, sujette à signaler des faux positifs, et nécessitant donc que chaque résultat positif de l'index soit revérifié par rapport à la ligne réelle. La documentation Redis expose un filtre créé avec un taux de faux positifs souhaité et une capacité attendue. Le filtre de base ne peut pas supprimer : mettre un bit à 0 pourrait effacer la trace d'un autre élément. Les filtres de Bloom comptants (counting) et les filtres cuckoo existent pour répondre à ce besoin.

Pourquoi c'est important

Le filtre tient en mémoire là où l'ensemble complet ne tient pas, et il répond « non » à faible coût, ce qui évite une lecture disque, un aller-retour réseau ou une requête en base pour des clés qui n'existent certainement pas. Les moteurs de stockage en utilisent un par fichier de données pour ignorer des fichiers, les robots d'indexation en utilisent un pour « URL déjà vue », les caches en utilisent un pour éviter des recherches côté serveur pour des clés inconnues.

Comment l'appliquer

• Dimensionner le filtre à partir du nombre d'éléments attendu et du taux de faux positifs visé ; le taux augmente à mesure que le filtre dépasse sa capacité de conception, donc prévoir pour le maximum ou utiliser une variante extensible.
• Traiter chaque résultat positif comme « à vérifier auprès du magasin réel » ; ne sauter la vérification que là où un faux positif est inoffensif, comme un défaut de cache supplémentaire.
• Stocker le filtre avec les identifiants de ses fonctions de hachage, sa graine (seed) et sa taille ; tout changement implique une reconstruction à partir de l'ensemble complet.
• Le déployer là où les recherches négatives dominent (noms d'utilisateur inconnus, clés supprimées, objets froids), et mesurer la part des requêtes qu'il filtre avant de le conserver.
• Le reconstruire selon un calendrier lorsque l'ensemble sous-jacent rétrécit ; le filtre ne fait que croître.

Pièges

Dériver les k empreintes de fonctions corrélées gonfle les faux positifs. Un filtre partagé entre processus ou langages a besoin d'un hachage identique bit à bit. Rien ne peut être listé, compté ou retiré. Un filtre dont la graine ou la taille diffère de celui utilisé pour le construire renvoie silencieusement des réponses fausses plutôt que des erreurs. Le dimensionner pour la moyenne plutôt que pour le pic de taille de l'ensemble va à l'encontre de son but.