当前位置：首页 > article >正文

Level DB --- BloomFilterPolicy

article 2025/1/7 17:18:19

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 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; 
}

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 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].
      uint32_t h = BloomHash(keys[i]); /*hash 值计算*/
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (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 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; /*如果有一次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里面进行检索、验证。

查看全文

http://www.kler.cn/a/468645.html