探索C#之布隆过滤器(Bloom filter)

背景介绍

Bloom filter(后面简称BF)是Bloom在1970年提出的二进制向量数据结构。通俗来说就是在大数据集合下高效判断某个成员是否属于这个集合。BF其优点在于:

  • 插入和查询复杂度都是O(n)
  • 空间利用率极高。

例子1:

像Yahoo这类的公共邮件服务提供商,总是需要过滤垃圾邮件。 假设有50亿个邮件地址,需要存储过滤的方法有:

  1. 所有邮件地址都存储到数据库。 缺点:每次都需要查询数据库,效率低。
  2. 使用Hashtable保存到内存里,接近O(1)的查询效率。 缺点:太占内存,假定每个地址需要十六个字符,50亿个需要180G内存。
  3. 创建位数组,将每个邮件地址用Hash函数映射到位数组中的某一位。 缺点: 单个Hash函数冲突太高,会发生多个邮件会映射到同一位上。

而使用BF可以最大限度避免上述缺点,使其可以在更小空间上,进行高效插入和查询。

例子2:

经常使用缓存的肯定知道,命中率是个永远的话题。 特别是在分布式缓存中,每次不命中就意味着一次跨网络通信的浪费,无故增加缓存服务器压力。使用BF可以在很大程度上提高缓存命中率。

算法原理

BF很合适解决类似上面的问题。 BF和例子1中的第三种方法非常类似了。不同的是,BF对同一个邮件地址使用多个不同的Hash函数,再去映射位数组的中对应位置。

算法步骤:

  1. 创建长度为m的位数组,全部置为0。
  2. 取出邮件地址集合(m)中的某一个地址(a), 分别使用k个hash函数对a计算。
  3. 将结果分别映射到位数组中,并设置为1。
  4. 其他成员依次处理。

以函数个数k=8来算,50亿个邮件地址只需要5G内存足够了,比例子1中方法2节省32倍空间。

当查询成员a时是否在垃圾邮件集合m中时,使用同样k个hash函数进行计算,如果k个结果在位数组中的位值都是1,则判断a属于m集合中,即a邮件地址属于垃圾邮件地址集合m(a∈m)。

关于例子2,可以将所有key存储到本地内存中,每次远程获取缓存时,优先在内存集合中判断是否存在。

  1. 存在?去远程获取实际缓存内容。
  2. 不存在?直接返回,无需再去远程缓存服务器判断。

这样能极大提高缓存命中率,因为BF存在误判率,所有并不能达到100%(在key的数量级不高时,用其他方法全存下来也可以)。如图:

误判率

因为BF使用Hash函数来取得成员的特征(可理解为成员的指纹信息),并没有在位数组中存储集合内的实际数据内容,所以空间利用率极高,但存在个潜在问题,就是查询某个成员是否属于集合时,会发生误判(False positive)。 也就是说,某个成员实际不在集合中,但BF会得出在集中的结论。 所以BF适用于允许发生一定误判的场景,如例子1、2中少量过滤失败或去服务器拿都是可以接受的。

为什么会有误判?

假定有一个长度12的位数组,使用3个hash函数,根据算法计算成员a得出3、7、11位置,并在位数组中设置为1。 另外个成员b根据算法也计算得出3、7、11,去位数组检查其位值时,就发现3、7、11都为1是存在的,而实际不存在(1是成员a设置的),此时就发生了误判现象。

BF会发生误判,但不会发生漏判(False Negative),即成员实际在集合中,那么BF一定能判断出在集合中,因为成员对应的位置都设置为1了。

可控制性

根据其数组长度m、集合大小n、hash函数个数k、误判率p,简单得出下:

  1. 其他不变,集合大小n越大,越多位被设置1,误判率p越大。
  2. 其他不变,数组涨肚m越大,剩余为0的位越多,误判率p越小
  3. 其他不变,添加时k越多,位数组越多被设置为1,即会增大误判率。查询时k越多,明显误判率可能就会越小。

hash函数个数取值公式 k = ln 2 * m/n 。

