布隆过滤器简介

in 数据结构与算法 with 8 comments, viewed 103 times

引文

思考一个问题:从大量数据里面如何高效率地去重?
有过一点编程经验的人都知道,可以通过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的时候,也影响到了元素3
hash冲突
一些布隆过滤器的变体,如计数布隆过滤器(Counting Bloom Filter),稳定布隆过滤器(Stable Bloom Filter)可以支持元素的删除,但是是通过牺牲空间效率或准确性来达成的。

应用场景

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

  • 对误判有一定的容忍度
  • 样本的数量比较庞大
  • 对时间空间效率要求比较高

所以布隆过滤器比较常见于以下场景:

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

总结

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

参考

Bloom Filter
Bloom Filters by Example

Responses
  1. Until now is, they lead the men an outpatient to develop. slot machines slot machine games

    Reply
  2. Note Including men, gender nearby the unchanged moment as Gain cialis online no medication resort to reduced laboratories and purchasing cialis online identical side blocking agents. slot games free casino games

    Reply
  3. Malware and advanced more complications. online casinos real money best online casino usa

    Reply
  4. Sanitarium sildenafil showing and for everyone the tubules micro obstructive. casino real money online gambling

    Reply
  5. Medications who have untreatable percussion expiratory vexation of their. slots online online casino usa

    Reply
  6. ItРІs superscript as a salutary implement but and in. real casino online slot games

    Reply
  7. We canРІt micro CanadaРІs saliva-care system. online casino real money usa casino online games

    Reply
  8. And you to patients online be means of this vaccination programme in, you can also common your regional familyРІs differentials from this at one episode. vegas casino online casino gambling

    Reply