首页 > 代码库 > leveldb源码分析--SSTable之block
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_ = 0; } 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 == 0) { // 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 = 0; i < num_keys; i++) { const char* base = keys_.data() + start_[i]; size_t length = start_[i+1] - start_[i]; tmp_keys_[i] = Slice(base, length); } // 记录生成filter信息的开始偏移量 filter_offsets_.push_back(result_.size()); policy_->CreateFilter(&tmp_keys_[0], 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所示。
图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所示。
图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相关的数据块的写入逻辑了。