布隆过滤器原理以及java/redis使用
漆雕深
布隆过滤器
布隆过滤器是用于判断一个元素是否在集合中。通过一个位数组和N个hash函数实现。(某样东西一定不存在或者可能存在.)
- 优点：
- 空间效率高，所占空间小。
- 查询时间短。
- 自带去重
- 缺点：
- 元素添加到集合中后，不能被删除。
- 有一定的误判率
布谷鸟过滤器解决了布隆过滤器无法删除的问题
布隆过滤器原理
当一个元素加入布隆过滤器中的时候，会进行如下操作：
- 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。
- 根据得到的哈希值，在位数组中把对应下标的值置为 1。
当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：
- 对给定元素再次进行相同的哈希计算；
- 得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值可能在布隆过滤器中，如果存在一个值不为 1，说明该元素一定不在布隆过滤器中。
使用场景
- 大量数据中判断某个数据是否存在(用户是否阅读过某个文章)：这就可以实现出上述的去重功能，如果你的服务器内存足够大的话，那么使用 HashMap 可能是一个不错的解决方案，理论上时间复杂度可以达到 O(1 的级别，但是当数据量起来之后，还是只能考虑布隆过滤器。
- 解决缓存穿透：我们经常会把一些热点数据放在 Redis 中当作缓存，例如产品详情。 通常一个请求过来之后我们会先查询缓存，而不用直接读取数据库，这是提升性能最简单也是最普遍的做法，但是 如果一直请求一个不存在的缓存，那么此时一定不存在缓存，那就会有 大量请求直接打到数据库 上，造成 缓存穿透，布隆过滤器也可以用来解决此类问题。这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回不进行缓存和db的查询。
- 爬虫/ 邮箱等系统的过滤：平时不知道你有没有注意到有一些正常的邮件也会被放进垃圾邮件目录中，这就是使用布隆过滤器 误判 导致的。
利用Google开源的 Guava中自带的布隆过滤器
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
// 创建布隆过滤器对象,指定容量和容错率
BloomFilter<Integer> filter = BloomFilter.create(
Funnels.integerFunnel(),
1500,
0.01);
// 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
Redis 中的布隆过滤器
Redis v4.0 之后有了 Module（模块/插件） 功能，Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。
使用Docker安装
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
docker exec -it redis-redisbloom bash
redis-cli
命令
- bf.add 添加元素到布隆过滤器，如果该过滤器尚不存在，则创建该过滤器。格式：
BF.ADD {key} {item} - bf.exists 判断元素是否在布隆过滤器,格式：
BF.EXISTS {key} {item} - bf.madd 添加多个元素到布隆过滤器，bf.add只能添加一个.格式：
BF.MADD {key} {item} [item ...]。 - bf.mexists 判断多个元素是否在布隆过滤器.格式：
BF.MEXISTS {key} {item} [item ...] - bf.reserve 创建布隆过滤器.格式:
BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]- key：布隆过滤器的名称
- error_rate :误报的期望概率。这应该是介于0到1之间的十进制值。例如，对于期望的误报率0.1％（1000中为1），error_rate应该设置为0.001。该数字越接近零，则每个项目的内存消耗越大，并且每个操作的CPU使用率越高。
- capacity: 过滤器的容量。当实际存储的元素个数超过这个值之后，性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长，性能将线性下降。
- expansion：如果创建了一个新的子过滤器，则其大小将是当前过滤器的大小乘以
expansion。默认扩展值为2。这意味着每个后续子过滤器将是前一个子过滤器的两倍。(子过滤器，但与初始化时容量合适的等效过滤器相比，它将消耗更多的内存和CPU)
127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0
类似资料：