BloomFilterPolicy类
源文件位置
util/bloom.cc
优点：相对于其他表示数据集的数据结构，如平衡二叉搜索树、Trie 树、哈希表，甚至更简单的数组或者链表，Bloom Filter有着巨大的时空优势。上述提到的表示数据集的数据结构，大都需要对数据项本身存储，可能有的做了压缩，比如Trie 树。但是Bloom Filter并不存储数据项本身，而是存储数据项的几个哈希值，并且用高效紧凑的位数组来存，避免了指针的额外开销，除此之外，Bloom Filter所需内存大小于数据项本身大小无关。
缺点：仅适用于判断目标数据是否在集合中的场景，并且存在误判的可能。
误判率
Bloom Filter误判率与下述因素相关：
1、哈希函数的个数k
2、底层位数组的长度m
3、数据集大小n
当k = ln2 * (m / n)时，Bloom Filter具备最优的准确率。
其中m / n即bits per key(集合中每个key平均分到的bit数)
接口定义
// 过滤策略的名称，用于唯一标识此Filter持久化、载入内存时的编码方法
const char* Name() const override；
// 为长度为n的keys集合(可能存在重复)创建过滤策略，并将策略序列化为string，追加到dst之后
void CreateFilter(const Slice* keys, int n, std::string* dst) const override;
// 过滤函数，若调用CreateFilter时传入的集合为keys，则如果key不在keys中，则返回false
bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override;
const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);
私有成员变量
size_t bits_per_key_; // 每个key平均分到的bit数
size_t k_; // 哈希函数的个数
构造函数/析构函数
explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
// 依据Bloom Filter具备最优准确率的结论(k = ln2 * (m / n))，获取哈希函数的个数k
// 此处对k向下取整、限制最小值、最大值，会导致误判率增加，但同样降低了过滤成本
// We intentionally round down to reduce probing cost a little bit
k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)
if (k_ < 1) k_ = 1;
if (k_ > 30) k_ = 30;
}
关键接口
void CreateFilter(const Slice* keys, int n, std::string* dst) const override;
// 为长度为n的keys集合(可能存在重复)创建过滤策略，并将策略序列化为string，追加到dst之后 void CreateFilter(const Slice* keys, int n, std::string* dst) const override { // 计算Bloom Filter的bit数组长度 // Compute bloom filter size (in both bits and bytes) size_t bits = n * bits_per_key_; // For small n, we can see a very high false positive rate. Fix it // by enforcing a minimum bloom filter length. if (bits < 64) bits = 64; // 位数组过短会导致误判率较高，因此位数组长度最低为64 // 由于最终使用char数组进行保存，需要对齐为8的倍数 size_t bytes = (bits + 7) / 8; bits = bytes * 8; const size_t init_size = dst->size(); dst->resize(init_size + bytes, 0); dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter 记录下哈希函数的个数 char* array = &(*dst)[init_size]; for (int i = 0; i < n; i++) { // Use double-hashing to generate a sequence of hash values. // See analysis in [Kirsch,Mitzenmacher 2006]. // 通过double-hashing法，仅通过单个hash函数来生成k个hash值，近似于通过k个哈希函数生成k个哈希值 uint32_t h = BloomHash(keys[i]); const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits 循环右移17bit作为步长 for (size_t j = 0; j < k_; j++) { const uint32_t bitpos = h % bits; array[bitpos / 8] |= (1 << (bitpos % 8)); h += delta; } } }
bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override;
// 过滤函数，若调用CreateFilter时传入的集合为keys，则如果key不在keys中，则返回false bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override { const size_t len = bloom_filter.size(); if (len < 2) return false; const char* array = bloom_filter.data(); const size_t bits = (len - 1) * 8; // -1是去掉k所占的空间 // Use the encoded k so that we can read filters generated by // bloom filters created using different parameters. // 取出创建Filter时保存的哈希函数个数k const size_t k = array[len - 1]; if (k > 30) { // Reserved for potentially new encodings for short bloom filters. // Consider it a match. // 超出设定k的最大值，直接返回true return true; } uint32_t h = BloomHash(key); const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits 循环右移作为步长 for (size_t j = 0; j < k; j++) { const uint32_t bitpos = h % bits; if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false; h += delta; } return true; }