Filtre de Bloom

Soit U l'univers de tous les éléments que pourrait contenir l'ensemble considéré. Par exemple, U est l'ensemble des entiers sur 32 bits, ou un ensemble de mots. Le filtre a deux composantes[2] :

• T : un tableau de bits de taille m dont chaque case est initialisée à 0. (indexé de 1 à m)
• ${\displaystyle (h_{i})_{1\leq i\leq k}}$ : k fonctions de hachage de ${\displaystyle U\rightarrow [\![1,m]\!]}$.

Pour ajouter un élément ${\displaystyle e}$, on met des 1 dans les cases d'indice ${\displaystyle h_{1}(e),\dots ,h_{k}(e)}$.

Pour tester si un élément ${\displaystyle e}$ est présent, on vérifie que les cases d'indice ${\displaystyle h_{1}(e),\dots ,h_{k}(e)}$ contiennent toutes un 1. Il se peut que le test d'appartenance renvoie vrai alors que l'élément est absent, c'est un faux positif.

Les éléments ne peuvent pas être retirés de l'ensemble (bien que cela soit possible avec certaines variantes telles que les filtres de Bloom par comptage (en)).

Le filtre de Bloom utilise un espace constant. C'est son principal intérêt.

Il est possible d'évaluer la proportion de faux-positifs en fonction de divers paramètres. Ainsi, si l'on considère une fonction de hachage qui choisit un élément de l'ensemble de manière équiprobable, et que m représente le nombre de bits dans le tableau, alors la probabilité qu'un bit donné soit laissé à 0 par une fonction de hachage donnée lors de l'insertion d'un élément vaut ${\displaystyle 1-{1 \over m}}$.

Généralisons ceci à un ensemble contenant exactement k fonctions de hachage. La probabilité qu'un bit donné soit laissé à 0 par l'une des fonctions de hachage lors de l'insertion d'un élément est ${\displaystyle \left(1-{1 \over m}\right)^{k}}$.

Si l'on considère à présent que l'on insère n éléments (par exemple des chaînes de caractères, etc.), la probabilité qu'un bit donné vaille 0 vaut ${\displaystyle \left(1-{1 \over m}\right)^{kn}}$. On en déduit que la probabilité que ce bit vaille 1 est ${\displaystyle 1-\left(1-{1 \over m}\right)^{kn}}$

Ainsi, si l'on teste la probabilité de présence d'un élément qui n'est pas dans l'ensemble, chacune des m positions possède la probabilité ci-dessus de valoir 1. Si l'on suppose (et cette supposition est fausse) que ces événements sont indépendants, la probabilité que tous les k vaillent 1 (déclenchant un faux-positif) découle des calculs précédents : ${\displaystyle \left(1-\left[1-{1 \over m}\right]^{nk}\right)^{k}\approx \left(1-e^{-kn \over m}\right)^{k}}$

La formule ci-dessus suppose que la probabilité que chaque bit vaille 1 est indépendante des autres bits, ce qui est faux, et peut mener à des résultats significativement différents quand ${\displaystyle {\frac {m}{n}}}$ est élevé[3]. Au contraire, quand le rapport ${\displaystyle {\frac {m}{n}}}$ est faible, le taux d'erreur tend effectivement vers la valeur ci-dessus.

La formule exacte est plus complexe, et vaut :

${\displaystyle P={\frac {m!}{m^{k(n+1)}}}\sum _{i=1}^{m}\sum _{j=1}^{i}(-1)^{i-j}{\frac {j^{kn}i^{k}}{(m-i)!j!(i-j)!}}}$

Cette valeur peut être calculée récursivement. Cependant, il est simple d'utiliser l'encadrement suivant, donné par Bose et al. [4] :

${\displaystyle \left(1-\left[1-{1 \over m}\right]^{nk}\right)^{k}<P<\left(1-\left[1-{1 \over m}\right]^{nk}\right)^{k}\times \left(1+O\left({\frac {k}{p}}{\sqrt {\frac {\ln n-k\ln p}{m}}}\right)\right)}$

