LevelDB源碼解析14. Version的數據結構
Version的數據結構
LevelDB裡面有很多名詞，有的還非常接近。比如 Version, VersionEdit, VersionSet, VersionSet::Builder。這些名詞放一起，嗯，再加上各種內部各種同名的數據結構，感覺比較雜亂。
所以這裡主要是解決：
- 他們的關係是什麼樣的？
- 為什麼內部需要這些數據結構?
Version
LevelDB裡面的Version是一個靜態概念。一個版本裡麪包含有多少文件，這個都是固定的。
class Version {
// ...
std::vector<FileMetaData*> files_[config::kNumLevels];
// ...
};
這個變數一旦生成後，後面就不會被更改。
兩種類型
為了更加清楚地說明問題，這裡定義兩種類型：
- 常量類型
- delta類型
常量類型是描述一個靜態的狀態的，不可更改。比如手裡有一個蘋果。能夠清晰準確地傳達手裡面蘋果的數量為1。
delta類型是一種操作，比如：來，給你一個蘋果。這個delta類型是增加的，並不能清晰的描述出手裡蘋果的數量。
常量類型A: 手裡有一個蘋果
delta類型B: 給你一個蘋果
常量類型C: 手裡有兩個蘋果
常量類型D: 手裡有三個蘋果
是可以得到: A + B = C， A + B + B = D， C + B = D
可以看出，Version就是常量類型。那麼在LevelDB裡面，什麼樣的類型是delta類型呢？答案就是VersionEdit。
VersionEdit
VersionEdit就是delta類型，所以在VersionEdit的結構裡面就需要有：
class VersionEdit {
std::set< std::pair<int, uint64_t> > deleted_files_;
std::vector< std::pair<int, FileMetaData> > new_files_;
}
可以看出，這裡放了新增加的文件new_files，需要刪除的文件deleted_files。與Version不同的是，這裡pair<int, ...>前面的int表示的LevelDB的level。而不再是像Version一樣，利用一個數組的index來表示LevelDB的level。
現在常量類型 = Version有了，delta類型 VersionEdit也有了，那麼，加號怎麼辦？
加號
在LevelDB中，加號則是由VersionSet::Builder來伴演的。也就是說，一個正常的表達式是： A + B = C。如果要用LevelDB的語言來描述，那麼就會變成Version (+VersionSet::Builder) + VersionEdit = Version。那麼接下來看一下VersionSet::Builder是如何定義的：
class VersionSet::Builder {
struct LevelState {
std::set<uint64_t> deleted_files;
std::set<FileMetaData*, BySmallestKey>* added_files;
};
Version* base_;
LevelState levels_[config::kNumLevels];
這裡需要大概講解一下這些數據結構設計的作用。正常書寫變數相加的時候，可以寫 A + B + B = D。這裡可以生成兩個加號。但是在書寫代碼的時候，考慮到內存申請釋放高效性，我們更想是通過一個變數完成這個操作。在LevelDB裡面的設計思想就是：
VersionSet::Builder build(A); // 這裡把A做為基礎項
build.Apply(B); // 累加B
build.Apply(B); // 累加B
build.SaveTo(&D); // 把結果保存到D
其中，兩個B實際上是可以合併一起的。也就是把所有要增刪的文件合併一下。合併的結果放到另外一個Delta變數中。也就是LevelState levels_[config::kNumLevels];。
如何合併
其實這個合併動作就像表達式裡面的加號。
// 累加delta變數
void Apply(VersionEdit* edit) {
// .. 這裡略過一些代碼
// 累加要刪除的文件
const VersionEdit::DeletedFileSet& del = edit->deleted_files_;
for (VersionEdit::DeletedFileSet::const_iterator iter = del.begin();
iter != del.end();
++iter) {
const int level = iter->first;
const uint64_t number = iter->second;
levels_[level].deleted_files.insert(number);
}
// 累加新文件
for (size_t i = 0; i < edit->new_files_.size(); i++) {
// 取層數
const int level = edit->new_files_[i].first;
// 根據文件的編號取出文件相應的信息
FileMetaData* f = new FileMetaData(edit->new_files_[i].second);
// 設置文件的引用
f->refs = 1;
// We arrange to automatically compact this file after
// a certain number of seeks. Lets assume:
// (1) One seek costs 10ms
// (2) Writing or reading 1MB costs 10ms (100MB/s)
// (3) A compaction of 1MB does 25MB of IO:
// 1MB read from this level
// 10-12MB read from next level (boundaries may be misaligned)
// 10-12MB written to next level
// This implies that 25 seeks cost the same as the compaction
// of 1MB of data. I.e., one seek costs approximately the
// same as the compaction of 40KB of data. We are a little
// conservative and allow approximately one seek for every 16KB
// of data before triggering a compaction.
// 文件大小除以16K可以得到允許的seek次數
// 其實這個可以做成一個配置項
f->allowed_seeks = (f->file_size / 16384);
if (f->allowed_seeks < 100) f->allowed_seeks = 100;
// 注意要把deleted_files裡面去掉這個文件number!!
levels_[level].deleted_files.erase(f->number);
levels_[level].added_files->insert(f);
}
}
等號的處理
A + B + B = D，加號是得到處理了，那麼=號應該怎麼辦呢？這裡則是由VersionSet::Builder::SaveTo來完成的。
// 從Builder中導出Version
// Save the current state in *v.
void SaveTo(Version* v) {
BySmallestKey cmp;
cmp.internal_comparator = &vset_->icmp_;
for (int level = 0; level < config::kNumLevels; level++) {
const auto &base_files = base_->files_[level];
const FileSet* added = levels_[level].added_files;
v->files_[level].reserve(base_files.size() + added->size());
// 把base_files和added這兩個有序的數組合併到一起
// ...
}
}
// 這個函數主要就是做：
// 看一下f是否是在要刪除的列表裡面
// 如果不在，那麼添加到version v相應的level的文件列表中。
void MaybeAddFile(Version* v, int level, FileMetaData* f) {
if (levels_[level].deleted_files.count(f->number) > 0) {
// File is deleted: do nothing
} else {
std::vector<FileMetaData*>* files = &v->files_[level];
if (level > 0 && !files->empty()) {
// Must not overlap
assert(vset_->icmp_.Compare((*files)[files->size()-1]->largest,
f->smallest) < 0);
}
f->refs++;
files->push_back(f);
}
}
VersionSet
按照正常的習慣，當A版本升級到B版本之後，因為A版本是老版本，這個時候實際上是可以扔掉的。但是，對於leveldb而言，這個版本有可能還在服務讀請求。所以還不能扔掉，那麼就需要同時保留AB這兩個版本。形成{A->B}這樣的結構。也就是形成一個鏈表。是的VersionSet就是利用鏈表來操作的。
class VersionSet {
// 雙向鏈表的頭指針
Version dummy_versions_;
// 當前最新版本
Version* current_;
};
這個時候，Version裡面就還必須要加上兩個指針，這樣纔可以把Version串成一個雙向鏈表。
class Version {
VersionSet* vset_; // VersionSet to which this Version belongs
Version* next_; // Next version in linked list
Version* prev_; // Previous version in linked list
int refs_; // Number of live refs to this version
};
值得注意的是：current_總是指向雙向鏈表的最後一個元素。
void VersionSet::AppendVersion(Version* v) {
// Make "v" current
assert(v->refs_ == 0);
assert(v != current_);
if (current_ != nullptr) {
current_->Unref();
}
current_ = v;
v->Ref();
// Append to linked list
v->prev_ = dummy_versions_.prev_;
v->next_ = &dummy_versions_;
v->prev_->next_ = v;
v->next_->prev_ = v;
}
那麼當有新版本生成的時候，操作流程如下：
Version v;
VersionEdit edit;
VersionSet x; // 已經包含v在裡面
VersionSet::Builder builder(&x, v);
builder.Apply(edit);
Version new;
builder.SaveTo(&new);
x.AppendVersion(new);
VersionSet
當不斷有新版本生成的時候，那麼就需要不斷地Append到version_set裡面。實際上，在leveldb的實例中，只有一個version_set。 那麼這個set雙向鏈表會不會炸掉呢？
當然是不會的，當某一個version不再服務讀請求之後，這個version就會從雙向鏈表中移除(current除外)。
推薦閱讀：
