leveldb源码分析--SSTable之block

在SSTable中主要存储数据的地方是data block,block_builder就是这个专门进行block的组织的地方,我们来详细看看其中的内容,其主要有Add,Finish和CurrentSizeEstimate三个函数。Finish的逻辑十分简单就是简单的将restart点信息和restart点个数分别以PutFixed32的格式写入数据最后;CurrentSizeEstimate则是简单的计算当前块需要的存储大小 = 已插入的KV对的大小 + 重启点个数 * 4 + 1 * 4(重启点计数器)。需要注意的是Datablock,Metablock, MetaIndex block, Indexblock,Footer这几个数据块中Datablock, MetaIndex block, Indexblock都是以KV对的形式组成的,所以都由BlockBuilder负责管理。

我们详细分析一下BlockBuilder的Add函数

void BlockBuilder::Add(const Slice& key, const Slice& value) {
//一些基本的状态判断,如上次插入的key是否比当前key小等
if (counter_ < options_->block_restart_interval) {
// 不需要restart时取得跟上一个restart点的key的相同部分
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 {
// 否则,完整存储key,并记录restart点
restarts_.push_back(buffer_.size());
counter_ = ;
}
const size_t non_shared = key.size() - shared;
// 按“共享长度 | 非共享长度| 值长度| 非共享数据| value值写入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_++;
}

理解了BlockBuilder之后接下来我们再看看filter_block,首先看看他的几个成员变量

const FilterPolicy* policy_;         //  filter,即hash算法实现类
std::string keys_; // 所有key,一个接一个一直添加在一起
std::vector<size_t> start_; // 每个key在keys_中的开始位置
std::string result_; // 已经产生的Filter数据
std::vector<Slice> tmp_keys_; // 用来还原keys的一个临时数组
std::vector<uint32_t> filter_offsets_; //每次生成的filter值偏移

了解了基本成员以后我们描述一下FilterBlockBuilder的逻辑:

Add:当程序向一个block添加数据时就调用Add将key的内容添加到keys_,并记录这个key在keys_中的开始下标;

StartBlock: 当该block达到指定的域大小以后就调用StartBlock根据block最后写入文件的大小生成一个filter值并添加到result中,同时记录该开始地址;

Finish: 当SSTable写入结束后(TableBuilder.Finish)会调用Finish() 将每次生成的filter的偏移量(数组filter_offsets_)和总的Filter的大小写入Metablock的最后。

需要注意的是在生成过程中从函数StartBlock的逻辑可以看出当一个数据块大小/2k >=2 时,为了方便处理会再次记录空偏移,在读取的时候处理就可以简单的读取当前的block_offset / kFilterBase 和其后的一个数值就可以得到两个偏移量(开始和结束)。我们看一下代码逻辑

void FilterBlockBuilder::StartBlock(uint64_t block_offset) {
uint64_t filter_index = (block_offset / kFilterBase); // block的偏移 / 2K
// 这里上一个block时 filter_index == 上次 block_offset / kFilterBase,
//所以这次block大小/kFilterBase >=2 时会调用两次以上GenerateFilter,
//而连续调用时,只是在filter_offsets_中添加一个当前大小,但并未扩充其空间
while (filter_index > filter_offsets_.size()) {
GenerateFilter();
}
}
void FilterBlockBuilder::GenerateFilter() {
const size_t num_keys = start_.size();
if (num_keys == ) {
// Fast path if there are no keys for this filter ,连续被第二次调用时进入此逻辑
filter_offsets_.push_back(result_.size());
return;
}
//还原为key数组
start_.push_back(keys_.size()); // Simplify length computation
tmp_keys_.resize(num_keys);
for (size_t i = ; i < num_keys; i++) {
const char* base = keys_.data() + start_[i];
size_t length = start_[i+] - start_[i];
tmp_keys_[i] = Slice(base, length);
}
// 记录生成filter信息的开始偏移量
filter_offsets_.push_back(result_.size());
policy_->CreateFilter(&tmp_keys_[], num_keys, &result_);
//还原状态
tmp_keys_.clear();
keys_.clear();
start_.clear();
}

FilterBlockReader为从文件中将FilterBlockBuilder生成filter信息还原回来(读取),只包含一个构造函数FilterBlockReader和KeyMayMatch,根据名称就能知道其功能而且逻辑较简单,所以这里就不再详细解释。

这里引用Leveldb源码分析--13的一个例子以便于理解:

8.5.5 简单示例

让我们根据TableBuilder对FilterBlockBuilder接口的调用范式:
(StartBlock AddKey*)* Finish以及上面的函数实现,结合一个简单例子看看leveldb是如何为data block创建filter block(也就是meta block)的。

考虑两个datablock,在sstable的范围分别是:Block 1 [0, 7KB-1], Block 2 [7KB, 14.1KB]

S1 首先TableBuilder为Block 1调用FilterBlockBuilder::StartBlock(0),该函数直接返回;

S2 然后依次向Block 1加入k/v,其中会调用FilterBlockBuilder::AddKey,FilterBlockBuilder记录这些key。

S3 下一次TableBuilder添加k/v时,例行检查发现Block 1的大小超过设置,则执行Flush操作,Flush操作在写入Block 1后,开始准备Block 2并更新block offset=7KB,最后调用FilterBlockBuilder::StartBlock(7KB),开始为Block 2构建Filter。

S4 在FilterBlockBuilder::StartBlock(7KB)中,计算出filter index = 3,触发3次GenerateFilter函数,为Block 1添加的那些key列表创建filter,其中第2、3次循环创建的是空filter。

此时filter的结构如图8.5-1所示。

leveldb源码分析--SSTable之block

图8.5-1

在StartBlock(7KB)时会向filter的偏移数组filter_offsets_压入两个包含空key set的元素,filter_offsets_[1]和filter_offsets_[2],它们的值都等于7KB-1。

S5 Block 2构建结束,TableBuilder调用Finish结束table的构建,这会再次触发Flush操作,在写入Block 2后,为Block 2的key创建filter。最终的filter如图8.5-2所示。

leveldb源码分析--SSTable之block

图8.5-2

这里如果Block 1的范围是[0, 1.8KB-1],Block 2从1.8KB开始,那么Block 2将会和Block 1共用一个filter,它们的filter都被生成到filter 0中。

当然在TableBuilder构建表时,Block的大小是根据参数配置的,也是基本均匀的。

至此我们就介绍完了Datablock,Metablock, MetaIndex block, Indexblock,Footer,即所有SSTable相关的数据块的写入逻辑了。

上一篇:java面试教程视频


下一篇:Android 再按一次退出程序