Perl高效率健值判断模块之Bloom::Filter
2013-08-05 15:55:47 阿炯
该模块是一个大数据处理的模块，用于取代hash判断键是否存在的算法，它允许很低的重复来换取高效率与低内存使用量，同时不需要借助于第三方式辅助实现(比如使用memache来存放对应的结果)。

Bloom::Filter - Sample Perl Bloom filter implementation

用于比较数据是否存在在已知列表中。布隆过滤(Bloom Filter)是一种效率较高的内存索引算法，它本身具有矛盾性：一方面能快速测试目标成员是否存在，另一方面又不可避免的具有假命中率。

如果要索引的样本数量巨大，全部放在 hash 表里，在内存中肯定放不下。因此采用一种概率的方式，用一个短一些的串来记录，把所有的key 分别通过一组 hash 函数，来映射到串上，标记为1(初始都为0)，这样就建立了一个可供检索的filter。 

查询某个给定值是否存在时，让他通过所有的hash函数，找到串上对应的位置，如果对应位置上都标记为 1，则这个值“可能”存在，如果有一个位标记不为1，则这个值“肯定”不存在。

Bloom filter允许你在有限的内存里(你想在这块内存里存放关键字的完整列表)，执行成员测试，这样就能避开使用磁盘或数据库进行查询的性能瓶颈。

因为bloom filters使用单向hash来存储数据，因此不可能在不做穷举搜索的情况下，重建filter里的keys列表。甚至这点看起来并非象很有用，既然来自穷举搜索的假命中会覆盖掉真正的keys列表。

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

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

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

如果对现有的bloom filter的效率还是不满，可以尝试一下使用c开发的Bloom-Faster模块。

参考文档

Bloom::Filter
原译：使用Bloom Filters