LevelDB 源码分析【5】—— BloomFilter

在之前的 SSTable 中的逻辑结构中，可以看到 Filter Block，它用于减少读放大，提高读取的效率。在 Leveldb 源码中，可以看到它使用了 FilterPolicy 这个类来表示抽象的过滤策略，体现了一种依赖于抽象而不是具体的依赖倒转原则。

而 Leveldb 默认的过滤策略就是布隆过滤器（bloom filter）；leveldb 中利用布隆过滤器判断指定的 key 值是否存在于 sstable 中，若过滤器表示不存在，则该 key 一定不存在，由此加快了查找的效率。

该数据结构的详细介绍参看布隆过滤器；我们的工作还是主要关注 Leveldb 源码是怎么实现 Bloom Filter 的；

但有一些重要的点还是要说一下，和 bloom filter 的效率相关的参数：

hash 函数个数 k
布隆过滤器位数组的容量 m
布隆过滤器插入的 key 的数量 n

主要的数学结论有：

为了获得最优的准确率，当k = ln2 * (m/n)时，布隆过滤器获得最优的准确性；
在哈希函数的个数取到最优时，要让错误率不超过є，m至少需要取到最小值的1.44倍；

FilterPolicy

首先来看下过滤策略的抽象接口该怎么设计。

class FilterPolicy {
    virtual const char* Name() const = 0;
    virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const = 0;
    virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0;
};

const const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);

FilterPolicy::CreateFilter 的参数是一个 Slice 数组，里面是已经有序的 keys（根据用户提供的 comparator），该方法会把 keys 中的每一个 key 经过计算，最终得到一个过滤结果，并把它 append 到 dst 中去；这里 Leveldb 为了性能考虑，竟然用了 std::string*，因此方法中不能对原来的 string 进行 in-place write，只能进行 append，不然会出错。

FilterPolicy::KeyMayMatch 能够根据 filter 返回给定 key 是否在 keys 中。

Bloom Filter

来看下 bloom filter 具体是怎么实现的。

static uint32_t BloomHash(const Slice& key) {
  return Hash(key.data(), key.size(), 0xbc9f1d34);
}

class BloomFilterPolicy : public FilterPolicy {
 public:
  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;
  }

  const char* Name() const override { return "leveldb.BuiltinBloomFilter2"; }

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

    // 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;
    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]);
      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;
        array[bitpos / 8] |= (1 << (bitpos % 8));
        h += delta;
      }
    }
  }

  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) {
      // 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;
      h += delta;
    }
    return true;
  }

 private:
  size_t bits_per_key_;
  size_t k_;
};

首先你得有一个普通的 Hash 函数，用 std::hash 就可以了，Leveldb 则是自己实现的；CreateFilter 和 KeyMayMatch 的流程十分相似，它们都要：

根据 key 和 Hash 函数得到 32位 hash 值 h
翻转 h 的高15 位和低 17 位得到 delta
循环 k_ 次，每一次都让 h 对 bits 取余，并通过 delta 更新 h

唯一的区别在于，CreateFilter 会把 k_ 次取余的结果写到 filter 中去；而 KeyMayMatch 是从 filter 中读数据，并判断是否和取余得到的结果匹配；

在构造函数里，根据上面的数学公式，可以推断出，bits_per_key = m/n，这样 k_ = log2*bits_per_key；

leveldb 源码分析 [5] —— BloomFilter

LevelDB 源码分析【5】—— BloomFilter

FilterPolicy

Bloom Filter