Bloom filter:大数据快速排除算法

标签: 开源软件 秀技术 Bloom filter 算法 | 发表时间:2012-04-01 23:28 | 作者:xiuwz
出处:http://www.xiuwz.com

Bloom filter是由 Howard Bloom在 1970 年提出的一种多哈希函数映射的快速查找算法,该算法能够在非常快速的判定某个元素是否在一个集合之外。这种检测只会对在集合内的数据错判,而不会对不是集合内的数据进行错判,这样每个检测请求返回有“在集合内(可能错误)”和“不在集合内(绝对不在集合内)”两种情况。目前 Bloom filter在分布式系统中有着广泛的使用,比如说GFS/HDFS/Cassandra/ Bigtable/ Squid

实例

为了说明 Bloom filter存在的重要意义,举一个实例:

假设要你写一个网络蜘蛛(web crawler)。由于网络间的链接错综复杂,蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道蜘蛛已经访问过那些URL。给一个URL,怎样知道蜘蛛是否已经访问过呢?稍微想想,就会有如下几种方案:

  1. 将访问过的URL保存到数据库。
  2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
  3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
  4. Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。

方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。

以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。

方法1的缺点:数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了?

方法2的缺点:太消耗内存。随着URL的增多,占用的内存会越来越多。就算只有1亿个URL,每个URL只算50个字符,就需要5GB内存。

方法3:由于字符串经过MD5处理后的信息摘要长度只有128Bit,SHA-1处理后也只有160Bit,因此方法3比方法2节省了好几倍的内存。

方法4消耗内存是相对较少的,但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么?若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。

实质上上面的算法都忽略了一个重要的隐含条件:允许小概率的出错,不一定要100%准确!也就是说少量url实际上没有没网络蜘蛛访问,而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。

Bloom Filter的算法

下面引入本篇的主角—— Bloom filter。其实上面方法4的思想已经很接近 Bloom filter了。方法四的致命缺点是冲突概率高,为了降低冲突的概念, Bloom filter 使用了多个哈希函数,而不是一个

Bloom filter采用的是哈希函数的方法,将一个元素映射到一个 m 长度的阵列上的一个点,当这个点是 1 时,那么这个元素在集合内,反之则不在集合内。这个方法的缺点就是当检测的元素量很多时候可能有冲突,解决方法就是使用 k 个哈希 函数对应 k 个点,如果所有点都是 1 的话,那么元素在集合内,如果有 0 的话,元素则不再集合内。

Bloom filter 特点

Bloom filter优点就是它的插入和查询时间都是常数,另外它查询元素却不保存元素本身,具有良好的安全性。它的缺点也是显而易见的, 当插入的元素越多,错判“在集合内”的概率就越大了,另外 Bloom filter也不能删除一个元素,因为多个元素哈希的结果可能在 Bloom filter 结构中占用的是同一个位,如果删除了一个比特位,可能会影响多个元素的检测。

其实要做到能够删除一个元素,就需要修改下算法, 把bitmap修改成计数,这会带来另外一个缺点: 内存浪费

最后附上一个PHP实现的版本,请参考: http://code.google.com/p/php-bloom-filter/

您可能也喜欢:

MurmurHash算法:高运算性能,低碰撞率的hash算法

DataX:在异构数据源之间交换数据的工具

Gizzard:Twitter开源的通用数据切分中间件

searchtb:淘宝搜索技术博客

Druid:用于实时OLAP的分布式内存数据存储引擎
无觅

相关 [bloom filter 大数据] 推荐:

Bloom filter:大数据快速排除算法

- - 网站那些事 | 网站点兵
Bloom filter是由 Howard Bloom在 1970 年提出的一种多哈希函数映射的快速查找算法,该算法能够在非常快速的判定某个元素是否在一个集合之外. 这种检测只会对在集合内的数据错判,而不会对不是集合内的数据进行错判,这样每个检测请求返回有“在集合内(可能错误)”和“不在集合内(绝对不在集合内)”两种情况.

