BloomFilter（布隆滤波器）原理与使用

BloomFilter在NoSql、大数据的去重、判断数据是否存在等领域有着广泛的应用。它是一种空间效率极高的概率型算法和数据结构，用于判断一个元素是否在集合中（类似Hashset），其核心一个很长的二进制向量和一系列hash函数。
常见应用场景：

Google著名的分布式数据库Bigtable以及Hbase使用了布隆过滤器来查找不存在的行或列，以及减少磁盘查找的IO次数；
文档存储检查系统也采用布隆过滤器来检测先前存储的数据；
Goole Chrome浏览器使用了布隆过滤器加速安全浏览服务；
垃圾邮件地址过滤；
爬虫URL地址去重；
解决缓存穿透问题

BloomFilter的原理：

要实现去重或者判断数据是否存在，常规的方法有一下几个：

Hash表：
集合：
位图
假设有10240个int整数，进行去重；

有上面的表格可以看到，位图在空间时间方面的效率最高，但是它有一个严重的限制：数据只能在有限的集合范围内，这对于大数据来说，尤其不能接受。为了充分利用位图的有点，克服其限制， BloomFilter就正好可以满足这两个条件。
BloomFilter原理：
当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。

BloomFilter（布隆滤波器）原理与使用-LMLPHP
如上图所示，我们定义了一个16位的二进制向量， 3个hash 函数，这个3个函数hash的结果为0或者1，该结果存放的位置为0 ~ 15之间，将hash的结果的位置映射到二进制向量的index，并保存结果.
对于输入数据input1，得到的的结果存在于0， 8， 14，结果全部为1，那么说明input1 可能存在于指定的集合。
对于input2，得到的结果存在于0，4,10，有一个是0 ，那么说明input2一定不存在于指定的集合。

LevelDB 中BloomFilter的使用

LevelDB采用的是分层的存储结构，那么当Get一个key的时候最坏情况就是在所有的层级上都查询一遍这个key，这个开销是非常大的，引入BloomFilter之后，利用BloomFilter能够快速判断“是否存在”的特点可以很快速的知道需不需要在这个Level中进行查询。
为了支持Filter机制，LevelDB为SSTable增加了一个新的MetaBlock类型：”filter” MetaBlock。如果数据库在打开时，指定了FilterPolicy，metaindex block内将会包含一条记录用来将”filter.“映射到针对该filter meta block的block handle。此处””代表了由filter policy的Name，也就是说在metaindex block内将会有一个KeyValue对用来寻址filter summary数据组成的meta block，对于该KeyValue对来说，Key就是”filter.“，value就是filter meta block的handle}。

Filter Block存储了一系列的filters。对于这些filters来说，filter i包含了以offset落在[ ibase … (i+1)base-1 ]的那个block的所有key为输入的FilterPolicy::CreateFilter()函数的输出结果，因此实际中一个filter可能对应不止一个block，但是肯定是整数个block，一个block不会跨越两个filter，这样可以快速地计算出一个block对应的filter，因为data index block中存储了data block的offset，直接根据offset和base取值就可以计算出该data block对应了第几个filter。只要知道了是第几个filter，根据Filter Block自身的结构，就可以直接访问该filter数据了。

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

class BloomFilterPolicy : public FilterPolicy {
 private:
  size_t bits_per_key_;
  size_t k_;

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

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

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

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

小蜜蜂