本文介绍LevelDB的SSTable相关功能。
SSTable是LevelDB的内存数据结构。当一个Memtable满之后,会被变成Immutable Memtable,并写入SSTable Level0。Level0的SSTable是没有经过归并的,各个Key可能互相重叠。经过Compaction达到Level1之后,就是有序的了。
SSTable格式
SSTable体现在后缀为.sst或者.ldb的文件。
其实在官方文档中,对SSTable的格式已经有了介绍。
1 | <beginning_of_file> |
data block
放KV对,是有序的(doc里面说的)。因此在查询SSTable文件的时候,也可以二分。【待确认】
关于Block的组织,我们将专门讨论。meta block
用来快速定位key是否在data block中metaindex block
每个metaindex block一条记录。其中K是meta block的名字,V是指向这个meta block的BlockHandle。
BlockHandle类似于指针,具有下面的结构。容易看到,这里面也用了VarInt结构。1
2offset: varint64
size: varint64有两种meta block类型,filter和stats:
- 如果在数据库启动时指定了某个
FilterPolicy
,就会创建一个filter block。 - 统计信息
- 如果在数据库启动时指定了某个
index block
每个data block一条entry。这个index block entry的.key()
大于等于指向的data block最后一个K【性质1】,但是严格小于下一个data block的第一个K【性质2】。
因此,我们可以通过和index block比较来快速定位data block。footer
包含:- metaindex handle
- index handle
- padding
- magic number
Block实现
SST的构建主要集中在table_builder.h/cc
和block_builder.h/cc
中。
SST的读取主要集中在table.h/cc
和block.h/cc
中。
从前面可以看到,SSTable主要有两层结构,Table(SSTable)和Block(data/index等)。
Table由多个Block构成,所以从Block开始分析。
BlockBuilder/Block原理
BlockBuilder负责生成诸如data block、index block等所有block。
Block对象负责读取这些block。
共享前缀
因为BlockBuilder是有序的,所以可以使用共享前缀来节约空间,我们比较下面两种方式:
普通
1
2Hello World
Hello William共享
1
2Hello World
illiam
Block的构造如下图所示
其中:
- shared_bytes
Key的共享前缀的长度,这里的共享指的是上一个entry - key_delta/unshared_bytes
Key共享前缀后的剩余串和其长度 - value/value_length
值的串和其长度
那么如何读呢?
最坏状况,我们需要读到第一个Entry,考虑下面的Key
1
2
3a
ab
abc最好状况,我们读当前的就行
1
2a
b
restart
可见共享前缀会给读带来困难,因此又引入restart机制,即每隔block_restart_interval
之后会去存储一次完整的key,对应的entry的位置称为restart point。在block中,会存储下所有的restart point。
因为数字存储是有序的,所以我们能通过二分restart point来加速读取,具体代码在Block::Iter
中。读取需求一般是给定target,要求找到第一个K大于等于target的entry。因此我们可以得到如下二分
mid < target
则搜索[mid, right]
mid >= target
搜索[left, mid-1]
因为这是一个TTT…F/T的二分,所以我们要令mid = (left + right + 1)/2
filter block
在每个data block内部,借助于二分restart可以实现$log(n)$复杂度的查询,那么能在data block之间二分么?
可以通过filter block来判断某个key是否属于该data block,实现是bloom filter。
BlockBuilder实现
方法
void Add(const Slice& key, const Slice& value);
每一次Add的Key,必须是有序的,从小到大的。Slice Finish();
void Reset();
BlockBuilder::Add
首先是三个assert:
- 第一个很好理解,如果
finished_
,相当于已经调用了Finish或者Abandon等方法。 block_restart_interval
表示每过多少个key就要设置一个restarts。设置完之后,counter_
会被重置为0,所以这个不等式是成立的。- 最后一个是有序性检验,要不是空的,要不新来的
key
要大于老的last_key_piece
。1
2
3
4
5
6void 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);
下面判断要不要restart:
- 如果不要,和前一个key即
last_key_
比较,算出来能share多少长度。 - 如果要,就restart。
1
2
3
4
5
6
7
8
9
10
11
12
13size_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;
下面就是往buffer_
里面写数据了。
1 | // Add "<shared><non_shared><value_size>" to buffer_ |
下面这个优化点也很有趣,首先last_key_
保存的是一个完整的key。但是我们可以复用之前一个key的shared部分,这个是安全的。接着我们把non shared部分append上去。
1 | // Update state |
BlockBuilder::Finish
为啥restarts_
不用VarInt存呢?
1 | Slice BlockBuilder::Finish() { |
Block实现
uint32_t NumRestarts() const;
之前了解过block的结构,在Block的最后,是restart点的个数。1
2
3
4inline uint32_t Block::NumRestarts() const {
assert(size_ >= sizeof(uint32_t));
return DecodeFixed32(data_ + size_ - sizeof(uint32_t));
}const char* data_;
/size_t size_
;
也就是这个Block的指针和长度。uint32_t restart_offset_;
表示restart的开始位置1
size_ - (1 + NumRestarts()) * sizeof(uint32_t)
bool owned_;
取决于构造函数传入的BlockContents
的owned_
字段。
Block::Iter
Seek
这个函数是一个二分的实现。
1 | void Seek(const Slice& target) override { |
Table实现
TableBuilder
对于Add/Flush/Finish/Abandon,此时Adandon和Finish不能已经被调用。
Status ChangeOptions(const Options& options);
修改option,但是只有某些可以在构建之后被修改。对于那些不能修改的,会报错。void Add(const Slice& key, const Slice& value);
增加一个KV对。
key is after any previously added key according to comparator,往TableBuilder里面加KV,必须是有序的?void Flush();
刷盘,一般不直接用。主要被用来保证两个相邻的Entry不会在同一个data block中。Status status() const;
Status Finish();
结束当前表的构建。void Abandon();
表示需要丢弃当前缓存内容,并且结束表的构建。uint64_t NumEntries() const;
Add了多少次,实际上返回的是TableBuilder::Rep
里面的num_entries
uint64_t FileSize() const;
void WriteBlock(BlockBuilder* block, BlockHandle* handle);
void WriteRawBlock(const Slice& data, CompressionType, BlockHandle* handle);
此外,TableBuilder持有一个Req类型的对象指针,用来隐藏相关实现。
TableBuilder::Rep
具有下面的:
Options options;
Options index_block_options;
WritableFile* file;
WritableFile
是一个接口,具体实现可以分为随机读写文件,顺序读写文件等。uint64_t offset;
Status status;
是ok()
的返回值,表示是否发生了错误。一般,错误会在file
里面的Append和Flush方法中出现。BlockBuilder data_block;
BlockBuilder index_block;
std::string last_key;
每一次Add会更新这个字段。因为Add是有序的,所以实际上就表示了当前最大的key。int64_t num_entries;
见NumEntries
。bool closed;
Finish和Abandon会设置为true。FilterBlockBuilder* filter_block;
bool pending_index_entry;
当写完一个data block之后,设置pending_index_entry
,表示需要更新index block。
因此这里有个不变量,当且仅当data_block
为空的时候pending_index_entry
才是true。也就是说当写入一个data block后(注意一个table中有多个data block),设置pending_index_entry
为true,之后更新index block。
原因是直到我们见到下一个data block的第一个key的时候才能写index。这样我们可以在写index的时候用尽可能短的key。例如我们已经知道第一个data block中最大的是”the quick brown fox”,而第二个data block中最小的是”the who”。这样通过之前提到的FindShortestSeparator
,我们就可以用”the r”作为index block中的entry。这个entry满足条件,即大于等于第一个block中的所有key,并且小于第二个block中的所有key。
因此,顺序是:- 写一个data block
- 接到下一个Add请求
- 根据
last_key
和当前传入的Key,写index - 正常处理该Add请求
BlockHandle pending_handle;
Handle to add to index block。不是说用这个handle来写index block,而是会把这个handle里面的值写到index block里面作为index。std::string compressed_output;
TableBuilder::Add
1 | void TableBuilder::Add(const Slice& key, const Slice& value) { |
如果pending_index_entry
是true,说明之前已经写入了一个data block。于是我们就要插入index,并且清空pending_index_entry
标志。这一部分原理在pending_index_entry
讲解过了。
1 | if (r->pending_index_entry) { |
下面是添加的逻辑,先处理filter block。
1 | if (r->filter_block != nullptr) { |
然后设置last_key
,并向当前的data block中添加KV。
估算当前data block的大小,如果超过配置的阈值options.block_size
就进行dump。这个估算实际上就是统计所有entry以及restart的总大小。相比Spark里面的大小估计,感觉LevelDB/Redis里面的大小估计要简单很多,感觉得益于C/C++能自己管理内存。
1 | r->last_key.assign(key.data(), key.size()); |
TableBuilder::WriteBlock
WriteBlock
Table要写某个Block,首先Finish这个block,也就是说把所有restart都写到文件里面。
1 | void TableBuilder::WriteBlock(BlockBuilder* block, BlockHandle* handle) { |
接着,是写data block。实际写入的block_contents
可能是被压缩了的,也可能是没有被压缩的。
1 | Slice block_contents; |
清空这个block里面buffer_
、restarts_
等状态。
1 | block->Reset(); |
TableBuilder::WriteRawBlock
每一个block包含:
- data
- type 表示有没有压缩
- crc32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void TableBuilder::WriteRawBlock(const Slice& block_contents,
CompressionType type, BlockHandle* handle) {
Rep* r = rep_;
handle->set_offset(r->offset);
handle->set_size(block_contents.size());
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;
}
}
}
TableBuilder::Flush
前面是判断一些条件。如果说data block是空的,那么就直接返回。接着断言pending_index_entry
这个是true,这个是之前提到的不变量。
1 | void TableBuilder::Flush() { |
根据pending_handle
的说明,它的值会被写到index block里面。
1 | WriteBlock(&r->data_block, &r->pending_handle); |
TableBuilder::Finish
Finish操作用来生成一个SSTable。
首先先Flush,也就是把data_block
写盘。
1 | Status TableBuilder::Finish() { |
什么时候不ok呢?也就是发生错误的情况。
下面,写入filter block。
1 | BlockHandle filter_block_handle, metaindex_block_handle, index_block_handle; |
如果上面的写入是成功的,接着写入meta index block。
1 | // Write metaindex block |
如果上面的写入是成功的,接着写入index block。
1 | // Write index block |
如果上面的写入是成功的,接着写入footer。
1 | // Write footer |
Table
下面介绍Table类,它的作用是负责读取SSTable。
static Status Open(const Options& options, RandomAccessFile* file, uint64_t file_size, Table** table);
解析传入的file
。
如果成功,返回ok,并且设置*table
,这是一个指针,由调用方释放。
如果失败,返回一个非ok,并且设置*table
为nullptr。
Does not take ownership of “*source”, but the client must ensure that “source” remains live for the duration of the returned table’s lifetime.Iterator* NewIterator(const ReadOptions&) const;
uint64_t ApproximateOffsetOf(const Slice& key) const;
传入一个key,返回它在文件中的大概位置。对不存在的key,返回如果存在,那么大概在的位置。static Iterator* BlockReader(void*, const ReadOptions&, const Slice&);
TwoLevelIterator需要这个函数,通过它来构建一个data_iter_
Status InternalGet(const ReadOptions&, const Slice& key, void* arg, void (*handle_result)(void* arg, const Slice& k, const Slice& v));
void ReadMeta(const Footer& footer);
void ReadFilter(const Slice& filter_handle_value);
Table::Rep
Options options;
Status status;
RandomAccessFile* file;
uint64_t cache_id;
FilterBlockReader* filter;
const char* filter_data;
BlockHandle metaindex_handle;
Block* index_block;
Table::Open
首先解析出footer。
1 | Status Table::Open(const Options& options, RandomAccessFile* file, |
接下来,解析index block。
1 | // Read the index block |
初始化rep_
字段。
1 | if (s.ok()) { |
Table::NewIterator
实际上调用NewTwoLevelIterator
得到一个TwoLevelIterator
。
1 | Iterator* Table::NewIterator(const ReadOptions& options) const { |
方法NewIterator
的实现如下。如果没有restart点,那么就创建一个空的迭代器,否则创建一个Block::Iter
。
1 | Iterator* Block::NewIterator(const Comparator* comparator) { |
两个Level的含义是:
IteratorWrapper index_iter_
负责查询index block,找到key所在的data block。
IteratorWrapper
封装了Iterator
,可以理解为一层对valid()
和key()
的cache。Iterator
是个接口,实际类型应该是Block::Iter
【待确认】。IteratorWrapper data_iter_
负责在这个block里面查找。
TwoLevelIterator
BlockFunction block_function_;
由block_function_
可以从一个index_iter_
创建一个data_iter_
。
在Table的实现中,是Table::BlockReader
这个函数。我们将在后面详细分析这个函数。void* arg_;
在Table的实现中,传入了Table* this
。const ReadOptions options_;
Status status_;
IteratorWrapper index_iter_;
IteratorWrapper data_iter_;
std::string data_block_handle_;
如果data_iter_
不是null,那么data_block_handle_
持有传给block_function_
的那个index_iter_
的值。
TwoLevelIterator::Next
存在一个问题,如果我们一直data_iter_.Next()
,我们迟早会碰到一个Block的右边界,这样后面迭代器就Invalid了。因此需要检查如果data_iter_
当前已经失效了,那么就递增index_iter_
,获取下一个data_iter_
,具体实现见下面。
1 | void TwoLevelIterator::Next() { |
TwoLevelIterator::SkipEmptyDataBlocksForward
【Q】在上面说过这个函数的作用了,但是为啥这里实现是while
而不是if
呢?
1 | void TwoLevelIterator::SkipEmptyDataBlocksForward() { |
SetDataIterator
函数接受一个迭代器作为参数,如果迭代器不是空,那么就设置为data_iter_
,并且释放掉原来的iter_
内存。
1 | ... |
需要注意,这里需要显式将data_iter_
移动到当前data block的开头。
1 | ... |
TwoLevelIterator::InitDataBlock
InitDataBlock
作用是从index_iter_
构建(解析)出一个data block。
如果index_iter_
无效,那么设置data_iter_
也无效。
如果data_iter_
不为空,并且等于之前的data_block_handle_
,说明data_iter_
现在就指向的这个data block,那么就跳过。
否则,以index_iter_
为参数,通过block_function_
生成一个新的data_iter_
。
1 | void TwoLevelIterator::InitDataBlock() { |
TwoLevelIterator::Seek
首先,在index block层Seek。下面证明只要找这个index_iter_
指向的data block就行,也就是说,target不会出现在(index_iter_ - 1)
和(index_iter_ + 1)
指向的data block里面。
- 因为LevelDB中的性质,Seek得到的是第一个大于等于target的指针。此时,
(index_iter_ - 1)
中的.key()
是严格小于target的。而根据index block的【性质1】,这个index block entry指向的data block中的所有K都小于等于(index_iter_ - 1).key()
。因此,(index_iter_ - 1)
指向的data block里面所有的K,都小于target。 - 此外,
index_iter_.key()
是大于等于target的。 - 下面,还要证明
(index_iter_ + 1).key()
指向的data block里面的所有K都大于target。根据【性质2】我们知道index_iter_.key()
会严格小于它指向的下一个data block中的所有K,根据我们上一条结论可以知道target严格小于下一个data block中的所有K,所以target如果存在的话,一定是当前data block上的。1
2void TwoLevelIterator::Seek(const Slice& target) {
index_iter_.Seek(target);
接着初始化data_iter_
。接着在data block层Seek。
1 | InitDataBlock(); |
Table::BlockReader
接受三个参数:
arg
这个类型设置就很奇怪,实际上是一个Table*
,表示我们现在读的那个Table的上下文。index_value
1 | // Convert an index iterator value (i.e., an encoded BlockHandle) |
1 | Iterator* iter; |