|
Google的leveldb是个非常优秀的存储引擎。但还是有一些不尽人意的地方，比方leveldb不支持多线程合并。对key范围查找的支持还非常easy，未做优化措施，等等。而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之前）。
上面这些信息源主要来自下面几个參考资料：
2. rocksdb中Get接口实现优化（与leveldb对照）以下简单总结下rocksdb中Get接口实现过程中的一些优化技术，整体实现流程与leveldb一致，都是memtable —>immemtable—>sstable的过程。但实现细节有所不同，主要有以下几点不同： （1）memtable/ immemtable的Get实现（memtable.cc::Get） Rocksdb在这个过程中增加了Bloomfilter机制，例如以下：
这个Bloomfilter是动态生成的（没有持久化）且是prefix bloom。依据prefix进行过滤。
（2）sstable中的Get实现：level —>file -> block逐层搜索 a. 在level 0层，在找files之前加了预读取功能（prefetch bloom filter data blockfor L0 files）
採用的是prefix hashing技术（參考资料2）。 b．然后在各层找到可能的files(查找方式与leveldb同)，并对files进行key range filtering和fractional cascading技术优化level上的文件查找，但要满足两个条件：一是不仅仅有一个L0层。二是L0层必须有3个文件以上。即假设L0层少于3个文件。就不做key range filtering。由于这样的情况下系统每次查询的table数目已经非常少了，所以这时候key range filtering非常可能反而没有直接查询files高效。 key range filtering非常easy，就是看key在不在file的[smallest_key,largest_key]之间，而fractional cascading技术简单说是利用上层key range filtering的比較信息作为下一层key range filtering的參考，以降低比較的次数，使得更快定位下一层的files，详细看參考资料3。定位到file后。就要进行block的查询了。rocksdb中（block_based_table_reader.cc）的block查找使用的Bloomfilter机制与leveldb一样。
除此之外，rocksdb还有非常多与leveldb不一样的地方。比方rocksdb中memtable的数据结构除了skiplist实现外还有linked list的实现，sstable的实现除了block table之外还有plain table；RocksDB支持多线程合并，支持在单个进程中启用多个实例，除了主要的Put/Get/Delete接口外还添加了个Merger接口，等等……
3. rocksdb中prefix Bloomfilter的实现细节研究rocksdb的源代码后，以我自己理解的角度总结rocksdb实现prefixbloom的大致方法例如以下： （1）首先rocksdb中持久化数据的存储格式有两种：BlockBasedTable格式和PlainTable格式。当中BlockBasedTable格式衍生自新版leveldb中的BlockTable格式，整体格式全然没变。例如以下所看到的：
可是在实现上与leveldb有有所不同。比方红色标出的filter block部分，leveldb的filter block部分能够存储全部key的bloomfilter。而rocksdb的filter block部分不仅能够存储全部key的bloomfilter。还能够存储全部key的prefix的bloomfilter。通过两个參数whole_key_filtering_和prefix_extractor_来控制。当中whole_key_filtering_控制是否存储整个key的bloomfilter，而prefix_extractor_控制是否存储prefix的bloomfilter。 假设想要存储prefixbloomfilter。就须要事先将prefix长度信息存入prefix_extractor_中，以便filterblock building过程中能依据长度信息抽取出key的prefix然后生成prefixbloomfilter，并有个PrefixMayMatch()函数用来过滤prefix（leveldb中仅仅有KeyMayMatch()）。 注：除了filter block实现不同之外。以下的iindexblock实现也不同，rocksdb中增加了prefixindex block的实现。prefixindex block会为datablock中每一个key的prefix部分保存一条索引记录，以方便通过prefix进行查找。 （2）在filter block building完毕后就能够进行prefix scan了，例如以下： 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文件：
这11个prefix ranges相应的key ranges分别为：
当中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对外的接口是这样：
当中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. 參考资料2.Prefix hashing in RocksDB -Speeding up queries for special workloads |
|
|
