LevelDB源码分析-Get

Get

LevelDB提供了Get接口用于给定key的查找：

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

Get操作可以指定在某个snapshot的情况下进行，如果指定了snapshot，则获取该snapshot的sequencenumber，如果没有指定snapshot，就取当前最新的sequencenumber：

 Status s; MutexLock l(&mutex_); SequenceNumber snapshot; if (options.snapshot != nullptr) { snapshot = static_cast<const SnapshotImpl *>(options.snapshot)->sequence_number(); } else { snapshot = versions_->LastSequence(); } MemTable *mem = mem_; MemTable *imm = imm_; Version *current = versions_->current(); mem->Ref(); if (imm != nullptr) imm->Ref(); current->Ref(); 

首先在memtable里找，如果找到了就结束查找，然后再immutable memtable里找（如果immutable memtable存在），如果找到了就结束查找，在这两个地方查找使用的都是MemTable类提供的Get接口函数（在这里有分析LevelDB源码分析-MemTable。最后使用Version类提供的Get接口函数在sstable中查找：

 // 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)) { // Done } else if (imm != nullptr && imm->Get(lkey, value, &s)) { // Done } else { s = current->Get(options, lkey, value, &stats); have_stat_update = true; } mutex_.Lock(); } 

如果在sstable中查找了，会更新查找涉及到的sstable的seek次数，可能会触发compact条件，因此需要调用MaybeScheduleCompaction函数进行可能的compact操作（在这里有分析https://www.cnblogs.com/YuNanlong/p/9440548.html）：

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

接下来分析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 = nullptr; stats->seek_file_level = -1; FileMetaData *last_file_read = nullptr; int last_file_read_level = -1; // We can search level-by-level since entries never hop across // levels. Therefore we are guaranteed that if we find data // in an smaller level, later levels are irrelevant. std::vector<FileMetaData *> tmp; FileMetaData *tmp2; 

在每一层中搜索：

 for (int level = 0; level < config::kNumLevels; level++) { 

如果该level没有文件则直接跳过：

 size_t num_files = files_[level].size(); if (num_files == 0) continue; 

如果当前位于level0，将所有可能包含key的文件都加入files中：

 // Get the list of files to search in this level FileMetaData *const *files = &files_[level][0]; if (level == 0) { // Level-0 files may overlap each other. Find all files that // overlap user_key and process them in order from newest to oldest. 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(); } 

如果当前不是level0，则调用FindFile进行二分查找，找到file后验证要找的key是不是在file中，如果是，加入files：

 else { // Binary search to find earliest index whose largest key >= ikey. uint32_t index = FindFile(vset_->icmp_, files_[level], ikey); if (index >= num_files) { files = nullptr; num_files = 0; } else { tmp2 = files[index]; if (ucmp->Compare(user_key, tmp2->smallest.user_key()) < 0) { // All of "tmp2" is past any data for user_key files = nullptr; num_files = 0; } else { files = &tmp2; num_files = 1; } } } 

遍历找到的files，如果seek的文件不止一个，则记录下第一个seek的文件，之后要将这个文件的seek减一（调用UpdateStats函数）：

 for (uint32_t i = 0; i < num_files; ++i) { if (last_file_read != nullptr && stats->seek_file == nullptr) { // We have had more than one seek for this read. Charge the 1st file. 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; 

调用table_cache_->Get函数在文件中搜索key值，如果没有找到，则继续搜索下一个file，如果找到了，不论是删除的还是过期的，都返回（因为之后就算找到了key，也比现在的key旧，被现在的key覆盖）：

 Saver saver; saver.state = kNotFound; saver.ucmp = ucmp; saver.user_key = user_key; saver.value = value; 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()); // Use empty error message for speed return s; case kCorrupt: s = Status::Corruption("corrupted key for ", user_key); return s; } } 

230 Love u