手机浏览 RSS 2.0 订阅 膘叔的简单人生 , 腾讯云RDS购买 | 超便宜的Vultr , 注册 | 登陆

【老博客】Using Bloom Filters

首页 > PHP >

这,又是两年前的博客了。但觉得还是一个不错的东西,所以还是贴出来吧。。

前段时间,yhustc问群里的人说是,如果有两个4G的文件,怎么样把其中相同的URL取出来?(文件大小4G,每行一个URL,每个URL64个字节),一下子迷惘了。后来他说了这个Bloom Filters,于是找了点资料 。
以下为部分资料,下次贴带图片(公式)的。。【文中有图片,但事实上原文并没有图片,来源于http://www.chinaunix.net/jh/25/601028.html】
仙子注:这篇文章是半年前翻译的,最早贴于公司内部的BBS上,并引起一些争论。Bloom Filters是一种效率较高的内存索引算法,它本身具有矛盾性:一方面能快速测试目标成员是否存在,另一方面又不可避免的具有假命中率。如下文档仅供参考。
由于不知道如何在这里粘贴图片,因此本文中没有包含图片说明,请对照原文档来阅读,原文档在:http://www.perl.com/pub/a/2004/04/08/bloom_filters.html?page=1 或可email给我索取中文PDF文档。

使用Bloom Filters

原作者:Maciej Ceglowski
April 08, 2004

任何perl使用者都熟悉hash查询,一个存在测试的语句可以这样写:

foreach my $e ( @things ) { $lookup{$e}++ }  sub check { my ( $key ) = @_; print "Found $key!" if exists( $lookup{ $key } ); }

虽然hash查询很有用,但对非常大的列表,或keys自身非常大时,这种查询可能变得不实用。当查询hash增长得太大,通常的做法是将它移到数据库或文件中,只在本地缓存里保存最常用的关键字,这样能改善性能。

许多人不知道有一种优雅的算法,用以代替hash查询。它是一种古老的算法,叫做Bloom filter。 Bloom filter允许你在有限的内存里(你想在这块内存里存放关键字的完整列表),执行成员测试,这样就能避开使用磁盘或数据库进行查询的性能瓶颈。也许你会 认为,空间的节省是有代价的:存在着可大可小的假命中率风险,并且一旦你增加key到filter后,就不能删除它。然而在许多情形下,这些局限是可接受 的,bloom filter能编制有用工具。(仙子注:例如代理服务器软件Squid就使用了bloom filter算法。)

例如,假如你运行了一个高流量的在线音乐存储站点,并且如果你已知歌曲存在,就可以通过仅获取歌曲信息的方法,来最大程度的减少数据库压力。你可以在启动时构建一个bloom filter,在试图执行昂贵的数据库查询前,可以用它执行快速的成员存在测试。

use Bloom::Filter;  my $filter = Bloom::Filter->new( error_rate => 0.01, capacity => $SONG_COUNT ); open my $fh, "enormous_list_of_titles.txt" or die "Failed to open: $!";  while (< $fh>) { chomp; $filter->add( $_ ); }  sub lookup_song { my ( $title ) = @_; return unless $filter->check( $title ); return expensive_db_query( $title ) or undef; }

在该示例里,该测试给出假命中的几率是1%,在假命中率情况下程序会执行昂贵的数据库索取操作,并最终返回空结果。尽管如此,你已避开了99%的昂 贵查询时间,仅使用了用于hash查询的一小片内存。更进一步,1%假命中率的filter,每个key的存储空间在2字节以下。这比你执行完整的 hash查询所需的内存少得多。

bloom filters在Burton Bloom之后命名,Burton Bloom 1970年首先在文档里描述了它们,文档名 Space/time trade-offs in hash coding with allowable errors.在那些内存稀少的日子里,bloom filters因其简洁而倍受重视。事实上,最早的应用之一是拼写检查程序。然而,由于有少数非常明显的特性,该算法特别适合社会软件应用。

因为bloom filters使用单向hash来存储数据,因此不可能在不做穷举搜索的情况下,重建filter里的keys列表。甚至这点看起来并非象很有用,既然来 自穷举搜索的假命中会覆盖掉真正的keys列表。所以bloom filters能在不向全世界广播完整列表的情况下,共享关于已有资料的信息。因为这个理由,它们在peer-to-peer应用中特别有用,在这个应用 中大小和隐私是重要的约束。

bloom filters如何工作

