Skip to content

Commit 3aaaea3

Browse files
author
yangjingjing
committed
init blog
1 parent 7095f97 commit 3aaaea3

20 files changed

Lines changed: 3750 additions & 0 deletions

‎_posts/2014-09-01-算法题目.md‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
---
2+
layout: post
3+
categories: [CODE]
4+
description: none
5+
keywords: CODE
6+
---
7+
# 算法题目

‎_posts/2017-05-20-LevelDB版本控制Version.md‎

Lines changed: 281 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,281 @@
1+
---
2+
layout: post
3+
categories: [LevelDB]
4+
description: none
5+
keywords: LevelDB
6+
---
7+
# LevelDB版本控制Version
8+
9+
## 版本控制
10+
版本Version记录着LevelDB的元数据信息，LevelDB的元信息是按照版本控制的方式来管理的，一个版本Version便是一套完整的元信息记录。
11+
12+
LevelDB为何要引入版本控制？正常来说，当版本A升级到版本B后，版本A就是老版本了，这个时候实际上是可以删掉的。但是，在LevelDB中，版本A有可能还在服务读请求，因此，还不能扔掉，那么就需要同时保留这两个版本A、B，因此就形成了A->B这样的链接关系来记录，所有VersionSet就是利用链表来组织的，其中，Version dummy_versions_是双向链表的头指针，Version* current_是当前最新版本。当某一个Version不再服务读请求之后，这个Version就会从双向链表中移除。
13+
14+
15+
下面我们来解释这些跟版本相关的概念：Version、VersionEdit、VersionSet。
16+
版本Version
17+
```
18+
class Version {
19+
VersionSet* vset_; // VersionSet to which this Version belongs
20+
Version* next_; // Next version in linked list
21+
Version* prev_; // Previous version in linked list
22+
int refs_; // Number of live refs to this version
23+
// List of files per level
24+
std::vector<FileMetaData*> files_[config::kNumLevels];
25+
// Next file to compact based on seek stats.
26+
FileMetaData* file_to_compact_;
27+
int file_to_compact_level_;
28+
// Level that should be compacted next and its compaction score.
29+
// Score < 1 means compaction is not strictly needed. These fields
30+
// are initialized by Finalize().
31+
double compaction_score_;
32+
int compaction_level_;
33+
};
34+
```
35+
这是一个静态的概念，我们看到Version中的成员变量非常的多，可以分为几个功能：
36+
37+
1）前面4个成员变量与VersionSet相关的Version双向链表：这是将多个Version链接起来的。
38+
39+
2）每个版本Version都记录了它所包含的各个level中的所有文件，即：files_成员变量std::vector<FileMetaData*> files_[config::kNumLevels]，它是一个数组，数组下标就是level，每个level记录的是文件元数据集合，也就是该level所包含的全部文件元数据信息。
40+
41+
3）与文件压缩相关的信息：LevelDB通过合并操作来生成一个新的版本，因此，需要在当前Version中指定如何合并。当前level的一个文件需要与下一级里面的文件合并生成多个新文件，那就要求当前版中需要记录如何生成下一个版本，Version中就是通过最后4个compaction成员变量来记录的。
42+
43+
版本增量VersionEdit
44+
```
45+
class VersionEdit {
46+
private:
47+
friend class VersionSet;
48+
typedef std::set<std::pair<int, uint64_t>> DeletedFileSet;
49+
std::string comparator_;
50+
uint64_t log_number_;
51+
uint64_t prev_log_number_;
52+
uint64_t next_file_number_;
53+
SequenceNumber last_sequence_;
54+
bool has_comparator_;
55+
bool has_log_number_;
56+
bool has_prev_log_number_;
57+
bool has_next_file_number_;
58+
bool has_last_sequence_;
59+
std::vector<std::pair<int, InternalKey>> compact_pointers_;
60+
DeletedFileSet deleted_files_;
61+
std::vector<std::pair<int, FileMetaData>> new_files_;
62+
};
63+
```
64+
这是一个动态的概念，delta类型，是相对当前版本的增量信息，同样包括了几个功能：
65+
66+
1）与文件序号相关的记录：Version在合并时，新生成的文件会使用统一的序号，所以新文件的序号也会发生变化。这些文件序号变化也需要做为更改的一部分记录下来，各种has_xxx指示符就是说明这个序号是否发生了变化。而序号的更改，并不是累加到展现到Version上，而是直接作用于VersionSet。
67+
68+
2）压缩指针compact_pointers_：由于SSTable文件数量可能庞大，合并操作并不是一次性完成的，而且过多的压缩Compaction也会占用机器CPU资源，因此，压缩是阶段式进行的。压缩指针compact_pointers_记录在版本增量VersionEdit中，并不记录在版本Version中，每个Level下一次合并的位置最终是记录在VersionSet中的compact_pointer_。
69+
70+
每一个Version需要合并的时候，都会经过一定的计算得到每个Level下一次合并的位置，在合并操作Apply()时，直接使用压缩指针compact_pointers_中记录的Level作为索引，因为是版本的Apply，这意味着总是后面的一个版本增量VersionEdit去覆盖前面一个版本增量VersionEdit的合并位置，因此可直接赋值覆盖VersionSet中的compact_pointer_。
71+
72+
3）与文件变化有关的记录：新增文件信息new_files_和删除文件信息deleted_files_，这两个成员变量都是一个std::pair<>对象，表示哪个level新增和删除的文件信息。
73+
74+
那么Version和VersionEdit是什么关系呢？
75+
76+
我们知道数学中有表达式： A + B = C，表达的是两数相加得到另外一个数，这样的思想也体现在编程领域：base + delta = new，在LevelDB中，Version和VersionEdit之间也是这种关系，如果要用LevelDB的语言来描述，那么就会变成Version + VersionEdit = new Version。那么加号和等号是怎么体现的呢？那就是VersionSet::Builder，接下来看一下VersionSet::Builder是如何定义的：
77+
```
78+
class VersionSet::Builder {
79+
private:
80+
typedef std::set<FileMetaData*, BySmallestKey> FileSet;
81+
struct LevelState {
82+
std::set<uint64_t> deleted_files;
83+
FileSet* added_files;
84+
};
85+
VersionSet* vset_;
86+
Version* base_;
87+
LevelState levels_[config::kNumLevels];
88+
};
89+
```
90+
A + B = C用LevelDB的语言来描述，就是如下：
91+
```
92+
Version* v = new Version(this);
93+
{
94+
Builder builder(this, current_); //把current_作为基础项
95+
builder.Apply(edit); //累加增量版本edit：current_ + edit
96+
builder.SaveTo(v); //把结果保存到新版本v：current_ + edit = v
97+
}
98+
```
99+
将增量版本中记录的删除和新增的文件记录到LevelState levels_[config::kNumLevels]中，然后和当前版本Current中记录的已存在版本，一起生成一个新版本Version。
100+
101+
具体如何合并(+)？我们来看builder.Apply(edit)的实现。
102+
103+
1）更新vset_中当前压缩指针：把增量版本中压缩指针的位置记录到vset_中。
104+
105+
2）把增量版本中删除的文件file记录到Builder.levels_的已删除文件中。
106+
107+
3）把增量版本中新增的文件file记录到Builder.levels_的已添加文件中。
108+
109+
代码：
110+
```
111+
// Apply all of the edits in *edit to the current state.
112+
void Apply(VersionEdit* edit) {
113+
// Update compaction pointers 把增量版本中压缩指针的位置记录到vset_中
114+
|-for (size_t i = 0; i < edit->compact_pointers_.size(); i++) {
115+
const int level = edit->compact_pointers_[i].first;
116+
vset_->compact_pointer_[level] =
117+
edit->compact_pointers_[i].second.Encode().ToString();
118+
|-}
119+
// Delete files 把增量版本中删除的文件file记录到Builder.levels_的已删除文件中
120+
|-for (const auto& deleted_file_set_kvp : edit->deleted_files_) {
121+
const int level = deleted_file_set_kvp.first;
122+
const uint64_t number = deleted_file_set_kvp.second;
123+
levels_[level].deleted_files.insert(number);
124+
|-}
125+
// Add new files 把增量版本中新增的文件file记录到Builder.levels_的已添加文件中
126+
|-for (size_t i = 0; i < edit->new_files_.size(); i++) {
127+
const int level = edit->new_files_[i].first;
128+
FileMetaData* f = new FileMetaData(edit->new_files_[i].second);
129+
f->refs = 1;
130+
f->allowed_seeks = static_cast<int>((f->file_size / 16384U)); //为了提高读性能，文件大小除以16K可以得到允许的seek次数，超过这个次数，将触发文件被压缩Compaction。
131+
if (f->allowed_seeks < 100) f->allowed_seeks = 100;
132+
levels_[level].deleted_files.erase(f->number);
133+
levels_[level].added_files->insert(f);
134+
|-}
135+
```
136+
等号(=)的处理：我们来看builder.SaveTo(v)的实现
137+
138+
遍历所有的层级level：
139+
140+
1）把base_files和added这两个有序的数组合并到一起。
141+
142+
2）遍历这些新增文件和base文件：看一下file是否是在要删除的列表里面，如果不在，那么添加到version v相应的level的文件列表中。
143+
144+
代码：
145+
```
146+
// Save the current state in *v.
147+
void SaveTo(Version* v) {
148+
BySmallestKey cmp;//[zll]:这个对象的操作方法operator返回是否较小的key的bool值
149+
cmp.internal_comparator = &vset_->icmp_;
150+
for (int level = 0; level < config::kNumLevels; level++) {//[zll]:遍历所有的层级level
151+
// Merge the set of added files with the set of pre-existing files.
152+
// Drop any deleted files. Store the result in *v.
153+
const std::vector<FileMetaData*>& base_files = base_->files_[level];//[zll]:每一层级中，
154+
当前版本Current里面的已存在文件。
155+
std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin();
156+
std::vector<FileMetaData*>::const_iterator base_end = base_files.end();
157+
const FileSet* added_files = levels_[level].added_files;//[zll]:Builder里面记录的增量版本
158+
的新添加文件状态
159+
v->files_[level].reserve(base_files.size() + added_files->size());//[zll]:待保存的版本
160+
Version中文件files_扩展为当前版本Current里面已存在的文件+增量版本中新增加的文件。
161+
for (const auto& added_file : *added_files) {//[zll]:遍历这些新增文件
162+
// Add all smaller files listed in base_
163+
for (std::vector<FileMetaData*>::const_iterator bpos =
164+
std::upper_bound(base_iter, base_end, added_file, cmp);//[zll]:通过二分
165+
查找，找到第一个不满足cmp规则的文件，即：那些较小的文件
166+
base_iter != bpos; ++base_iter) {
167+
MaybeAddFile(v, level, *base_iter);//[zll]:把这些较小的文件追加到待保存版本Version中
168+
}
169+
MaybeAddFile(v, level, added_file);//[zll]:把新增版本中的文件追加到待保存版本Version中
170+
}
171+
// Add remaining base files
172+
for (; base_iter != base_end; ++base_iter) {
173+
MaybeAddFile(v, level, *base_iter);//[zll]:然后把当前版本CurrentVersion中的文件追加
174+
到待保存版本Version中
175+
}
176+
}
177+
}
178+
```
179+
看一下file是否是在要删除的列表里面，如果不在，那么添加到version v相应的level的文件列表中。
180+
```
181+
void MaybeAddFile(Version* v, int level, FileMetaData* f) {
182+
if (levels_[level].deleted_files.count(f->number) > 0) {
183+
// File is deleted: do nothing
184+
} else {
185+
std::vector<FileMetaData*>* files = &v->files_[level];
186+
if (level > 0 && !files->empty()) {
187+
// Must not overlap
188+
assert(vset_->icmp_.Compare((*files)[files->size() - 1]->largest,
189+
f->smallest) < 0);
190+
}
191+
f->refs++;
192+
files->push_back(f);
193+
}
194+
}
195+
};
196+
```
197+
198+
文件元数据FileMetaData
199+
```
200+
struct FileMetaData {
201+
FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) {}
202+
int refs;
203+
int allowed_seeks; // Seeks allowed until compaction
204+
uint64_t number;
205+
uint64_t file_size; // File size in bytes
206+
InternalKey smallest; // Smallest internal key served by table
207+
InternalKey largest; // Largest internal key served by table
208+
};
209+
```
210+
文件的元数据信息比较简单，包含文件号、文件大小、最小key、最大key、允许查找的次数、引用计数。对于查找key来说，最重要的是最小key和最大key，在一个文件中查找key，只要判断这个key是否在这个[smallest, largest]区间，就可以很快判定。
211+
212+
版本集VersionSet
213+
```
214+
class VersionSet {
215+
Env* const env_;
216+
const std::string dbname_;
217+
const Options* const options_;
218+
TableCache* const table_cache_;
219+
const InternalKeyComparator icmp_;
220+
uint64_t next_file_number_; //下一个manifest文件编号，在manifest日志里
221+
uint64_t manifest_file_number_; //manifest文件编号，每次重启后递增
222+
uint64_t last_sequence_; //sequence号，用于snapshot，每次写入操作都会递增
223+
uint64_t log_number_; //WAL日志文件编号
224+
uint64_t prev_log_number_; // 0 or backing store for memtable being compacted
225+
// Opened lazily
226+
WritableFile* descriptor_file_;
227+
log::Writer* descriptor_log_;
228+
Version dummy_versions_; // Head of circular doubly-linked list of versions.
229+
Version* current_; // == dummy_versions_.prev_
230+
// Per-level key at which the next compaction at that level should start.
231+
// Either an empty string, or a valid InternalKey.
232+
std::string compact_pointer_[config::kNumLevels];
233+
};
234+
```
235+
用于管理所有的Version，当不断有新版本生成的时候，那么就需要不断地Append到VersionSet里面，当旧的Version不再服务读请求之后，这个Version就会从双向链表中移除，Version* current_用于不会被移出。VersionSet同样包括了几个功能：
236+
237+
1）与Compaction压缩信息相关：每个Level下一次合并的位置最终是记录在VersionSet中的compact_pointer_。
238+
239+
2）SSTable文件LRU缓存：TableCache* const table_cache_
240+
241+
3）InternalKey比较器：InternalKeyComparator icmp_
242+
243+
4）记录版本增量VersionEdit合并之后，新文件序号的最新值。
244+
245+
5）MANIFEST文件WritableFile* descriptor_file_
246+
247+
6）WAL日志文件log::Writer* descriptor_log_
248+
249+
7）版本链表：正常来说，当版本A升级到版本B后，版本A就是老版本了，这个时候实际上是可以删掉的。但是，在LevelDB中，版本A有可能还在服务读请求，因此，还不能扔掉，那么就需要同时保留这两个版本A、B，因此就形成了A->B这样的链接关系来记录，所有VersionSet就是利用链表来组织的，其中，Version dummy_versions_是双向链表的头指针，Version* current_是当前最新版本。当某一个Version不再服务读请求之后，这个Version就会从双向链表中移除。
250+
251+
Version结构中的链表指针如下：
252+
```
253+
class Version {
254+
VersionSet* vset_; // VersionSet to which this Version belongs
255+
Version* next_; // Next version in linked list
256+
Version* prev_; // Previous version in linked list
257+
int refs_; // Number of live refs to this version
258+
… …
259+
};
260+
```
261+
注意的是：当前版本current_总是指向双向链表的最后一个元素。
262+
263+
代码：
264+
```
265+
void VersionSet::AppendVersion(Version* v) {
266+
// Make "v" current
267+
assert(v->refs_ == 0);
268+
assert(v != current_);
269+
if (current_ != nullptr) {
270+
current_->Unref();
271+
}
272+
current_ = v;//当前版本current_指向最新加的这个Version
273+
v->Ref();
274+
// Append to linked list 新版本Version追加到链表的末尾
275+
v->prev_ = dummy_versions_.prev_;
276+
v->next_ = &dummy_versions_;
277+
v->prev_->next_ = v;
278+
v->next_->prev_ = v;
279+
}
280+
```
281+
至此，版本Version、版本增量VersionEdit、版本集VersionSet以及VersionSet::Builder之间的密切又复杂的关系梳理完毕，总体感觉LevelDB对版本的处理还是有点乱的。

0 commit comments

Comments
 (0)