Google的leveldb是个很优秀的存储引擎，但还是有一些不尽人意的地方，比如leveldb不支持多线程合并，对key范围查找的支持还很简单，未做优化措施，等等。而Facebook的RocksDB是个更彪悍的引擎，实际上是在LevelDB之上做的改进，在用法上与LevelDB非常的相似，两者的对比可以参考下面的参考资料1。

这里之所以要调研rocksdb是因为rocksdb中加入了prefix bloomfilter的实现，能够支持对范围查找的优化，对我目前的项目很有参考意义，下面是我调研和剖析rocksdb部分源码总结出的部分结果。

1. 对RocksDB中与Bloomfilter相关的调研结果

这一步主要参考rocksdb的官方博客和相关讨论，总结得到以下信息：

（1）rocksdb支持在key的sub-part上设置Bloomfilter，这使得范围查询成为可能。

（2）将key分为prefix和suffix，配置了一个prefix_extractor 来指定key-prefix，并用此存储每个key-prefix的blooms，然后用指定了prefix的iterator来使用这些bloom bits避免查询那些不包含所指定prefix的keys，从而实现了prefix过滤。

（3）Rocksdb实现了两个Bloomfilter，一个是在读block之前使用Bloomfilter过滤不包含key的blocks（与leveldb相同），另一个是在查询memtable时动态生成一个bloomfilter实现内存中的key过滤（在block read之前）。

上面这些信息源主要来自以下几个参考资料：

•  
• 中关于rocksdb特性的讨论
•  

2. rocksdb中Get接口实现优化（与leveldb对比）

 下面简单总结下rocksdb中Get接口实现过程中的一些优化技术，总体实现流程与leveldb一致，都是memtable —>immemtable—>sstable的过程，但实现细节有所不同，主要有下面几点不同：

（1）memtable/ immemtable的Get实现（memtable.cc::Get）

Rocksdb在这个过程中加入了Bloomfilter机制，如下：

    autoiter = DB::NewIterator(ReadOptions());
    for (iter.Seek(prefix); iter.Valid()&& iter.key().startswith(prefix); iter.Next()) {
       //do something
    }

具体实现通过封装的iter内部的多个不同类型Iterator的Seek方法，其中使用到prefixbloomfilter的Iterator是sstable的TwoLevelIterator（即过滤的是磁盘IO），Two_level_iterator中的Seek方法在读磁盘IO之前先进行了一次prefixfilter，如下（two_level_iterator.cc:: Seek）：

 if (state_->check_prefix_may_match &&
     !state_->PrefixMayMatch(target)) {
   SetSecondLevelIterator(nullptr);
    return;
  }

这里PrefixMayMatch函数的具体实现分为以下几个步骤（block_based_table_reader.cc:: PrefixMayMatch）：

a. 首先根据prefix_extractor信息抽取出key的prefix部分

b. 然后构造prefix的Index Iterator以根据索引信息查找该prefix是否可能在这个file里（此时还没开始真正的block读，即此时没有磁盘IO操作）

c. 如果不可能在file里则返回false；如果有可能在，则进一步检查下当前Iterator所指向的完整key的prefix是否是要查找的prefix（因为index只能确定范围，不能精确确定prefix一定存在），若是则返回true，否则就获取filterblock里的bloomfilter，通过prefixbloomfilter的PrefixMayMatch进行过滤，如果过滤不了才开始真正的block磁盘查找。

上面的流程简单讲述了如何实现prefix scan，下面举个简单的例子（来自db_test.cc）：

使用下面的几组prefixranges 生成11个sst文件：

GROUP 0:[0,10]                             (level 1)
GROUP 1:[1,2], [2,3], [3,4], [4,5], [5, 6] (level 0)
GROUP 2:[0,6], [0,7], [0,8], [0,9], [0,10] (level 0)

这11个prefix ranges对应的key ranges分别为：

GROUP 0: [00______:start, 10______:end]
GROUP 1: [01______:start, 02______:end], [02______:start, 03______:end],
         [03______:start, 04______:end], [04______:start, 05______:end],
         [05______:start,06______:end]
GROUP 2: [00______:start, 06______:end], [00______:start,07______:end],
         [00______:start,08______:end], [00______:start, 09______:end],
         [00______:start,10______:end]

其中prefix长度为8，此时如果要通过prefix“03______:”查找 这11个sst文件，先前的API（比如leveldb中）需要11次随机IO才能找到，而用rocksdb中新的API及prefixfilter选项的启用，我们只需要2次随机IO即可，因为只有两个文件包含该prefix。

4.  RocksDB中关于get_range接口

 rocksdb中虽然实现了prefix Bloomfilter，但是并未提供get_range接口，官方文档中说支持Bloomfilter范围查询指的应该是rocksdb已经实现了prefix Bloomfilter，那么用户可以利用这个实现范围查找的过滤机制，但接口需要用户自己实现。RocksDB对原来LevelDB中sst文件预留下来的MetaBlock进行了具体利用，其中Prefixes信息存在metablock里（Block_based_table_builder.cc）。因此我们可以借鉴prefixBloomfilter的原理实现我们自己的范围Bloomfilter。

5. leveldb中范围Bloomfilter实现的初步思路

首先get_range对外的接口是这样：

int get_range(int area, const data_entry &pkey, const data_entry &start_key,   
const data_entry &end_key, int offset, int limit, vector<data_entry*> 
&values,short type=CMD_RANGE_ALL);

其中pkey就是prefix key，因此我们根据对pkey实现bloomfilter来实现范围bloomfilter的过滤。

基本实现思路如下：

（1）对data block里的每个key抽取出合适的prefix

（2）对prefix key实现bloomfilter（与key实现一样），并添加到filter block里，这里可以与整个key的bloomfilter放在一起，也可以分开放，通过index block控制索引

（3）在get_range实现过程中，首先获取prefix bloomfilter，然后对pkey进行prefixfilter，过滤掉prefix不匹配的file或block，这样就实现了范围bloomfilter。

6. 参考资料

1. 

2.

3.

4.

对LevelDB的“升级版”存储引擎RocksDB的调研成果,布布扣,bubuko.com