布隆过滤器:用极小内存快速判断元素是否可能存在
在很多系统里都有这样一个问题:数据量很大,但是我们只想快速知道一个元素是否可能存在,而不想把全部数据都装进内存。直接用哈希表保存全部键,内存开销会随数据量线性增长;每次都去查数据库或者远程缓存,又会把请求压力打到后端。布隆过滤器就是为了解决这个矛盾而出现的一种概率型数据结构,它用很小的内存换来一次快速的可能存在判断。
一、布隆过滤器到底是什么
布隆过滤器的核心只有两样东西:一个长度为 m 的位数组,以及 k 个相互独立的哈希函数。初始时位数组全部为 0。加入一个元素时,用 k 个哈希函数分别计算这个元素,得到 k 个位置,把这些位置上的位都置为 1。查询一个元素时,同样用这 k 个哈希函数计算位置:如果所有位置都是 1,说明这个元素可能存在;如果其中任何一个位置是 0,说明这个元素一定不存在。
这个不对称的结论是理解布隆过滤器的关键。说一定不存在是可靠的:如果查询的 k 个位置中有一个是 0,这个元素一定没有被加入过。反过来,即使 k 个位置全是 1,也只能说可能存在,因为这些位置可能恰好被其他元素置为 1,这就是误判。多个不同的元素可能共享同一个位,不同元素的哈希位置也可能重合,于是查询时所有位置恰好都是 1,但这个元素本身并没有被加入过。布隆过滤器允许这种误判存在,但永远不会出现漏判:一个真正被加入过的元素,查询时一定会返回可能存在。
二、一个直观的例子
假设位数组长度是 16,哈希函数个数是 3。加入元素 A,三个哈希值落在第 2、7、11 位,这三位置为 1。再加入元素 B,哈希值落在第 3、7、14 位,第 7 位本来就是 1,继续保持为 1。这时查询元素 C,它的三个哈希值是 2、3、14,全部都是 1,过滤器会回答可能存在,但实际上 C 从未加入过,这就是一次误判。查询元素 D,它的哈希值包含第 5 位,而第 5 位是 0,过滤器立刻可以确定 D 一定不存在。
从这个例子可以看出,位数组越满,误判的概率就越高。当加入的元素越来越多,位数组里 1 的比例不断上升,一个从未加入过的元素恰好撞上全 1 位置的可能性也随之上升。因此布隆过滤器并不是无限装数据的结构,它的有效容量是有限的,需要在设计时就预估好数据量。
三、误判率与参数选择
误判率主要由三个参数决定:位数组长度 m、预计加入的元素个数 n、哈希函数个数 k。位数组越大,误判率越低;元素越多,误判率越高;哈希函数个数则存在一个最优值,太少会让每次查询覆盖的位置太少、区分度不足,太多又会让位数组很快被填满。
在给定 m 和 n 的情况下,最优的哈希函数个数大约是位数组长度除以元素个数再乘以 0.7。举一个常见的工程取值:如果预计加入一百万个元素,希望误判率控制在百分之一左右,位数组大约需要九百六十万位,也就是大约 1.2 MB 内存。用同样的内存去存一百万个字符串键,远远不够。反过来想,如果把误判率放宽到百分之五,内存还可以再省一半左右。实际选型时,应该先定下可以接受的误判率和预计的数据量,再反推位数组大小,而不是先定内存再看误判率。
四、用 Go 写一个简化实现
下面的实现只是为了说明原理,生产环境应该使用经过充分测试的成熟库。示例用两次不同的哈希计算模拟多个哈希函数,通过在元素后面拼接不同的序号来得到不同的哈希值。
package main
import (
"fmt"
"hash/fnv"
)
type BloomFilter struct {
Size int
HashCount int
Bits []bool
}
func NewBloomFilter(size, hashCount int) *BloomFilter {
return &BloomFilter{Size: size, HashCount: hashCount, Bits: make([]bool, size)}
}
func (b *BloomFilter) positions(item string) []int {
positions := make([]int, 0, b.HashCount)
for i := 0; i < b.HashCount; i++ {
h := fnv.New64a()
h.Write([]byte(item))
h.Write([]byte{byte(i)})
positions = append(positions, int(h.Sum64()%uint64(b.Size)))
}
return positions
}
func (b *BloomFilter) Add(item string) {
for _, pos := range b.positions(item) {
b.Bits[pos] = true
}
}
func (b *BloomFilter) MightContain(item string) bool {
for _, pos := range b.positions(item) {
if !b.Bits[pos] {
return false
}
}
return true
}
func main() {
bloom := NewBloomFilter(1000, 3)
bloom.Add("alice")
bloom.Add("bob")
bloom.Add("carol")
fmt.Println(bloom.MightContain("alice"))
fmt.Println(bloom.MightContain("dave"))
fmt.Println(bloom.MightContain("carol"))
}
运行这段代码,加入过的 alice 和 carol 一定会返回 True,没有加入过的 dave 大概率返回 False,但也有小概率返回 True。把 Size 改小或者加入更多元素,再多次运行,就能直观地看到误判率上升的过程。
五、适合用在哪里
布隆过滤器最典型的用途是挡在昂贵的查询前面,先做一次廉价的排除。缓存穿透防护就是一个例子:请求先经过布隆过滤器,如果过滤器说一定不存在,就直接返回,不再去查数据库,避免大量不存在的键把数据库打垮。爬虫系统里也可以用它来判断一个链接是否已经被抓取过,避免重复抓取。数据库的存储引擎里也有类似思想,用布隆过滤器快速判断某个键是否可能在某个数据文件里,不在就直接跳过这个文件,减少磁盘读取。
还有一些场景是做去重和黑白名单的初步筛选,比如判断一个邮箱是否可能在垃圾邮件发送者集合里,或者一个用户名是否可能已经被注册。需要注意的是,这些场景都必须能接受误判带来的额外处理:把可能存在的结果再用一次精确查询确认一遍。布隆过滤器只是第一道筛子,而不是最终答案。
六、不适合用在哪里
首先,布隆过滤器不能删除元素。把某一位从 1 改回 0,可能会影响其他共享这一位的元素,导致它们被误判为不存在。如果业务需要频繁删除,可以考虑计数布隆过滤器,用一个小的计数器代替一位,删除时计数减一,但这会把内存开销放大几倍,需要权衡。
其次,它不能用来做精确的集合查询。任何需要百分之百准确回答存在与否的场景,都不能只依赖布隆过滤器。它也不能告诉你元素是什么、元素对应的值是多少,它只回答一个二值问题:可能存在,或者一定不存在。
最后,当数据量会持续无上限增长时,布隆过滤器会逐渐失效。位数组一旦接近全满,误判率会趋近于百分之百,过滤器就失去了意义。这种情况下需要定期重建,或者按时间分片使用多个布隆过滤器,让旧的数据随时间过期。
七、工程落地的注意事项
第一,容量要按峰值预估,而不是按当前数据量。预留增长空间比事后扩容容易得多,因为位数组一旦建好就很难在不重建的情况下扩大,扩容基本等于重新把全部元素加一遍。
第二,哈希函数的质量很重要。质量差的哈希函数会让位置分布不均匀,局部区域很快被填满,整体误判率会高于理论值。示例里用标准库哈希只是为了演示,生产实现通常会用速度更快、分布均匀的非密码学哈希函数。
第三,布隆过滤器的数据需要持久化时,要把位数组和参数一起保存下来,只保存位数组而不保存哈希函数个数和长度,恢复后是无法正确查询的。多实例之间共享同一个过滤器时,参数必须完全一致,否则查询结果没有意义。
八、小结
布隆过滤器用一个位数组和多个哈希函数,换来了极低的内存占用和很快的查询速度,代价是允许一定概率的误判,并且无法删除元素、无法给出精确答案。理解它,就要抓住两句话:说不存在一定是对的,说存在只是可能。只要业务能接受误判后用一次精确查询来确认,并且数据量可以预估,它就是一个非常划算的工具。反过来,如果业务要求百分之百准确,或者需要频繁删除和扩容,就应该换用哈希表、数据库索引或者其他精确结构,而不是勉强使用布隆过滤器。
- 点赞
- 收藏
- 关注作者
评论(0)