Bloom Filter 原理与应用

- - CSDN博客云计算推荐文章
Bloom Filter是一种简单的节省空间的随机化的数据结构,支持用户查询的集合. 一般我们使用STL的std::set, stdext::hash_set,std::set是用红黑树实现的,stdext::hash_set是用桶式哈希表. 上述两种数据结构,都会需要保存原始数据信息,当数据量较大时,内存就会是个问题.

[译]JVM上最快的Bloom filter实现

- - 鸟窝
英文原始出处: Bloom filter for Scala, the fastest for JVM. 本文介绍的是我用Scala实现的Bloom filter. 依照 性能测试结果,它是JVM上的 最快的Bloom filter实现. 零分配(Zero-allocation)和高度优化的代码.

JVM上最快的Bloom filter实现

- - ImportNew
英文原始出处:  Bloom filter for Scala, the fastest for JVM. 本文介绍的是我用Scala实现的Bloom filter. 依照 性能测试结果,它是JVM上的 最快的Bloom filter实现. 零分配(Zero-allocation)和高度优化的代码.

一个用于白名单服务的布隆过滤器(bloom filter)

- - CSDN博客架构设计推荐文章
      bloom filter这种数据结构用于判断一个元素是否在集合内,当然,这种功能也可以由HashMap来实现. bloom filter与HashMap的区别在于,HashMap会储存代表这个元素的key自身(如key为"IKnow7",那么HashMap将存储"IKnow7"这12个字节(java),其实还需要包括引用大小,但java中相同string只存一份),而bloom filter在底层只会使用几个bit来代表这个元素.

Servlet Filter 学习

- - CSDN博客架构设计推荐文章
最近在研究CAS , CAS 中的Servlet Filter 不太熟悉, 所以花了点时间学下了下这部分的知识, 分成以下几部分 学习. Servlet Filter  的功能和用法. Servlet Filter 顺序的注意事项. A filter is an object that performs filtering tasks on either the request to a resource (a servlet or static content), or on the response from a resource, or both.

Servlet、Filter和Listener

- - Web前端 - ITeye博客
Java Servlet是与平台无关的服务器端组件,运行于Servlet容器中(如Tomcat),Servlet容器负责Servlet和客户端的通信以及调用Servlet的方法,Servlet和客户端的通信采用“请求/响应”的模式. Servlet可完成以下功能:. 1、创建并返回基于客户请求的动态HTML页面.

dubbo中的Filter顺序

- - 互联网 - ITeye博客
最近发现dubbo的小 bug,顺便整理了一下dubbo中的Filter调用顺序及如何确定的. 服务提供方的过滤器被调用顺序:. EchoFilter->ClassLoaderFilter->GenericFilter->ContextFilter->(这4个是在代码中指定的). 服务消费方的过滤器顺序:.

activity、 intent 、intent filter、service、Broadcast、BroadcaseReceiver解释

- - CSDN博客推荐文章
Android中,Activity是所有程序的根本,所有程序的流程都运行在Activity之中,Activity具有自己的生命周期(由系统控制生命周期,程序无法改变,但可以用onSaveInstanceState保存其状态). 对于Activity,关键是其生命周期的把握(如那张经典的生命周期图=.=),其次就是状态的保存和恢复(onSaveInstanceState onRestoreInstanceState),以及Activity之间的跳转和数据传输(intent).

webservice的安全机制3---Filter

- - 博客园_首页
本节摘要:本节继续讨论webservice的安全机制,本节采用servlet的过滤器Filter来实现.    前面讲了webservice的安全机制1和2,本节继续webservice的安全之旅,.    本节采用servlet的Filter的来实现对webservice的安全访问.    在调用webservice之前,过滤器会拦截匹配的请求,只有满足安全要求的客户端才能访问webservice服务.