bloom filter由2部分组成:1套k hash函数,1个给定长度的位向量。选择位向量的长度,和hash函数的数量,依赖于我们想增加多少keys到设置中,以及我们能容忍的多高的假命中率。

bloom filter中所有的hash函数被配置过,其范围匹配位向量的长度。例如,假如向量是200位长,hash函数返回的值就在1到 200之间。在filter里使用高质量的hash函数相当重要,它保证输出等分在所有可能值上--hash函数里的“热点”会增加假命中率。(仙子注: 所谓“热点”是指结果过分频繁的分布在某些值上。)

要将某个key输入bloom filer中,我们在每个k hash函数里遍历它,并将结果作为在位向量里的offsets,并打开我们在该offsets上找到的任何位。假如该位已经设置,我们继续保留其打开。还没有在bloom filter里关闭位的机制。

在本示例里,让我们看看某个bloom filter,它有3个hash函数,并且位向量的长度是14。我们用空格和星号来表示位向量,以便于观察。你也许想到,空的bloom filter以所有的位关闭为开始,如图1所示。

图1:空的bloom filter

现在我们将字符apples增加到filter中去。为了做到这点,我们以apples为参数来运行每个hash函数,并采集输出:

hash1(“apples”) = 3
hash2(“apples”) = 12
hash3(“apples”) = 11

然后我们打开在向量里相应位置的位--在这里就是位3,11,和12,如图2所示。

图2:激活了3位的bloom filter

为了增加另1个key,例如plums,我们重复hash运算过程:

hash1(“plums”) = 11
hash2(“plums”) = 1
hash3(“plums”) = 8

再次打开向量里相应的位,如图3里的高亮度显示。

图3:增加了第2个key的bloom filter

注意位置11的位已被打开--在前面的步骤里,当我们增加apples时已设置了它。位11现在有双重义务,存储apples和plums两者的信 息。当增加更多的keys时,它也会存储其他keys的信息。这种交迭让bloom filters如此紧凑--任何位同时编码多个keys。这种交迭也意味着你永不能从filter里取出key,因为你不能保证你所关闭的位没有携载其他 keys的信息。假如我们试图执行反运算过程来从filter里删除apples,就会不经意的关闭编码plums的1个位。从bloom filter里剥离key的唯一方法是重建filter,剔除无用key。

检查是否某个key已经存在于filter的过程,非常类似于增加新key。我们在所有的hash函数里遍历key,然后检查是否在那些 offsets上的位都是打开的。假如任何一位关闭,我们知道该key肯定不存在于filter中。假如所有位都打开,我们知道该key可能存在。

我说“可能”是因为存在一种情况,该key是个假命中。例如,假如我们用字符mango来测试filter,看看会发生什么情况。我们运行mango遍历hash函数:

hash1(“mango”) = 8
hash2(“mango”) = 3
hash3(“mango”) = 12

然后检查在那些offsets上的位,如图4所示。

图4:bloom filter的假命中

所有在位置3,8,和12的位都是打开的,故filter会报告mango是有效key。

当然,mango并非有效key--我们构建的filter仅包含apples和plums。事实是mango的offsets非常巧合的指向了已激活的位。这就找到了1个假命中--某个key看起来位于filter中,但实际不是。

正如你想的一样,假命中率依赖于位向量的长度和存储在filter里的keys的数量。位向量越宽阔,我们检查的所有k位被打开的可能性越小,除非 该key确实存在于filter中。在hash函数的数量和假命中率之间的关系更敏感。假如使用的hash函数太少,在keys之间的差别就很少;但假如 使用hash函数太多,filter会过于密集,增加了冲突的可能性。可以使用如下公式来计算任何filter的假命中率:

c = ( 1 – e(-kn/m) )k

这里c是假命中率,k是hash函数的数量,n是filter里keys的数量,m是filter的位长。

当使用bloom filters时,我们先要有个意识,期待假命中率多大;也应该有个粗糙的想法,关于多少keys要增加到filter里。我们需要一些方法来验证需要多大的位向量,以保证假命中率不会超出我们的限制。下列方程式会从错误率和keys数量求出向量长度:

m = -kn / ( ln( 1 – c ^ 1/k ) )

请注意另1个自由变量:k,hash函数的数量。可以用微积分来得出k的最小值,但有个偷懒的方法来做它:

sub calculate_shortest_filter_length { my ( $num_keys, $error_rate ) = @_; my $lowest_m; my $best_k = 1;  foreach my $k ( 1..100 ) { my $m = (-1 * $k * $num_keys) /  ( log( 1 - ($error_rate ** (1/$k))));  if ( !defined $lowest_m or ($m < $lowest_m) ) { $lowest_m = $m; $best_k   = $k; } } return ( $lowest_m, $best_k ); }

