LevelDB 源码层次上看读取过程

本文主要是介绍LevelDB 源码层次上看读取过程，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

读取流程

LevelDB的读取流程相对简单，从其中读取一个数据，会按照从上而下memtable->immutable->sstable的顺序读取，读不到就从下一个层级读取，因此LevelDB更适合读取新写入的数据。流程如下图：

Level0中的文件直接由Immutable通过dump产生，所以说，这一level的文件之中的key可能会相互重叠，所以需要对level0的每个文件依次查找。对于其他层次，LevelDB的归并过程保证了其中的key互相不重叠并且有序，因此可以直接使用二分方式进行数据查找。下面我们来通过代码看看这个过程：

所有发生的这一切过程，我们都可以在DBImpl::Get方法中看到，其原型如下：

Status DBImpl::Get(const ReadOptions& options, const Slice& key,std::string* value);

而读取的过程如下：

  {mutex_.Unlock();LookupKey lkey(key, snapshot);//首先在memtable查找if (mem->Get(lkey, value, &s)) {//如果没有找到就在immutable查找} else if (imm != nullptr && imm->Get(lkey, value, &s)) {} else {//最后在SSTable查找s = current->Get(options, lkey, value, &stats);have_stat_update = true;}mutex_.Lock();}

1）memtable查找

我们看到这里用来查找的key都是LookupKey这个实例化类的对象，这个类的构造函数传入一个Slice类对象key和一个SequenceNumber类的对象seq序列号。而其主要作用就是对key进行封装，让这个key带上序列号seq信息。

/*** @brief 将序列号信息s封装到user_key后面* * @param user_key key* @param s 序列号信息*/
LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {size_t usize = user_key.size();size_t needed = usize + 13;  // A conservative estimatechar* dst;//空间够用if (needed <= sizeof(space_)) {dst = space_;} else {dst = new char[needed];}//dst = [Varint32](usize+8) + [string](user_key) + [Varint64]((s<<8)|ValueType)start_ = dst;//(usize+8)dst = EncodeVarint32(dst, usize + 8);kstart_ = dst;//dst = user_keystd::memcpy(dst, user_key.data(), usize);dst += usize;//(s<<8)|ValueTypeEncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));dst += 8;end_ = dst;
}

而memtable本质上是一个跳表，所以这里再memtable上查找就是一个查找跳表的过程。查找到之后，由于跳表存储从value实际上是一个聚合怪，其格式如下：

我们的目标只是其中的value，所以这里的另一个主要工作就是反解析出这个value。

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {//取出封装好的keySlice memkey = key.memtable_key();Table::Iterator iter(&table_);//memtable 搜寻key，这里其实是跳表的查找过程iter.Seek(memkey.data());if (iter.Valid()) {//找到了，格式中反解析出key的value，赋值给value// entry format is://    klength  varint32//    userkey  char[klength]//    tag      uint64//    vlength  varint32//    value    char[vlength]const char* entry = iter.key();uint32_t key_length;const char* key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);if (comparator_.comparator.user_comparator()->Compare(Slice(key_ptr, key_length - 8), key.user_key()) == 0) {// Correct user keyconst uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);switch (static_cast<ValueType>(tag & 0xff)) {case kTypeValue: {Slice v = GetLengthPrefixedSlice(key_ptr + key_length);value->assign(v.data(), v.size());return true;}case kTypeDeletion:*s = Status::NotFound(Slice());return true;}}}return false;
}

2) immutable查找

这一步和上一步其实一模一样，就不多bb了

3）SSTable查找

SSTable查找，表面上调用了Version::Get，实际上真正的逻辑在Version::ForEachOverlapping，其逻辑描述也跟我们刚刚说的查找过程一样：

void Version::ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,bool (*func)(void*, int, FileMetaData*)) {const Comparator* ucmp = vset_->icmp_.user_comparator();//在第0层寻找std::vector<FileMetaData*> tmp;tmp.reserve(files_[0].size());for (uint32_t i = 0; i < files_[0].size(); i++) {FileMetaData* f = files_[0][i];//这里是通过FileMetaData里面存储的每一层最大key和最小key，通过对比就知道key在不在这个文件之中if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&ucmp->Compare(user_key, f->largest.user_key()) <= 0) {//符合条件就push_backtmp.push_back(f);}}//比较所有符合条件的if (!tmp.empty()) {//这里排序的目的是找到最新的，找到就返回，后面不找了std::sort(tmp.begin(), tmp.end(), NewestFirst);for (uint32_t i = 0; i < tmp.size(); i++) {//这里调用State::Match函数，每次都会把磁盘上的SSTable打开，加载到table_cache，之后查找if (!(*func)(arg, 0, tmp[i])) {return;}}}// Search other levels.for (int level = 1; level < config::kNumLevels; level++) {size_t num_files = files_[level].size();  //获取这一层的文件数量if (num_files == 0) continue;//FindFile这里采用二分查找，找到符合条件范围的keyuint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);if (index < num_files) {FileMetaData* f = files_[level][index];if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) {// All of "f" is past any data for user_key} else {//查找 返回if (!(*func)(arg, level, f)) {return;}}}}
}

参考文献

[1] LevelDB 原理解析：数据的读写与合并是怎样发生的？(在原文基础上增添内容)

这篇关于LevelDB 源码层次上看读取过程的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---