Bloom过滤器

2019-11-20 本文已影响0人 night_field

引文

思考一个问题：从大量数据里面如何高效率地去重？
有过一点编程经验的人都知道，可以通过Set这种数据结构来做到。比如HashSet，采用了Hash算法，可以在O(1)的复杂度完成数据的添加和查询操作。确实，大多数情况，这也是我们会采取的方案。但是因为Set需要保存源数据信息，且有Hash冲突，当样本数据量特别庞大的情况下，比如有千万甚至上亿的数据量时，这种方式显得有些不切实际。

布隆过滤器

布隆过滤器(Bloom Filter)的思想跟Hashmap有部分类似，也是通过hash函数映射的方式保存样本信息，不一样的是它依赖的数据结构是一个位数组，数组每一位上要么是0，要么是1，初始状态全是0。

位数组

当要往过滤器添加一个元素的时候，我们需要n(n是正整数)个独立的hash函数给目标元素做哈希运算，然后我们将得到的n个结果分别映射到位数组上。
举个简单的例子，假设我们要添加元素的元素是数字，我们取n为3，选取的3个hash函数分别是

$hash_{1}(x) = (x ^ 2)$ %20

$hash_{2}(x) = (x ^ 3)$ %20

$hash_{3}(x) = (x ^ 4)$ %20

当添加7这个元素的时候，通过三个hash函数计算的结果分别是9，3和1，我们把位数组对应下标的元素记为1。

元素7的指纹信息

这样元素7就在位数组上以9，3和1三个位置信息的形式，存储了起来。后续所有的元素都经过三个hash函数，映射到位数组上。于是当我们要判断某个元素是否存在的时候，我们去数组上此元素应该在的位置处查看，对应的数字是否都为1。如果有数字为0，那么元素肯定不存在。如果数字都为1，那么元素大概率存在。

算法研究

布隆过滤器是一种概率数据结构(probabilistic data structure)，可能会出现误判，但不会漏判。因为不同元素的hash结果可能会相同，而且被映射位置的数字可能已经被其他元素置为1，所以我们不能判断某个元素一定重复。

Hash函数

过滤器需要一系列独立的hash函数，函数的目标是将输出均匀地打散在目标域上。也就是说，元素通过hash函数映射到位数组上任何位置的概率应该是相同的。另外还有重要的一点，就是算法速度要快，过滤器的性能很大程度上取决于hash函数的性能。好的hash函数能在保持良好时间效率的情况下，降低过滤器的误判率。其中比较知名的是MurmurHash, FNV Hash, MD5

参数选择

一个合格的布隆过滤器，需要有很高的空间时间效率，较低并且可控的误判率。从而我们很容易发现几个问题。

如何选取位数组长度m。m越大，占用的空间越大；m越小，误判的几率越高。
如何选取hash函数个数k。k越大，数组越快被占满从而误判率越高；k越小，产生hash冲突的概率越大，导致误判率也越高。

对于上述的问题，切入点是最小化误差率。怎样是误差？不就是当查询一个未重复元素的时候，对应映射的位置已经都为1了吗。对于长度为m的位数组，某个位置被设为1的概率是 $\frac{1}{m}$ ，所以这个位置仍然为0的概率是

$1-\frac{1}{m}$

每个元素都会有k个hash映射，假设所有的hash结果相互独立，当数组已经添加了n个元素的时候，该位置依然为0的概率是

$(1-\frac{1}{m})^{kn}$

于是这个位置已经是1了的概率是

$1-(1-\frac{1}{m})^{kn}$

所以对于某个元素做k次hash映射，对应位置都已为1的概率，即误判率 $P_f$ 为

$P_f=(1-(1-\frac{1}{m})^{kn})^k$

因为

$\lim\limits_{x \to \infty} (1-\frac{1}{x})^x=\frac{1}{e}$

所以当数据量很大的时候，误判率可以近似的表示为

$P_f\approx(1-e^\frac{-kn}{m})^k$

对于给定的m和n，可以解出当 $P_f$ 达到极小值也就是最优值时，k的取值为

$k=\frac{m}{n}ln2$

将这个结果代入到原来的表达式中消去k，最终可以得到

$lnP_f=-\frac{m}{n}(ln2)^2$

从而得到最优位数组的大小

$m=-\frac{nlnP_f}{(ln2)^2}$

举个例子，当我们预估样本数量大小n为5,000,000的时候，期望过滤器有低于1%的误判率，依据以上两个公式，我们可以算出理想的位数组长度为

$m=-\frac{nlnP_f}{(ln2)^2}=-\frac{5,000,000*ln0.01}{(ln2)^2}\approx47,925,292$

最优hash函数个数为

$k=\frac{m}{n}ln2=\frac{47,925,292}{5,000,000}ln2\approx7$

也就是说在这种情况下我们可以将位数组长度为设置为47,925,292，并且选择7个hash函数来达到目标。

布隆过滤器的优势

时间效率高

因为是通过数组下标查询，对每个hash函数映射结果查询的时间复杂度都是O(1)。而且各个hash函数都是不相关的，查询任务可以并行地处理，充分地发挥计算机多核多线程的优势，甚至可以利用分布式的计算力来进一步优化效率。

占用内存小

对于给定的误判率1%，每个元素的存储通常不会超过10字节。相较于Hashset之类的要保存源元素的数据结构来说，无论元素的原始大小是多少，布隆过滤器的大小都是恒定的，一般只需要10%-25%的内存占用。

信息安全

布隆过滤器并不保存源信息，而是保存源信息的几个hash指纹，所以有非常好的保密性，非常适合对信息比较敏感的场景。

布隆过滤器的不足

误判

作为一种概率数据结构，误判应该是最大的缺点了。不过我们还是可以通过选取适当的参数，将误判率控制在一定的可接受范围内。

无法删除数据

因为hash冲突的存在，当考虑要删除某个元素的时候，我们不能简单地把相应映射位置的数字记为0，因为很可能有其他元素也映射到了这些位置。如下图，3和7元素都映射到了1和9两个位置，当把7对应位置的元素置为0的时候，也影响到了元素3。

hash冲突
一些布隆过滤器的变体，如计数布隆过滤器(Counting Bloom Filter)，稳定布隆过滤器(Stable Bloom Filter)可以支持元素的删除，但是是通过牺牲空间效率或准确性来达成的。

应用场景

综合布隆过滤器的优劣，我们可以知道过滤器的适用场景大致有几个特点

对误判有一定的容忍度

样本的数量比较庞大

对时间空间效率要求比较高

避免缓存穿透
将缓存的数据放到布隆过滤器里面，当请求一个一定不存在的资源的时候，在过滤器层便可把请求返回，从而防止缓存穿透攻击导致DB瘫痪。如：Bigtable, Apache HBase
垃圾邮件/黑名单/危险网站的过滤
将所有被标记为垃圾邮件的邮箱地址存到过滤器里，当收到新邮件时，如果发现发件人在过滤器里则自动拉入垃圾邮箱。因为误判的存在，所以有时候我们会发现正常的邮件会被归入垃圾邮件。如：浏览器，邮件系统
URL的去重
对于某些网页爬虫程序，把已经处理过的URL放到过滤器里面，可以减少爬虫的很多重复工作。
用户喜好推送系统
根据用户的浏览记录，给用户发一些推送。我们可以把所有用户的浏览记录放到过滤器里面，保证推送不重复。如：Medium

总结

布隆过滤器是一个时间空间效率都很高的过滤器，但是会有一定的误判率。在海量数据的处理场景中有广泛的应用。

参考

Bloom Filter
Bloom Filters by Example