你真的了解bloom filter吗？

你真的了解bloom filter吗？

5 years ago

source link: https://www.tuicool.com/articles/vEFNbuM
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

当系统设计中出现多级缓存结构时，为了防止大量不存在的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