布隆过滤器
布隆过滤器常被用于检测一个元素是否在一个集合中，但存在一定的误判率。
特点
- 能代表全集，其它所有数据结构都不行
- 存在一定的误判率，存在布隆过滤器里的元素不一定真的存在，不存在布隆过滤器里的元素一定不存在
- 无法仅删除指定元素
布隆过滤器本质上是一串很长的二进制向量和一系列随机映射函数，它的优点是空间效率和查询时间都比一般算法好很多，缺点是有一定误识别率和删除困难。
使用场景
- 缓存穿透
- 垃圾邮件过滤
- 某个用户短视频的不重复推荐
当遇到数据量大，又需要去重的时候就可以考虑布隆过滤器
扩展知识点
- 缓存穿透指的是数据库本就没有这个数据，请求直奔数据库，缓存系统形同虚设。
- 解决方案：布隆过滤器
- 缓存击穿（失效）指的是数据库有数据，缓存本应该也有数据，但是缓存过期了，Redis 这层流量防护屏障被击穿了，请求直奔数据库。
- 解决方案：1.热点数据key不设置过期时间 2. 使用互斥锁访问数据库
- 缓存雪崩指的是大量的热点数据无法在 Redis 缓存中处理（大面积热点数据缓存失效、Redis 宕机），流量全部打到数据库，导致数据库极大压力。
- 解决方案：1.超时时间在原有失效时间上加个1-5分钟的随机值 2. 若无法避免，采用熔断机制，返回”系统拥塞“
Java内存实现的布隆过滤器
引入依赖
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>29.0-jre</version>
</dependency>
测试布隆过滤器
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BFTest {
//预计插入的数据
private static Integer expectedInsertions = 10000000;
//误判率
private static Double fpp = 0.01;
//布隆过滤器
private static BloomFilter<Integer> bloomFilter =
BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);
public static void main(String[] args) {
//插入1千万条数据
for (int i = 0; i < expectedInsertions; i++) {
bloomFilter.put(i);
}
//用1千万条不存在布隆过滤器的数据测试误判率
int count = 0;
for (int i = expectedInsertions; i < expectedInsertions *2; i++) {
if (bloomFilter.mightContain(i)) {
count++;
}
}
int c = 0;
for (int i = 0; i < expectedInsertions; i++) {
if (bloomFilter.mightContain(i)) {
c++;
}
}
System.out.println("一共误判了：" + count);
System.out.println("存在于布隆过滤器：" + c);
}
}
一共误判了：100075
存在于布隆过滤器：10000000可见结果误判率和一开始设置的误判率基本一致
且布隆过滤器成功过滤了这一千万条数据
布隆过滤器创建参数说明
- Funnel funnel：数据类型，由Funnels类指定即可
- long expectedInsertions：预期插入的值的数量
- fpp：错误率
- BloomFilter.Strategy：hash算法
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 1300452403@qq.com
