Filtre Bloom en Java avec Guava

1. Vue d'ensemble

Dans cet article, nous examinerons la construction du filtre Bloom de la bibliothèque Guava . Un filtre Bloom est une structure de données probabiliste efficace en mémoire que nous pouvons utiliser pour répondre à la question de savoir si un élément donné fait partie d'un ensemble .

Il n'y a pas de faux négatifs avec un filtre Bloom, donc quand il renvoie faux , nous pouvons être sûrs à 100% que l'élément n'est pas dans l'ensemble.

Cependant, un filtre Bloom peut renvoyer des faux positifs , donc quand il renvoie vrai , il y a une forte probabilité que l'élément soit dans l'ensemble, mais nous ne pouvons pas être sûrs à 100%.

Pour une analyse plus approfondie du fonctionnement d'un filtre Bloom, vous pouvez suivre ce tutoriel.

2. Dépendance de Maven

Nous utiliserons l'implémentation du filtre Bloom par Guava, ajoutons donc la dépendance goyave :

 com.google.guava guava 29.0-jre 

La dernière version est disponible sur Maven Central.

3. Pourquoi utiliser le filtre Bloom?

Le filtre Bloom est conçu pour être rapide et peu encombrant . Lors de son utilisation, nous pouvons spécifier la probabilité de réponses faussement positives que nous pouvons accepter et, selon cette configuration, le filtre Bloom occupera le moins de mémoire possible.

En raison de cette efficacité d'espace, le filtre Bloom s'intégrera facilement en mémoire, même pour un grand nombre d'éléments. Certaines bases de données, notamment Cassandra et Oracle, utilisent ce filtre comme première vérification avant d'aller sur le disque ou dans le cache, par exemple, lorsqu'une demande pour un ID spécifique arrive.

Si le filtre renvoie que l'ID n'est pas présent, la base de données peut arrêter le traitement ultérieur de la demande et revenir au client. Sinon, il va sur le disque et renvoie l'élément s'il se trouve sur le disque.

4. Création d'un filtre Bloom

Supposons que nous voulions créer un filtre Bloom pour jusqu'à 500 entiers et que nous puissions tolérer une probabilité de un pour cent (0,01) de faux positifs.

Nous pouvons utiliser la classe BloomFilter de la bibliothèque Guava pour y parvenir. Nous devons transmettre le nombre d'éléments que nous espérons insérer dans le filtre et la probabilité de faux positifs souhaitée:

BloomFilter filter = BloomFilter.create( Funnels.integerFunnel(), 500, 0.01);

Ajoutons maintenant quelques chiffres au filtre:

filter.put(1); filter.put(2); filter.put(3);

Nous n'avons ajouté que trois éléments et nous avons défini que le nombre maximum d'insertions sera de 500, donc notre filtre Bloom devrait donner des résultats très précis . Testons- le en utilisant la méthode mightContain () :

assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(100)).isFalse();

Comme son nom l'indique, nous ne pouvons pas être sûrs à 100% qu'un élément donné est réellement dans le filtre lorsque la méthode renvoie true .

Lorsque mightContain () renvoie true dans notre exemple, nous pouvons être sûrs à 99% que l'élément est dans le filtre, et il y a une probabilité d'un pour cent que le résultat soit un faux positif. Lorsque le filtre renvoie false , nous pouvons être sûrs à 100% que l'élément n'est pas présent.

5. Filtre Bloom sursaturé

Lorsque nous concevons notre filtre Bloom, il est important que nous fournissions une valeur raisonnablement précise pour le nombre d'éléments attendu . Sinon, notre filtre renverra des faux positifs à un taux beaucoup plus élevé que souhaité. Voyons un exemple.

Supposons que nous ayons créé un filtre avec une probabilité de faux positifs souhaitée de un pour cent et des éléments attendus égal à cinq, mais nous avons ensuite inséré 100000 éléments:

BloomFilter filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put); 

Le nombre d'éléments attendu étant si petit, le filtre occupera très peu de mémoire.

Cependant, à mesure que nous ajoutons plus d'éléments que prévu, le filtre devient sursaturé et a une probabilité beaucoup plus élevée de renvoyer des résultats faussement positifs que le pourcentage souhaité:

assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(1_000_000)).isTrue();

Notez que la méthode mightContatin () a renvoyé true même pour une valeur que nous n'avons pas insérée précédemment dans le filtre.

6. Conclusion

Dans ce rapide tutoriel, nous avons examiné la nature probabiliste de la structure de données du filtre Bloom - en utilisant l' implémentation de Guava .

Vous pouvez trouver l'implémentation de tous ces exemples et extraits de code dans le projet GitHub.

Il s'agit d'un projet Maven, il devrait donc être facile à importer et à exécuter tel quel.