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

Iterator

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

leveldb iterator 的使用方式可以参考官方文档(https://github.com/google/leveldb/blob/v1.20/doc/index.md#iteration) 。

关于 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 保存数据的数据结构有两种：

1. MemTable

2. SST 文件

MemTable

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

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


template <typename Key, class Comparator>
inline void SkipList::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
#include
#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();

}

总结

• 由于 leveldb 维护的有序数据是单向的，一般情况下，Next 操作的时间复杂度 O(1)，而 Prev 每次操作都需要重新定位数据。

• 在一些特殊情况下，比如大量删除的数据或者同一个 key 有很多版本需要跳过，也会影响 Next 和 Prev 的性能。

参考内容

• https://github.com/google/leveldb