LevelDB的sstable解读
LevelDB分析
文章目录
1. 分析点
1.1 静态分析点
- 磁盘存储的物理结构与逻辑结构，借鉴到目前的正排结构；
- 内存存储的物理结构与逻辑结构，借鉴到目前的正排结构；
- 缓存cache的物理结构与逻辑结构，缓存的更新、淘汰；
1.2 动态分析点
- 添、删、改、查的流程；
- 多线程的并发问题；
2. leveldb中的SSTable
2.1 引言
SSTable文件是落在磁盘上的真正文件，leveldb存储路径中的.sst 类型的文件都是SSTable文件。 本文介绍该文件的格式，以及leveldb如何一条记录一条记录的增加到SSTable文件。
首先要注意，SSTable文件里面存放的是大量的key-value，因为leveldb就是一个key-value DB。我们都买过字典，如果把字典的每一个字当成key，对字的解释当成value，字典就是一个key-value DB。
在收录几千上万个字的字典中，如何快速寻找到茴香的茴字？
字典第一个思想是有序，按照一定的顺序收录，如果无序，杂乱无章地收录key-value就会给检索带来麻烦。
字典的第二个思想是目录，本质是索引，茴读作Hui，因此，在字典中有如下的格式.
A ...............................................................页码
B ...............................................................页码
C ...............................................................页码
D ...............................................................页码
E ...............................................................页码
F ...............................................................页码
H
|____ a ...............................................................页码
|____ .. ...............................................................页码
|____ u
|____ a ...............................................................页码
|____ .. ...............................................................页码
|____ i ...............................................................页码
...
这两种思想在leveldb中都有体现，但是leveldb的挑战要大于组织一个字典。
首先字典的是死的，一旦字典组织好，字典不会发生变动，既不会增加新的内容，也不会删除某一个字，leveldb则不同，leveldb是动态变化的，你无法预测用户会插入多少笔key-value的记录，用户可能修改某条key-value对，也可能删除某条记录。
另外一个难点是字可以穷尽，但是key-value中的key无法穷举。
2.2 SSTable的layout
在doc/table_format.txt中如下图：
<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer] (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>
首先SSTtable文件不是固定长度的，从上图中也可以看出，文件的内容要能够自解释，就需要有在固定位置有一定数据结构，顺藤摸瓜，理顺文件的内容。
对于leveldb而言，Footer是线头，从Footer开始就可以找到该文件的其他组成部分如index block和metaindex block，进而解释整个文件的内容。>
Footer的长度是固定的，因此对于SSTable文件的最后 sizeof(Footer)字节就是存放的Footer信息。 Footer固定48B，如下图所示：>
metaindex_handle: char[p]; // Block handle for metaindex
index_handle: char[q]; // Block handle for index
padding: char[40-p-q]; // zeroed bytes to make fixed length
// (40==2*BlockHandle::kMaxEncodedLength)
magic: fixed64; // == 0xdb4775248b80fb57 (little-endian)
其中最后的magic number是固定的长度的8字节：
static const uint64_t kTableMagicNumber = 0xdb4775248b80fb57ull;
为了文件的自解释，内部必须要有指针指向文件的其他位置来表示某个section的开始和结束位置。负责记录这个的变量叫做BlockHandle，他有两个成员变量offset_ 和 size_，分别记录的某个数据块的起始位置和长度。
class BlockHandle {
private:
uint64_t offset_;
uint64_t size_;
};
一个uint64整数经过varint64编码后最大占用10个字节，一个BlockHandle包含两个uint64类型(size和offset)，则一个BlockHandle最多占用20个字节，即BLockHandle::kMaxEncodedLength=20。metaindex_handle和index_handle最大占用字节为40个字节。magic number占用8个字节，是个固定数值，用于读取时校验是否跟填充时相同，不相同的话就表示此文件不是一个SSTable文件(bad magic number)。padding用于补齐为40字节。
sstable文件中footer中可以解码出在文件的结尾处距离footer最近的index block的BlockHandle，以及metaindex block的BlockHandle，从而确定这两个组成部分在文件中的位置。
事实上，在table/table_build.cc中的Status TableBuilder::Finish()函数，我们可以看出，当生成sstable文件的时候，各个组成部分的写入顺序：
Status TableBuilder::Finish() {
Rep* r = rep_;
Flush(); /*写入尚未Flush的Block块*/
assert(!r->closed);
r->closed = true;
BlockHandle filter_block_handle, metaindex_block_handle, index_block_handle;
// 写入filter_block块，即图中的meta block
if (ok() && r->filter_block != NULL) {
WriteRawBlock(r->filter_block->Finish(), kNoCompression,
&filter_block_handle);
}
// 写入metaindex block
if (ok()) {
BlockBuilder meta_index_block(&r->options);
if (r->filter_block != NULL) {
// Add mapping from "filter.Name" to location of filter data
std::string key = "filter.";
key.append(r->options.filter_policy->Name());
std::string handle_encoding;
filter_block_handle.EncodeTo(&handle_encoding);
meta_index_block.Add(key, handle_encoding);
}
// TODO(postrelease): Add stats and other meta blocks
WriteBlock(&meta_index_block, &metaindex_block_handle);
}
// 写入index block
if (ok()) {
if (r->pending_index_entry) {
r->options.comparator->FindShortSuccessor(&r->last_key);
std::string handle_encoding;
r->pending_handle.EncodeTo(&handle_encoding);
r->index_block.Add(r->last_key, Slice(handle_encoding));
r->pending_index_entry = false;
}
WriteBlock(&r->index_block, &index_block_handle);
}
// 写入footer， footer为固定长度，在文件的最尾部
if (ok()) {
Footer footer;
//将metaindex block在文件中的位置信息记录在footer
footer.set_metaindex_handle(metaindex_block_handle);
//将index block在sstabke文件中的位置信息记录在footer
footer.set_index_handle(index_block_handle);
std::string footer_encoding;
footer.EncodeTo(&footer_encoding);
r->status = r->file->Append(footer_encoding);
if (r->status.ok()) {
r->offset += footer_encoding.size();
}
}
return r->status;
}
从Finish函数也可以看出，各个部分在文件中的位置即是上图所绘制的那样。
index block, metaindex block , filter block（图中的meta block），甚至最终的data block，这些block都是干啥用的，数据又是怎么组织的呢？
- Data Blocks: 存储一系列有序的key-value
- Meta Block：存储key-value对应的filter(默认为bloom filter)
- metaindex block: 指向Meta Block的索引
- Index BLocks: 指向Data Blocks的索引
- Footer : 指向索引的索引
它们之间的关系如下图所示,后面会详细介绍这些部分的关系和存在的作用。
2.2 Data Block
2.2.1 技术点
- 由于key是按照顺序存储，所以可以使用前缀的方式进行数据压缩（value目前看来不好压缩）；
2.2.2 技术简介
最容易理解的应该是Data Block，存放的就是一系列有序的key-value，为了节省存储空间，Data block做了一些改进。
初次阅读代码，或者看示意图，很容易产生的误解是 Data Block是定长的，这种理解是错误的，实际上data block是变长的。
“block_size” is not a “size”, it is a threshold. Data is never split
across blocks. A single block contains one or more key/value pairs.
leveldb starts a new block only when the total size of all key/values in
the current block exceed the threshold.
只不过它总是在写满options.block_size的时候开始Flush，追加写入到sstable file，如table/table_build.cc中的
void TableBuilder::Add(const Slice& key, const Slice& value) {
Rep* r = rep_;
...
r->data_block.Add(key, value);
const size_t estimated_block_size = r->data_block.CurrentSizeEstimate();
if (estimated_block_size >= r->options.block_size) {
Flush();
}
}
而这个options.block_size默认为4KB。
2.2.3 Data block的物理结构
1）Data Block里面的数据是按照顺寻存放的，是有序的；
2）跳跃表、二级跳、遍历找；
注意，很多key可能有重复的字节，比如“hellokitty”和”helloworld“是两个相邻的key，由于key中有公共的部分“hello”，因此，如果将公共的部分提取，可以有效的节省存储空间。
处于这种考虑，LevelDb采用了前缀压缩(prefix-compressed)，由于LevelDb中key是按序排列的，这可以显著的减少空间占用。另外，每间隔16个keys(目前版本中options_->block_restart_interval默认为16)，LevelDb就取消使用前缀压缩，而是存储整个key(我们把存储整个key的点叫做重启点，实际也是跳跃表)。
向sstable添加一个key－value，函数的入口点是：
void TableBuilder::Add(const Slice& key, const Slice& value) {
Rep* r = rep_;
assert(!r->closed);
if (!ok()) return;
if (r->num_entries > 0) {
assert(r->options.comparator->Compare(key, Slice(r->last_key)) > 0);
}
/*此处我们先忽略index block的部分*/
if (r->pending_index_entry) {
assert(r->data_block.empty());
r->options.comparator->FindShortestSeparator(&r->last_key, key);
std::string handle_encoding;
r->pending_handle.EncodeTo(&handle_encoding);
r->index_block.Add(r->last_key, Slice(handle_encoding));
r->pending_index_entry = false;
}
/*此处我们先忽略filter block的部分*/
if (r->filter_block != NULL) {
r->filter_block->AddKey(key);
}
r->last_key.assign(key.data(), key.size());
r->num_entries++;
/* 向data block中添加一组key-value pair */
r->data_block.Add(key, value);
const size_t estimated_block_size = r->data_block.CurrentSizeEstimate();
if (estimated_block_size >= r->options.block_size) {
Flush();
}
}
我们先忽略index block和filter block的部分，集中精力查看data block如何新增key－value对：
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() // No values yet?
|| options_->comparator->Compare(key, last_key_piece) > 0);
size_t shared = 0;
if (counter_ < options_->block_restart_interval) {
// See how much sharing to do with previous string
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 {
// Restart compression
/*新的重启点，记录下位置*/
restarts_.push_back(buffer_.size());
counter_ = 0;
}
const size_t non_shared = key.size() - shared;
// Add "<shared><non_shared><value_size>" to buffer_
PutVarint32(&buffer_, shared);
PutVarint32(&buffer_, non_shared);
PutVarint32(&buffer_, value.size());
// Add string delta to buffer_ followed by value
buffer_.append(key.data() + shared, non_shared);
buffer_.append(value.data(), value.size());
// Update state
last_key_.resize(shared);
last_key_.append(key.data() + shared, non_shared);
assert(Slice(last_key_) == key);
counter_++;
}
2.2.4 Data block的记录的格式
对于data block中的每一个记录，其格式如下：
当当前data_block中的内容足够多，预计大于预设的门限值的时候，就开始flush，所谓data block的Flush就是将所有的重启点指针记录下来，并且记录重启点的个数：
Slice BlockBuilder::Finish() {
// Append restart array
for (size_t i = 0; i < restarts_.size(); i++) {
PutFixed32(&buffer_, restarts_[i]);
}
PutFixed32(&buffer_, restarts_.size());
finished_ = true;
return Slice(buffer_);
}
至此，介绍完了SSTable文件中的data block。
注意，一个SSTable中存在着多个data block，尽管他们之间是有序的，可是你查找的key到底位于哪个block上？典型的sstable文件大小为2M，可以设置的更大，每个sstable 文件中data block 的个数可能上百，如何在这上百个data block中寻找你要的key？
2.3 Index Block
2.3.1 技术点
2.3.2 技术简介
上面介绍了SSTable的layout，以及footer和Data Block的结构。本文介绍index block。
footer中记录了index block和metaindex block的位置信息，这说明两者是非常重要的。 我们先介绍index block的作用。
典型的Data Block大小为4KB，而sstable文件的典型大小为2MB，也就说，一个sstable中，存在很多data block块，如果用户要查找某个key，该key到底位于which data block?
如果没有index block，只有data block的起始位置和长度 （这个信息一定要有，否则无法确定查找，因为data block是变长的，并不是固定大小的），当用户查找某个key的时候，尽管是数据是有序的，可是还是不得不线性地找遍所有data block。任何一次查找要不得不读取2MB左右的内容，势必造成性能的恶化。
（其实也可以采用瞎猜算法，比如有256个data block的位置信息，先去找第128个 data block，判断第一个key和要找的key的关系，来二分查找。但是这种思路已经非常逼近index block的实现了。）
上帝说要有光，所有就有了光。Leveldb说要有索引，所有就有了index block。
index block的组织形式 data block的组织形式是一模一样的，不同点的地方在于存储的内容。data block存放的客户输入的key-value，而 index block存放的是 索引，我们细细展开。
如果上一个data block的最后一个key是 “helloleveldb”， 而当前data block的第一个key是“helloworld ”，那么index block就会在新block插入第一个key “helloworld”的时候，计算出两个data block之间的分割key（比如leveldb中算出来的hellom）。比分割key（hellom）小的key，在上一个data block，比分割key(hellom)大的key在下一个data block，因此
key = 分割key
value = 上一个data block的（offset，size）
通过这种手段，可以快速地定位出我们要找的key位于哪个data block(当然也可能压根不存在)。
2.3.3 index block的实现
前言介绍了index block的原理部分，下面介绍index block的细节。
首先index block中的数据元素，是根据上一个data block的最后一个key和下一个data block的第一个key，计算出来一个分割key，结合上一个data block的位置信息（offset ，size），作为一组key-value存入index block。那么时机就很明确了，就是当data block插入第一个key-value的时候，就需要计算分割key，以及存入index block。
void TableBuilder::Add(const Slice& key, const Slice& value) {
Rep* r = rep_;
assert(!r->closed);
if (!ok()) return;
if (r->num_entries > 0) {
assert(r->options.comparator->Compare(key, Slice(r->last_key)) > 0);
}
/********************************************************************************
pending_index_entry 标志位用来判定是不是data block的第一个key，
因此在上一个data block Flush的时候，会将该标志位置位，
当下一个data block第一个key-value到来后，成功往index block插入分割key之后，就会清零
**********************************************************************************/
if (r->pending_index_entry) {
assert(r->data_block.empty());
r->options.comparator->FindShortestSeparator(&r->last_key, key);
std::string handle_encoding;
r->pending_handle.EncodeTo(&handle_encoding);
/*****************************************************************************
计算出来的分割key即r->last_key作为key，而上一个data block的位置信息作为value。
pending_handle里面存放的是上一个data block的位置信息，BlockHandle类型*
注意index_block的组织形式和上一篇讲的Data block是一模一样的，
区别在于存放的key-value pair不同。
*****************************************************************************/
r->index_block.Add(r->last_key, Slice(handle_encoding));
r->pending_index_entry = false;
}
/*暂时忽略filter block部分*/
if (r->filter_block != NULL) {
r->filter_block->AddKey(key);
}
r->last_key.assign(key.data(), key.size());
r->num_entries++;
r->data_block.Add(key, value);
/*估算当前data block的长度，如果超过了阈值，就要Flush*/
const size_t estimated_block_size = r->data_block.CurrentSizeEstimate();
if (estimated_block_size >= r->options.block_size) {
Flush();
}
}
void TableBuilder::Flush() {
Rep* r = rep_;
assert(!r->closed);
if (!ok()) return;
if (r->data_block.empty()) return;
assert(!r->pending_index_entry);
WriteBlock(&r->data_block, &r->pending_handle);
if (ok()) {
/************************************
设置pending_index_entry为true
当下一个key-value到来的时候，就需要计算分割key，
融合pending_handle中存放的上一个data block位置信息，
作为key-value pair，插入到index block
*************************************/
r->pending_index_entry = true;
/*文件Flush，写入硬件。*/
r->status = r->file->Flush();
}
if (r->filter_block != NULL) {
r->filter_block->StartBlock(r->offset);
}
}
void TableBuilder::WriteBlock(BlockBuilder* block, BlockHandle* handle) {
// File format contains a sequence of blocks where each block has:
// block_data: uint8[n]
// type: uint8
// crc: uint32
assert(ok());
Rep* r = rep_;
Slice raw = block->Finish();
Slice block_contents;
CompressionType type = r->options.compression;
// TODO(postrelease): Support more compression options: zlib?
switch (type) {
case kNoCompression:
block_contents = raw;
break;
/*可以将内容压缩，但是一般不开启，走上面那个分支*/
case kSnappyCompression: {
std::string* compressed = &r->compressed_output;
if (port::Snappy_Compress(raw.data(), raw.size(), compressed) &&
compressed->size() < raw.size() - (raw.size() / 8u)) {
block_contents = *compressed;
} else {
// Snappy not supported, or compressed less than 12.5%, so just
// store uncompressed form
block_contents = raw;
type = kNoCompression;
}
break;
}
}
WriteRawBlock(block_contents, type, handle);
r->compressed_output.clear();
block->Reset();
}
void TableBuilder::WriteRawBlock(const Slice& block_contents,
CompressionType type,
BlockHandle* handle) {
Rep* r = rep_;
/*此处handle即为前面传入的 r->pending_handle,记录下上一个data block的offset和size*/
handle->set_offset(r->offset);
handle->set_size(block_contents.size());
/*追加写入data block的内容*/
r->status = r->file->Append(block_contents);
if (r->status.ok()) {
char trailer[kBlockTrailerSize];
trailer[0] = type;
uint32_t crc = crc32c::Value(block_contents.data(), block_contents.size());
crc = crc32c::Extend(crc, trailer, 1); // Extend crc to cover block type
EncodeFixed32(trailer+1, crc32c::Mask(crc));
r->status = r->file->Append(Slice(trailer, kBlockTrailerSize));
if (r->status.ok()) {
r->offset += block_contents.size() + kBlockTrailerSize;
}
}
}
往index block添加 key-value pair的时机，我们基本已经走了一遍，但是我们一直说分割key，那么分割key到底是怎么算出来的。
2.3.4 分割key的计算Comparator
Comparator负责计算两个data block之间的分割key，他需要的输入只有2个，
- 上一个data block的最后一个key
- 下一个data block的第一个key
根据两者，就能算出一个key，作为两个data block之间的分割线。
/********************************************************************************
pending_index_entry 标志位用来判定是不是data block的第一个key，
因此在上一个data block Flush的时候，会将该标志位置位，
当下一个data block第一个key-value到来后，成功往index block插入分割key之后，就会清零
**********************************************************************************/
if (r->pending_index_entry) {
assert(r->data_block.empty());
r->options.comparator->FindShortestSeparator(&r->last_key, key);
std::string handle_encoding;
r->pending_handle.EncodeTo(&handle_encoding);
/*****************************************************************************
计算出来的分割key即r->last_key作为key，而上一个data block的位置信息作为value。
pending_handle里面存放的是上一个data block的位置信息，BlockHandle类型*
注意index_block的组织形式和上一篇讲的Data block是一模一样的，
区别在于存放的key-value pair不同。
*****************************************************************************/
r->index_block.Add(r->last_key, Slice(handle_encoding));
r->pending_index_entry = false;
}
TableBuild中Add函数的这段逻辑就是用来计算分割key，并插入key-value pair到index block。关键函数在
r->options.comparator->FindShortestSeparator(&r->last_key, key);
FindShortestSeparator的声明如下：
FindShortestSeparator(std::string *start, const Slice& limit)
该函数的的作用是，如果start<limit,就把start修改为*start和limit的共同前缀后面多一个字符加1。很难理解用例子来说明下：
*start: helloleveldb 上一个data block的最后一个key
limit: helloworld 下一个data block的第一个key
由于 *start < limit, 所以调用 FindShortSuccessor(start, limit)之后，start变成：
hellom (保留前缀，第一个不相同的字符+1)
这里面有一个特例，即上一个data block的最后一个key是下一个data block第一个可以 的子串，怎么处理?
*start: hello 上一个data block的最后一个key
limit: helloworld 下一个data block的第一个key
由于 *start < limit, 所以调用 FindShortSuccessor(start, limit)之后，start变成：
hello (保留前缀，第一个不相同的字符+1)
答案是就用上一个 data block的最后一个key作为分割key。详情可以阅读下面代码：
virtual void FindShortestSeparator(
std::string* start,
const Slice& limit) const {
// Find length of common prefix
size_t min_length = std::min(start->size(), limit.size());
size_t diff_index = 0;
while ((diff_index < min_length) &&
((*start)[diff_index] == limit[diff_index])) {
diff_index++;
}
/*上一个data block的key是下一个data block的子串，则不处理*/
if (diff_index >= min_length) {
// Do not shorten if one string is a prefix of the other
} else {
uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
if (diff_byte < static_cast<uint8_t>(0xff) &&
diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
(*start)[diff_index]++;
start->resize(diff_index + 1);
assert(Compare(*start, limit) < 0);
}
}
}
2.3.5 index block的落盘
index block的组织形式和 data block一样，区别在于key value的内容。这些index信息最终要写入sstable文件，落在磁盘上。何时做，怎么做？
在TableBuilder::Finish函数，实现了将index block写入sstablefile，并最终落盘。
Status TableBuilder::Finish() {
Rep* r = rep_;
Flush();
assert(!r->closed);
r->closed = true;
BlockHandle filter_block_handle, metaindex_block_handle, index_block_handle;
// Write filter block
if (ok() && r->filter_block != NULL) {
WriteRawBlock(r->filter_block->Finish(), kNoCompression,
&filter_block_handle);
}
// Write metaindex block
if (ok()) {
BlockBuilder meta_index_block(&r->options);
if (r->filter_block != NULL) {
// Add mapping from "filter.Name" to location of filter data
std::string key = "filter.";
key.append(r->options.filter_policy->Name());
std::string handle_encoding;
filter_block_handle.EncodeTo(&handle_encoding);
meta_index_block.Add(key, handle_encoding);
}
// TODO(postrelease): Add stats and other meta blocks
WriteBlock(&meta_index_block, &metaindex_block_handle);
}
// Write index block
if (ok()) {
if (r->pending_index_entry) {
r->options.comparator->FindShortSuccessor(&r->last_key);
std::string handle_encoding;
r->pending_handle.EncodeTo(&handle_encoding);
r->index_block.Add(r->last_key, Slice(handle_encoding));
r->pending_index_entry = false;
}
/*写入Index Block的内容，
*最重要的是，算出index block在file中的offset和size，存放到index_block_handle中，
*这个信息要记录在footer中
*/
WriteBlock(&r->index_block, &index_block_handle);
}
// Write footer
if (ok()) {
Footer footer;
footer.set_metaindex_handle(metaindex_block_handle);
footer.set_index_handle(index_block_handle);
std::string footer_encoding;
footer.EncodeTo(&footer_encoding);
r->status = r->file->Append(footer_encoding);
if (r->status.ok()) {
r->offset += footer_encoding.size();
}
}
return r->status;
}
注意，写入的Index Block内容之后，记录了Index Block在sstable中的offset和size，存放在index_block_handle中，然后将index_block_handle记录在footer中，由此，就可以完成顺藤摸瓜的大业：
从footer，可以找到index block，而index存放的是{“分割key”：data block的位置信息}，所以根据index block可以找到任何一个data block的起始位置和结束位置。
2.4 Bloom Filter
首先，解决存在不存在的问题，接着解决存在哪里的问题。
sstable 文件的foot， data block 和index block都已经介绍过了，看起来好像已经齐备了，根据footer 能够找到index block，而index记录了data block的索引信息，可以根据index block中的索引，快速定位到某个key（可能）位于which data block。
那么meta block和metaindex block到底是干啥的呢，为什么要有它呢？meta block的作用在于快速的确定，是否存在某个key，如果不存在，就没必要去遍历data block查找该key了。
如何快速判断某个key是否存在？
Bloom Filter这种数据结构就是干这个活的。
2.4.1 Bloom Filter的分析
详见我的另外一篇博客：