布隆过滤器

布隆过滤器 leveldb

昨天在看leveldb的时候再次看到布隆过滤器。决定今天要看下这个这个东西,于是在网上找了几篇介绍的文章。

参考文章

从文章看来《数学之美》里面已经对这个算法有过详细介绍了。布隆过滤器用于判断一个元素是否在集合中。

  • 优点:速度快,空间使用率高
  • 缺点:存在False Position情况,不在集合中的元素有概率会被判断成在集合中

使用场景

  1. 加速查询,比如减少数据库磁盘操作。判断一个元素是否存在于数据库中,如果不存在则可以不用从磁盘中读取数据了
  2. 垃圾邮件地址。黑名单数据较多,存放在链表结构中查询速度慢,如果放在Hash表中则空间使用率较低。使用布隆过滤器,会造成一定误判。

    而至于误判问题,常见的补救办法是在建立一个小的白名单,存储那些可能别误判的邮件地址。

原理

一个empty bloom filter是一个有m bits的bit array,每一个bit位都初始化为0。并且定义有k个不同的hash function,每个都以uniform random distribution将元素hash到m个不同位置中的一个。在下面的介绍中n为元素数,m为布隆过滤器或哈希表的slot数,k为布隆过滤器重hash function数。

为了add一个元素,用k个hash function将它hash得到bloom filter中k个bit位,将这k个bit位置1。

为了query一个元素,即判断它是否在集合中,用k个hash function将它hash得到k个bit位。若这k bits全为1,则此元素在集合中;若其中任一位不为1,则此元素比不在集合中(因为如果在,则在add时已经把对应的k个bits位置为1)。

不允许remove元素,因为那样的话会把相应的k个bits位置为0,而其中很有可能有其他元素对应的位。因此remove会引入false negative,这是绝对不被允许的。

False Position

算法推导没有看懂,明天可以找同事帮指导指导。

leveldb实现代码

  // keys[0,n-1] contains a list of keys (potentially with duplicates)
  // that are ordered according to the user supplied comparator.
  // Append a filter that summarizes keys[0,n-1] to *dst.
  //
  // Warning: do not change the initial contents of *dst.  Instead,
  // append the newly constructed filter to *dst.
  virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
    // 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;
      }
    }
  }

  // "filter" contains the data appended by a preceding call to
  // CreateFilter() on this class.  This method must return true if
  // the key was in the list of keys passed to CreateFilter().
  // This method may return true or false if the key was not on the
  // list, but it should aim to return false with a high probability.
  virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const {
    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;
  }
};
}

源码分析查看: https://yq.aliyun.com/articles/5833

通过以上接口,可以看出Filter应该是在Sorted Table生成的时候,批量创建的filter。

问题

在用于加速key-value查询,减少磁盘操作的情况下。如果key被删除了之后,过滤器怎么更新?

大致看了下 leveldb 中的布隆过滤器的粒度是block相关的(在FilterBlockBuilder中)。所以每次 merge 的时候应该会重新生成一个新的布隆过滤器。这样,就可以解决key被删除导致,布隆过滤器不能一直更新的问题。

const uint32_t delta = (h >> 17) | (h << 15); 这句代码为什么?

False Positive 概率的推导函数,要找人帮过一遍啊。

吕飞

锲而舍之,朽木不折;锲而不舍,金石可镂