Bloom Filter (海量数据处理)

什么是Bloom Filter

先来看这样一个爬虫相关问题：文件A中有10亿条URL，每条URL占用64字节，机器的内存限制是4G，现有一个URL，请判断它是否存在于文件A中(爬过的URL无需再爬)。如果有很多个URL需要判断呢？

分析之后我们可以发现，这就是快速query问题，通常查操作居多，写操作较少。要快速判断一个URL是否在文件A中，由于

[{1,000,000,000*64 B = 64,000,000,000 B ≈ 60GB } ]

而60G是放不进内存的，所以逐个读入内存判断的话，时间复杂度起码是O(10亿)，这显然不能满足要求。如何节约内存又可以节省时间才是关键！Bloom Filter就是解决这种问题的数据结构，主要是能很好地节省内存。

原理简析

Bloom Filter (下简称BF)在海量数据方面的处理表现不错，它的内部需要的结构有：

hash函数k个，hashfun[k]；
位图bitset[m]，且m>k；

一个URL依次经过k个hash函数后得到k个数字，设为({X_i})，置bitset[({X_i})] = 1。先将A文件中的URL都这样处理，那么得到的bitset就是记录了与文件A相关的信息。将60GB的文件信息压缩成m个bit，如果能很好利用这m个bit，那内存将大大减少。

如何利用bitset[m]？

对于每个询问的URL，经过这k个hash函数之后同样能得到k个数字，设为({Y_j})，如果有

[{1= bitset[{Y_1}]& bitset[{Y_2}] & } cdots {& bitset[{Y_k}]} ]

说明此URL可能存在于A中，但是目前不能确定是否存在；如果有

[{0= bitset[{Y_1}]& bitset[{Y_2}] & } cdots {& bitset[{Y_k}]} ]

那就可以确定此URL不在A中。对于此URL是否一定存在于文件A中，Bloom Filter无法给出肯定的答复。设n为数据量(即10亿)，m为bitset大小(即槽个数)，k为hash函数个数，则它的错误率公式是

[{F(n,m,k) = [1-(1-frac{1}{m})^{kn}]^{k}≈(1-e^{frac{-kn}{m}})^{k}} ]

从上式中知道，

当n=0时，F(n,m,k)=0；
当n=+∞时，F(n,m,k)=1，即百分百错误；

看回最上面的问题，文件A在4GB内存中能达到的最低错误率是多少？

其实有3个因素决定了错误率，n、m、k，其中n与数据量挂钩，m与空间挂钩，k与时间挂钩，既然n已固定为10亿，m已固定约为32Gb，那么k的大小将决定错误率的大小。分析一下，预处理时需要先将n个数据都进行hash成k个数，所以时间复杂度为O(n*k)，而预处理完后每个查询仅需时间复杂度O(k)。

关于证明，如果有兴趣可以去维基上看。

Bloom Filter特点

算法简单，实现方便(百行以内)。
时空复杂度灵活，时间与空间上的控制相对比较容易。
无法实现确定性判断，但可以配合其他算法再次降低错误率。
操作的集合不能删除，即信息添加到bitset中后就无法取出。