Comprendre les filtres de Bloom par l’exemple

• Un filtre de Bloom est une structure de données probabiliste qui permet de vérifier rapidement la présence d’un élément dans un ensemble de manière efficace en mémoire
• Il indique seulement si un élément est certainement absent de l’ensemble ou peut-être présent, avec une probabilité de faux positifs
• Sa structure de base repose sur un vecteur de bits et plusieurs fonctions de hachage qui positionnent à 1 les bits correspondant à chaque élément
• Le taux d’erreur et les performances dépendent de la taille du filtre et du nombre de fonctions de hachage, avec des réglages possibles selon l’usage
• L’article présente aussi les fonctions de hachage recommandées, les méthodes de configuration optimale, l’efficacité spatiale et des cas d’usage concrets

---

Qu’est-ce qu’un filtre de Bloom ?

• Un filtre de Bloom est une structure de données qui permet de déterminer rapidement et avec une bonne efficacité mémoire si un élément est présent dans un ensemble
• Pour obtenir cette efficacité, le filtre de Bloom est une structure probabiliste dont le résultat d’un test se limite à « certainement absent de l’ensemble » ou « peut-être présent dans l’ensemble »
• La structure centrale d’un filtre de Bloom est un vecteur de bits
• Lorsqu’on ajoute un élément, on le hache plusieurs fois afin de mettre à 1 les bits des index correspondants
• Si tous les bits correspondant aux index produits par chaque fonction de hachage valent 1, on conclut que l’élément « peut être présent » ; sinon, on le considère comme « certainement absent »

Exemple de fonctionnement

• Plusieurs fonctions de hachage (ex. : Fnv, Murmur) servent à projeter un élément vers plusieurs index de bits
• Lors de l’ajout d’un élément, les bits des index calculés sont mis à 1
• Pour vérifier la présence d’un élément donné, si tous les index obtenus avec les mêmes fonctions de hachage valent 1, on considère qu’il « peut être présent »
• Si au moins un de ces bits vaut 0, on peut conclure avec certitude qu’il n’est pas dans l’ensemble
• Cela introduit la possibilité de faux positifs

Sujets avancés

Attention : l’auteur n’a en réalité aucune expérience directe d’utilisation d’un filtre de Bloom dans un service à grande échelle

Choix des fonctions de hachage

• Il est recommandé d’utiliser des fonctions de hachage indépendantes et à distribution uniforme
• Les fonctions de hachage cryptographiques (sha1, etc.) ne conviennent pas, car elles sont trop lentes
• Exemples de fonctions de hachage rapides et simples : Murmur, xxHash, Fnv, HashMix, etc.
• Dans un cas réel, le passage de md5 à murmur a permis un gain de vitesse de plus de 800 %

Déterminer la taille du filtre de Bloom

• Plus la taille du filtre (m) est grande, plus le taux de faux positifs diminue
• Le taux de faux positifs peut généralement être approximé par (1-e^(-kn/m))^k
• Il faut choisir de manière appropriée le nombre attendu d’éléments (n), la taille du filtre (m) et le nombre de fonctions de hachage (k)

Combien de fonctions de hachage ?

• Plus le nombre de fonctions de hachage est élevé, plus l’exécution ralentit et plus le filtre se remplit vite
• S’il y en a trop peu, le taux de faux positifs augmente
• La valeur idéale de k se calcule par (m/n)ln(2)
• Lors de la conception, on peut suivre la procédure suivante :
  • estimer le nombre attendu d’éléments n
  • fixer le nombre de bits m
  • calculer le k optimal
  • vérifier si le taux d’erreur souhaité est atteint ; sinon, ajuster m

Performances et efficacité spatiale

• Dans un filtre de Bloom, l’ajout d’un élément et le test de présence ont une complexité temporelle de O(k)
• L’efficacité spatiale dépend de la tolérance au taux d’erreur et de la plage d’éléments considérée
• S’il est impossible d’estimer même approximativement l’ordre de grandeur des éléments, une table de hachage ou un filtre de Bloom extensible peut être préférable

