Comprendre les filtres de Bloom par l’exemple

 (llimllib.github.io)
2 points par GN⁺ 2025-07-01 | 1 commentaires | Partager sur WhatsApp
  • Un filtre de Bloom est une structure de données qui permet de filtrer rapidement l’appartenance à un grand ensemble avec peu de mémoire, en distinguant uniquement « certainement absent » et « peut-être présent »
  • Son principe repose sur un vecteur de bits et plusieurs fonctions de hachage ; lors de l’insertion, les bits aux positions indiquées par les résultats de hachage sont mis à 1
  • À la consultation, si l’une de ces mêmes positions vaut 0, l’élément peut être exclu ; mais même si elles valent toutes 1, la possibilité d’un faux positif demeure
  • Les fonctions de hachage doivent être indépendantes, proches d’une distribution uniforme et rapides ; un cas rapporte un gain de vitesse d’environ 800 % en passant de md5 à murmur
  • La précision et le coût du filtre dépendent de l’équilibre entre le nombre attendu d’éléments n, le nombre de bits m et le nombre de hachages k ; l’insertion comme la recherche sont toutes deux en O(k)

Fonctionnement d’un filtre de Bloom

  • Un filtre de Bloom est une structure de données probabiliste qui détermine rapidement et efficacement en mémoire si un élément appartient à un ensemble
  • Le résultat se limite à deux possibilités
    • l’élément est certainement absent de l’ensemble
    • l’élément est peut-être présent dans l’ensemble
  • Sa structure interne est un vecteur de bits ; lorsqu’on ajoute un élément, l’entrée est passée dans plusieurs fonctions de hachage
  • L’insertion se termine en mettant à 1 les indices de bits pointés par chaque valeur de hachage
  • Dans l’exemple, Fnv et Murmur sont utilisés comme fonctions de hachage simples

Vérification d’appartenance et faux positifs

  • La recherche utilise les mêmes fonctions de hachage que lors de l’insertion
  • Si l’un des bits pointés par les valeurs de hachage vaut 0, l’élément est certainement absent de l’ensemble
  • Si tous les bits concernés valent 1, l’élément est peut-être présent
    • Ces mêmes bits peuvent déjà avoir été positionnés par un autre élément, ou par une combinaison de plusieurs éléments
  • À cause de ces collisions, un filtre de Bloom peut produire des faux positifs (false positives)

Critères de choix des fonctions de hachage

  • Les fonctions de hachage d’un filtre de Bloom doivent être indépendantes, proches d’une distribution uniforme et aussi rapides que possible
  • Les hachages cryptographiques comme sha1 sont très répandus, mais ne constituent pas toujours un bon choix pour un filtre de Bloom
  • Voici des exemples de hachages rapides et simples
  • Il existe un cas où le passage de md5 à murmur dans une implémentation de filtre de Bloom a permis d’obtenir environ 800 % de gain de vitesse

Hachages utilisés dans les implémentations réelles

  • Différentes implémentations utilisent différentes fonctions de hachage pour les filtres de Bloom
    • Chromium : utilise murmur
    • Plan9 : utilise le hachage simple proposé dans Mitzenmacher 2005
    • Sdroege Bloom filter : utilise fnv1a
    • Squid : utilise MD5
    • RedisBloom : utilise murmur
    • Apache Spark : utilise murmur
    • influxdb : utilise xxhash
    • bloomd : les deux premiers hachages sont murmur, les deux suivants SpookyHash, puis les hachages suivants utilisent une combinaison des deux
    • fleur, flor, bloom : utilisent fnv
    • Sqlite : ajoute un filtre de Bloom pour les requêtes analytiques
    • RocksDB : configurable ; le code source indique que xxh3, de la famille xxhash, donnait les meilleurs résultats
    • ScyllaDB : utilise murmur

