Bloom Filter

Posted by Night Field's Blog on October 29, 2019

引文

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

布隆过滤器

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

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

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

当添加7这个元素的时候,通过三个hash函数计算的结果分别是931,我们把位数组对应下标的元素记为1元素7的指纹信息

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

算法研究

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

Hash函数

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

参数选择

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

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

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

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

因为每个元素都会有k个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=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,因为很可能有其他元素也映射到了这些位置。如下图,37元素都映射到了1和9两个位置,当把7对应位置的元素置为0的时候,也影响到了元素3hash冲突 一些布隆过滤器的变体,如计数布隆过滤器(Counting Bloom Filter),稳定布隆过滤器(Stable Bloom Filter)可以支持元素的删除,但是是通过牺牲空间效率或准确性来达成的。

应用场景

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

  • 对误判有一定的容忍度
  • 样本的数量比较庞大
  • 对时间空间效率要求比较高
  1. 避免缓存穿透

将缓存的数据放到布隆过滤器里面,当请求一个一定不存在的资源的时候,在过滤器层便可把请求返回,从而防止缓存穿透攻击导致DB瘫痪。如:Bigtable, Apache HBase

  1. 垃圾邮件/黑名单/危险网站 的过滤

将所有被标记为垃圾邮件的邮箱地址存到过滤器里,当收到新邮件时,如果发现发件人在过滤器里则自动拉入垃圾邮箱。因为误判的存在,所以有时候我们会发现正常的邮件会被归入垃圾邮件。如:浏览器,邮件系统

  1. URL的去重

对于某些网页爬虫程序,把已经处理过的URL放到过滤器里面,可以减少爬虫的很多重复工作。

  1. 用户喜好推送系统

根据用户的浏览记录,给用户发一些推送。我们可以把所有用户的浏览记录放到过滤器里面,保证推送不重复。如:Medium

总结

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

参考

Bloom Filter

Bloom Filters by Example