ToC
Bloom Filter 和 Cuckoo Filter有类似的用途，很多人将它们称为概率数据结构或者近似成员数据结构(approximate membership data structure)。最近看了一个Bloom Filter和一个Cuckoo Filter的比较好的实现，代码都是用C++实现，代码量也不大，读起来没有什么难度。
本文贴出来的是两个项目的大体构成，不涉及到空间、错误率等的理论分析，希望能给需要的新手一些帮助。
两个项目的网址如下：
- C++ Bloom filter library: https://code.google.com/p/bloom/
- Cuckoo Filter: https://github.com/efficient/cuckoofilter
1. Bloom Filter
(https://code.google.com/p/bloom/)
源码目录：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
$ tree . ├── Makefile ├── bloom_filter.hpp ├── bloom_filter_example01.cpp ├── bloom_filter_example02.cpp ├── bloom_filter_example03.cpp ├── random-list.txt ├── word-list-extra-large.txt ├── word-list-large.txt └── word-list.txt |
文件包括三个用于测试example、三个用于测试insert的txt词典，bloom filter的实现在bloom_filter.hpp中。
bloom_filter.hpp中包括3个class：bloom_parameters、bloom_filter和compressible_bloom_filter。其中bloom_parameters是构建一个BF需要的参数，compressible_bloom_filter 类继承自bloom_filter类。
1.1 bloom_filter.hpp
- bloom_parameters
包含的成员：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// BF所允许的最小、最大bit数 unsigned long long int minimum_size; unsigned long long int maximum_size; // BF所允许的最小、最大哈希函数 unsigned int minimum_number_of_hashes; unsigned int maximum_number_of_hashes; // 预计要插入的元素数，默认为10000 unsigned long long int projected_element_count; // 预计的false positive概率，默认为projected_element_count的倒数 double false_positive_probability; unsigned long long int random_seed; // 以下关于“最优参数”的结构和方法计算限制projected_element_count和 // false_positive_probability条件下最小的bit数和最小的哈希函数数 struct optimal_parameters_t { ... }; optimal_parameters_t optimal_parameters; virtual bool compute_optimal_parameters() { ... } |
- bloom_filter
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
protected: typedef unsigned int bloom_type; typedef unsigned char cell_type; public: //构造函数1，无参数，默参数默认都为0 bloom_filter() :... {} // 构造函数2，传入的参数为一个bloom_parameters对象， // 会根据对象中的optimal_parameters结构中的参数初始化一个BF bloom_filter(const bloom_parameters& p) :... { salt_count_ = p.optimal_parameters.number_of_hashes; table_size_ = p.optimal_parameters.table_size; generate_unique_salt(); raw_table_size_ = table_size_ / bits_per_char; bit_table_ = new cell_type[static_cast<std::size_t>(raw_table_size_)]; std::fill_n(bit_table_,raw_table_size_,0x00); } // 构造函数3，参数是另一个bloom filtrer bloom_filter(const bloom_filter& filter) :... { this->operator=(filter); } // 一些运算符重载 inline bool operator == (const bloom_filter& f) const {...} inline bool operator != (const bloom_filter& f) const {...} inline bloom_filter& operator = (const bloom_filter& f) {...} inline bool operator!() const {...} // 析构函数 virtual ~bloom_filter() {...} // 清空BF inline void clear() { std::fill_n(bit_table_,raw_table_size_,0x00); inserted_element_count_ = 0; } // 一些insert方法，参数不同 inline void insert(const unsigned char* key_begin, const std::size_t& length) { std::size_t bit_index = 0; std::size_t bit = 0; for (std::size_t i = 0; i < salt_.size(); ++i) { compute_indices(hash_ap(key_begin,length,salt_[i]),bit_index,bit); bit_table_[bit_index / bits_per_char] |= bit_mask[bit]; } ++inserted_element_count_; } template<typename T> inline void insert(const T& t) {...} inline void insert(const std::string& key) {...} inline void insert(const char* data, const std::size_t& length) {...} template<typename InputIterator> inline void insert(const InputIterator begin, const InputIterator end) {...} // 一些contains(即BF lookup)方法 inline virtual bool contains(const unsigned char* key_begin, const std::size_t length) const {...} template<typename T> inline bool contains(const T& t) const {...} inline bool contains(const std::string& key) const {...} inline bool contains(const char* data, const std::size_t& length) const {...} template<typename InputIterator> inline InputIterator contains_all(const InputIterator begin, const InputIterator end) const {...} inline InputIterator contains_none(const InputIterator begin, const InputIterator end) const {...} // size方法，返回BF所占空间 inline virtual unsigned long long int size() const { return table_size_; } // element_count方法，返回BF总共所插入的元素 inline std::size_t element_count() const { return inserted_element_count_; } // 返回当前计算的false positive 概率，而不是目标概率。 inline double effective_fpp() const {...} // 一些运算符重载 inline bloom_filter& operator &= (const bloom_filter& f) {...} inline bloom_filter& operator |= (const bloom_filter& f) {...} inline bloom_filter& operator ^= (const bloom_filter& f) {...} // 返回BF地址 inline const cell_type* table() const { return bit_table_; } // 返回所用哈希函数数量 inline std::size_t hash_count() { return salt_.size(); } // 给定一个哈希值，计算素应该置位BF中哪些bits inline virtual void compute_indices(const bloom_type& hash, std::size_t& bit_index, std::size_t& bit) const { bit_index = hash % table_size_; bit = bit_index % bits_per_char; } // 生成哈希函数 void generate_unique_salt() {...} // 计算一个元素的哈希值 inline bloom_type hash_ap(const unsigned char* begin, std::size_t remaining_length, bloom_type hash) const {...} |
compressible_bloom_filter
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// 构造函数，通过一个bloom_parameters对象构造可以压缩的BF compressible_bloom_filter(const bloom_parameters& p) : bloom_filter(p) { size_list.push_back(table_size_); } // 返回BF的大小 inline unsigned long long int size() const {...} // 压缩，参数是个小于1的数，即压缩后是占原来的大小的百分比 // 压缩的方法是将被压缩部分的bits置位到前面，这样会减小大小，但是提升false postive inline bool compress(const double& percentage) {...} // 计算大小 inline void compute_indices(const bloom_type& hash, std::size_t& bit_index, std::size_t& bit) const {...} |
1.2 example01
- 设置目标元素为10000个，false postive为0.5%，然后计算最优的参数，并生成一个BF。(这时BF需要13794 Bytes，需要8个函数)
- 往里面插入3个string字符串和100个int数字。
- 测试contains方法，看里面是否有刚才插入的3个string和100个int。
- 测试contains，查找3个不存在的string的100个不存在的int。
1.3 example02
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
// 从txt文件中读出要插入的word load_word_list(argc,argv,word_list)) // 生成outliers generate_outliers(word_list,outliers); // 计算单词表一共占多大空间，存到word_list_storage_size变量中。 for (unsigned int i = 0; i < word_list.size(); ++i) { word_list_storage_size += word_list[i].size(); } // 指定一个false positive率 const double desired_probability_of_false_positive = 1.0 / word_list.size(); // /* Terminology MinFPC : Minimum (smallest) False Positive Count MaxFPC : Maximum (largest) False Positive Count AverageFPC : Average False Positive Count AverageFPP : Average False Positive Probability FPQ : False Positive Queries IPFP : Indicative (desired) False Positive Probability PFP : Probability of a False Positive (based on the FPQ) DPFP : Difference as a percentage between IPFP and PFP TvD : percentage of the filter size versus the raw data size */ printf("Round\t Queries\t FPQ\t IPFP\t PFP\t DPFP\t TvD\n"); unsigned int max_false_positive_count = 0; unsigned int min_false_positive_count = std::numeric_limits<unsigned int>::max(); unsigned int total_false_positive = 0; unsigned int total_zero_fp = 0; unsigned long long int bloom_filter_size = 0; static const unsigned int rounds = 1000; // 以1~1000 作为随机种子。 while (random_seed < rounds) { // 设置参数：目标元素数和false positive bloom_parameters parameters; parameters.projected_element_count = word_list.size(); parameters.false_positive_probability = desired_probability_of_false_positive; parameters.random_seed = ++random_seed; if (!parameters) { std::cout << "Error - Invalid set of bloom filter parameters!" << std::endl; return 1; } // 计算最优BF大小等参数 parameters.compute_optimal_parameters(); // 初始化BF bloom_filter filter(parameters); // 插入word_list的所有词 filter.insert(word_list.begin(),word_list.end()); // lookup所有已经插入的词，并打印没有找到的元素，一般这情况不会发生 std::vector<std::string>::iterator it = filter.contains_all(word_list.begin(),word_list.end()); if (word_list.end() != it) { std::cout << "ERROR: key not found in bloom filter! =>" << (*it) << std::endl; return 1; } // lookup一些未插入的词，统计false positive个数 unsigned int current_total_false_positive = 0; for (std::deque<std::string>::iterator it = outliers.begin(); it != outliers.end(); ++it) { if (filter.contains(*it)) { ++current_total_false_positive; } } total_number_of_queries += (outliers.size() + word_list.size()); // 计算false positive率 double pfp = current_total_false_positive / (1.0 * outliers.size()); printf("%6llu\t%10llu\t%6d\t%8.7f\t%8.7f\t%9.3f%%\t%8.6f\n", static_cast<unsigned long long>(random_seed), static_cast<unsigned long long>(total_number_of_queries), current_total_false_positive, desired_probability_of_false_positive, pfp, (100.0 * pfp) / desired_probability_of_false_positive, (100.0 * filter.size()) / (bits_per_char * word_list_storage_size)); // 记录多个rounds中最小和最大的false positve个数 if (current_total_false_positive < min_false_positive_count) min_false_positive_count = current_total_false_positive; else if (current_total_false_positive > max_false_positive_count) max_false_positive_count = current_total_false_positive; total_false_positive += current_total_false_positive; if (0 == current_total_false_positive) ++total_zero_fp; bloom_filter_size = filter.size(); } // 平均每个round的false positive个数和百分比 double average_fpc = (1.0 * total_false_positive) / rounds; double average_fpp = average_fpc / (outliers.size() + word_list.size()); // 打印最小、最大的false positive数、平均FP百分率、无FP的round的百分比 // 打印BF的大小、 所插入数据的总大小 printf("Bloom Filter Statistics\n" "MinFPC: %d\tMaxFPC: %d\tAverageFPC: %8.5f\tAverageFPP: %9.8f Zero-FPC:%d\n" "Filter Size: %lluKB\tData Size: %dKB\n", min_false_positive_count, max_false_positive_count, average_fpc, average_fpp, total_zero_fp, bloom_filter_size / (8 * 1024), static_cast<unsigned int>(word_list_storage_size / 1024)); return 0; |
1.4 example03
是关于压缩bloom filter的测试。(略)
2. Cuckoo Filter
(https://github.com/efficient/cuckoofilter)
文件：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
$ tree . ├── LICENSE ├── Makefile ├── README.md ├── benchmarks │ ├── Makefile │ ├── bulk-insert-and-query.cc │ ├── conext-figure5.cc │ ├── conext-table3.cc │ ├── random.h │ └── timing.h ├── example │ └── test.cc └── src ├── bitsutil.h ├── cuckoofilter.h ├── debug.h ├── hashutil.cc ├── hashutil.h ├── packedtable.h ├── permencoding.h ├── printutil.cc ├── printutil.h ├── simd-block.h └── singletable.h |
2.1 Example和Benchmarks
example中一个最简单的test.cc是一个最简单的功能测试。
benchmarks文件夹中有bulk-insert-and-query、conext-figure5和conext-table3三个benchmarks。具体的：
- bulk-insert-and-query：用argv[1]个随机生成的元素批量Add到filter中测试insert操作，并用指定成功率(比如75%成功率每4个有一个应该是没有insert过的元素)的Contain()来测试lookup操作。
统计的信息包括：bulk insert和bulk query的速率(每秒多少次)。输出示例：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Million Find Find Find Find Find optimal wasted adds/sec 0% 25% 50% 75% 100% ε bits/item bits/item space Cuckoo12 23.78 37.24 35.04 37.17 37.35 36.35 0.131% 18.30 9.58 91.1% SemiSort13 11.63 17.55 17.08 17.14 17.54 22.32 0.064% 18.30 10.62 72.4% Cuckoo8 35.31 49.32 50.24 49.98 48.32 50.49 2.044% 12.20 5.61 117.4% SemiSort9 13.99 22.23 22.78 22.13 23.16 24.06 1.207% 12.20 6.37 91.5% Cuckoo16 27.06 36.94 37.12 35.31 36.81 35.10 0.009% 24.40 13.46 81.4% SemiSort17 10.37 15.70 15.84 15.78 15.55 15.93 0.004% 24.40 14.72 65.8% SimdBlock8 74.22 72.34 74.23 74.34 74.69 74.32 0.508% 12.20 7.62 60.1% time: 14.34 seconds |
测试的几种filter包括：cuckoo、semisort、semblock，每种每个元素又用不同的bits表示。
conext-figure5和conext-table3是作者CoNEXT会议上论文的对应figure5和table3两张图。figure5：当filter满时的查找性能。table3： 相同大小和近似元素数的filter的false positive率和构建(插入？)速度。
2.2 具体实现
src文件夹是具体实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
├── bitsutil.h -----> 一些位操作的宏定义 ├── cuckoofilter.h -----> cuckoofilter的实现 ├── debug.h -----> 一些用于DEBUG信息的宏定义 ├── hashutil.cc -----> 用于求指纹的几种哈希函数的实现 ├── hashutil.h --/ ├── packedtable.h -----> PackedTable类 ├── permencoding.h --/ ├── printutil.cc -----> 用于打印的封装 ├── printutil.h --/ ├── simd-block.h -----> SIMD优化的block bloom filter的实现 └── singletable.h -----> SingleTable类 |
- cuckoofilter.h：
定义了模板类CuckooFilter，并定义了几个public方法：Add、Contain、Delete、Info、Size和SizeInBytes。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// A cuckoo filter class exposes a Bloomier filter interface, // providing methods of Add, Delete, Contain. It takes three // template parameters: // ItemType: the type of item you want to insert // bits_per_item: how many bits each item is hashed into // TableType: the storage of table, SingleTable by default, and // PackedTable to enable semi-sorting template <typename ItemType, size_t bits_per_item, template <size_t> class TableType = SingleTable, typename HashFamily = TwoIndependentMultiplyShift> class CuckooFilter { ... } |
如上图，创建一个cuckoofilter需要2~4个参数，其中元素的类型和每个元素指纹所占的bits数是必要的两个参数，后两个参数分别表示table 的类型和hash函数的类型，都有默认值。其中table类型中，SingleTable即普通的cuckoofilter，PackedTable即经过semi-sorting压缩过的cuckoofilter，可以节省一些空间。
下面是Add方法的实现，其中又调用了AddImpl方法。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
template <typename ItemType, size_t bits_per_item, template <size_t> class TableType, typename HashFamily> Status CuckooFilter<ItemType, bits_per_item, TableType, HashFamily>::Add( const ItemType &item) { size_t i; uint32_t tag; if (victim_.used) { return NotEnoughSpace; } GenerateIndexTagHash(item, &i, &tag); // 生成item的index(位置/桶号)和tag(指纹) return AddImpl(i, tag); // 调用AddImpl进行insert } template <typename ItemType, size_t bits_per_item, template <size_t> class TableType, typename HashFamily> Status CuckooFilter<ItemType, bits_per_item, TableType, HashFamily>::AddImpl( const size_t i, const uint32_t tag) { size_t curindex = i; uint32_t curtag = tag; uint32_t oldtag; for (uint32_t count = 0; count < kMaxCuckooCount; count++) { // kickout 过程 bool kickout = count > 0; oldtag = 0; if (table_->InsertTagToBucket(curindex, curtag, kickout, oldtag)) { num_items_++; return Ok; } if (kickout) { curtag = oldtag; } curindex = AltIndex(curindex, curtag); // AltIndex找到当前桶号对应的另一个桶位置 } victim_.index = curindex; victim_.tag = curtag; victim_.used = true; return Ok; } |
- singletable.h和packedtable.h：
在cuckoofilter.h中的模板类中，有一个cuckoo哈希表的类型可以选择，即未压缩的SingleTable和用semi-sorting压缩过的PackedTable，对应的类分别定义在singletable.h和packedtable.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库。