Comment éviter la pénétration du cache ? L'article suivant vous fera découvrir le Bloom Filter (Bloom Filter), un outil puissant de Redis pour éviter la pénétration du cache. J'espère qu'il vous sera utile !
Présentation
Le filtre Bloom (Bloom Filter) est une structure de données proposée par Burton Howard Bloom en 1970. Il s'agit en fait d'un long vecteur binaire et d'une série de fonctions de cartographie aléatoire. [Recommandations associées : Tutoriel vidéo Redis] Bloom Filter）是一个数据结构，由布隆（Burton Howard Bloom）于 1970 年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。【相关推荐：Redis视频教程】
布隆过滤器可以用于高效的检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远优于一般的算法，缺点是有一定的误识别率，而且难以删除（一般不支持，需要额外的实现）。
误识率指的是可以判断元素肯定不在集合中，判断元素可能在集合中，无法判断元素一定在集合中。
布隆过滤器之所以高效，因为它是一个概率数据结构，它能确认元素肯定不在集合中，或者元素可能在集合中。之所以说是可能，是因为它有一定的误识别率，使得无法 100% 确定元素一定在集合中。
问题引出
在日常工作中，有一个比较常见的需求，就是需要判断一个元素是否在集合中。例如以下场景
- 给定一个IP黑名单库，检查指定IP是否在黑名单中？
- 在接收邮件的时候，判断一个邮箱地址是否为垃圾邮件？
- 在文字处理软件中，检查一个英文单词是否拼写正确？
遇到这种问题，通常直觉会告诉我们，应该使用集合这种数据结构来实现。例如，先将 IP 黑名单库的所有 IP 全部存储到一个集合中，然后再拿指定的 IP 到该集合中检查是否存在，如果存在则说明该 IP 命中黑名单。
通过一段代码来模拟 IP 黑名单库的存储和检查。
public class IPBlackList {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("192.168.1.1");
set.add("192.168.1.2");
set.add("192.168.1.4");
System.out.println(set.contains("192.168.1.1"));
System.out.println(set.contains("192.168.1.2"));
System.out.println(set.contains("192.168.1.3"));
System.out.println(set.contains("192.168.1.4"));
}
}Copier après la connexion
集合的内部，通常是使用散列表来实现。其优点是查询非常高效，缺点是比较耗费存储空间。
一般在数据量比较小的时候，我们会使用集合来进行存储。以空间换时间，在占用空间较小的情况下，同时又能提高查询效率。
但是，当存储的数据量比较大的时候，耗费大量空间将会成为问题。因为这些数据通常会存储到进程内存中，以加快查询效率。而机器的内存通常都是有限的，要尽可能高效的使用。
另一方面，散列表在空间和效率上是需要做平衡的。存储相同数量的元素，如果散列表容量越小，出现冲突的概率就越高，用于解决冲突的时间将会花费更多，从而影响性能。
而布隆过滤器（Bloom Filter）的产生，能够很好的解决这个问题。一方面能够以更少的内存来存储数据，另一方面能够实现非常高效的查询性能。
基本原理
添加元素
当添加一个元素到集合中时，通过 K 个散列函数分别作用于元素，生成 K 个值作为下标，并对向量的相应位设置为 1。
检查元素
如果要检查一个元素是否存在集合中，用同样的散列方法，生成 K 个下标，并检查向量的相应位是否全部是 1。
如果全为 1，则该元素很可能在集合中；否则（只要有1个或以上的位为0），该元素肯定不在集合中。
Demo
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|0|||||||||||||||||||
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|||||||||
再添加一个字符串 b
Filtre Bloom Peut être utilisé pour récupérer efficacement si un élément se trouve dans une collection. Son avantage est que l'efficacité spatiale et le temps de requête sont bien meilleurs que les algorithmes ordinaires. Son inconvénient est qu'il a un certain taux de mauvaise reconnaissance et est difficile à supprimer (généralement non pris en charge et nécessite une implémentation supplémentaire).
Le taux d'erreur signifie qu'on peut juger que l'élément n'est définitivement pas dans l'ensemble, on peut juger que l'élément peut être dans l'ensemble, mais on ne peut pas juger que l'élément doit être dans l'ensemble.
Le filtre Bloom est efficace car c'est une structure de données probabiliste qui confirme qu'un élément n'est définitivement pas dans l'ensemble, ou que l'élément est probablement dans l'ensemble. La raison pour laquelle cela est possible est qu'il y a un certain taux de mauvaise reconnaissance, ce qui rend impossible d'être sûr à 100 % que l'élément doit être dans l'ensemble. 🎜
Question 🎜🎜Dans le travail quotidien, il existe un besoin courant de déterminer si un élément fait partie d'un ensemble. Par exemple, le scénario suivant🎜- Étant donné une base de données de liste noire d'adresses IP, vérifier si l'adresse IP spécifiée figure dans la liste noire ? 🎜
- Lors de la réception d'e-mails, comment déterminer si une adresse e-mail est du spam ? 🎜
- Dans un logiciel de traitement de texte, vérifier si un mot anglais est correctement orthographié ? 🎜🎜🎜Lorsque nous rencontrons ce genre de problème, notre intuition nous dit généralement que nous devons utiliser une structure de données telle qu'un ensemble pour l'implémenter. Par exemple, stockez d'abord toutes les adresses IP de la base de données de la liste noire IP dans un ensemble, puis vérifiez si l'adresse IP spécifiée existe dans l'ensemble. Si elle existe, cela signifie que l'adresse IP figure sur la liste noire. 🎜🎜Simulez le stockage et la vérification de la bibliothèque de listes noires IP via un morceau de code. 🎜
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>Copier après la connexion
Copier après la connexion
Bloom Filter) peut très bien résoudre ce problème. D'une part, il peut stocker des données avec moins de mémoire et, d'autre part, il peut atteindre des performances de requête très efficaces. 🎜Principe de base🎜- 🎜Tout d'abord, créez un vecteur binaire et définissez tous les bits sur 0🎜 🎜< li>🎜Ensuite, K fonctions de hachage sont sélectionnées pour hacher les éléments K fois et calculer l'indice binaire du vecteur. 🎜🎜🎜
Ajouter un élément
🎜Lors de l'ajout d'un élément à l'ensemble, des fonctions de hachage K sont appliquées respectivement aux éléments pour générer des valeurs K. sont utilisés comme index et les bits correspondants du vecteur sont mis à 1. 🎜Vérification d'un élément
🎜Si vous souhaitez vérifier si un élément existe dans l'ensemble, utilisez la même méthode de hachage pour générer K indices, Et vérifiez si les bits correspondants du vecteur sont tous des 1. 🎜🎜Si tous valent 1, l'élément est probablement dans l'ensemble ; sinon (tant qu'un ou plusieurs bits sont 0), l'élément n'est certainement pas dans l'ensemble. 🎜Démo🎜- 🎜Supposons qu'il y ait un filtre Bloom d'une capacité de 15 bits et 2 hachages utilisés fonctionner comme indiqué ci-dessous. 🎜🎜🎜🎜|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|0||||||||||||||||🎜
- 🎜Ajouter une chaîne
a< /code> , deux temps de hachage ont abouti aux indices 4 et 10, et les bits correspondant à 4 et 10 ont été marqués de 0 à 1. 🎜🎜🎜🎜|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1|||||1||||||||🎜<ul style="list-style-type: disc;"><li>🎜Ajoutez une autre chaîne <code> b</code >, haché deux fois pour obtenir l'indice 11, et marque le bit correspondant à 11 de 0 à 1. 🎜🎜🎜🎜|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|1|||||||🎜<ul style="list-style-type: disc;"><li><p>Ajoutez une autre chaîne <code>c, hachez deux fois pour obtenir les indices 11 et 12 et marquez les bits correspondants de 0 à 1. c，2 次哈希得到下标为 11 和 12，将对应的位由 0 标记为 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|1|1|||||||
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|1||||1|||1|||1|1|1|||||||
上面，我们添加了 4 个字符串，每个字符串分别进行 2 次哈希，对应的2个位标记为1，最终被标记为1的共有6位而不是8位。
这说明，不同的元素，哈希后得到的位置是可能出现重叠的。如果元素越多，出现重叠的概率会更高。如果有2个元素出现重叠的位置，我们是无法判断任一元素一定在集合中的。
如果要检查一下元素是否存在集合中，只需要以相同的方法，进行 2 次哈希，将得到的 2 个下标在布隆过滤器中的相应位进行查找。如果对应的 2 位不是全部为1，则该元素肯定不在集合中。如果对应的 2 位全部为1，则说明该元素可能在集合中，也可能不存在。
例如，检查字符串 b 是否存在集合中，哈希得到的 2 个下标都为11。检查发现，11对应的位为1。但是，这并不能说明 b 一定在集合中。这是因为，字符串 c 哈希后的下标也包含11，有可能只是字符串c在集合中，而 b 却不存在，这就是造成了误识别，也称为假阳性。
再检查字符串 foo，哈希得到的下标分别为 8 和 13，对应的位都为0。因此，字符串 foo 肯定不在集合中。
数学原理
布隆过滤器背后的数学原理是
两个完全随机的数字相冲突的概率很小，因此可以在很小的误识别率条件下，用很少的空间存储大量信息。
误识别率
误识别率（FPP，false positive probabilistic）的计算如下。
假设布隆过滤器大小为 m 比特，存储了 n 个元素，使用 k 次散列函数来计算元素的存储位置。
- 添加 1 个元素，则任一比特为 1 的概率为
1/m，任一比特为 0 的概率为 1-1/m； - 添加 1 个元素，执行 k 次散列之后，则任一比特为 0 的概率为
(1-1/m)^k，任一比特为 1 的概率为 1-(1-1/m)^k； - 如果添加 n 个元素，那么任一比特为 0 的概率为
(1-1/m)^kn，任一比特为 1 的概率为 1-(1-1/m)^kn； - 如果将 1 个新的元素，添加到已存在
n 个元素的布隆过滤器中，则任一比特已经为 1 的概率与上面相同，概率为 1-(1-1/m)^kn。因此，k 个比特都为1的概率为：(1-(1-1/m)^kn)^k，此即为新插入元素的误识别率。
当 n 值比较大时，$(1-(1-1/m)^{kn})^k$ 约等于 $(1-e^{-kn/m})^k$
假定布隆过滤器大小 m 为 16 比特，k为 8，存储元素 n 为1，那么误识别（假阳性）的概率是万分之五（5/10000）。
此时，m/n=16，事实上这表示 1个元素使用 16 个比特的空间来存储。
因此，当 k 相同时，m/n 为 16/1、32/2、64/4 等值时具有相同的误识别率。
网站 Bloom Filters - the math 给出了布隆过滤器的误识别率表，可以很方便的查处不同 m，n，k
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1|||||1|1|1||||||- Enfin, ajoutez une chaîne
sam et hachez-la deux fois pour obtenir l'indice : 0 et 7, marquez le bit correspondant de 0 à 1. - |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|1||||1|||1|||1|1|1||||||Ci-dessus, nous avons ajouté 4 chaînes, chaque chaîne hachée 2 fois, correspondant à 2 bits marqués comme 1, et un total de 6 bits sont finalement marqués à 1 au lieu de 8 bits.
Cela montre que les positions obtenues en hachant différents éléments peuvent se chevaucher. Plus il y a d’éléments, plus la probabilité de chevauchement est élevée. S’il y a deux éléments dans des positions qui se chevauchent, nous ne pouvons pas juger si l’un ou l’autre élément doit être dans l’ensemble. Si vous souhaitez vérifier si un élément existe dans l'ensemble, il vous suffit de le hacher deux fois de la même manière, et de rechercher dans les bits correspondants dans le filtre Bloom les deux indices obtenus. Si les 2 bits correspondants ne sont pas tous à 1, alors l'élément n'est définitivement pas dans l'ensemble. Si les 2 bits correspondants sont tous à 1, cela signifie que l'élément peut être dans l'ensemble ou qu'il n'existe pas.
Par exemple, lors de la vérification si la chaîne b existe dans l'ensemble, les deux indices obtenus par hachage sont tous deux 11. Vérifiez et trouvez que le bit correspondant à 11 est 1. Cependant, cela ne signifie pas que b doit être dans la collection. En effet, l'indice haché de la chaîne c contient également 11. Il est possible que la chaîne c soit dans l'ensemble, mais b n'existe pas. C'est la raison. Erreur d'identification, également appelée faux positif. Vérifiez à nouveau la chaîne foo, les indices obtenus par hachage sont respectivement 8 et 13, et les bits correspondants sont tous 0. Par conséquent, la chaîne foo n'est définitivement pas dans l'ensemble. Principe mathématique
Le principe mathématique derrière le filtre Bloom est
La probabilité que deux nombres complètement aléatoires entrent en collision est très faible, elle peut donc être détectée de manière très petit Dans des conditions de faible taux de fausse reconnaissance, une petite quantité d'espace est utilisée pour stocker une grande quantité d'informations.
Taux de mauvaise reconnaissance 🎜🎜Le taux de mauvaise reconnaissance (FPP, faux positifs probabilistes) est calculé comme suit. 🎜🎜Supposons que la taille du filtre bloom est de m bits et stocke n éléments. Utilisez les fonctions de hachage k pour calculer l'emplacement de stockage des éléments. 🎜🎜Ajoutez 1 élément, alors la probabilité qu'un bit soit 1 est 1/m, et la probabilité que n'importe quel bit soit 0 est 1-1/m ;🎜🎜Ajoutez 1 élément et effectuez k hachages, alors la probabilité qu'un bit soit 0 est (1-1/m)^k, et la probabilité que n'importe quel bit soit 1 est 1 -(1-1/m)^k; 🎜🎜Si n éléments sont ajoutés, la probabilité qu'un bit soit 0 est (1-1/m)^kn</code >, la probabilité que n'importe quel bit est 1 est <code>1-(1-1/m)^kn 🎜🎜Si un nouvel élément est ajouté au n</code > existant dans un filtre Bloom avec des éléments , la probabilité qu'un bit soit déjà 1 est la même que ci-dessus, et la probabilité est <code>1-(1-1/m)^kn. Par conséquent, la probabilité que tous les k bits soient 1 est : (1-(1-1/m)^kn)^k, qui est le taux de mauvaise reconnaissance des éléments nouvellement insérés. 🎜🎜🎜🎜Lorsque la valeur n est relativement grande, $(1-(1-1/m)^{kn})^k$ est approximativement égal à $(1-e ^{- kn/m})^k$🎜🎜🎜Supposons que la taille du filtre Bloom m est de 16 bits, k est de 8 et l'élément de stockage n</ code> est 1, Alors la probabilité d'une erreur d'identification (faux positif) est de cinq sur dix mille (5/10 000). 🎜🎜À l'heure actuelle, <code>m/n=16, en fait, cela signifie qu'1 élément utilise 16 bits d'espace pour stocker. 🎜🎜Par conséquent, lorsque k est le même, m/n a le même taux de mauvaise reconnaissance lorsqu'il est 16/1, 32/2, 64/4, etc. 🎜🎜Site WebFiltres Bloom - le calcul donne le tableau des taux de fausses reconnaissances du filtre Bloom, qui peut facilement vérifier et traiter différents m, n, k</ code> Taux de fausses reconnaissances à une valeur donnée. 🎜🎜Pour résoudre le taux de fausse reconnaissance🎜🎜Les méthodes courantes pour résoudre le taux de fausse reconnaissance incluent 🎜🎜🎜🎜Liste blanche🎜🎜🎜🎜Confirmation de retour en arrière🎜🎜🎜🎜🎜Liste blanche🎜🎜🎜Une méthode courante pour résoudre le taux de fausse reconnaissance consiste à construire une plus petite Une petite liste blanche est utilisée pour stocker des données qui peuvent être mal identifiées. 🎜🎜Prenons l'exemple du filtrage anti-spam. Supposons que nous disposions d'une bibliothèque de spam qui filtre le spam lors de la réception d'e-mails. 🎜🎜À l'heure actuelle, vous pouvez d'abord stocker cette bibliothèque de spam dans le filtre Bloom. Lorsque vous recevez des e-mails, vous pouvez d'abord filtrer efficacement la plupart des e-mails normaux via le filtre Bloom. 🎜🎜Pour un petit nombre de courriers indésirables (éventuellement), certains d'entre eux peuvent être des e-mails normaux. 🎜<p>再创建一个白名单库，当在布隆过滤器中判断可能为垃圾邮件时，通过查询白名单来确认是否为正常邮件。</p><p>对于没在白名单中的邮件，默认会被移动到垃圾箱。通过人工识别的方式，当发现垃圾箱中存在正常邮件的时候，将其移入白名单。</p><h3 data-id="heading-11"><strong>回源确认</strong></h3><p>很多时候，使用布隆过滤器是为了低成本，高效率的拦截掉大量数据不在集合中的场景。例如</p><ul><li>Google Bigtable，Apache HBase以及Apache Cassandra和PostgreSQL 使用 Bloom 过滤器来减少对不存在的行或列的磁盘查找。避免进行昂贵的磁盘查找，可大大提高数据库查询操作的性能。</li><li>在谷歌浏览器用于使用布隆过滤器来识别恶意URL的网页浏览器。首先会针对本地 Bloom 过滤器检查所有 URL，只有在 Bloom 过滤器返回肯定结果的情况下，才对执行的 URL 进行全面检查（如果该结果也返回肯定结果，则用户会发出警告）。</li><li>拦截掉大量非IP黑名单请求，对于少量可能在黑名单中的IP，再查询一次黑名单库。</li></ul><p><strong>这是布隆过滤器非常典型的应用场景，先过滤掉大部分请求，然后只处理少量不明确的请求。</strong></p><p><strong>这个方法，和白名单库的区别是，不需要再另外建立一套库来处理，而是使用本来就已经存在的数据和逻辑。</strong></p><p>例如 Google Bigtable 查询数据行本来就是需要查的，只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的，同样是先使用布隆过滤器来拦截掉大部分IP。</p><p>而上面垃圾邮件的处理，对于可能为垃圾邮件的情况，不是通过完整的垃圾邮件库再查询一次进行确认，而是用增加白名单来进行判断的方式。因为通常来说，白名单库会更小，便于缓存。</p><p>这里所说的回源，实际上是对可能被误识别的请求，最后要回到数据源头或逻辑确认一次。</p><h2 data-id="heading-12">Guava中的布隆容器的实现</h2><p>Guava 中就提供了一种 Bloom Filter 的实现。</p><h3 data-id="heading-13"><strong>guava包引入</strong></h3><p>要使用 Bloom Filter，需要引入 guava 包</p><div class="code" style="position:relative; padding:0px; margin:0px;"><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:js;toolbar:false;"><dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency></pre><div class="contentsignin">Copier après la connexion</div></div><div class="contentsignin">Copier après la connexion</div></div><h3 data-id="heading-14"><strong>误判率测试</strong></h3><p>下面对布隆容器的误判率进行测试，分2步</p><ul style="list-style-type: disc;"><li><p>往过滤器中放一百万个数，然后去验证这一百万个数是否能通过过滤器</p></li><li><p>另外找一万个数，去检验漏网之鱼的数量</p></li></ul><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:js;toolbar:false;">/**
* 测试布隆过滤器(可用于redis缓存穿透)
*
* @author 敖丙
*/
public class TestBloomFilter {
private static int total = 1000000;
private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
// private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001);
public static void main(String[] args) {
// 初始化1000000条数据到过滤器中
for (int i = 0; i < total; i++) {
bf.put(i);
}
// 匹配已在过滤器中的值，是否有匹配不上的
for (int i = 0; i < total; i++) {
if (!bf.mightContain(i)) {
System.out.println("有坏人逃脱了~~~");
}
}
// 匹配不在过滤器中的10000个值，有多少匹配出来
int count = 0;
for (int i = total; i < total + 10000; i++) {
if (bf.mightContain(i)) {
count++;
}
}
System.out.println("误伤的数量：" + count);
}
}</pre><div class="contentsignin">Copier après la connexion</div></div><p>运行结果</p><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:js;toolbar:false;">误伤的数量：320</pre><div class="contentsignin">Copier après la connexion</div></div><p>运行结果表示，遍历这一百万个在过滤器中的数时，都被识别出来了。一万个不在过滤器中的数，误伤了320个，错误率是0.03左右。</p><h3 data-id="heading-15"><strong>Bloom Filter 源码分析</strong></h3><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:js;toolbar:false;">public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {
return create(funnel, (long) expectedInsertions);
}
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}
public static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp) {
return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
......
}</pre><div class="contentsignin">Copier après la connexion</div></div><p>Bloom Filter 一共四个 <code>create 方法，不过最终都是走向第4个。看一下每个参数的含义
funnel：数据类型(一般是调用Funnels工具类中的)
expectedInsertions：期望插入的值的个数
fpp： 错误率(默认值为0.03)
strategy： 哈希算法 Bloom Filter的应用
更多编程相关知识，请访问：编程视频！！
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!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