Déterminer la taille du filtre et le nombre de fonctions de hachage

  • Un filtre de Bloom permet d’ajuster le taux de faux positifs
    • Un filtre plus grand réduit les faux positifs
    • Un filtre plus petit augmente les faux positifs
  • Le taux de faux positifs se calcule approximativement avec (1-e^-kn/m)^k
    • n : nombre d’éléments que l’on prévoit d’insérer
    • m : nombre de bits du filtre
    • k : nombre de fonctions de hachage
  • Plus il y a de fonctions de hachage, plus la recherche et l’insertion sont lentes, et plus le filtre se remplit rapidement
  • À l’inverse, s’il y a trop peu de fonctions de hachage, les faux positifs peuvent devenir excessifs
  • Pour des valeurs données de m et n, la valeur optimale de k peut être choisie avec (m/n)ln(2)
  • La taille du filtre peut être ajustée dans l’ordre suivant
    • Estimer grossièrement la valeur attendue de n
    • Choisir une valeur de m
    • Calculer la valeur optimale de k
    • Calculer le taux d’erreur avec les valeurs choisies de n, m et k
    • Si le taux d’erreur est difficile à accepter, modifier m et recalculer

Performances et conditions d’utilisation adaptées

  • Dans un filtre de Bloom avec m bits et k fonctions de hachage, l’insertion comme la vérification d’appartenance sont en O(k)
  • Lorsqu’on ajoute ou recherche un élément, il suffit de le passer dans k fonctions de hachage, puis de positionner ou vérifier les bits correspondants
  • L’efficacité en espace dépend du taux d’erreur acceptable
  • Si l’ensemble des éléments pouvant être insérés est très limité, un vecteur de bits déterministe peut être préférable
  • S’il est impossible d’estimer, même approximativement, le nombre d’éléments qui seront insérés, une table de hachage ou un scalable Bloom filter peut être plus adapté

Références et exemples d’usage

À lire aussi

