你真的了解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



推荐阅读:
使用双buffer无锁化
谈谈pImpl模式
我为什么关掉了超线程

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

欢迎使用微信扫描下方二维码,关注我的微信公众号TechTalking,技术·生活·思考:
后端技术小黑屋

Comments