LevelDB基本读流程按照如下顺序:

  1. 从内存memtable读;
  2. 从内存Immutable memtable读;
  3. 从level0的sstable读;
  4. 从level1的sstable读;
  5. ……

上面的读流程中,如果在上一级命中,就不再进入下一层级去读取,因为上一层级的数据总是比下一层级的数据更新,这也是取名levelDB的原因所在。

读接口

Status DBImpl::Get(const ReadOptions& options,
                   const Slice& key,
                   std::string* value) {
  Status s;
  MutexLock l(&mutex_);
  SequenceNumber snapshot;
  // 从snapshot读取
  if (options.snapshot != NULL) {
    snapshot = reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_;
  } else {
    snapshot = versions_->LastSequence();
  }

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

  bool have_stat_update = false;
  Version::GetStats stats;

  // Unlock while reading from files and memtables
  {
    mutex_.Unlock();
    // 从memtable读取
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {
      // 从Immutable memtable读取
    } else if (imm != NULL && imm->Get(lkey, value, &s)) {
      // Done
    } else {
      // 从sstable读取
      s = current->Get(options, lkey, value, &stats);
      have_stat_update = true;
    }
    mutex_.Lock();
  }

  if (have_stat_update && current->UpdateStats(stats)) {
    MaybeScheduleCompaction();
  }
  mem->Unref();
  if (imm != NULL) imm->Unref();
  current->Unref();
  return s;

关于这个的实现比较简单,符合我们一开始说的大逻辑:先从memtable中读取,再从磁盘上的sstable读取。

疑问:另外,在对可能的memtable、sstable进行访问之前先进行了Ref()调用,所谓何意呢?为了防止在读过程中防止其他线程修改么?

从内存memtable读

前面我们说过,LevelDB的内存memtable的实现其实是一个LSM tree。至于怎么快速地从LSM tree中查找特定key我们会在后面的相关文章中介绍LSM tree时作详细描述:

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
  Slice memkey = key.memtable_key();
  Table::Iterator iter(&table_);
  // 调用的其实是skiplist.h中的Iterator::Seek()方法
  iter.Seek(memkey.data());
  if (iter.Valid()) {
    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 key
      const 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;
        }
        // 如果记录是删除标记,返回NotFound错误
        case kTypeDeletion:
          *s = Status::NotFound(Slice());
          return true;
      }
    }
  }
  return false;
}

从Immutable memtable中读取的逻辑和上面描述的完全一样,这里就忽略。

从sstable读

如果在内存memtable中没有找到感兴趣的key,接下来便是从位于磁盘的sstable中查询。从sstable读取过程为:

查找sstable file的元数据信息(索引信息),根据索引查找感兴趣的key位于哪个block,进而读出block,然后从block中读出key。

但是level0的sstable和其他level的sstable还不尽相同:level0的sstable之间key的范围可能有重叠:因此,一个key的更新记录可能位于多个sstable文件之中。这就要求对level-0进行读取时要做一些特殊处理。

读sstable的记录的方法位于version_set.cc的Version::Get()。

Status Version::Get(const ReadOptions& options,
                    const LookupKey& k,
                    std::string* value,
                    GetStats* stats) {
  Slice ikey = k.internal_key();
  Slice user_key = k.user_key();
  const Comparator* ucmp = vset_->icmp_.user_comparator();
  Status s;

  stats->seek_file = NULL;
  stats->seek_file_level = -1;
  FileMetaData* last_file_read = NULL;
  int last_file_read_level = -1;

  // 使用tmp记录所有可能需要参与读的sstable file的元数据信息
  // 主要包括该sstable大小、起始、结束key等信息
  std::vector<FileMetaData*> tmp;
  FileMetaData* tmp2;
  // 从level-0一直读直到level_kNumLevels为止
  for (int level = 0; level < config::kNumLevels; level++) {
    // 该level的sstable file数量
    size_t num_files = files_[level].size();
    if (num_files == 0) continue;

    // Get the list of files to search in this level
    FileMetaData* const* files = &files_[level][0];
    // level_0读取
    if (level == 0) {
      level_0_process()
    } else {
      level_n_process() 
    }
    // 上面统一处理完level需要读取的文件
    // 接下来从文件中读取key
    for (uint32_t i = 0; i < num_files; ++i) {
      if (last_file_read != NULL && stats->seek_file == NULL) {
        stats->seek_file = last_file_read;
        stats->seek_file_level = last_file_read_level;
      }

      FileMetaData* f = files[i];
      last_file_read = f;
      last_file_read_level = level;

      Saver saver;
      saver.state = kNotFound;
      saver.ucmp = ucmp;
      saver.user_key = user_key;
      saver.value = value;
      // 从sstable中读取内容,底层可能使用cache缓存
      s = vset_->table_cache_->Get(options, f->number, f->file_size, ikey, &saver, SaveValue);
      if (!s.ok()) {
        return s;
      }
      switch (saver.state) {
        case kNotFound:
          break;      // Keep searching in other files
        case kFound:
          return s;
        case kDeleted:
          s = Status::NotFound(Slice());
          return s;
        case kCorrupt:
          s = Status::Corruption("corrupted key for ", user_key);
          return s;
      }
    }
  }
  return Status::NotFound(Slice());
} 

该方法的前半部分根据level层级作不同处理,主要是筛选出需要参与读的sstable文件,对于level-0,可能需要多个文件;对于其他level的sstable,一般只有一个文件。方法的后半部分则用来从前半部分筛选出来的sstable中读取可以。

从level0读

level_0_process()

tmp.reserve(num_files);
for (uint32_t i = 0; i < num_files; i++) {
    FileMetaData* f = files[i];
    if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
        ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
          tmp.push_back(f);
        }
    }
}
if (tmp.empty()) continue;
std::sort(tmp.begin(), tmp.end(), NewestFirst);
files = &tmp[0];
num_files = tmp.size();

如果是leve-0,可能会有多个sstable文件参与读取,我们需要将这些文件一一筛选出来(如果某个sstable文件的key范围包含要读取的key,视为候选人)。然后按照sstable文件的修改时间排序,最近修改的位于前面,这样如果我们读到可以了,就可以忽略其他的sstable。

从levelN读

level_N_process()

// 在level的所有sstable file中找到可能含有key的sstable
// 二分查找
uint32_t index = FindFile(vset_->icmp_, files_[level], ikey);
if (index >= num_files) {
    files = NULL;
    num_files = 0;
} else {
    tmp2 = files[index];
    // 二分查找只是比较sstable中largest key
    if (ucmp->Compare(user_key, tmp2->smallest.user_key()) < 0) {
      // All of "tmp2" is past any data for user_key
      files = NULL;
      num_files = 0;
    } else {
      files = &tmp2;
      num_files = 1;
    }
}