Cas d’usage

• Pour des exemples d’utilisation détaillés, voir Wikipedia
• C. Titus Brown présente un cas d’application des filtres de Bloom en bio-informatique

Références

• Broder, Mitzenmacher : Network Applications of Bloom Filters: A Survey — article de synthèse sur les filtres de Bloom
• Wikipedia – Bloom Filter
• Kirsch, Mitzenmacher: Less Hashing, Same Performance
• Almeida et al. : Scalable Bloom Filters

[GN⁺]

Commentaires sur Hacker News

• J’ai l’impression que cet article est exactement fait pour des gens comme moi. J’en avais déjà entendu parler, mais je remettais toujours à plus tard le moment de m’y intéresser. Cette fois, en voyant l’article, je m’y suis enfin penché, et c’était précisément le genre d’introduction que je cherchais
  • J’ai découvert les Bloom filters pour la première fois en implémentant la fonction de recherche d’iBooks. C’était il y a déjà plus de 10 ans
  • Les Bloom filters sont vraiment amusants. Quand on résout un problème et qu’on se rend compte qu’un Bloom filter est nécessaire, c’est très excitant, mais selon le domaine, ces situations sont assez rares, ce qui est un peu dommage
• Une suggestion à l’auteur. La partie interactive est très satisfaisante. Pour mieux faire comprendre les propriétés d’un Bloom filter, ce serait bien de montrer un exemple où deux chaînes provoquent une collision de hachage, puis de faire saisir l’une et entrer l’autre dans le deuxième champ. Cela permettrait de comprendre facilement pourquoi on obtient ce résultat si particulier : « pas certain que ce soit dans l’ensemble, mais peut-être »
  • Par exemple, "bloom" et "demonstrators " (avec un espace final) entrent en collision sur fnv: 7, murmur: 12
• À l’université en 2009, j’ai eu l’occasion d’implémenter un Bloom filter en CUDA. Mon directeur de recherche venait auparavant de Nvidia. Mais dans ma carrière, je suis parti dans une voie sans aucun rapport avec la programmation GPU. Je me dis parfois que j’aurais peut-être pu gagner 100 millions de dollars si j’avais fait d’autres choix
  • Comme l’idée en informatique date de 1970, je pense que ça n’aurait pas été possible. J’ai l’impression que les idées autour du GPGPU avaient déjà été suffisamment explorées. J’ai moi aussi implémenté Hashcash sur GPU il y a 10 ans, et vu d’aujourd’hui, cela vaut presque zéro
  • Après avoir porté un algorithme de machine learning sur CUDA pour mon projet de fin d’études, j’ai changé d’orientation vers la programmation embarquée en pensant que ce n’était pas grand-chose
  • J’ai eu une expérience similaire. En 2009, avec une GeForce 8 et CUDA v1(!), j’ai probablement créé l’un des premiers toolkits de bioinformatique optimisés pour GPU. Je l’ai fait par simple curiosité, puis j’ai complètement bifurqué, ratant ainsi une occasion de gagner beaucoup d’argent
  • Une remarque à moitié en plaisantant disant qu’il aurait été encore plus rentable d’acheter du Bitcoin
• J’ai un petit truc que j’aime bien. Pour un petit set qui peut contenir peu d’éléments mais pour lequel on fait souvent des vérifications d’appartenance, on peut intégrer un Bloom filter 64 bits avec une fonction de hachage très simple. Ça a l’air idiot, mais le coût est si faible qu’on peut presque le tenter comme un pari. Même si ça ne marche pas, cela n’ajoute qu’environ 10 ns aux vérifications d’appartenance ou aux insertions, mais quand ça marche bien, cela peut réduire énormément la charge de travail
  • Chromium utilise aussi ce genre d’astuce un peu partout. L’article ne mentionne que Safe Browsing, mais dans la couche Blink, rapidhash et ce type de micro-filtres sont activement utilisés. Par exemple pour querySelector(), comme préfiltre de dictionnaire de recherche par hachage dans les buckets CSS, ou pour un rejet rapide lors de la recherche d’attributs Aria pour l’accessibilité. Les petits filtres 32 bits et 64 bits fonctionnent très bien en pratique. Des Bloom filters plus grands sont aussi utilisés de manière pertinente, et j’ai moi-même ajouté ce genre de fonctionnalité
