導(dǎo)讀
本篇博文主要是記錄leveldb的Get實(shí)現(xiàn)！Get的流程從宏觀上來說非常簡單句旱，無非是遞歸往下找阳藻，直到找到或者沒有！歷程為：
如圖谈撒，很直觀腥泥，先在內(nèi)存中的兩個(gè)table查找，找不到就去sstable（level 0 ~ n啃匿，至于n是多少可以指定蛔外，一般是10）中找.蛆楞。
step by step
讓我們一步一步看Get的流程是如何的。
1. Get函數(shù)
首先我們從db_impl中的Get函數(shù)入手冒萄，函數(shù)原型為：
Status DBImpl::Get(const ReadOptions& options,
const Slice& key,
std::string* value)
//status 是leveldb自己定義的用來處理各種狀態(tài)返回的
//ReadOptions提供一些讀取參數(shù)臊岸，目前可忽略
//key是要查找的key，而value是指針尊流，用來保存查找到的值
很直觀帅戒，其實(shí)核心就是根據(jù)key獲取到value。讓我們看看其實(shí)現(xiàn)：
Status DBImpl::Get(const ReadOptions& options,
const Slice& key,
std::string* value) {
Status s;
MutexLock l(&mutex_);
SequenceNumber snapshot;
//版本號(hào),可以讀取指定版本的數(shù)據(jù),否則讀取最新版本的數(shù)據(jù).
//注意:讀取的時(shí)候數(shù)據(jù)也是會(huì)插入的,假如Get請(qǐng)求先到來,而Put后插入一條數(shù)據(jù),這時(shí)候新數(shù)據(jù)并不會(huì)被讀取到!
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計(jì)數(shù),防止在讀取的時(shí)候并發(fā)線程釋放掉memtable的數(shù)據(jù)
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和版本號(hào)的封裝.用來查找,不然每次都要傳兩個(gè)參數(shù).把高耦合的參數(shù)合并成一個(gè)數(shù)據(jù)結(jié)構(gòu)!
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中查找(內(nèi)存中找不到就會(huì)進(jìn)入這一步)
have_stat_update = true;
}
mutex_.Lock();
}
if (have_stat_update && current->UpdateStats(stats)) {
MaybeScheduleCompaction(); //檢查是否要進(jìn)行compaction操作
}
//釋放引用計(jì)數(shù). ps:自己維護(hù)一套這樣的機(jī)制思維要非常清晰,否則很容易出bug.
mem->Unref();
if (imm != NULL) imm->Unref();
current->Unref();
return s;
}
對(duì)于函數(shù)內(nèi)部的實(shí)現(xiàn)大部分都在代碼中通過注釋的形式來說明了:其實(shí)代碼邏輯基本都是建立在一個(gè)大的框架中崖技，然后一點(diǎn)一點(diǎn)填充內(nèi)容而已逻住。如果我們總結(jié)一下，我們可以知道上面代碼的框架就是：
- 獲取版本號(hào)迎献，只讀取該版本號(hào)之前的數(shù)據(jù)瞎访；
- 在memtable中查找
- 在Imuable memtable中查找
- 在sstable（磁盤文件）中查找
所以我覺得看完這段代碼，知道這四個(gè)步驟基本差不多了吁恍。
接下來我想我們會(huì)深入看看2扒秸，3，4這三個(gè)步驟的具體實(shí)現(xiàn)冀瓦，尤其是4.因?yàn)槲覀冎榔鋵?shí)2和3不過是在跳躍表中查找而已伴奥。這種內(nèi)存數(shù)據(jù)結(jié)構(gòu)的查找無疑大家應(yīng)該是熟悉的，就跟在hashmap查找一樣翼闽！
2. memtable和Imuable memtable查找
memtable和Imuable memtable在數(shù)據(jù)結(jié)構(gòu)層面是一樣的東西拾徙，也是一樣的實(shí)現(xiàn)，只不過被使用的時(shí)候Imuable memtable加了只讀的限制感局！
簡單不尼啡！就是通過迭代器在跳躍表中查找，找到后解碼（由于數(shù)據(jù)被按照二進(jìn)制格式封裝起來了）構(gòu)造結(jié)果返回询微。就是這么簡單的兩個(gè)步驟崖瞭！
3. sstable查找
在sstable中的查找就比較復(fù)雜了，涉及到了許多文件的讀取撑毛，我們一點(diǎn)一點(diǎn)剖析读恃！
在進(jìn)入復(fù)雜的邏輯之前，我們先掌握以下脈絡(luò)是非常重要的代态。而sstable中的查找脈絡(luò)就是一個(gè)for循環(huán)：
for (int level = 0; level < config::maxLevel; level ++) {
// seek
}
簡單吧寺惫，就是從level 0中的文件中開始查找，直到最大的level蹦疑，如果中間找到就直接返回了西雀。
我們這里還需特別強(qiáng)調(diào)一下，level 0的數(shù)據(jù)是Imuable memtable直接dump到磁盤的歉摧，所以文件與文件之間的key有可能重疊的艇肴。而level n（n>0）中每個(gè)sst文件之間key是不重疊的腔呜，且key在level中是全局有序的（
注意是該level中）。
那么在每一層中是如何查找key的呢再悼？答案很簡單核畴，不外乎兩個(gè)步驟：
- 找到所有可能含有該key的文件列表fileList；
- 遍歷fileList查找key冲九；
第2步就是讀取文件內(nèi)容找出key而已谤草，那么1是如何實(shí)現(xiàn)的呢？這里我們有必要復(fù)習(xí)一下前面的內(nèi)容莺奸。我們除了sst文件（實(shí)際數(shù)據(jù)文件）丑孩，leveldb還有manifest文件，該文件保存了每個(gè)sst文件在哪一層灭贷，最小key是啥温学，最大key是啥？所以：
我們通過讀取manifest文件就能知道key有可能在哪一個(gè)sst文件中甚疟！
好了仗岖，大概的脈絡(luò)到這里應(yīng)該清楚了，我們來看代碼：
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特殊對(duì)待,key有可能在任何一個(gè)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落在該文件大小范圍,則加到文件列表供下面進(jìn)一步查詢
}
}
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); //直接找到在哪一個(gè)文件中,或者不在這個(gè)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中讀取文件的內(nèi)容,至于cache實(shí)現(xiàn),現(xiàn)在先不進(jìn)入細(xì)節(jié)
if (!s.ok()) {
return s;
}
switch (saver.state) { //查找結(jié)果返回!
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
}
代碼很長览妖，其實(shí)就是兩部分箩帚。所以掌握脈絡(luò)是多么重要！
其實(shí)上面已經(jīng)差不多把Get的流程跑了一遍了黄痪，但是有一點(diǎn)特別有意思得還想在這里交代一下：我們?cè)谏厦娲a中發(fā)現(xiàn)在sst文件中查找的時(shí)候用到了cache，畢竟要讀取磁盤盔然。這里想深入進(jìn)去看看這個(gè)cache是咋搞的桅打？
cache 你好
LRU Cache
leveldb所用到的cache是LRUCache，這個(gè)大家學(xué)操作系統(tǒng)的時(shí)候應(yīng)該都學(xué)過愈案，這里不詳細(xì)敘述了挺尾，簡單說幾句這個(gè)原理（使用java的linkedHashMap可以非常簡單實(shí)現(xiàn)！）
這里多說一句：在學(xué)生時(shí)代一直對(duì)這個(gè)概念有著錯(cuò)誤的理解站绪，當(dāng)時(shí)覺得是什么鬼遭铺？如果大家結(jié)合java的linkedHashMap來思考應(yīng)該是很簡單的。
如圖恢准，要注意這是一個(gè)linkedlist加上hashmap的性質(zhì)魂挂。linkedlist的屬性方便刪除插入，hashmap的性質(zhì)能在線性時(shí)間查找馁筐。這樣隊(duì)首元素就是最近最少使用的涂召，可以被替換掉！
上面圖中訪問到的添加到隊(duì)列前面可以在代碼中清晰看到（cache.cc文件）：
先刪除然后append到隊(duì)尾敏沉！
Leveldb cache
我們先來看一下leveldb中是如何讀取一個(gè)文件的果正。
1. 根據(jù)filenumber讀取對(duì)應(yīng)的數(shù)據(jù)文件：
很簡單兩個(gè)步驟：
- cache中查找
- cache中找不到則直接磁盤中讀取炎码，并且插入cache
那么這里還有一個(gè)問題：在哪里淘汰？
答曰：在Insert函數(shù)內(nèi)部秋泳。讓我們來看看代碼（cache.cc文件）：
上面我們只是講解了leveldb中是如何運(yùn)用LRUCache的潦闲。可是我們還沒講解cache中cache的數(shù)據(jù)是什么數(shù)據(jù)迫皱？是單個(gè)sst文件的數(shù)據(jù)歉闰？還是文件句柄數(shù)據(jù)？還是啥啥啥舍杜？
讓我們繼續(xù)深入去看看新娜。
LRUHandle
我們知道隊(duì)列元素是LRUHandle。而LRUHandle中的value就是我們實(shí)際緩存的數(shù)據(jù)：
那么這個(gè)value的數(shù)據(jù)是在哪里添加進(jìn)去的呢既绩？（table_cache.cc）：
這個(gè)value指針實(shí)際是TableAndFile的指針概龄。我們獲取到一個(gè)LRUHandle之后就可以得到一個(gè)TableAndFile指針，里面包含了：
RandomAccessFile是對(duì)讀取文件的封裝饲握。因此我們可以讀取想要的數(shù)據(jù)內(nèi)容了私杜。
總結(jié)
我們這篇文章主要講解了數(shù)據(jù)是如何讀取的以及cache是如何實(shí)現(xiàn)的。當(dāng)然講的還是脈絡(luò)救欧，很多細(xì)節(jié)都沒涉及到衰粹。不過我相信有了脈絡(luò)的掌握，再去閱讀細(xì)節(jié)就非常簡單的了笆怠。