Un filtre de Bloom permet d'éviter des appels inutiles à une très grande base de données en vérifiant tout de suite l'absence d'une ligne recherchée. Le filtre n'étant pas parfait, la recherche inutile aura toutefois lieu dans certains cas, mais une grande partie sera néanmoins évitée, multipliant ainsi le nombre de requêtes utiles possibles à matériel donné. Cette méthode est utilisée par Google dans leur base de données distribuées, BigTable[5].

Les filtres de Bloom sont utilisés en bio-informatique pour la recherche rapide de motifs dans des larges jeux de données génomiques[6].

Ce type de filtre est également utilisé pour réaliser de l'inspection de paquets en profondeur[7], en vertu des raisons citées plus haut. Leur implémentation au niveau matériel a permis de réaliser de l'inspection de paquets en profondeur à la vitesse du réseau.

Elle permet aussi d'optimiser les flux entre pairs dans un réseau informatiques pair à pair (comme Gnutella, BitTorrent, Freenet, le réseau Tor, les nœuds Bitcoin, et bien d'autres)[8].

Cela permet de réduire le nombre de recherches à transmettre à un sous-ensemble suffisant de pairs voisins pour trouver par quels chemins un objet identifiable est accessible, sans avoir à les interroger tous simultanément avant d'établir de nouveaux chemins supplémentaires vers d'autres pairs, si aucun de ceux interrogés ne donnent de réponse en un temps raisonnable. En effet, la surconsommation sur le réseau global par les diverses recherches identiques effectuées en parallèle par les pairs déjà atteints, s'ils ne possèdent pas directement eux-mêmes une copie de l'objet demandé croit rapidement de façon exponentielle avec la longueur maximale des chemins de recherche (en fonction du degré moyen d'interconnexion de chacun des pairs et de la profondeur atteinte, même si chacun des nœuds traversés dispose d'un cache local lui évitant de répéter en aval la même recherche provenant de plusieurs pairs en amont).

Par exemple sur un réseau pair à pair connexe comprenant au total 100 000 nœuds, et où chacun des nœuds est interconnecté à 10 nœuds (choisis idéalement de façon aléatoire parmi les 100 000 nœuds connus), une exploration totale à une profondeur de 5 niveaux permettrait en principe d'interroger tous les nœuds du réseau si la topologie était parfaitement hypercubique de degré 10; cependant la sélection des nœuds étant aléatoire, la couverture totale du réseau ne sera pas atteinte car des nœuds seront traversés plusieurs fois, par des chemins différents (mais aussi avec des délais différents sur chaque chemin suivi, selon les profondeurs, les débits et les taux d'occupation variables de chacun des chemins suivis d'un nœud à l'autre et les délais de traitement par chacun des nœuds traversés).

Du fait que le réseau ne soit pas suffisamment couvert, le risque est alors élevé que le réseau ne soit plus fortement connexe, mais formé d'îlots devant inaccessibles entre eux (même s'il existe encore une liaison entre ces îlots, cette liaison peut être totalement saturée donc inutilisable pour éviter la formation de tels îlots). On augmente donc la profondeur d'exploration des chemins au delà de 5, et on permet également au nœuds intermédiaires de librement pouvoir augmenter localement leur degré d'interconnexion (s'ils peuvent se le permettre en fonction de leurs capacité locale) et cela accroit encore plus la redondance des requêtes identiques puisque chaque nouvelle profondeur peut potentiellement multiplier par 10 le nombre total des requêtes véhiculées sur le réseau (et de même toutes les réponses associées pouvant provenir plusieurs fois des mêmes nœuds finaux disposant de l'objet cherché).

