leveldb源码分析补充之布隆过滤器

之前分析leveldb时,忘了分析过滤器.简单的说,leveldb的过滤器主要作用是当从磁盘数据时,可以通过过滤器先判断读取的键值是否在读取的data block中,如果在,则读取,如果不在,则直接空值返回,在一定程度上较少了磁盘IO.

再介绍布隆过滤器之前,先介绍下位开关,很有意思的位运算.

位运算


假如有20个开关,控制着20掌灯.我们可以通过输入序号,来控制灯的开关,这就是位运算.编程时,最关键的操作就是要找到设置的位在哪,先看下这个小程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <stdlib.h>
unsigned char bits[4];
void set_on(int pos);
void set_close(int pos);
void print(int pos);
int main(void)
{
set_on(25);
print(25);
set_close(25);
print(25);
return 0;
}
void set_on(int pos)
{
bits[pos/8] |= (1 << (pos%8) );
}
void set_close(int pos)
{
bits[pos/8] &= ~(1 << (pos%8) );
}
void print(int pos)
{
char b = ( bits[pos/8] & (1<<(pos%8) ) )>0?1:0;
printf("%d\n",b);
}

这个程序,用char bits[4]来表示32个位,然后打开某个位时,

  1. 先通过pos/8找到在哪个字节;
  2. 通过pos%8找到在哪个位;
  3. 然后把相应的位设置为1.

当关闭某个位时,直接把(1 << (pos%8) ) 取反,再与那个字节与运算即可

leveldb布隆过滤器


leveldb的布隆过滤器思想是,如果有某条过滤信息有n个键,则可以设置n*bits_per_key个位,然后对每个键进行n次运算,得到n个值,然后设置n个值为1即可.当验证时,则对查找的键也是进行n此运算,得到n各数,在判断n*bits_per_key中,这n个位是否为1,如果全部为1,则说明查找的键在过滤器中,如果有某个位不为1,则说明键值不在过滤器.

成员变量为:

1
2
3
4
5
6
7
8
9
10
11
12
13
class BloomFilterPolicy : public FilterPolicy {
private:
size_t bits_per_key_;
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
k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)
if (k_ < 1) k_ = 1;
if (k_ > 30) k_ = 30;
}

bits_per_key_为每个键值设置的比特位数,k_为每个键值需要计算的次数.当创建布隆过滤器,需要传入bits_per_key_,这也是唯一可设置的参数.

来看下布隆过滤器创建:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
// Compute bloom filter size (in both bits and bytes)
//根据n个键,设置n个位
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;
//向上取整,使bits位刚好是8的倍数,即整数个字节
size_t bytes = (bits + 7) / 8;
bits = bytes * 8;//更新后的字节
const size_t init_size = dst->size();
dst->resize(init_size + bytes, 0);//将每条过滤器添加总过滤器之后
dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
char* array = &(*dst)[init_size];//array指向dst未使用的首位置
for (size_t i = 0; i < n; i++) {
//先算键值的哈希值
uint32_t h = BloomHash(keys[i]);
//向右循环移位17位.
const uint32_t delta = (h >> 17) | (h << 15);
for (size_t j = 0; j < k_; j++) {
const uint32_t bitpos = h % bits;
array[bitpos/8] |= (1 << (bitpos % 8));//将相应位设为1
h += delta;//重复计算哈希值,计算k_值
}
}
}

接来下是对查询键值过滤器验证:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const {
const size_t len = bloom_filter.size();//一条Filter的大小
if (len < 2) return false;
const char* array = bloom_filter.data();//一条Filter的数据
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;
}
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;
//进行验证,必须k次数据都必须为1,否则出错
if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;
h += delta;
}
return true;
}

创建过滤器是在dbformat.cc中的InternalFilterPolicy->CreateFilter,验证函数是在InternalFilterPolicy->KeyMayMatch中调用.在leveldb中,最终验证时,是在table.cc的Table->InternalGet中.

布隆过滤器使用挺广的,之前还了解过在推荐系统只能中也有使用,所以学学这个也是很有帮助的.