BloomFilterPolicy是Level DB中重要的数据过滤模块，它主要用来先过滤在Block中不存在的key，减少Block的搜索计算量。
Bloom Filter
从原理上来讲Bloom FIlter相对来说原理还是比较简单的，将一个key经过一次（组合）hash，将hash值映射到bit array的某一个位置上置为1，这样的操作经过k次，一个key 就可以在bit array的k个位置置为1，同样的操作应用到一个 key set上。 这样经过上述的计算，如果再来一个key，将这个key用同样的（组合）hash k 次， 如果有一次在hash array的映射位置检查该位置不为1，那么可以证明这个key不在key set里面。
图1是Level DB中的Bloom Filter的内存结构，这里面的k_就是上段中提到的k次hash的k。而bits_per_key_决定了bit array的大小。很明显，bits_per_key_值越大，bit array越大，相同的hash值碰撞的几率越小，但是需要的内存也越大。
图1. Bloom Hash Memory
代码核心
BloomFilterPolicy
BloomFilterPolicy的构造函数接收bits_per_key值，它决定了bit array 的大小，同时k_也由这个值决定。
explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {// We intentionally round down to reduce probing cost a little bitk_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)if (k_ < 1) k_ = 1;if (k_ > 30) k_ = 30;
}CreateFilter
CreateFilter主要用来根据输入的key set，计算bloom hash bit array。细节如下注释：
void CreateFilter(const Slice* keys, int n, std::string* dst) const override {// Compute bloom filter size (in both bits and bytes)size_t bits = n * bits_per_key_; /*hash bit array 大小计算*/// 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;size_t bytes = (bits + 7) / 8; /*换成bytes大小，向下取整*/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 filterchar* 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].uint32_t h = BloomHash(keys[i]); /*hash 值计算*/const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bitsfor (size_t j = 0; j < k_; j++) { /*k_次hash ， 选择k_个bit array 的位置，set为1*/const uint32_t bitpos = h % bits;array[bitpos / 8] |= (1 << (bitpos % 8));h += delta;}}
}KeyMayMatch
KeyMayMatch，用来计算生成bloom filter bit array后，当输入一个新key，判断这个key是否在之前的key set里面。细节如下注释：
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;// Use the encoded k so that we can read filters generated by// bloom filters created using different parameters.const size_t k = array[len - 1];if (k > 30) { /*这种情况不会发生，因为在构造函数中k_在[1, 30]范围内*/// Reserved for potentially new encodings for short bloom filters.// Consider it a match.return true;}uint32_t h = BloomHash(key);const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bitsfor (size_t j = 0; j < k; j++) {const uint32_t bitpos = h % bits;if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false; /*如果有一次hash bit 没有对上，可以证明这个key不在之前key set里面*/h += delta;}return true;
}总结
Level DB中实现的Bloom Filter计算代码不长，但是里面涉及到的bit计算还是很简洁的。一个Block会存储大量的key，所以一个Block的bit array占用内存的空间还是比较大的，但是Bloom Filter也大量减少了Block的检索的计算。当KeyMayMatch返回false，证明这个key一定不在Block里面，直接返回即可;当KeyMayMatch返回true，可以继续再在Block里面进行检索、验证。
