一个设计的非常巧妙的数据结构

BloomFilter 原理

布隆过滤器由巴顿布隆于1970年提出，由一个很长的bit数组以及一系列hash函数组成。bloomfilter可以用于检索一个元素是否出现在一个集合中，bloomfilter的优点是相比hash表拥有极大的空间效率，缺点是会出现一定的错误概率(False positive,一个不在集合中的元素被误认为处于集合中）。
bloomfilter 的原理是，当一个元素在加入集合时，通过k个hash 函数映射到bit数组的k个位置，并将相应的位置置1。在查找一个元素是否存在于集合中时，使用相同的k个hash 函数查看bit数组中的位置是否为全为1，如果出现一个0，则该key 一定不存在集合中，否则有可能出现在集合中。

优点

Bloomfilter 可以使用较少的空间存储大量数据的全集，并且存储的不是每个元素的原本的数值，只是设置对应的bit位，一定程度上实现了加密的效果。除空间效率之外，bloomfilter的时间效率都是常数级别O(k),其中k 代表使用的hash 函数个数，由于k个hash 函数式相互独立的性质，在进行k个hash 计算时可以并行计算进一步加速插入查找。

缺点

Bloomfilter 的缺点是会出现False positive 的误判率，而且随着元素的增加，误算率也随之增加。因此尽可能降低误判率需要一些额外工作。

BloomFilter参数选择

以下均参考wikipedia bloomfilter 中关于误差率的计算章节。直接说结论，当k(hash 函数个数)，m(bit数组大小)，n(插入元素个数)满足下式的时候，可以保证最低的误差率。$$k=\cfrac{m}{n}ln2$$下图(摘自wikipedia) 表示在最优hash函数个数的情况下，不同m,n之间误差率关系。

从上图可以看到当存储10亿个元素时使用4GB的存储空间可以保证不到1e-06的错误率。可以看到bloomfilter在实现高空间利用率的同时可以保证较低误差率。

Leveldb 实现

leveldb bloomfilter 实现在util/bloom.cc

成员变量以及构造函数

class BloomFilterPolicy : public FilterPolicy {
 private:
  // 平均每个key拥有的bit 数目
  size_t bits_per_key_;
  // hash function 的个数
  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
    // 按照上面的公式设定hash函数的个数
    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

将传入的n个key 存储到bloomfilter 中，bloomfilter结果使用string存储。

virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
    // Compute bloom filter size (in both bits and bytes)
    // bloomfilter 需要多少bit
    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;
	// 在string 中分配空间
    const size_t init_size = dst->size();
    dst->resize(init_size + bytes, 0);
    // string 的最后一个byte存储使用的hash 函数的个数
    dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
    // 获得string内部的char 型数组
    char* array = &(*dst)[init_size];
    // 逐个将每个key 写入bloom fliter
    for (int i = 0; i < n; i++) {
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      // leveldb 使用一个hash 函数，每次对hash值向右循环移位17个bit来模拟实现多个hash 函数的效果
      uint32_t h = BloomHash(keys[i]);
      // 每次向右循环移位17个bit
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {
        // 在整个bit 数组的位置
        const uint32_t bitpos = h % bits;
        // 在char型数组的位置
        array[bitpos/8] |= (1 << (bitpos % 8));
        // 更新获得一个新的hash 数值
        h += delta;
      }
    }
  }

KeyMayMatch

判断一个 key 在bloomfilter中是否存在。

 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();
    // 最后一个byte数值代表使用了多少hash函数
    // 除最后一个byte之外代表bit数组
    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;
    }
	// 使用相同的方法模拟多个hash函数计算的hash值
    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;
      // 找到一个bit位置不匹配，提前返回false
      // 在bit数组中位置的索引和设置时的方法一致
      if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;
      // 更新获得下一个hash value
      h += delta;
    }
    // 全部匹配return true
    return true;
  }

BloomFilter 应用场景

由于其高效的空间效率，bloomfilter 可以应用于以下场景：

• 爬虫系统记录以经爬取过的url
• 垃圾邮件过滤
• p2p 网络中查找资源操作: 使用一个bloomfilter 保存拥有此资源的网络通路
• 广播信息时检查某个ip是否发包
• 字典纠错：将所有单词存储到bloomfilter中，如果不存在则认为是一个错误拼写
• CDN 代理缓存: 每个cache 服务器上使用bloomfilter 存储兄弟cache 服务器上是否有缓存关键字，如果没有则可以避免一次查找

总结

Bloomfilter 是一种设计巧妙的数据结构，由于其良好的空间效率，可以用于判断一个元素是否包含于海量元素集合的场景。
Leveldb 的实现的bloomfilter 可以灵活配置hash 函数的个数，使用一个hash 函数模拟任意多个hash 函数的场景，并将使用hash函数的个数存储到bloomfilter编码结果中。除此之外，leveldb bloomfilter 实现bit数组个数，hash函数个数以及存储元素个数的最优配置，保证最低的误差率。