Bloom Filter 是一种空间效率很高的随机数据结构，由1970年布隆提出，它实际上是一个很长的二进制向量（位图）和 一系列随机映射函数（哈希函数）组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
错误识别率在于：如果布隆过滤器判定一个元素不存在，那么可以得出该元素肯定不存在，但如果判定一个元素存在，则有一定的误报率。一句话总结：布隆过滤器可以判定一个元素一定不存在或者可能存在
布隆过滤器原理
布隆过滤器.png
如果我们要映射一个值到布隆过滤器中，需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位 置为1。
baidu.png
假设这里对 "baidu" 分别对应3次hash。并将对应的bit 位置为1，如上图所示。
现在，这里我们再存一个 "tencent"，图变为：
tencent.png
这里，第3位的 bit 重复了，所以还是如此。
假设现在，我们查找 "taobao" 返回 bit 位是1 4 7，查看图表，我们可以肯定的说这个值是不存在的。
但假设我们查找"ali"，那返回的bit位都是0 3 8，那么我们能说"ali"一定存在吗？答案是不可以，只能说可能存在。因为随着增加的值越来越多，被置为1的bit位也会越来越多，这样的值即使没有被存储过，但万一hash函数返回的3个bit都被其他值置为了1，那么程序还是会判断这个值存在。
这就是上面我们所说的误报率了，从上面也可以看出：怎么避免这种冲突就成了布隆过滤器是否误报的关键了。
如何选择哈希函数的个数和布隆过滤器的长度。
假设这里有 n 个整数的 set，以及一个 m 位的bit 数组，以及k个哈希函数。m[i] 表示第 i 个 bit 位。
很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。
那么如何选择业务的 k 和 m 值：
LevelDB中布隆过滤器的实现
LevelDB中布隆过滤器代码实现在util/bloom.cc。
LevelDB 首先定义了 FilterPolicy 接口，布隆过滤器是这一个接口的实现。
class LEVELDB_EXPORT FilterPolicy
{
public:
virtual ~FilterPolicy();
// 过滤器名称
virtual const char* Name() const = 0;
// 创建1个过滤器
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:
explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key)
{
k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 约等于 ln(2)
if (k_ < 1)
k_ = 1;
if (k_ > 30)
k_ = 30;
}
private:
size_t bits_per_key_;
size_t k_;
}
bits_per_key，等同于
k_` 等同于是hash函数的个数
构建布隆过滤器 CreateFilter
// keys 代表布隆过滤器中要插入的袁术数组
// n 表示keys数组的个数
// dst 最后布隆过滤器的内容
void CreateFilter(const Slice* keys, int n, std::string* dst) const override
{
// n 表示键的个数，bits_per_key_表示 每个key使用的位数，所以 bits 表示使用的总的位数
size_t bits = n * bits_per_key_;
if (bits < 64) bits = 64;
size_t bytes = (bits + 7) / 8; // 向上取整，因为最后1个字节需要记录k_
bits = bytes * 8;
const size_t init_size = dst->size();
dst->resize(init_size + bytes, 0);
dst->push_back(static_cast<char>(k_)); // 记录一下hash函数的个数
char *array = &(*dst)[init_size];
for (int i = 0; i < n; i++)
{
uint32_t h = BloomHash(keys[i]); // 计算键的hash值
const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
// 理论上应该需要对每一个键计算k_次hash值，这里通过将对键计算得到的hash值加delta来模拟
for (size_t j = 0; j < k_; j++)
{
const uint32_t bitpos = h % bits;
// 访问m[i] 把相应位设置为1
array[bitpos / 8] |= (1 << (bitpos % 8));
h += delta;
}
}
}
理论上应该需要对每一个键计算k_次hash值，这里通过将对键计算得到的hash值加delta来模拟，这里的做法可以参考论文：Less hashing, same performance: Building a better Bloom filter
模拟使用方式如下：
std::vector<Slice> tmp_keys;
tmp_keys_.push_back("he");
tmp_keys_.push_back("hello");
BloomFilterPolicy bloom_filter_policy(8);
std::string filter;
bloom_filter_policy.CreateFilter(&tmp_keys[0], tmp_keys.size(), &filter);
KeyMayMatch
virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const
{
// bloom_filter是一个bit数组
// 只不过是用Slice字符串的方式组装起来的
const size_t len = bloom_filter.size();
if (len < 2) return false;
// 获得相应的内存区域
const char* array = bloom_filter.data();
// 总共的bits数目
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.
// 取得k哈希函数的数目
const size_t k = array[len-1];
// 对于大于30个哈希函数的情况，这里直接返回存在
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;
}
布隆过滤器在LevelDB中的应用
参考资料
1、https://zhuanlan.zhihu.com/p/43263751
2、https://www.jasondavies.com/bloomfilter/
3、https://zhuanlan.zhihu.com/p/45942533
网友评论