What is Bloom filter

14 Jun 2022

Bloom filter是一个概率数据结构，用于检测一个元素是否存在于一个集合中，特点是空间占用少、计算速度快。

基本原理

Bloom filter是一个数据结构，由一个长度为m的比特位数组和k个相互独立的哈希函数组成。每个哈希函数都可以将一个元素映射到数组的一个比特位上。

元素加入集合的方法是，先用哈希函数将这个元素映射到k个位置，而后将比特位数组中的这k个位置的值都置为1。显而易见，在确定哈希函数和元素的情况下，比特位数组中置为1 的位置也是确定的。

查询元素在集合中是否存在的方法是，先用哈希函数把元素映射成k个位置，然后再检查比特位数组中这k个位置的值。如果全是1则返回真，表示元素可能存在，相反则返回假，表示元素肯定不存在。

这里说元素可能存在是因为这k个位置的1可能是在别的元素加入集合时设置的，被查询元素可能不在集合中。其他元素写入导致查询结果为真但实际上元素不在集合中，这种情况叫误报（假阳性）。误报是有一定概率的，叫误报率（假阳性率）。

误报率（假阳性率）

误报率由元素数量n、比特位数组长度m和哈希函数数量k共同决定。

误报率近似公式：

简单来说，

• 元素数量越多，误报率越高
• 比特位数组越短，误报率越高
• 哈希函数越少，误报率越高

所以，提升比特位数组长度和哈希函数数量可以降低误报率。但是，提升数组长度和哈希函数数量的代价是，比特位数组越长，所需存储空间越大；哈希函数数量越多，每次插入和查询的过程就越慢。

如何配置参数n、m、k？

使用n和m计算最优k值的公式：

于是，可以通过以下步骤确定参数：

1. 确定集合的数据量n
2. 确定预期的存储大小m
3. 使用公式计算得到k
4. 使用n、m和k计算得到误报率
5. 若误报率太高，回到第2步通过提升m来调整

一些在线的Bloom filter参数计算器：

• https://hur.st/bloomfilter/
• https://krisives.github.io/bloom-calculator/

应用

在存储系统中，可以使用Bloom filter来判断一条记录是否在表中存在，从而减少磁盘I/O。例如，BigTable论文中提到了使用Bloom filter来优化读取操作：在BigTable中，读取操作需要访问所有的SSTable。若这些SSTable不在内存中，可能会产生多次磁盘访问。BigTable可以为每个SSTable都建立一个Bloom filter，这样可以快速地知道一条指定的数据在一个SSTable中是否存在，从而避免无效的磁盘访问。