布隆过滤器是一个精巧而且经典的数据结构。
你可能没想到: RocketMQ、 Hbase 、Cassandra 、LevelDB 、RocksDB 这些知名项目中都有布隆过滤器的身影。
对于后端程序员来讲,学习和理解布隆过滤器有很大的必要性。来吧,我们一起品味布隆过滤器的设计之美。
1 缓存穿透
我们先来看一个商品服务查询详情的接口:
public Product queryProductById (Long id){
// 查询缓存
Product product = queryFromCache(id);
if(product != null) {
return product ;
}
// 从数据库查询
product = queryFromDataBase(id);
if(product != null) {
saveCache(id , product);
}
return product;
}
假设此商品既不存储在缓存中,也不存在数据库中,则没有办法回写缓存,当有类似这样大量的请求访问服务时,数据库的压力就会极大。
这是一个典型的缓存穿透的场景。
为了解决这个问题呢,通常我们可以向分布式缓存中写入一个过期时间较短的空值占位,但这样会占用较多的存储空间,性价比不足。
问题的本质是:"如何以极小的代价检索一个元素是否在一个集合中?"
我们的主角布隆过滤器出场了,它就能游刃有余的平衡好时间和空间两种维度。
2 原理解析
布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
布隆过滤器的原理:当一个元素被加入集合时,通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点,把它们置为 1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:如果这些点有任何一个 0,则被检元素一定不在;如果都是 1,则被检元素很可能在。
简单来说就是准备一个长度为 m 的位数组并初始化所有元素为 0,用 k 个散列函数对元素进行 k 次散列运算跟 len (m) 取余得到 k 个位置并将 m 中对应位置设置为 1。
如上图,位数组的长度是8,散列函数个数是 3,先后保持两个元素x,y。这两个元素都经过三次哈希函数生成三个哈希值,并映射到位数组的不同的位置,并置为1。元素 x 映射到位数组的第0位,第4位,第7位,元素y映射到数组的位数组的第1位,第4位,第6位。
保存元素 x 后,位数组的第4位被设置为1之后,在处理元素 y 时第4位会被覆盖,同样也会设置为 1。
当布隆过滤器保存的元素越多,被置为 1 的 bit 位也会越来越多,元素 x 即便没有存储过,假设哈希函数映射到位数组的三个位都被其他值设置为 1 了,对于布隆过滤器的机制来讲,元素 x 这个值也是存在的,也就是说布隆过滤器存在一定的误判率。
▍ 误判率
布隆过滤器包含如下四个属性:
-
k : 哈希函数个数
-
m : 位数组长度
-
n : 插入的元素个数
-
p : 误判率
若位数组长度太小则会导致所有 bit 位很快都会被置为 1 ,那么检索任意值都会返回”可能存在“ , 起不到过滤的效果。 位数组长度越大,则误判率越小。
同时,哈希函数的个数也需要考量,哈希函数的个数越大,检索的速度会越慢,误判率也越小,反之,则误判率越高。
从张图我们可以观察到相同位数组长度的情况下,随着哈希函数的个人的增长,误判率显著的下降。
误判率 p 的公式是
-
k 次哈希函数某一 bit 位未被置为 1 的概率为
-
插入 n 个元素后某一 bit 位依旧为 0 的概率为
-
那么插入 n 个元素后某一 bit 位置为1的概率为
-
整体误判率为 ,当 m 足够大时,误判率会越小,该公式约等于
我们会预估布隆过滤器的误判率 p 以及待插入的元素个数 n 分别推导出最合适的位数组长度 m 和 哈希函数个数 k。
▍ 布隆过滤器支持删除吗
布隆过滤器其实并不支持删除元素,因为多个元素可能哈希到一个布隆过滤器的同一个位置,如果直接删除该位置的元素,则会影响其他元素的判断。
▍ 时间和空间效率
布隆过滤器的空间复杂度为 O(m) ,插入和查询时间复杂度都是 O(k) 。 存储空间和插入、查询时间都不会随元素增加而增大。 空间、时间效率都很高。
▍哈希函数类型
Murmur3,FNV 系列和 Jenkins 等非密码学哈希函数适合,因为 Murmur3 算法简单,能够平衡好速度和随机分布,很多开源产品经常选用它作为哈希函数。
3 Guava实现
Google Guava是 Google 开发和维护的开源 Java开发库,它包含许多基本的工具类,例如字符串处理、集合、并发工具、I/O和数学函数等等。
1、添加Maven依赖
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre<</version>
</dependency>
2、创建布隆过滤器
BloomFilter<Integer> filter = BloomFilter.create(
//Funnel 是一个接口,用于将任意类型的对象转换为字节流,
//以便用于布隆过滤器的哈希计算。
Funnels.integerFunnel(),
10000, // 插入数据条目数量
0.001 // 误判率
);
3、添加数据
@PostConstruct
public void addProduct() {
logger.info("初始化布隆过滤器数据开始");
//插入4个元素
filter.put(1L);
filter.put(2L);
filter.put(3L);
filter.put(4L);
logger.info("初始化布隆过滤器数据结束");
}
4、判断数据是否存在
public boolean maycontain(Long id) {
return filter.mightContain(id);
}
接下来,我们查看 Guava 源码中布隆过滤器是如何实现的 ?
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BloomFilter.Strategy strategy) {
// 省略部分前置验证代码
// 位数组长度
long numBits = optimalNumOfBits(expectedInsertions, fpp);
// 哈希函数次数
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
try {
return new BloomFilter<T>(
new LockFreeBitArray(numBits),
numHashFunctions,
funnel,
strategy
);
} c