• J’ai récemment utilisé un Bloom filter pour une fonction anti-spam sur des messages de log. Je hachais les messages de log et les mettais dans le filtre, puis s’ils y étaient déjà, je ne les affichais pas. Je remettais périodiquement à zéro tous les bits du filtre. Pas besoin d’effacer tous les bits de façon atomique : même si certains bits sont effacés pendant que des messages arrivent, cela ne fait que permettre à certains logs d’être réémis. Avant, je gardais un compteur séparé pour chaque message, mais cette méthode était bien plus efficace. J’ai été très satisfait de cette application concrète d’un Bloom filter
• Pour une visualisation de Bloom filter, il y a un bon exemple à la fin de cette page
• Je recommande aussi un autre article d’introduction aux Bloom filters écrit par Eli Bendersky. Si vous voulez aller plus loin, voir ici
• J’ai l’impression que près de 95 % des concepts nécessaires pour comprendre les Bloom filters, les sets et les tables de hachage se recoupent. Un set est une table de hachage qui ne s’intéresse qu’aux clés, et un Bloom filter est un set qui exploite activement les propriétés de collision du hachage. Il utilise volontairement des fonctions de hachage qui favorisent les collisions. Si une clé donnée a déjà été insérée, le résultat sera forcément positif. Mais il peut exister une autre clé produisant les mêmes valeurs de hachage. Ce n’est donc pas un bug, c’est une propriété voulue
  • Moi aussi, j’ai tendance à voir un Bloom filter comme une table de hachage dont on retire les données elles-mêmes pour ne suivre que les buckets. Je suis content de voir que je ne suis pas le seul à avoir cette façon de penser
  • Ce serait bien d’ajouter une précision sur le fait qu’un Bloom filter utilise plusieurs fonctions de hachage pour réduire les collisions. Par exemple, si 3 fonctions de hachage correspondent toutes, on considère que l’élément est dans le set. Cette structure permet de réduire la probabilité de faux positifs tout en garantissant l’absence totale de faux négatifs
  • Si vous avez compris les Bloom filters, vous pourrez aussi rapidement comprendre les projections aléatoires ou certaines implémentations des Locality Sensitive Hashes
• En déboguant un pic de lectures sur Cassandra, je suis vraiment tombé dans le sujet des Bloom filters. Il y avait un nombre anormalement élevé de consultations de sstable pour des clés inexistantes. J’ai compris assez tard le rôle des Bloom filters attachés à chaque sstable. Le taux de faux positifs par défaut était de 0,1, ce qui était beaucoup trop élevé dans notre cas. Nous avions surtout des cache misses, et les faux positifs provoquaient beaucoup trop de lectures inutiles. En abaissant ce taux à 0,01, l’utilisation mémoire a légèrement augmenté, mais les lectures inutiles ont fortement diminué, ce qui a réduit la latence de lecture p99 de 16 à 18 %
• J’adore vraiment les Bloom filters. Quand je parle technique, il y a trois concepts clés que j’essaie toujours de transmettre : les Bloom filters, le Random Weight Hashing (Rendezvous Hashing, Highest Random Weight Hashing) et le Cumulative flow diagram. Je pense que ces trois concepts sont essentiels pour exploiter des systèmes distribués complexes
  • Je pense aussi que les structures de tables de hachage distribuées sont tout aussi importantes. Par exemple : circle, chord, CAN, kademlia, etc.