简介
英语：(Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。
布隆过滤器原理
当一个元素加入布隆过滤器中的时候，会进行如下操作：
- 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。
- 根据得到的哈希值，在位数组中把对应下标的值置为 1。
当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：
- 对给定元素再次进行相同的哈希计算；
- 得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。
举个简单的例子：
布隆过滤器初始状态.png
元素添加到布隆过滤器.png
查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了
- 如果这些点有任何一个 0，则被查询变量一定不在；
- 如果都是 1，则被查询变量很
可能存在；
为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。
- 误判率
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。
这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)
布隆过滤器使用场景
- 判断给定数据是否存在：比如判断一个数字是否在于包含大量数字的数字集中（数字集很大，5亿以上！）、 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）、邮箱的垃圾邮件过滤、黑名单功能等等；
- 去重：比如爬给定网址的时候对已经爬取过的 URL 去重；
代码示例
pom.xml引入依赖：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>
public class GuavaBloomFilterDemo {
public static void main(String[] args) {
// 后边两个参数：预计包含的数据量，和允许的误差值
BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 100000, 0.01);
for (int i = 0; i < 100000; i++) {
bloomFilter.put(i);
}
System.out.println(bloomFilter.mightContain(1));
System.out.println(bloomFilter.mightContain(2));
System.out.println(bloomFilter.mightContain(3));
System.out.println(bloomFilter.mightContain(100001));
//bloomFilter.writeTo();
}
}
Guava 提供的布隆过滤器的实现还是很不错的（想要详细了解的可以看一下它的源码实现），但是它有一个重大的缺陷就是只能单机使用（另外，容量扩展也不容易），而现在互联网一般都是分布式的场景。为了解决这个问题，我们就需要用到 Redis 中的布隆过滤器了。
Redis 中的 BloomFilter
Redis v4.0 之后有了 Module（模块/插件） 功能，Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 ：https://redis.io/modules。
在已安装 Redis 的前提下，安装 RedisBloom，有两种方式:
-
直接编译进行安装
git clone https://github.com/RedisBloom/RedisBloom.git cd RedisBloom make #编译 会生成一个rebloom.so文件 redis-server --loadmodule /path/to/rebloom.so #运行redis时加载布隆过滤器模块 redis-cli # 启动连接容器中的 redis 客户端验证 -
使用Docker进行安装
docker pull redislabs/rebloom:latest # 拉取镜像 docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest # 运行容器 docker exec -it redis-redisbloom bash redis-cli -
常用命令一览
注意： key:布隆过滤器的名称，item : 添加的元素。- BF.ADD ：将元素添加到布隆过滤器中，如果该过滤器尚不存在，则创建该过滤器。格式：BF.ADD {key} {item}。
- BF.MADD : 将一个或多个元素添加到“布隆过滤器”中，并创建一个尚不存在的过滤器。该命令的操作方式BF.ADD与之相同，只不过它允许多个输入并返回多个值。格式：BF.MADD {key} {item} [item ...] 。
- **BF.EXISTS ** : 确定元素是否在布隆过滤器中存在。格式：BF.EXISTS {key} {item}。
- BF.MEXISTS ： 确定一个或者多个元素是否在布隆过滤器中存在格式：BF.MEXISTS {key} {item} [item ...]。
BF.RESERVE需要单独介绍：
格式 BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]
简单介绍一下每个参数的具体含义：
1. key：布隆过滤器的名称
2. error_rate :误报的期望概率。这应该是介于0到1之间的十进制值。例如，对于期望的误报率0.1％（1000中为1），error_rate应该设置为0.001。该数字越接近零，则每个项目的内存消耗越大，并且每个操作的CPU使用率越高。
3. capacity: 过滤器的容量。当实际存储的元素个数超过这个值之后，性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长，性能将线性下降。
可选参数：
1. expansion：如果创建了一个新的子过滤器，则其大小将是当前过滤器的大小乘以expansion。默认扩展值为2。这意味着每个后续子过滤器将是前一个子过滤器的两倍。
- Redis bloom demo
// 使用Redisson实现
public class RedissonBloomFilterDemo {
public static void main(String[] args) {
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("user");
// 初始化布隆过滤器，预计统计元素数量为55000000，期望误差率为0.03
bloomFilter.tryInit(55000000L, 0.03);
bloomFilter.add("Tom");
bloomFilter.add("Jack");
System.out.println(bloomFilter.count()); // 2
System.out.println(bloomFilter.contains("Tom")); // true
System.out.println(bloomFilter.contains("Linda")); // false
}
}
总结
- 一个元素如果判断结果为存在的时候元素不一定存在；
- 但是判断结果为不存在的时候则一定不存在；
- 布隆过滤器可以添加元素，但是不能删除元素；
————————————————————
坐标帝都，白天上班族，晚上是知识的分享者
如果读完觉得有收获的话，欢迎点赞加关注
网友评论