Cette croissance exponentielle de recouvrement des chemins aléatoire, si elle reste incontrôlée, conduit fatalement à la saturation des liaisons individuelles, notamment au plus près du nœud initiateur de la recherche et des rares nœuds du réseau qui peuvent y répondre (également au cas où certains nœuds ne sont plus accessibles que par un seul chemin critique ou une poignée insuffisante de chemins) ; au cas où aucun des nœuds du réseau ne dispose de l'objet recherché, la totalité des nœuds réseau sera intensivement recherché plusieurs fois par tous les chemins possibles (y compris le nœud initiateur de la recherche initiale si le chemin suivi par une recherche relayée en amont n'est pas transmis en aval par les nœuds intermédiaires). Le réseau pair à pair devient alors très inefficace, il se sature très vite en totalité. Il faut donc modérer le degré de propagation des recherches en aval, quitte à introduire des délais en utilisant des priorités, et utiliser une mise en cache avec une durée raisonnable mais suffisante, sans saturer non plus le cache local de chaque nœud avec les requêtes déjà transmises en amont et les réponses déjà retournées en aval).

Il faut donc disposer d'une heuristique permettant de calculer de façon probabiliste et réduire les recouvrements de chemins, tout en conservant la possibilité de parcourir une partie suffisante du réseau connexe. Un filtre Bloom permet de définir cette probabilité suffisante pour éliminer une grande quantité des requêtes redondantes, qu'il n'est alors pas utile de transmettre en aval aux nœuds voisins, en tenant compte au niveau de chaque nœud intermédiaire des réponses positives ou négatives déjà obtenues sur chaque chemin déjà interrogé en aval, mais aussi d'éliminer les réponses identiques déjà renvoyées en aval au demandeur mais qui pourraient arriver depuis les chemins en amont déjà interrogés. Et cela ne demande aucune connaissance préalable de la topologie effective du réseau pair à pair (d'autant plus si ces nœuds peuvent se connecter ou se déconnecter librement du réseau, et que donc cette topologie est fluctuante).

De plus le nombre de nœuds participant au réseau n'est pas nécessairement connu au départ et peut fluctuer au cours du temps : le réseau dispose aussi d'un protocole de découverte, qui lui aussi va utiliser des annonces récursives de propagation des nœuds actuellement connectés et actifs et d'une indication de leur dernière date connue d'activité, afin que cela soit mis en cache et répercuté aux autres nœuds qui pourront alors tenter d'y établir une liaison, s'ils souhaitent augmenter leur degré d'interconnexion. Ce protocole adjoint au réseau pair à pair est ce qui assure de conserver le réseau fortement connexe (sans formation d'îlots, et encore moins facilement de vastes continents longtemps séparés), mais lui aussi bénéficie d'un filtre de Bloom pour qu'il reste efficace. Mais il dépend aussi de la synchronisation des horloges entre les nœuds ou de pouvoir mesurer leurs écarts, faute de quoi la pertinence de la datation des noeuds découverts et réputés actifs serait compromise et pourrait même amener à des perturbations massives et très indésirables : cela permettrait des attaques distribuées de déni de service (DDoS) vers des nœuds ne participant pas du tout au protocole de découverte, ni même au réseau pair à pair lui-même, et vite conduire soit au bannissement du protocole pair à pair sur une partie significative de l'Internet ou de ses points d'accès publics, ou à une forte dégradation des débits autorisés sur chaque liaison d'un nœud à l'autre.

La même problématique survient sur des topologies de réseau pair à pair pour les systèmes de réplication et d'annonce, notamment au sein des protocoles d'annonce de routage entre réseaux IP (avec des pairs, les routeurs, fortement hétérogènes selon leurs capacité de traitement ou de mise en cache, leur degré local d'interconnexion et les débits utilisables sur chacune de leurs liaison d'interconnexion), ou encore pour la réplication et la mise en cache des requêtes de résolution DNS (et la vérification de leur authenticité). Sur Internet, il existe généralement un noyau relativement stable d'interconnexions au sein du réseau, entre des nœuds à forte capacité de traitement et de mise en cache local (disposant entre eux de liaisons très rapides et avec un degré d'interconnexion plus élevé que le reste du réseau), mais cette optimisation avec des filtres de Bloom évite là encore la saturation de ces nœuds fortement sollicités et de leurs liaisons, qui malgré tout peuvent connaitre des variations, du fait de pannes intermittentes sur les nœuds ou leurs liaisons, ou des besoins réguliers de maintenance locale de ces systèmes.

Ce filtre est utilisé dans les moteurs de rendu HTML pour augmenter les performances des sélecteurs CSS[9].