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
插入
某个值时,分别利用 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 {};