Filtre Bloom en Java avec Guava

Bonne journée à tous.

Nous avons lancé un nouveau cours - "Algorithmes pour les développeurs" , conçu pour ceux qui souhaitent améliorer leurs connaissances des différentes structures et algorithmes de traitement des données, résoudre les problèmes algébriques et les problèmes de programmation dynamique pour différents langages. Aujourd'hui, nous partageons donc une petite note sur le fonctionnement du filtre Bloom en Java.

Présentation

Dans cet article, nous examinerons la structure du filtre Bloom de la bibliothèque Guava. Le filtre Bloom est une structure de données probabiliste avec une utilisation efficace de la mémoire que nous pouvons utiliser pour répondre à la question «Cet élément est-il dans l'ensemble?».

Il n'y a pas de faux négatifs dans le filtre Bloom, donc s'il renvoie faux, vous pouvez être sûr à 100% que cet élément n'est pas dans l'ensemble.

Cependant, le filtre Bloom peut renvoyer des faux positifs , donc lorsque true est renvoyé, la probabilité est élevée que l'élément soit vraiment dans l'ensemble, mais la probabilité n'est pas de 100%.

Pour en savoir plus sur le fonctionnement du filtre Bloom, consultez ce guide.



Dépendance Maven

Nous utiliserons l'implémentation Guava du filtre Bloom, alors ajoutez une dépendance Guava
La dernière version peut être trouvée dans Maven Central .

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency> 

Pourquoi utiliser un filtre bloom?

Le filtre Bloom est conçu pour être économique et rapide . En l'utilisant, nous pouvons clarifier la probabilité de réponses faussement positives que nous sommes prêts à accepter et, conformément à la configuration, le filtre Bloom prendra le moins de mémoire possible.

En raison de son économie, le filtre Bloom tient facilement en mémoire même avec un grand nombre d'éléments. Certaines bases de données, notamment Cassandra et Oracle, utilisent ce filtre pour les vérifications initiales avant d'accéder au disque ou au cache, par exemple lorsqu'une demande d'ID spécifique est reçue.

Si le filtre indique qu'il n'y a pas d'ID, la base de données peut cesser de traiter la demande et retourner au client. Sinon, la requête va sur le disque et renvoie l'élément trouvé.

Création d'un filtre Bloom

Supposons que nous voulons créer un filtre Bloom pour pas plus de 500 entiers et que nous soyons triplés par une probabilité de faux positifs de un pour cent (0,01).

Pour ce faire, nous pouvons utiliser la classe BloomFilter de la bibliothèque Guava. Il est nécessaire de transférer le nombre d'éléments rapportés au filtre, et la probabilité souhaitée de faux positifs:

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

Ajoutez maintenant quelques chiffres au filtre:

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

Nous n'avons ajouté que trois éléments et déterminé le nombre maximum d'inserts - 500, donc notre filtre Bloom devrait donner des résultats assez précis. Testez-le avec 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% que cet élément est vraiment dans le filtre si la méthode retourne true.

Dans notre cas, lorsque mightContain() renvoie true, 99% que l'élément est dans le filtre et 1%, que le résultat est faux positif. Si le filtre renvoie false, vous pouvez être sûr à 100% que l'élément est manquant.

Filtre Bloom sursaturé

Lors de la conception d'un filtre Bloom, il est important de fournir une valeur suffisamment précise pour le nombre attendu d'éléments. Sinon, notre filtre retournera les faux positifs beaucoup plus souvent que nous le souhaiterions. Prenons un exemple.

Supposons que nous créons un filtre avec la probabilité souhaitée de faux positifs égale à un pour cent et le nombre attendu d'éléments égal à cinq, mais ensuite nous insérons 100 000 éléments:

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

Attendant si peu d'éléments, le filtre prendra très peu de mémoire.
Cependant, après avoir ajouté un nombre beaucoup plus important d'éléments, le filtre devient sursaturé et a une probabilité plus élevée de produire un résultat faussement positif que le pour cent souhaité.

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

Conclusion

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

L'implémentation de tous ces exemples et extraits de code peut être trouvée dans le projet GitHub .

Il s'agit d'un projet Maven, donc l'importation et le lancement ne devraient pas être difficiles.

LA FIN

Nous attendons des commentaires et des questions qui, comme toujours, peuvent être laissés ici et aller à la journée portes ouvertes au professeur Mikhail Gorshkov .