其他它关系公式见wiki

BF改进 

基本的BF在使用时有个缺点:无法删除集合成员a,只能增加其成员并对其查询。 有一个很容易想到但错误的方法是:如果要删除成员a,那么先用k个hash函数对其计算,因为a已经是集合成员,那么其对应的位数组的位置一定被设置为1,所以只要将对应位置重新设置为0即可。   原因就是位数组的位置不但只提供给a使用,也给其他成员使用,一旦设置为0就会影响其他成员的使用。

比如上面中提高缓存命中率的例子,不能删除成员意味着实际缓存也不能删除。如果实际缓存删除了,而在集合中的数据无法删除,就会发生漏判现象。 这样的话就会大大限制BF的使用场景。

计数BF(count bloom filter)

计数BF是对基本BF的改进,使BF可以支持删除成员。  因为BF的基本单位是1个bit,只能表达2种状态,即存在、不存在。 如果把基本单位1bit拓展成多个bit,这样就能增加更多信息,表达出多种状态。

计数BF的基本单元由多个bit表示,一般情况为3、4个bit。  这样在添加时,在数组位置上的数值上加1即可,删除成员时-1即可。 查询集合成员时保持不变,只要数值不为0即认为成员是存在的。

计数BF使基本BF有了更多应用场景。 同样由于用了多个bit来表示,对应数组大小也相应增加,如果用3bit作为基本单位,那么数组大小对应增加了3倍。

总结

BF是大数据处理的利器,其使用场景非常多:

  • Google的爬虫重复URL检测。
  • 黑名单验证。
  • 例子中的缓存命中率,垃圾邮件过滤。
  • 内存挡一层,减轻db空查压力。
  • hbase、LevelDB内部使用。

基本BF的具体实现可参考 http://bloomfilter.codeplex.com。

参考资料

[1] http://en.wikipedia.org/wiki/Bloom_filter

[2] http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JavaEdge

亿万级数据处理的高效解决方案简介从set/map到hashtable/hashmap/hashset秘技一:分而治之/Hash映射 + HashMap统计 + 堆/快速/归并排序堆秘技二:双层桶划分秘

1.4K70
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版5.1节C风格数据结构内存布局之引言

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

6810
来自专栏PingCAP的专栏

SuRF: 一个优化的 Fast Succinct Tries

在前一篇文章中,我简单介绍了 Succinct Data Structure,这里我们继续介绍 SuRF。

36050
来自专栏Golang语言社区

使用 Go 语言学会 Tensorflow

Tensorflow 并不是一个专门用于机器学习的库,相反的,它是一个通用的用于图计算的库。它的核心部分是用 C++ 实现的,同时还有其它语言的接口库。Go 语...

51720
来自专栏用户2442861的专栏

STL deque源码实现及分析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

54520
来自专栏生信宝典

Python学习教程(二)

输入输出 交互式输入输出 在很多时候,你会想要让你的程序与用户(可能是你自己)交互。你会从用户那里得到输入,然后打印一些结果。我们可以分别使用raw_input...

28980
来自专栏决胜机器学习

有趣的算法(三)——Hash算法

有趣的算法(三)——Hash算法 (原创内容,转载请注明来源,谢谢) 一、Hash算法 近期看到用hash实现基于hash的简单的小型数据库(传统大型数据...

38270
来自专栏用户2442861的专栏

数据库系统——B+树索引

http://blog.csdn.net/cjfeii/article/details/10858721

51610
来自专栏ATYUN订阅号

使用Python建立你数据科学的“肌肉记忆”

你是否曾在在搜索语法时,因为打断了数据分析流而感到沮丧?为什么你在屡次查找后仍然不记得它?这是因为你还没有足够的练习来为它建立“肌肉记忆”。

9520
来自专栏Star先生的专栏

Tensorflow 术语表

本文主要简要介绍了广播操作、Graph(图)、Session(会话)、Tensor 等13个 Tensorflow 术语表。希望对大家了解学习 Tensorfl...

1.1K10

扫码关注云+社区

领取腾讯云代金券