對LevelDB的“更新版”存儲引擎RocksDB的調研成果

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之前）。

上面這些資訊源主要來自以下幾個參考資料：

•  Official Blog
• HackNews中關于rocksdb特性的讨論
•  RocksDB Basics

2. rocksdb中Get接口實作優化（與leveldb對比）

 下面簡單總結下rocksdb中Get接口實作過程中的一些優化技術，總體實作流程與leveldb一緻，都是memtable —>immemtable—>sstable的過程，但實作細節有所不同，主要有下面幾點不同：

（1）memtable/ immemtable的Get實作（memtable.cc::Get）

Rocksdb在這個過程中加入了Bloomfilter機制，如下：

if (prefix_bloom_&&

     !prefix_bloom_->MayContain(prefix_extractor_->Transform(user_key))){

    // iter is null if prefix bloom says thekey does not exist

} else {

   // 查詢memtable

}
      

這個Bloomfilter是動态生成的（沒有持久化）且是prefix bloom，根據prefix進行過濾。

（2）sstable中的Get實作：level —>file -> block逐層搜尋

a. 在level 0層，在找files之前加了預讀取功能（prefetch bloom filter data blockfor L0 files）

// Prefetch table data to avoidcache miss if possible

    if (level == 0) {

      for (int i = 0; i < num_files; ++i) {

        auto* r =files_[0][i]->fd.table_reader;

        if (r) {

          r->Prepare(ikey);

        }

      }

    }
      

采用的是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很簡單，就是看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格式，總體格式完全沒變，如下所示：

<beginning_of_file>

[datablock 1]

[datablock 2]

...

[datablock N]

[metablock 1: filter block]          

[metablock 2: stats block]           

...

[metablock K: future extended block] 

[metaindexblock]

[indexblock]

[Footer]                              

<end_of_file>


      

但是在實作上與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檔案：

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. RocksDB介紹：一個比LevelDB更彪悍的引擎

2.Prefix hashing in RocksDB -Speeding up queries for special workloads

3.使用fractional cascading優化level上的檔案查找

4.TheStory of RocksDB