LevelDB组件-Filter

基于 BL (BloomFilter) 来减少不必要的读IO

LevelDB 利用布隆过滤器判断指定的 key 是否存在于 sstable 中，若过滤器表示不存在，则该 key 一定不存在，由此加快了查找的效率。

BloomFilter

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组(bitmap)很简洁地表示一个集合，并能判断一个元素是否属于这个集合。

Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。 -- 引申出 “错误率”“假阳性概率”

因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

通常平均每个元素只需要不到 10 bits 的空间就能把错误率控制在 1% 左右。

不支持删除操作（因为无法确定真实存在）

原理

初始 bitmap

插入某个值时，分别利用 K个 Hash 函数（如下图：3个）对值进行Hash，将Hash的结果与BL的容量取余，找到对应的位，并将其置1.

查找与插入类似，同样用 K个 Hash 函数对需要查找的值进行Hash，只有Hash得到的每一个位的值均为1，才表示该值“有可能”存在；若有任何一位的值为0，则表示该值一定不存在。

y1一定不存在；而y2可能存在。

准确率

错误率，假阳性概率

影响准确率的因素：

• Hash函数的个数 k
• BL bitmap 的容量 m
• BL 插入的数据数量 n

$m/n ≈ -1.44log_2e$

当 $e=0.01$ 时，$m/n ~= 9.567$，每个Key 需要 9.5 个bit，可以保证 1% 的错误率。

即，为每个Key分配 $k = -log_{e}2 ≈ 5$ 个Hash函数，可以保证每个Key有10个bit，从而保证99%的准确率。

实现

class FilterPolicy {
 public:
  virtual ~FilterPolicy();

  // Return the name of this policy.  if bloom, return BloomFilterPolicy
  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;
};

class BloomFilterPolicy : public FilterPolicy {};