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