in LevelDB 分布式数据库 ~ read.

LevelDB组件-Filter

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

bitmap_init

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

bitmap_hash

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

bitmap_find

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