Redis中的布隆过滤器怎么实现
这篇文章主要介绍“Redis中的布隆过滤器怎么实现”，在日常操作中，相信很多人在Redis中的布隆过滤器怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”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"));
}
}集合的内部，通常是使用散列表来实现。其优点是查询非常高效，缺点是比较耗费存储空间。
一般在数据量比较小的时候，我们会使用集合来进行存储。以空间换时间，在占用空间较小的情况下，同时又能提高查询效率。
但是，当存储的数据量比较大的时候，耗费大量空间将会成为问题。因为这些数据通常会存储到进程内存中，以加快查询效率。而机器的内存通常都是有限的，要尽可能高效的使用。
另一方面，散列表在空间和效率上是需要做平衡的。存储相同数量的元素，如果散列表容量越小，出现冲突的概率就越高，用于解决冲突的时间将会花费更多，从而影响性能。
而布隆过滤器（Bloom Filter）的产生，能够很好的解决这个问题。一方面能够以更少的内存来存储数据，另一方面能够实现非常高效的查询性能。
基本原理
首先，建立一个二进制向量，并将所有位设置为 0
然后，选定 K 个散列函数，用于对元素进行 K 次散列，计算向量的位下标。
添加元素
当添加一个元素到集合中时，通过 K 个散列函数分别作用于元素，生成 K 个值作为下标，并对向量的相应位设置为 1。
检查元素
如果要检查一个元素是否存在集合中，用同样的散列方法，生成 K 个下标，并检查向量的相应位是否全部是 1。
如果全为 1，则该元素很可能在集合中；否则（只要有1个或以上的位为0），该元素肯定不在集合中。
Demo
假设有一个布隆过滤器，容量是15位，使用2个哈希函数，如下所示。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |0|||||||||||||||||||
添加一个字符串
a，2次哈希得到下标为 4 和 10，将 4 和 10 对应的位由 0 标记为 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|||||||||
再添加一个字符串
b，2 次哈希得到下标为 11，将 11 对应的位由 0 标记为 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|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|||||||
最后添加一个字符串
sam，2 次哈希得到下标为 0 和 7，将对应的位由 0 标记为 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 给定值下的误识别率。
解决误识别率
解决误识别率的常用方法包括
白名单
回溯确认
白名单
解决误识别率的常见方法，是建立一个较小的白名单，用来存储那些可能被误识别的数据。
以垃圾邮件过滤为例。假设我们有一个垃圾邮件库，用于在接收邮件的时候过滤掉垃圾邮件。
这时可以先将这个垃圾邮件库存储到布隆过滤器中，当接收到邮件的时候，可以先通过布隆过滤器高效的过滤出大部分正常邮件。
而对于少部分命中（可能为）垃圾邮件的，其中有一部分可能为正常邮件。
再创建一个白名单库，当在布隆过滤器中判断可能为垃圾邮件时，通过查询白名单来确认是否为正常邮件。
对于没在白名单中的邮件，默认会被移动到垃圾箱。通过人工识别的方式，当发现垃圾箱中存在正常邮件的时候，将其移入白名单。
回源确认
很多时候，使用布隆过滤器是为了低成本，高效率的拦截掉大量数据不在集合中的场景。例如
Google Bigtable，Apache HBase以及Apache Cassandra和PostgreSQL 使用 Bloom 过滤器来减少对不存在的行或列的磁盘查找。避免进行昂贵的磁盘查找，可大大提高数据库查询操作的性能。
在谷歌浏览器用于使用布隆过滤器来识别恶意URL的网页浏览器。首先会针对本地 Bloom 过滤器检查所有 URL，只有在 Bloom 过滤器返回肯定结果的情况下，才对执行的 URL 进行全面检查（如果该结果也返回肯定结果，则用户会发出警告）。
拦截掉大量非IP黑名单请求，对于少量可能在黑名单中的IP，再查询一次黑名单库。
这是布隆过滤器非常典型的应用场景，先过滤掉大部分请求，然后只处理少量不明确的请求。
这个方法，和白名单库的区别是，不需要再另外建立一套库来处理，而是使用本来就已经存在的数据和逻辑。
例如 Google Bigtable 查询数据行本来就是需要查的，只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的，同样是先使用布隆过滤器来拦截掉大部分IP。
而上面垃圾邮件的处理，对于可能为垃圾邮件的情况，不是通过完整的垃圾邮件库再查询一次进行确认，而是用增加白名单来进行判断的方式。因为通常来说，白名单库会更小，便于缓存。
这里所说的回源，实际上是对可能被误识别的请求，最后要回到数据源头或逻辑确认一次。
Guava中的布隆容器的实现
Guava 中就提供了一种 Bloom Filter 的实现。
guava包引入
要使用 Bloom Filter，需要引入 guava 包
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>误判率测试
下面对布隆容器的误判率进行测试，分2步
往过滤器中放一百万个数，然后去验证这一百万个数是否能通过过滤器
另外找一万个数，去检验漏网之鱼的数量
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);
}
}运行结果
误伤的数量：320运行结果表示，遍历这一百万个在过滤器中的数时，都被识别出来了。一万个不在过滤器中的数，误伤了320个，错误率是0.03左右。
Bloom Filter 源码分析
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) {
......
}Bloom Filter 一共四个 create 方法，不过最终都是走向第4个。看一下每个参数的含义
funnel：数据类型(一般是调用Funnels工具类中的)expectedInsertions：期望插入的值的个数fpp： 错误率(默认值为0.03)strategy： 哈希算法 Bloom Filter的应用
到此，关于“Redis中的布隆过滤器怎么实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
![redis的set get[布隆过滤器]](/upload/202205/01/r5jwlvvhzuv.jpg)
![[mysql]mysql8修改root密码](https://static.528045.com/imgs/35.jpg?imageMogr2/format/webp/blur/1x0/quality/35)
