布隆过滤器详解

做缓存的人多半绕不开一个问题:请求打过来的 key 在缓存和数据库里都不存在,查询却每次都穿透到数据库。要挡住这类请求,先得能快速判断"这个 key 到底存不存在",布隆过滤器就是为这件事而生的。

背景介绍

在 redis 缓存的场景里,如果有人拿大量根本不存在的 key 来请求,缓存永远不命中,压力全部落到数据库上,这就是常说的缓存穿透。想拦截这类请求,最朴素的思路是把所有合法的 key 存进一个集合,查询前先判断一下。但 key 的数量一大,用 HashSet 这类结构存全量 key,内存开销很难接受。布隆过滤器用极小的空间换来一个"可能有误差但足够快"的存在性判断,正好卡在这个需求点上。

布隆过滤器（Bloom Filter）是1970年由布隆提出的，它实际上是由一个很长的二进制向量和一系列随机映射函数组成。布隆过滤器使用场景一般是防止redis缓存穿透，使用布隆过滤器可以更好的节省空间，并且快速定位元素是否存在。

布隆过滤器通过 hash key 来定位 位图（Bitmap，其实就是bit数组）中对应的下标，并且在这个数组中每一个位置只有0和1两种状态，每个位置只占用1个比特（bit），其中0表示没有元素存在，1表示有元素存在。

具体来说，写入一个元素时，会用 k 个不同的哈希函数分别对 key 计算，得到 k 个下标，把位图中这 k 个位置全部置为 1。查询的时候走同样的流程：k 个位置只要有任何一个是 0，说明这个 key 从来没被写入过；只有 k 个位置全部为 1，才判断"可能存在"。整个过程只有哈希计算和位运算，时间复杂度是 O(k)，与已存入的元素数量无关，这也是它查询快的原因。

注意：两个不同的key哈希出来所对应的下标位可能存在部分重复，这样可以减少内存的占用，但也有概率会出现哈希碰撞，原本不存在的key哈希之后位图中都为1的情况。

所以通过上面的现象，我们从布隆过滤器的角度可以得出布隆过滤器主要有2大特点：

1、如果布隆过滤器判断一个元素存在，那么这个元素可能存在。

2、如果布隆过滤器判断一个元素不存在，那么这个元素一定不存在。

这两条特点决定了它的用法：它适合做"前置拦截"，把一定不存在的请求挡在外面；但不能拿它的"存在"结论当真，判断存在之后仍然要走缓存或数据库做二次确认。

因为布隆过滤器中总是会存在误判率，因为哈希碰撞是不可能百分百避免的。布隆过滤器对这种误判率称之为假阳性概率，即：False Positive Probability，简称为fpp。

误判率的大小主要由三个因素决定：位图的长度 m、哈希函数的个数 k、以及已经写入的元素数量 n。写入的元素越多，位图中被置为 1 的比特就越多，一个陌生 key 的 k 个位置"恰好全是 1"的概率也就越高。所以布隆过滤器在创建时通常要求预估元素规模和期望的 fpp，由实现（比如 Guava 的 BloomFilter）反推出合适的 m 和 k。

为避免fpp，我们可以加大位图长度或者多次哈希来减少冲突概率，但加大位图需要更多的内存空间，多次哈希又需要更多的cpu资源，需要做好对应的资源开销预算，选择合适的方式。这本质上是一个空间、CPU 与准确率三者之间的权衡，没有免费的午餐。

如何进行删除对应key ？

上面的布隆过滤器我们知道，判断一个元素存在就是判断对应下标位置是否为1来确定的，但是如果要删除掉一个元素是不能直接把1改成0的，因为这个位置可能存在其他元素，所以原始的布隆过滤器是无法支持删除操作的，如果需要支持删除，那我们应该怎么做呢？最简单的做法就是加一个计数器，就是说位数组的每个位如果不存在就是0，存在几个元素就存具体的数字，而不仅仅只是存1，那么这就有一个问题，本来存1就是一位就可以满足了，但是如果要存具体的数字比如说2，那就需要2位了，所以带有计数器的布隆过滤器会占用更大的空间。

这种改良版本一般叫计数布隆过滤器（Counting Bloom Filter）：写入时把 k 个位置的计数器各加 1，删除时各减 1，只有计数器减到 0 才表示该位置真正空了。代价除了空间膨胀（每个位置从 1 bit 变成若干 bit），还多了一个隐患——如果误删了一个从未写入过的元素，计数器被错误地减掉，就可能把本来存在的元素"删没了"，引入假阴性。所以删除操作只应该对确认写入过的元素执行。

如果业务上删除需求不强，还有一种更省事的做法：不删除，定期用最新的全量数据重建一个新的布隆过滤器，替换旧的。重建期间旧过滤器继续服务，切换是原子的，很多缓存穿透场景用的就是这个思路。

踩坑与注意

1）容量要预估充分。布隆过滤器创建之后位图长度就固定了，元素写入超过预估规模后，fpp 会显著恶化，而且没法在线扩容，只能重建。

2）"存在"不等于真的存在。误判放行的 key 依然会打到数据库，布隆过滤器只能大幅减少穿透，不能百分之百消灭，数据库侧的兜底（比如缓存空值）仍然需要。

3）哈希函数要和写入方保持一致。如果多个服务共用一个布隆过滤器（比如放在 redis 里），各端的哈希实现和参数必须完全相同，否则判断结果就是错的。

小结

布隆过滤器用一个位图加 k 个哈希函数，换来了空间占用极小、查询 O(k) 的存在性判断，代价是存在假阳性、且原始结构不支持删除。它的两条判定特点——"说不存在就一定不存在，说存在只是可能存在"——决定了它最适合做前置拦截，典型场景就是防缓存穿透。需要删除时可以换计数布隆过滤器，或者干脆走定期重建的路子;而容量预估和 fpp 的设定,则要在内存、CPU 和准确率之间按自己的业务算一笔账。