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<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();

}

总结

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

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

参考内容

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

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章