导读
本篇博文主要是记录leveldb的Get实现！Get的流程从宏观上来说非常简单，无非是递归往下找，直到找到或者没有！历程为：
如图，很直观，先在内存中的两个table查找，找不到就去sstable（level 0 ~ n，至于n是多少可以指定，一般是10）中找.。
step by step
让我们一步一步看Get的流程是如何的。
1. Get函数
首先我们从db_impl中的Get函数入手，函数原型为：
Status DBImpl::Get(const ReadOptions& options,
const Slice& key,
std::string* value)
//status 是leveldb自己定义的用来处理各种状态返回的
//ReadOptions提供一些读取参数，目前可忽略
//key是要查找的key，而value是指针，用来保存查找到的值
很直观，其实核心就是根据key获取到value。让我们看看其实现：
Status DBImpl::Get(const ReadOptions& options,
const Slice& key,
std::string* value) {
Status s;
MutexLock l(&mutex_);
SequenceNumber snapshot;
//版本号,可以读取指定版本的数据,否则读取最新版本的数据.
//注意:读取的时候数据也是会插入的,假如Get请求先到来,而Put后插入一条数据,这时候新数据并不会被读取到!
if (options.snapshot != NULL) {
snapshot = reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_;
} else {
snapshot = versions_->LastSequence();
}
//分别获取到memtable和Imuable memtable的指针
MemTable* mem = mem_;
MemTable* imm = imm_;
Version* current = versions_->current();
//增加reference计数,防止在读取的时候并发线程释放掉memtable的数据
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();
// First look in the memtable, then in the immutable memtable (if any).
//LookupKey是由key和版本号的封装.用来查找,不然每次都要传两个参数.把高耦合的参数合并成一个数据结构!
LookupKey lkey(key, snapshot);
if (mem->Get(lkey, value, &s)) { //memtable中查找
// Done
} else if (imm != NULL && imm->Get(lkey, value, &s)) { //Imuable memtable中查找
// Done
} else {
s = current->Get(options, lkey, value, &stats); //sstable中查找(内存中找不到就会进入这一步)
have_stat_update = true;
}
mutex_.Lock();
}
if (have_stat_update && current->UpdateStats(stats)) {
MaybeScheduleCompaction(); //检查是否要进行compaction操作
}
//释放引用计数. ps:自己维护一套这样的机制思维要非常清晰,否则很容易出bug.
mem->Unref();
if (imm != NULL) imm->Unref();
current->Unref();
return s;
}
对于函数内部的实现大部分都在代码中通过注释的形式来说明了:其实代码逻辑基本都是建立在一个大的框架中，然后一点一点填充内容而已。如果我们总结一下，我们可以知道上面代码的框架就是：
- 获取版本号，只读取该版本号之前的数据；
- 在memtable中查找
- 在Imuable memtable中查找
- 在sstable（磁盘文件）中查找
所以我觉得看完这段代码，知道这四个步骤基本差不多了。
接下来我想我们会深入看看2，3，4这三个步骤的具体实现，尤其是4.因为我们知道其实2和3不过是在跳跃表中查找而已。这种内存数据结构的查找无疑大家应该是熟悉的，就跟在hashmap查找一样！
2. memtable和Imuable memtable查找
memtable和Imuable memtable在数据结构层面是一样的东西，也是一样的实现，只不过被使用的时候Imuable memtable加了只读的限制！
简单不！就是通过迭代器在跳跃表中查找，找到后解码（由于数据被按照二进制格式封装起来了）构造结果返回。就是这么简单的两个步骤！
3. sstable查找
在sstable中的查找就比较复杂了，涉及到了许多文件的读取，我们一点一点剖析！
在进入复杂的逻辑之前，我们先掌握以下脉络是非常重要的。而sstable中的查找脉络就是一个for循环：
for (int level = 0; level < config::maxLevel; level ++) {
// seek
}
简单吧，就是从level 0中的文件中开始查找，直到最大的level，如果中间找到就直接返回了。
我们这里还需特别强调一下，level 0的数据是Imuable memtable直接dump到磁盘的，所以文件与文件之间的key有可能重叠的。而level n（n>0）中每个sst文件之间key是不重叠的，且key在level中是全局有序的（
注意是该level中）。
那么在每一层中是如何查找key的呢？答案很简单，不外乎两个步骤：
- 找到所有可能含有该key的文件列表fileList；
- 遍历fileList查找key；
第2步就是读取文件内容找出key而已，那么1是如何实现的呢？这里我们有必要复习一下前面的内容。我们除了sst文件（实际数据文件），leveldb还有manifest文件，该文件保存了每个sst文件在哪一层，最小key是啥，最大key是啥？所以：
我们通过读取manifest文件就能知道key有可能在哪一个sst文件中！
好了，大概的脉络到这里应该清楚了，我们来看代码：
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;
// 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++) {
/*-----------------找到可能包含key的文件列表begin------------------------*/
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];
if (level == 0) { //level0特殊对待,key有可能在任何一个level0的文件中
// 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); //如果查找key落在该文件大小范围,则加到文件列表供下面进一步查询
}
}
if (tmp.empty()) continue;
std::sort(tmp.begin(), tmp.end(), NewestFirst);
files = &tmp[0];
num_files = tmp.size();
} else {
// Binary search to find earliest index whose largest key >= ikey.
uint32_t index = FindFile(vset_->icmp_, files_[level], ikey); //直接找到在哪一个文件中,或者不在这个level
if (index >= num_files) {
files = NULL;
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 = NULL;
num_files = 0;
} else {
files = &tmp2;
num_files = 1;
}
}
}
/*-----------------找到可能包含key的文件列表end------------------------*/
/*-----------------遍历文件查找key begin------------------------*/
for (uint32_t i = 0; i < num_files; ++i) { //如果num_files不为0,说明key有可能在这些文件中
if (last_file_read != NULL && stats->seek_file == NULL) {
// 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;
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); //在cache中读取文件的内容,至于cache实现,现在先不进入细节
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;
}
}
/*-----------------遍历文件查找key begin------------------------*/
}
return Status::NotFound(Slice()); // Use an empty error message for speed
}
代码很长，其实就是两部分。所以掌握脉络是多么重要！
其实上面已经差不多把Get的流程跑了一遍了，但是有一点特别有意思得还想在这里交代一下：我们在上面代码中发现在sst文件中查找的时候用到了cache，毕竟要读取磁盘。这里想深入进去看看这个cache是咋搞的？
cache 你好
LRU Cache
leveldb所用到的cache是LRUCache，这个大家学操作系统的时候应该都学过，这里不详细叙述了，简单说几句这个原理（使用java的linkedHashMap可以非常简单实现！）
这里多说一句：在学生时代一直对这个概念有着错误的理解，当时觉得是什么鬼？如果大家结合java的linkedHashMap来思考应该是很简单的。
如图，要注意这是一个linkedlist加上hashmap的性质。linkedlist的属性方便删除插入，hashmap的性质能在线性时间查找。这样队首元素就是最近最少使用的，可以被替换掉！
上面图中访问到的添加到队列前面可以在代码中清晰看到（cache.cc文件）：
先删除然后append到队尾！
Leveldb cache
我们先来看一下leveldb中是如何读取一个文件的。
1. 根据filenumber读取对应的数据文件：
很简单两个步骤：
- cache中查找
- cache中找不到则直接磁盘中读取，并且插入cache
那么这里还有一个问题：在哪里淘汰？
答曰：在Insert函数内部。让我们来看看代码（cache.cc文件）：
上面我们只是讲解了leveldb中是如何运用LRUCache的。可是我们还没讲解cache中cache的数据是什么数据？是单个sst文件的数据？还是文件句柄数据？还是啥啥啥？
让我们继续深入去看看。
LRUHandle
我们知道队列元素是LRUHandle。而LRUHandle中的value就是我们实际缓存的数据：
那么这个value的数据是在哪里添加进去的呢？（table_cache.cc）：
这个value指针实际是TableAndFile的指针。我们获取到一个LRUHandle之后就可以得到一个TableAndFile指针，里面包含了：
RandomAccessFile是对读取文件的封装。因此我们可以读取想要的数据内容了。
总结
我们这篇文章主要讲解了数据是如何读取的以及cache是如何实现的。当然讲的还是脉络，很多细节都没涉及到。不过我相信有了脉络的掌握，再去阅读细节就非常简单的了。