为了给你直观的感觉,关于错误率和keys数量如何影响bloom filters的存储size,表1列出了一些在不同的容量/错误率组合下的向量size。

ErrorRate Keys RequiredSize Bytes/Key
1% 1K 1.87 K 1.9
0.1% 1K 2.80 K 2.9
0.01% 1K 3.74 K 3.7
0.01% 10K 37.4 K 3.7
0.01% 100K 374 K 3.7
0.01% 1M 3.74 M 3.7
0.001% 1M 4.68 M 4.7
0.0001% 1M 5.61 M 5.7

在Perl里构建bloom filter

为了构建1个工作bloom filter,我们需要1套良好的hash函数。这些容易解决--在CPAN上有几个优秀的hash算法可用。对我们的目的来说,较好的选择是 Digest::SHA1,它是强度加密的hash,用C实现速度很快。通过对不同值的输出列表进行排序,我们能使用该模块来创建任意数量的hash函 数。如下是构建唯一hash函数列表的子函数:

use Digest::SHA1 qw/sha1/;  sub make_hashing_functions { my ( $count ) = @_; my @functions;  for my $salt (1..$count ) { push @functions, sub { sha1( $salt, $_[0] ) }; }  return @functions; }

为了能够使用这些hash函数,我们必须找到1个方法来控制其范围。Digest::SHA1返回令人为难的过长160位hash输出,这仅在向量 长度为2的160次方时有用,而这种情况实在罕见。我们结合使用位chopping和division来将输出削减到可用大小。

如下子函数取某个key,运行它遍历hash函数列表,并返回1个长度($FILTER_LENGTH)的位掩码:

sub make_bitmask { my ( $key ) = @_; my $mask    = pack( "b*", '0' x $FILTER_LENGTH);  foreach my $hash_function ( @functions ){   my $hash       = $hash_function->($key); my $chopped    = unpack("N", $hash ); my $bit_offset = $result % $FILTER_LENGTH;  vec( $mask, $bit_offset, 1 ) = 1;        } return $mask; }

让我们逐行分析上述代码:

my $mask = pack( "b*", '0' x $FILTER_LENGTH);

我们以使用perl的pack操作来创建零位向量开始,它是$FILTER_LENGTH长。pack取2个参数,1个模型和1个值。b模型告诉 pack将值解释为bits,*指“重复任意多需要的次数”,跟正则表达式类似。perl实际上会补充位向量的长度为8的倍数,但我们将忽视这些多余位。

有1个空的位向量在手中,我们准备开始运行key遍历hash函数:

my $hash = $hash_function->($key); my $chopped = unpack("N", $hash );

我们保存首个32位输出,并丢弃剩下的。这点可让我们不必要求BigInt支持。第2行做实际的位chopping。模型里的N告诉unpack以网络字节顺序来解包32位整数。因为未在模型里提供任何量词,unpack仅解包1个整数,然后终止。

假如你对位chopping过度狂热,你可以将hash分割成5个32位的片断,并对它们一起执行OR运算,将所有信息保存在原始hash里:

my $chopped = pack( "N", 0 ); my @pieces  =  map { pack( "N", $_ ) } unpack("N*", $hash ); $chopped    = $_ ^ $chopped foreach @pieces;

但这样作可能杀伤力过度。

现在我们有了来自hash函数的32位整数输出的列表,下一步必须做的是,裁减它们的大小,以使其位于(1..$FILTER_LENGTH)范围内。

my $bit_offset = $chopped % $FILTER_LENGTH;

现在我们已转换key为位offsets列表,这正是我们所求的。

剩下唯一要做的事情是,使用vec来设置位,vec取3个参数:向量自身,开始位置,要设置的位数量。我们能象赋值给变量一样来分配值给vec:

vec( $mask, $bit_offset, 1 ) = 1;

在设置了所有位后,我们以1个位掩码来结束,位掩码和bloom filter长度一样。我们可以使用这个掩码来增加key到filter中:

sub add { my ( $key, $filter ) = @_;  my $mask = make_bitmask( $key ); $filter  = $filter | $mask; }

或者我们使用它来检查是否key已存在:

sub check { my ( $key, $filter ) = @_; my $mask  = make_bitmask( $key ); my $found = ( ( $filter & $mask ) eq $mask ); return $found; }

