LevelDB 源码分析：Block 的构建
block_builder.h/.cc
在 LevelDB 的 SSTable 中，数据不是一条一条顺序写入文件，而是先组织成一个个 Block，再由上层写入 SSTable。
block_builder.h/.cc 的职责，就是负责在内存中构建一个 Block。
1
2
3
4
5
6
7
8
9
| 不断 Add(key, value)
↓
编码并追加到 buffer_ [entry01, entry02..]
↓
Block 达到合适大小
↓
Finish()
↓
得到一个完整 Block
|
1. BlockBuilder 的核心状态
BlockBuilder 中的几个成员包括：
1
2
3
4
5
| std::string buffer_;
std::vector<uint32_t> restarts_;
int counter_;
std::string last_key_;
bool finished_;
|
2. 一条 Entry 是如何编码的
每次上层调用：Add(key, value), BlockBuilder 都会向 buffer_ 中追加一条 Entry。
一条 Entry 的基本格式是：
1
2
3
4
5
| <shared> // 与上一条key的公共部分的大小
<non_shared> // 非..
<value_size>
<key_delta> // 通常是key的不同部分
<value>
|
前三个字段使用 Varint32 编码。
例如：
1
2
| last_key = "apple001"
key = "apple002"
|
它们共享：
因此：
1
2
3
| shared = 7
non_shared = 1
key_delta = "2"
|
最终并不需要再次保存完整的 "apple002"。
3. 前缀压缩
BlockBuilder 中一个很重要的设计就是相邻 key 的前缀压缩。
由于 LevelDB 写入 SSTable 时，key 本身是有序的，相邻 key 往往会拥有较长的公共前缀。
因此代码会比较 last_key_ 与当前 key。
并计算二者的公共前缀长度： shared
随后计算non_shared
1
| const size_t non_shared = key.size() - shared;
|
真正写入 key 的代码：
1
| buffer_.append(key.data() + shared, non_shared);
|
含义就是：
跳过前面已经共享的部分，只保存当前 key 的剩余部分。
因此在不断调用 Add() 时，buffer_ 中的数据大致就是：
1
2
3
4
| <shared><non_shared><value_size><key_delta><value>
<shared><non_shared><value_size><key_delta><value>
<shared><non_shared><value_size><key_delta><value>
...
|
4. 为什么需要 Restart Point
如果所有 key 都一直依赖上一条 key，那么虽然压缩率很高，但如果想直接读取 Block 中间的某个 key，就必须从最前面开始，一个个恢复 key。
因此 LevelDB 引入了 restart point。
Options_ 配置中存在：
block_restart_interval = 16
即每16bytes记录一次完整的key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| size_t shared = 0;
if (counter_ < options_->block_restart_interval) {
const size_t min_length = std::min(last_key_piece.size(), key.size());
while ((shared < min_length) && (last_key_piece[shared] == key[shared])) {
shared++;
}
} else {
restarts_.push_back(buffer_.size());
counter_ = 0;
}
|
restart entry 并没有特殊的编码格式。
它依旧是：
只是此时：
shared = 0
所以 key_delta 本身就是完整 key。
5. Finish
在不断 Add() 的过程中，buffer_ 中主要保存的是一条条 Entry。
restart point 的位置则暂时单独保存在：
restarts_
直到调用：
才会把这些 restart offset 依次追加到 buffer_ 尾部，最后再保存 restart point 的数量。
因此，一个最终完成的 Block 大致可以表示为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| +-----------------------------+
| Entry 1 |
+-----------------------------+
| Entry 2 |
+-----------------------------+
| Entry 3 |
+-----------------------------+
| ... |
+-----------------------------+
| Entry N |
+-----------------------------+
| Restart Offset 0 |
+-----------------------------+
| Restart Offset 1 |
+-----------------------------+
| ... |
+-----------------------------+
| Number of Restarts |
+-----------------------------+
|
其中 restart offsets 和 restart 数量使用 fixed32 保存。
1
2
3
4
5
6
7
8
9
10
|
Slice BlockBuilder::Finish() {
for (size_t i = 0; i < restarts_.size(); i++) {
PutFixed32(&buffer_, restarts_[i]);
}
PutFixed32(&buffer_, restarts_.size());
finished_ = true;
return Slice(buffer_);
}
|
6. 总结
BlockBuilder 的职责：
将一批有序 key-value 编码成 LevelDB 所需要的 Block 格式。
其中最核心的设计主要有三个：
- 使用相邻 key 的公共前缀进行压缩；
- 使用 restart point 在压缩率和随机读取效率之间做平衡；
- 使用 Varint 保存长度信息，进一步减少空间占用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| void BlockBuilder::Add(const Slice& key, const Slice& value) {
Slice last_key_piece(last_key_);
assert(!finished_);
assert(counter_ <= options_->block_restart_interval);
assert(buffer_.empty()
|| options_->comparator->Compare(key, last_key_piece) > 0);
size_t shared = 0;
if (counter_ < options_->block_restart_interval) {
const size_t min_length = std::min(last_key_piece.size(), key.size());
while ((shared < min_length) && (last_key_piece[shared] == key[shared])) {
shared++;
}
} else {
restarts_.push_back(buffer_.size());
counter_ = 0;
}
const size_t non_shared = key.size() - shared;
PutVarint32(&buffer_, shared);
PutVarint32(&buffer_, non_shared);
PutVarint32(&buffer_, value.size());
buffer_.append(key.data() + shared, non_shared);
buffer_.append(value.data(), value.size());
last_key_.resize(shared);
last_key_.append(key.data() + shared, non_shared);
assert(Slice(last_key_) == key);
counter_++;
}
|