Qu'est-ce qu'un filtre bloom ? Comment l'utiliser dans Redis ?-Redis-php.cn

Qu'est-ce qu'un filtre bloom ? Comment l'utiliser dans Redis ?

青灯夜游

Libérer： 2021-08-18 10:08:31

avant

3901 Les gens l'ont consulté

Le filtre Bloom est une structure de données magique. Cet article vous donnera une compréhension approfondie du filtre Bloom et présentera la méthode d'utilisation du filtre Bloom dans Redis.

Qu'est-ce qu'un filtre bloom ? Comment l'utiliser dans Redis ?

Qu'est-ce que le "filtre Bloom"

Le filtre Bloom est une structure de données magique, peut être utilisé pour déterminer si un l'élément est dans un ensemble . Une fonction très couramment utilisée consiste à supprimer les doublons. Une exigence courante parmi les robots d'exploration : il existe des milliers d'URL de sites Web cibles. Comment déterminer si un robot d'exploration a favorisé une certaine URL ? Pour faire simple, chaque fois que le robot collecte une URL, il peut stocker l'URL dans la base de données. Chaque fois qu'une nouvelle URL apparaît, accédez à la base de données pour demander si elle a été visitée. [Recommandations associées : Tutoriel vidéo Redis]

select id from table where url = &#39;https://jaychen.cc&#39;

Copier après la connexion

Mais à mesure que le robot explore de plus en plus d'URL, la base de données doit être accédée une fois avant chaque requête, et pour ce type d'efficacité des requêtes SQL de chaîne n'est pas élevé. En plus de la base de données, l'utilisation de la structure définie de Redis peut également répondre à cette exigence, et ses performances sont meilleures que celles de la base de données. Mais Redis a aussi un problème : il consomme trop de mémoire. A ce moment, le filtre Bloom apparaît très horizontalement : Laissez-moi répondre à cette question.

Par rapport aux bases de données et à Redis, l'utilisation des filtres Bloom peut efficacement éviter les problèmes de performances et d'utilisation de la mémoire.

Le filtre Bloom est essentiellement un tableau de bits. Un tableau de bits signifie que chaque élément du tableau n'occupe qu'un seul bit. Chaque élément ne peut être que 0 ou 1. De cette façon, demander un tableau de bits de 10 000 éléments ne prend que 10 000/8 = 1 250 B d'espace. En plus d'un tableau de bits, le filtre Bloom possède également des fonctions de hachage K. Lorsqu'un élément est ajouté au filtre Bloom, les opérations suivantes seront effectuées :

Utilisez K fonctions de hachage pour effectuer K calculs sur la valeur de l'élément afin d'obtenir K valeurs de hachage.
En fonction de la valeur de hachage obtenue, définissez la valeur d'indice correspondante sur 1 dans le tableau de bits.

Par exemple, supposons que le filtre Bloom ait 3 fonctions de hachage : f1, f2, f3 et un tableau de bits arr. Nous devons maintenant insérer https://jaychen.cc dans le filtre bloom :

Hachez la valeur trois fois pour obtenir trois valeurs n1, n2, n3.
Réglez les trois éléments arr[n1], arr[n2], arr[3] dans le tableau de bits sur 1.

Lorsque vous souhaitez déterminer si une valeur se trouve dans le filtre Bloom, effectuez à nouveau un calcul de hachage sur l'élément. Après avoir obtenu la valeur, déterminez si chaque élément du tableau de bits est 1. Si le. les valeurs sont toutes 1, alors cela signifie que cette valeur est dans le filtre Bloom. S'il y a une valeur qui n'est pas 1, cela signifie que l'élément n'est pas dans le filtre Bloom.

Si vous ne comprenez pas le texte, regardez l'explication de la photo du peintre d'âme ci-dessous

Quest-ce quun filtre bloom ? Comment lutiliser dans Redis ?

Après avoir lu ce qui précède explication, vous rencontrerez certainement un problème : lorsque plus d'éléments sont insérés, plus de positions dans le tableau de bits sont définies sur 1. Lorsqu'un élément n'est pas dans le filtre Bloom, après le calcul de hachage, la valeur obtenue est interrogée dans le filtre Bloom. tableau de bits. Il y a Peut-être que ces emplacements sont également définis sur 1. Un tel objet qui n'existe pas dans le filtre Bloom peut également être considéré à tort comme étant dans le filtre Bloom. Mais si le filtre Bloom détermine qu'un élément n'est pas dans le filtre Bloom, alors cette valeur ne doit pas être dans le filtre Bloom. Pour faire simple :

Si le filtre Bloom indique qu'un certain élément est présent, il peut être mal jugé.
Le filtre Bloom dit qu'un élément n'est pas là, alors il ne doit pas être là.

Le défaut de ce filtre Bloom est lié aux exigences du robot d'exploration ci-dessus. Il peut y avoir des URL non visitées qui peuvent être considérées à tort comme visitées, mais si ce sont des URL visitées, elles le seront certainement. ne pas être jugé à tort comme non visité.

Filtre Bloom dans Redis

redis a ajouté la fonction de module dans la version 4.0. Le filtre Bloom peut être ajouté à Redis sous forme de module. Ainsi, en utilisant Redis 4.0 ou supérieur, vous pouvez utiliser le filtre bloom dans Redis en chargeant le module. Mais ce n'est pas le moyen le plus simple. Vous pouvez utiliser Docker pour expérimenter les filtres Bloom directement dans Redis.

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli

Copier après la connexion

le filtre redis Bloom a principalement deux commandes :

bf.add Ajouter des éléments au filtre Bloom : bf.add urls https://jaychen.cc.
bf.exists Déterminer si un élément est dans le filtre : bf.exists urls https://jaychen.cc.

Comme mentionné ci-dessus, il existe des erreurs de jugement dans les filtres Bloom. Il y a deux valeurs dans Redis qui déterminent la précision des filtres Bloom :