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.
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 = 'https://jaychen.cc'
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 :
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 :
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
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 :
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é.
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
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 :
error_rate
:允许布隆过滤器的错误率,这个值越低过滤器的位数组的大小越大,占用空间也就越大。initial_size
:布隆过滤器可以储存的元素个数,当实际存储的元素个数超过这个值之后,过滤器的准确率会下降。redis 中有一个命令可以来设置这两个值:
bf.reserve urls 0.01 100
三个参数的含义:
error_rate
的值。initial_size
的值。使用这个命令要注意一点:执行这个命令之前过滤器的名字应该不存在,如果执行之前就存在会报错:(error) ERR item exists
更多编程相关知识,请访问:编程入门!!
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!