你真的了解bloom filter吗？

当系统设计中出现多级缓存结构时，为了防止大量不存在的key值击穿高速缓存（比如主存），去直接访问低速缓存（如本地磁盘），我们一般需要将这部分key值，直接拦截在高速缓存阶段。这里，当然可以使用普通的hash table，也可以使用bitmap，但是这两种方式都比较耗费内存，当面对海量key值时，问题会变得更加严重。这时，就该介绍我们的主角bloom filter出场了。

一般的，bloom filter用于判断一个key值是否在一个set中，拥有比hash table/bitmap更好的空间经济性。如果bloom filter指示一个key值“不在”一个set中，那么这个判断是100%准确的。这样的特性，非常适合于上述的缓存场景。

原理

• 首先估计要判断的set中的元素个数N，然后选定k个独立的哈希函数。根据N和k，选定一个长度为M的bit array。
• 遍历set中的N个元素
  • 对每个元素，使用k个哈希函数，得到k个哈希值（一般为一个大整数）
  • 将上述bit array中，k个哈希值所对应的bit置1
• 对于需要判断的key值
  • 使用k个哈希函数，得到k个哈希值
  • 如果k个哈希值所对应的bit array中的值均为1，则判断此值在set中 “可能” 存在；
  • 否则，判定 “一定” 不存在

优缺点

• 优点：
  • 插入、查找都是常数时间
  • 多个hash函数之间互相独立，可以并行计算
  • 不需要存储元素本身，从而带来空间效率优势，以及一些保密上的优势
  • bloom filter的bitmap可以进行交、并、差运算
• 缺点：
  • 不准确：不在集合中的元素也有可能被判定在集合中
  • 无法删除：
    • 容易想到，可以将bitmap（0-1）变成可以计数的bitmap（0-1-2—-n），然后删除key时进行减法。
    • 但是，这样还是有问题：万一删除的元素本来就不在集合中呢？然鹅，又无法准确的判断一个元素是否在集合中（有概率误判）

扩展

• 谷歌的BigTable中，就使用到了bloom filter对查询加速
  • 预先缓存bloom filter在内存中，用于确定行或列是否“不存在”于磁盘上，从而避免了不必要的磁盘IO。而“不存在”是完全准确的
• 可以看到，Bloom Filter是一个利用概率学来对原始算法进行优化的例子。如果大家还有印象的话，我之前也介绍过一个使用类似思想的算法： Cardinality Estimation

转载请注明出处： http://blog.guoyb.com/2019/06/30/bloomfilter/

欢迎使用微信扫描下方二维码，关注我的微信公众号TechTalking，技术·生活·思考：