LevelDB的get操作

leveldb源码分析3

前面的Put操作实际上包括了写入和删除，接下来分析Get操作。

总的来说，Get操作就是找到userkey相同，并且SequenceNumber最大(最新)的数据。

DBImpl::Get(db/db_impl.cc1118行)

Status DBImpl::Get(const ReadOptions& options,
                   const Slice& key,
                   std::string* value) {
  Status s;
  MutexLock l(&mutex_);
  SequenceNumber snapshot;
  if (options.snapshot != nullptr) {
    snapshot =
        static_cast<const SnapshotImpl*>(options.snapshot)->sequence_number();
  } else {
    snapshot = versions_->LastSequence();
  }

leveldb支持对特定Snapshot的Get，只是简单的将Snapshot的SequenceNumber作为最大的SequenceNumber即可。

继续Get函数，1131～1155行：

  MemTable* mem = mem_;
  MemTable* imm = imm_;
  Version* current = versions_->current();
  mem->Ref();
  if (imm != nullptr) imm->Ref();
  current->Ref();

  bool have_stat_update = false;
  Version::GetStats stats;

  // Unlock while reading from files and memtables
  {
    mutex_.Unlock();
    // First look in the memtable, then in the immutable memtable (if any).
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) { // 在memtable中查找
      // Done
    } else if (imm != nullptr && imm->Get(lkey, value, &s)) { // 在memtable中未找到，则在immutable memtable中查找
      // Done
    } else { // 仍未找到，在SSTable中查找
      s = current->Get(options, lkey, value, &stats);
      have_stat_update = true;
    }
    mutex_.Lock();
  }

由于写leveldb的时候还没出C++11标准，所以memtable使用自己写的引用计数，而没有用智能指针。

查找的顺序是从memtable开始找，然后到immutable memtable，最后才在SSTable中查找， 从level-0开始，每个level上依次进行查找。

在由于memtable和immutable memtable底层都是skip list实现，所以MemTable::Get()都是 通过skip list来查找。

Version::Get(db/version_set.cc332行)

由于代码过长，所以就简单写一写流程：

  1. 首先找出level上可能包含key的sstable.(key包含在FileMetaData(FileMetaData是SSTable文件的元信息的封装)的[startest,largest].
    • level-0的查找只能顺序遍历files_[0]。考虑到level-0中的sstable是memtable dump生成的，所以新生成的sstable一定比旧生成有更新的数据，同时sstable文件的 FileNumber是递增，所以，将从 level-0 中获得的sstable(FileMetaData)按照 FileNumber排序（ NewestFirst()db/version_set.cc）,能够优化level-0中的查找。 level-0中可能会找到多个sstable
    • 非level-0中的查找，对files_[]基于FileMetaData::largest做二分查找 （FindFile()db/version_set.cc）即可定位到level中可能包含key的sstable。非level-0 上最多找到一个 sstable。
  2. 如果该level上没有找到可能的sstable，跳过。否则，对要进行查找的 sstable 获得其Iterator（ TableCache::NewIterator()）,做seek().
  3. seek 成功则检查有效性（ GetValue()db/version_set.cc）也就是根据ValueType判断是否是有效的数据：
    • kTypeValue，返回对应的value数据。
    • kTypeDeletion，返回data not exist

总结

从之前介绍的LevelDb的写操作和这里介绍的读操作可以看出，相对写操作，读操作处理起来要复杂很多， 所以写的速度必然要远远高于读数据的速度，也就是说，LevelDb比较适合写操作多于读操作的应用场合。 而如果应用是很多读操作类型的，那么顺序读取效率会比较高，因为这样大部分内容都会在缓存中找到，尽可能避免大量的随机读取操作。