1 commentaires

 
GN⁺ 2025-07-01
Avis sur Hacker News

  • Cet article vise exactement les gens comme moi. J’avais déjà entendu le nom filtre de Bloom, et chaque fois qu’il était mentionné je me disais qu’il faudrait que je me renseigne ; en lisant cet article, je l’ai enfin fait, et c’était l’introduction parfaite que je cherchais :)

    • J’ai découvert les filtres de Bloom il y a plus de dix ans, quand on m’a demandé d’en implémenter un pour la fonction de recherche d’iBooks
    • C’est une structure vraiment amusante. Quand un problème qui nécessite un filtre de Bloom se présente, c’est enthousiasmant, mais malheureusement, selon le domaine, ça peut être rare

  • En 2009, à l’université, j’ai créé un filtre de Bloom en CUDA, et mon directeur de recherche était un ancien de Nvidia. Mais ensuite, dans ma carrière, je n’ai plus jamais fait de programmation GPU
    Si j’avais fait d’autres choix à l’époque, j’aurais peut-être pu gagner 100 millions de dollars

    • Pareil pour moi. En 2009, par curiosité, j’ai utilisé CUDA v1 sur une GeForce 8 pour créer ce qui devait être une toute première forme de toolkit de bioinformatique optimisé GPU
      Puis je suis parti faire autre chose, et j’ai raté le gros lot
    • Vu que c’est une idée d’informatique datant de 1970, ça paraît peu probable. Les idées qui valaient le coup d’être tentées sur des GPU généralistes devaient déjà être dans le viseur de tout le monde
      Il y a 10 ans, j’ai créé une implémentation de hashcash sur GPU, mais aujourd’hui ça n’a probablement presque aucune valeur
    • Pour mon projet de licence avec mention, j’ai porté en CUDA un algorithme de machine learning, puis j’ai simplement haussé les épaules et je suis parti faire de la programmation embarquée
    • Même acheter du Bitcoin aurait rapporté bien plus

  • Note à l’auteur : la partie interactive est vraiment excellente. Pour rendre le point central encore plus évident, ce serait bien de donner un exemple de deux chaînes qui provoquent une collision de hachage, d’en faire saisir une dans le premier champ, puis de vérifier l’autre dans le second
    Cela montrerait pourquoi la réponse est toujours « peut appartenir à l’ensemble », et non « appartient »

    • "bloom" et "demonstrators " entrent en collision. Attention à l’espace à la fin de la seconde chaîne
      Les deux entrent en collision avec fnv: 7, murmur: 12

  • J’ai une astuce que j’aime bien. Quand on doit faire beaucoup de tests d’appartenance sur un ensemble qui peut être petit, on peut ajouter de façon spéculative un filtre de Bloom 64 bits avec une fonction de hachage très simple
    Ça a l’air complètement idiot, mais le coût est tellement faible que ça vaut le pari. Même si ça ne marche pas bien, ça ajoute environ 10 ns aux insertions et aux tests d’appartenance ; si ça marche, en revanche, ça peut éviter une quantité énorme de travail

    • Chromium fait aussi ça à plusieurs endroits. L’article ne renvoie qu’à l’exemple de Safe Browsing qui utilise murmur, mais le moteur de rendu Blink utilise généralement rapidhash et emploie ces micro-filtres à divers endroits
      Par exemple pour querySelector() dans certains cas, pour préfiltrer des recherches par hachage dans des buckets CSS, ou pour rejeter rapidement des éléments lorsqu’on cherche certains attributs Aria pour l’accessibilité. C’est surprenant que des filtres minuscules de 32 ou 64 bits fonctionnent, mais en pratique ils sont souvent efficaces. Il existe aussi quelques filtres de Bloom plus grands. J’en ai ajouté plusieurs

  • J’ai demandé à ChatGPT de m’en faire un en Python, et il a utilisé la méthode consistant à découper le digest md5 de base pour l’utiliser comme plusieurs hachages. Pour des usages peu critiques, ça me semble acceptable

  • On peut voir une autre visualisation des filtres de Bloom à la fin de cette page :
    https://www.chrislaux.com/hashtable.html

  • Je pensais l’avoir déjà vue, mais en réalité c’était cette autre page : https://bdupras.github.io/filter-tutorial/
    Cette page ajoute un peu plus d’informations en comparant les filtres de Bloom et les filtres cuckoo

  • Récemment, j’ai implémenté une fonctionnalité de prévention du spam dans les messages de log avec un filtre de Bloom. Dans le logger, on hachait le message et on l’ajoutait au filtre ; si l’élément y était déjà, on n’affichait pas le message
    Toutes les quelques secondes, on parcourait le filtre pour effacer tous les bits, et ça convenait bien parce qu’il n’était pas nécessaire de se soucier d’effacer atomiquement tous les bits du filtre. Même si seulement une partie des bits était effacée pendant l’arrivée d’un message, cela suffisait pour qu’il soit de nouveau journalisé. L’ancienne implémentation comptait le nombre de messages vus jusqu’à saturation à N, ce qui avait pour effet que lorsqu’un message précis se répétait, il n’apparaissait plus qu’à un rythme inférieur à celui de réinitialisation du filtre
    C’était assez satisfaisant de connaître les filtres de Bloom depuis longtemps, puis de leur trouver naturellement un vrai cas d’usage qui apportait une nette amélioration

  • Pour aller plus loin, l’article d’Eli Bendersky sur les filtres de Bloom était également très bon :
    https://eli.thegreenplace.net/2025/bloom-filters/

  • Les concepts nécessaires pour comprendre les filtres de Bloom, les ensembles et les tables de hachage se recoupent, à mon avis, à environ 95 %. Un ensemble est une table de hachage pour tests d’appartenance qui ne s’intéresse qu’aux clés, pas aux valeurs ; un filtre de Bloom est un ensemble qui exploite le fait que le hachage plusieurs-vers-un « compresse » l’espace des clés via les collisions
    En quelque sorte, on utilise volontairement des fonctions de hachage qui provoquent beaucoup de collisions. Si une clé donnée a été hachée au moins une fois, le résultat sera forcément positif, mais une autre clé ayant produit le même hachage peut aussi exister. Ce n’est pas un bug, c’est une fonctionnalité

    • Je suis content de ne pas être le seul à comprendre un filtre de Bloom comme une table de hachage qui ne suit pas les données elles-mêmes, mais seulement les buckets qui contiennent des données
    • Le point essentiel qui manque dans cette explication, c’est qu’un filtre de Bloom utilise plusieurs fonctions de hachage pour réduire les collisions. Par exemple, avec trois hachages, pour qu’une clé soit considérée comme appartenant à l’ensemble, les trois hachages doivent correspondre
      Cela réduit la probabilité de faux positifs dus aux collisions, tout en conservant la garantie d’absence de faux négatifs
    • Si vous avez bien compris les filtres de Bloom, vous êtes déjà presque au point pour comprendre les projections aléatoires et certaines implémentations du hachage sensible à la localité