布隆过滤器
0.引言
P：我们平时在刷抖音时，开发人员如何保证 不会刷到同样的内容 ？
- 1：把算法推荐中的内容根据历史记录做一遍筛选？在用户量大，用户查看内容多的场景，性能低
- 2：历史记录全部计入缓存？资源量大，并且会随着时间逐渐上涨，服务器耗费up
- 3：布隆过滤器？专门用于解决去重问题，存在一定误判概率但是在去重的同时能节省90%的空间
1.使用场景
- 1：在数据量很大(5亿以上)的场景下判断某一数据是否存在。对比hashMap节省了很大的存储空间
- 2：黑名单、邮箱的垃圾邮件过滤。正常邮件被放入垃圾邮箱，就是布隆过滤器的误判导致
- 3：去重。例如爬虫时，对已经爬取过的内容去重
- 4：缓存穿透（非法用户会使用一般数据库里没有的key来进行访问导致请求一直打到数据库，导致数据库崩溃）。布隆过滤器删除key困难（会影响其他key），更建议直接使用redis set（设置过期时间）
2.什么是布隆过滤器
2.1数据结构
布隆过滤器（Bloom Filter）1970年由Bloom的老哥提出
它由一个二进制数组来记录数据的相关性,数组中只有1或0
二进制数组的优势：申请一个 100w 个元素的位数组只占用 1000000Bit \ 8 = 125000 Byte = 125000\1024 kb ≈ 122kb 的空间。
因为数组为固定长度，在数据量越多而空间越少的情况，判断误差率会变大
2.2 原理
当一个元素加入布隆过滤器时：
- 布隆过滤器中的多个哈希函数对元素值进行计算，得到索引值，之后数组长度对该索引值取模算的数组位置
- 多个哈希函数有多个计算后的数组位置，置为1，完成add操作
当判断一个元素是否存在时：
- 多个哈希函数对元素值计算出位置后，如果有一个位置值为0，则肯定不存在
- 如果多个位置值都为1，则表示极有可能存在（可能其他元素把这几个位置提前置为1了，导致的误判）
2.3 使用
1. 使用注意点
- 使用时 不要让实际元素数量远大于初始化数量；
- 当实际元素数量超过初始化数量时，应该对布隆过滤器进行 重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进行；
- 初始化的数量和误判率根据实际业务场景分配
2. 场景
1. 单机场景中 - Guava Bloom Filter
1.依赖
<dependency>
<groupId>com.google.guava<\groupId>
<artifactId>guava<\artifactId>
<version>28.0-jre<\version>
<\dependency>
# 2.使用
# 2.1 创建布隆过滤器对象
BloomFilter<Integer> filter = BloomFilter.create(
Funnels.integerFunnel(),
1500,
0.01);
# 2.2 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
# 2.3 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));2. 分布式场景中 - Redisson Bloom Filter
# 1.依赖
<dependency>
<groupId>org.redisson<\groupId>
<artifactId>redisson<\artifactId>
<version>3.7.5<\version>
<\dependency>
# 2.获取存储在redis中的布隆过滤器
RBloomFilter<String> filter = redissonClient.getBloomFilter("BloomFilter");
# 3.不存在时初始化,
filter.tryInit(10000, 0.01);
for (int i=0;i<20;i++){
# 4.新增
filter.add(StrUtil.toString(i));
}
# 5.判断是否存在
for (int i=0;i<20;i++){
log.info("key:{},是否存在：{}",i,filter.contains(StrUtil.toString(i)));
}参考链接：
1：JavaGuide - 布隆过滤器
2：亿级数据过滤和布隆过滤器
3：学会布隆过滤器，能当CEO？