注意这些是位逻辑运算符OR(|)和AND(&),而并非通用的逻辑OR(||)和AND(&&)运算符。将这两者混在一 起,会导致数小时的有趣调试。第1个示例将掩码和位向量进行OR运算,打开任何未设置的位。第2个示例将掩码和filter里相应的位置进行比较--假如 掩码里所有的打开位也在filter里打开,我们知道已找到一个匹配。

一旦你克服了使用vec,pack和位逻辑运算符的难度,bloom filters实际非常简单。http://www.perl.com/2004/04/08/examples/Filter.pm 这里给出了Bloom::Filter模块的完整信息。

分布式社会网络中的bloom filters

当前的社会网络机制的弊端之一是,它们要求参与者泄露其联系列表给中央服务器,或公布它到公共Internet,这2种情况下都牺牲了大量的用户隐 私。通过交换bloom filters而不是暴露联系列表,用户能参与社会网络实践,而不用通知全世界他们的朋友是谁。编码了某人联系信息的 bloom filter能用来检查它是否包含了给定的用户名或email地址,但不能强迫要求它展示用于构建它的完整keys列表。甚至有可能将假命中率(虽然它听 起来不像好特性),转换为有用工具。

假如我非常关注这些人,他们通过对bloom filter运行字典攻击,来试图对社会网络进行反工程。我可以构建filter,它具备较高的假命中率(例如50%),然后发送filter的多个拷贝 给朋友,并变换用于构建每个filter的hash函数。我的朋友收集到的filters越多,他们见到的假命中率越低。例如,在5个filters情况 下,假命中率是0.5的5次方,或3%--通过发送更多filters,还能进一步减少假命中率。

假如这些filters中的任何一个被中途截取,它会展示全部50%的假命中率。所以我能隔离隐私风险,并且一定程度上能控制其他人能多清楚的

了解我的网络。我的朋友能较高程度的确认是否某个人位于联系列表里,但那些仅截取了1个或2个filters的人,几乎不会获取到什么。如下是个perl函数,它对1组嘈杂的filters检查某个key:

use Bloom::Filter;          sub check_noisy_filters { my ( $key, @filters ) = @_; foreach my $filter ( @filters ) { return 0 unless $filter->check( $key ); } return 1; }

假如你和你的朋友同意使用相同的filter长度和hash函数设置,你也能使用位掩码对比来估计在你们的社会网络之间的交迭程度。在2个bloom filters里的共享位数量会给出1个可用的距离度量。

sub shared_on_bits { my ( $filter_1, $filter_2 ) = @_; return unpack( "%32b*",  $filter_1 & $filter_2 ) }

另外,你能使用OR运算,结合2个有相同长度和hash函数的bloom filters来创建1个复合filter。例如,假如你参与某个小型邮件列表,并希望基于组里每个人的地址本来创建白名单,你可以为每个参与者独立的创 建1个bloom filter,然后将filters一起进行OR运算,将结果输入Voltron-like主列表。组里成员不会了解到其他成员的联系信息,并且 filter仍能展示正确的行为。

肯定还有其他针对社会网络和分布式应用的bloom filter妙用。如下参考列出一些有用资源。

参考
· Bloom Filters — the math. A good place to start for an overview of the math behind Bloom filters.
· Some Motley Bloom Tricks. Handy filter tricks and theory page.
· Bloom Filter Survey. A handy survey article on Bloom filter network applications.
· LOAF. Our own system for incorporating social networks onto email using Bloom filters.
· Compressed Bloom Filters. If you are passing filters around a network, you will want to optimize them for minimum size; this paper gives a good overview of compressed Bloom filters.
· Bloom16. A CPAN module implementing a counting Bloom filter.
· Text::Bloom. CPAN module for using Bloom filters with text collections.
· Privacy-Enhanced Searches Using Encryted Bloom Filters. This paper discusses how to use encryption and Bloom filters to set up a query system that prevents the search engine from knowing the query you are running.
· Bloom Filters as Summaries. Some performance data on actually using Bloom filters as cache summaries.
· Using Bloom Filters for Authenticated Yes/No Answers in the DNS. Internet draft for using Bloom filters to implement Secure DNS




本站采用创作共享版权协议, 要求署名、非商业和保持一致. 本站欢迎任何非商业应用的转载, 但须注明出自"易栈网-膘叔", 保留原始链接, 此外还必须标注原文标题和链接.

« 上一篇 | 下一篇 »

发表评论

评论内容 (必填):