Bloom Filter 和 Cuckoo Filter 的源码简析

Bloom Filter 和 Cuckoo Filter有类似的用途,很多人将它们称为概率数据结构或者近似成员数据结构(approximate membership data structure)。最近看了一个Bloom Filter和一个Cuckoo Filter的比较好的实现,代码都是用C++实现,代码量也不大,读起来没有什么难度。

本文贴出来的是两个项目的大体构成,不涉及到空间、错误率等的理论分析,希望能给需要的新手一些帮助。

两个项目的网址如下:

1. Bloom Filter

(https://code.google.com/p/bloom/)

源码目录:

文件包括三个用于测试example、三个用于测试insert的txt词典,bloom filter的实现在bloom_filter.hpp中。

bloom_filter.hpp中包括3个class:bloom_parametersbloom_filtercompressible_bloom_filter。其中bloom_parameters是构建一个BF需要的参数,compressible_bloom_filter 类继承自bloom_filter类。

1.1 bloom_filter.hpp

  • bloom_parameters

包含的成员:

  • bloom_filter

  • compressible_bloom_filter

1.2 example01

  1. 设置目标元素为10000个,false postive为0.5%,然后计算最优的参数,并生成一个BF。(这时BF需要13794 Bytes,需要8个函数)
  2. 往里面插入3个string字符串和100个int数字。
  3. 测试contains方法,看里面是否有刚才插入的3个string和100个int。
  4. 测试contains,查找3个不存在的string的100个不存在的int。

1.3 example02

1.4 example03

是关于压缩bloom filter的测试。(略)

2. Cuckoo Filter

(https://github.com/efficient/cuckoofilter)

文件:

2.1 Example和Benchmarks

example中一个最简单的test.cc是一个最简单的功能测试。

benchmarks文件夹中有bulk-insert-and-queryconext-figure5conext-table3三个benchmarks。具体的:

  1. bulk-insert-and-query:用argv[1]个随机生成的元素批量Add到filter中测试insert操作,并用指定成功率(比如75%成功率每4个有一个应该是没有insert过的元素)的Contain()来测试lookup操作。

    统计的信息包括:bulk insert和bulk query的速率(每秒多少次)。输出示例:

测试的几种filter包括:cuckoo、semisort、semblock,每种每个元素又用不同的bits表示。

  1. conext-figure5conext-table3是作者CoNEXT会议上论文的对应figure5和table3两张图。

    figure5:当filter满时的查找性能。

    table3: 相同大小和近似元素数的filter的false positive率和构建(插入?)速度。

2.2 具体实现

src文件夹是具体实现:

  • cuckoofilter.h:

    定义了模板类CuckooFilter,并定义了几个public方法:Add、Contain、Delete、Info、Size和SizeInBytes。

如上图,创建一个cuckoofilter需要2~4个参数,其中元素的类型和每个元素指纹所占的bits数是必要的两个参数,后两个参数分别表示table 的类型和hash函数的类型,都有默认值。其中table类型中,SingleTable即普通的cuckoofilter,PackedTable即经过semi-sorting压缩过的cuckoofilter,可以节省一些空间。

下面是Add方法的实现,其中又调用了AddImpl方法。

  • singletable.h和packedtable.h:

在cuckoofilter.h中的模板类中,有一个cuckoo哈希表的类型可以选择,即未压缩的SingleTable和用semi-sorting压缩过的PackedTable,对应的类分别定义在singletable.hpackedtable.h两个文件中。

以SingleTable为例,有NumBuckets、SizeInBytes、SizeInTags、Info、ReadTag、WriteTag、FindTagInBuckets、FindTagInBucket、DeleteTagFromBucket、InsertTagToBucket、NumTagsInBucket等方法,用途可顾名思义。

  • simd-block.h

这是一个block bloom filter的实现 (Putze, Felix, Peter Sanders, and Johannes Singler. “Cache-, hash-and space-efficient bloom filters.” International Workshop on Experimental and Efficient Algorithms. Springer, Berlin, Heidelberg, 2007.):

(1)每个block 是一个小的BF,且

(2)每个Add()操作锁带来的bit修改是一定数量的,来保证可以用SIMD指令加速。

  • hashutil.h

包含了好几个把item哈希到32bit指纹的哈希函数实现:Bobhash、MurmurHash、SuperFastHash、NullHash、MD5Hash、SHA1Hash。后两种直接调用了OpenSSL的evp库。

发表评论

电子邮件地址不会被公开。 必填项已用*标注