日志标签 ‘BloomFliter’

Level DB中的BloomFliter及Murmur Hash算法

2013年3月6日

1、LevleDb bloomfilter存储格式

在LevelDb 1.4版本中,加入了bloomfilter的支持,这样在DB::Get()方法的调用过程中,可以直接读取到bloom filter的block部分,从而减少了不存在key的大量的sstable文件随机读的操作。
在levelDb中的filter block是存储在Meta Block部分,目前的版本Meta BLock只有现在的bloom filter,后续版本还可能会加入新的内容。如下图所示。

3

对于Meta block中的bloom filter的存储方式,如下图所示。

[filter 0]
[filter 1]
[filter 2]

[filter N-1]

[offset of filter 0] : 4 bytes
[offset of filter 1] : 4 bytes
[offset of filter 2] : 4 bytes

[offset of filter N-1] : 4 bytes

[offset of beginning of offset array] : 4 bytes
lg(base) : 1 byte
首先有一个base,大小是以lg的方式进行存储的,默认为2Kb,则在数据存储区的[i*base,(i+1)*base)这一部分的数据就映射到了filter i上面,可以直接计算出i的值,然后获取到offset of beginning of offset array,就可以得到filter i和filter i+1的offset,这两段中间的内容即是该部分的bloom filter的存储内容。Table::InternalGet会首先利用filter进行判断该key是否match,如果不match就直接返回,无需读取相应的block,代码在/table/table.cc中。

2、bloomfilter构造算法

具体的bloom fliter的构造算法在https://github.com/google/leveldb/blob/master/util/bloom.cc
从该bloom.cc创建的代码可以看出,bloom fliter所占有的内存由n(key的个数)和bits_per_key_这两个参数来决定的。 而在整个leveldb中bloom fliter所占有的内存,应该是所有打开的sstable中的内存和,打开的sstable文件个数为max_open_files 进行指定,默认为1000。因此整个leveldb中bloom fliter占有的内存有所有打开的key的个数和keyt指定的bits_per_key_来决定的。a million keys and you use the suggested 10 bits per key as the argument to NewBloomFilterPolicy, the memory usage will be approximately 10 million bits =~ 1.25 MB。

3、bloomfilter Hash算法

bloom的Hash采用k_个hash函数的值,k_在1~30之间,由bits_per_key_*ln(2)计算所得。这些hash函数式通过BloomHash计算所得后,再进行相互移位所得。 具体的BloomHash的计算方法与MurMurHash类似。

4、MurmurHash 算法

MurmurHash 是一种非加密型哈希函数,适用于一般的哈希检索操作。由Austin Appleby在2008年发明 MurmurHash2能产生32-bit或64-bit哈希值。 murmurhash在多个开源项目中得到应用,包括libstdc、libmemcached、nginx、hadoop等。代码可见 https://github.com/lightkeeper/murmurhash/blob/master/MurmurHash1.cpp

5、参考资料

http://leveldb.googlecode.com/svn/trunk/doc/table_format.txt
https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash2.cpp
http://duanple.blog.163.com/blog/static/7097176720123227403134/
http://zh.wikipedia.org/wiki/Murmur%E5%93%88%E5%B8%8C
https://code.google.com/p/leveldb/source/detail?r=85584d497e7b354853b72f450683d59fcf6b9c5c