原译：使用Bloom Filters

仙子注：这篇文章是半年前翻译的，最早贴于公司内部的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,?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妙用。如下参考列出一些有用资源。