leveldb iterator 的 Prev 究竟比 Next 差在哪？

linjinhe

发布于 2020-02-18 17:15:08

1.5K0

发布于 2020-02-18 17:15:08

文章被收录于专栏：linjinhe的专栏linjinhe的专栏

Iterator

leveldb 通过 iterator 提供了范围查找、有序遍历的功能，支持正向迭代（Next）和反向迭代（Prev）。

leveldb iterator 的使用方式可以参考官方文档。

关于 Next 和 Prev 的性能问题，官网文档中有这么一段话：

You can also process entries in reverse order. (Caveat: reverse iteration may be somewhat slower than forward iteration.)

意思就是：Prev 的性能比 Next 差。 但是为什么差，差多少，文档没有说明。

Prev 和 Next 的实现

Iterator 是比较高层次的抽象。从代码上看，leveldb iterator 的遍历（Next/Prev）操作最终会对应到对底层具体数据结构的遍历。leveldb 保存数据的数据结构有两种：

MemTable
SST 文件

MemTable

MemTable 实际上就是一个单向的 skiplist —— 只有 next 指针，没有 prev 指针。所有 prev 操作都需要从头开始遍历。所以，MemTable 的 Next 操作的时间复杂度是 O(1)， Prev 操作的时间复杂度是 O(logN)。具体实现如下：

template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Next() {
  assert(Valid());
  node_ = node_->Next(0);
}

template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Prev() {
  // Instead of using explicit "prev" links, we just search for the
  // last node that falls before key.
  assert(Valid());
  node_ = list_->FindLessThan(node_->key);
  if (node_ == list_->head_) {
    node_ = nullptr;
  }
}

SST 文件

SST 可以简单认为它被组织成一个 index block + 多个 data block。由 index iter + data iter 组成的 TwoLevelIterator 来实现对 SST 的查找、遍历。

而 index block 本质上也是一个 data block，只不过这个 block 保存的是索引数据。所以，对 TwoLevelIterator 的 Next/Prev 本质上是对 Block 的 Next/Prev。同样，由于 block 中数据的单向性，Next 操作的时间复杂度是 O(1)，而每次 prev 都需要重新定位，性能也比 next 差不少。

virtual void Next() {
  assert(Valid());
  ParseNextKey();
}

virtual void Prev() {
  assert(Valid());
  // Scan backwards to a restart point before current_
  const uint32_t original = current_;
  while (GetRestartPoint(restart_index_) >= original) {
    if (restart_index_ == 0) {
      // No more entries
      current_ = restarts_;
      restart_index_ = num_restarts_;
      return;
    }
    restart_index_--;
  }
  SeekToRestartPoint(restart_index_);
  do {
    // Loop until end of current entry hits the start of original entry
  } while (ParseNextKey() && NextEntryOffset() < original);
}

性能测试

写了个简单的代码测试一下。在我的机器上，遍历一个 10000000 条记录的 leveldb，测试结果如下：

BenchNext: count 10000000 use time 3363045 us
BenchPrev: count 10000000 use time 7333961 us
BenchNext: count 10000000 use time 3669136 us

测试代码如下：

#include <sys/time.h>
#include <iostream>
#include "leveldb/db.h"
#include "leveldb/cache.h"
#include "leveldb/write_batch.h"

const std::string kDBName = "db_bench_iter";
const uint64_t  kKVPairCnt = 10000000;
const uint64_t kWBCnt = 100;

const int kWriteBufferSizeMB = 4;
const int kBlockCacheSizeMB = 8;
const int kBlockSizeKB = 4;
const int kMaxFileSize = kWriteBufferSizeMB;
const auto kCompression = leveldb::kSnappyCompression;

inline void OKOrAbort(const leveldb::Status& s, int line) {
    if (!s.ok()) {
        std::cerr << line << " " << s.ToString() << std::endl;
        abort();
    }
}

leveldb::DB* OpenDB() {
  leveldb::Options opts;
  opts.create_if_missing = true;
  opts.write_buffer_size = kWriteBufferSizeMB * 1024 * 1024;
  opts.block_cache = leveldb::NewLRUCache(kBlockCacheSizeMB * 1024 * 1024);
  opts.block_size = 4 * 1024;
  opts.max_file_size = kWriteBufferSizeMB * 1024 * 1024;
  opts.compression = kCompression;
   leveldb::DB* db = nullptr;
   OKOrAbort(leveldb::DB::Open(opts, kDBName, &db), __LINE__);
   return db;
}

leveldb::DB* OpenNewDB() {
  leveldb::Options opts;
  OKOrAbort(leveldb::DestroyDB(kDBName, opts), __LINE__);
  return OpenDB();
}

leveldb::DB* ReopenDB(leveldb::DB* db) {
   delete db;
   return OpenDB();
}

void FillWriteBatch(leveldb::WriteBatch& wb, uint64_t begin, uint64_t end) {
    for (; begin < end; begin++) {
        leveldb::Slice k((char*)&begin, sizeof(begin));
        wb.Put(k, k);
    }
}

void WriteData(leveldb::DB* db) {
  leveldb::WriteOptions wopts;
  for (uint64_t i = 0; i < kKVPairCnt; i+= kWBCnt) {
      leveldb::WriteBatch wb;
      FillWriteBatch(wb, i, i+kWBCnt);
      OKOrAbort(db->Write(wopts, &wb), __LINE__);
  }
  db->CompactRange(nullptr, nullptr);
}

uint64_t NowUS() {
    struct timeval tv;
    gettimeofday(&tv, nullptr);
    return tv.tv_sec * 1000000 + tv.tv_usec;
}

void BenchNext(leveldb::DB* db) {
     leveldb::ReadOptions ropts;
     auto iter = db->NewIterator(ropts);
     iter->SeekToFirst();
     auto begin = NowUS();
     uint64_t cnt = 0;
     for (; iter->Valid(); iter->Next()) {
         auto key = iter->key();
         auto value = iter->value();
         cnt++; 
     }
     auto end = NowUS();
     OKOrAbort(iter->status(), __LINE__);
     delete iter;
     std::cout << __func__ << ": " << "count " << cnt << " use time " << end - begin << " us" << std::endl;
}

void BenchPrev(leveldb::DB* db) {
     leveldb::ReadOptions ropts;
     auto iter = db->NewIterator(ropts);
     iter->SeekToLast();
     auto begin = NowUS();
     uint64_t cnt = 0;
     for (; iter->Valid(); iter->Prev()) {
         auto key = iter->key();
         auto value = iter->value();
         cnt++; 
     }
     auto end = NowUS();
     OKOrAbort(iter->status(), __LINE__);
     delete iter;
     std::cout << __func__ << ": " << "count " << cnt << " use time " << end - begin << " us" << std::endl;
}

void Bench() {
  auto db = OpenNewDB();
  WriteData(db);

  db = ReopenDB(db);
  BenchNext(db);

  db = ReopenDB(db);
  BenchPrev(db);

  db = ReopenDB(db);
  BenchNext(db);

  delete db;
}

int  main() {
  Bench();
}