美文网首页程序员C++
leveldb源码学习--BloomFilter布隆过滤器

leveldb源码学习--BloomFilter布隆过滤器

作者: icecity96 | 来源:发表于2017-02-08 19:47 被阅读0次

基本理论

详细理论及证明请看这篇博文--Bloom Filter概念和原理。强烈建议花半个小时仔细去阅读一下这篇文章,本文后续的介绍将以上述文章作为基础。
这里将几个结论先列出来(证明请参考上面的超链接):
结论一: 在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)
结论二: Bloom Filter通过极少的错误换取了存储空间的极大节省
结论三: k = ln2· (m/n)时取得最优的哈希函数的个数
结论四: 在错误率不大于є的情况下,m至少要等于n log2(1/є)才能表示任意n个元素的集合。
结论五: 在哈希函数的个数取到最优时,要让错误率不超过є,m至少需要取到最小值的1.44倍。

源码实现

成员变量

 private:
  size_t bits_per_key_;
  size_t k_;

bits_per_key_表示m/nk_表示选取哈希函数的个数,当然在leveldb中并不是真的使用了k_种哈希函数,而是采用的double hashing来模拟多个hash函数。模拟原理如下:

Gi(x)=H1(x)+iH2(x)
H2(x)=(H1(x)>>17) | (H1(x)<<15)

成员函数

构造函数

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

看看结论三,应该就知道为何要用bits_per_key_*0.69了吧😄。

CreateFilter(const Slice* keys, int n, std::string* dst)

    // 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);

首先根据n的值计算出m(bytes),然后计算并分配所需空间。

    dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter

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

对于每个key采用double hash的方式生成k_bitpos,然后在array的相应位置设置1

KeyMayMatch(const Slice& key, const Slice& bloom_filter)

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;

计算keyhash值,重复计算阶段的步骤,循环计算k_hash值,只要有一个结果对应的bit位为0,就认为不匹配,否则认为匹配

相关文章

  • leveldb源码学习--BloomFilter布隆过滤器

    基本理论 详细理论及证明请看这篇博文--Bloom Filter概念和原理。强烈建议花半个小时仔细去阅读一下这篇文...

  • BloomFilter 缓存穿透

    需求: BloomFilter 如何防止DB 回源攻击? 介绍: Bloomfilter: 布隆过滤器,它是由一个...

  • 布隆过滤器

    什么是布隆过滤器? 布隆过滤器(BloomFilter)是由一个叫“布隆”的小伙子在1970年提出的,它是一个很长...

  • 布隆过滤器

    什么是 BloomFilter 布隆过滤器(英语:Bloom Filter)是 1970 年由布隆提出的。它实际上...

  • Python使用布隆过滤器

    安装 该模块包含两个类实现布隆过滤器功能。BloomFilter 是定容。ScalableBloomFilter ...

  • mac 下 Redis5 BloomFilter 安装及与 py

    安装及使用布隆过滤器 以前的文章有布隆去重的原理,今天来个使用 Redis5中BloomFilter和Redis...

  • 布隆过滤器--BloomFilter

    引自:https://www.cnblogs.com/liyulong1982/p/6013002.html 布隆...

  • 布隆过滤器(BloomFilter)

    作者:HaigLeehttps://www.jianshu.com/u/67ec21fb270d本文由 HaigL...

  • BloomFilter布隆过滤器

    BloomFilter能解决什么问题 在我们对查询语句添加缓存的情况中,会存在缓存穿透的情况,即请求方故意以一种不...

  • Guava - 布隆过滤器的使用

    布隆过滤器简单介绍 布隆过滤器介绍 maven引入 布隆过滤器的使用 参考及拓展 Guava的布隆过滤器 布隆过滤...

网友评论

    本文标题:leveldb源码学习--BloomFilter布隆过滤器

    本文链接:https://www.haomeiwen.com/subject/idjbittx.html