Level DB中的BloomFliter及Murmur Hash算法

1、LevleDb bloomfilter存储格式

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

对于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的构造算法在/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等。

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