您现在的位置是:首页 > 文章详情

LevelDB源码分析-Get

日期:2019-04-05点击:278

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

原文链接:https://my.oschina.net/yunanlong/blog/3032918
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章