LevelDB源码解析(8) BlockBuilder

背景

一个SST文件由5个区块组成，其中三个区块都是由BlockBuilder构建的，所以在讲SST文件的构建之前，先讲一下BlockBuilder。BlockBuilder接受一组key-value，将其序列化到buffer中，buffer的数据就是要写入文件中的数据。

BlockBuilder类声明

//源码文件：table/block_builder.h
class BlockBuilder
{
public:
  explicit BlockBuilder(const Options *options);
  void Add(const Slice &key, const Slice &value);
  Slice Finish();
  void Reset();
  size_t CurrentSizeEstimate() const;
  bool empty() const

private:
  const Options *options_;
  std::string buffer_;
  std::vector <uint32_t> restarts_;
  int counter_;
  bool finished_;
  std::string last_key_;
};

options_：LevelDB的Options。
buffer_：序列化数据。
restarts_：重启点位置列表。
counter_：当前重启点关联的key数量。
finished_：Finish()是否已经被调用过了。
last_key_：上一次插入的key。

BlockBuilder::Add

Add每次插入一个key-value，代码如下：

//源码文件：table/block_builder.h
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;

  //Step1
  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;

  //Step2
  PutVarint32(&buffer_, shared);
  PutVarint32(&buffer_, non_shared);
  PutVarint32(&buffer_, value.size());
  buffer_.append(key.data() + shared, non_shared);
  buffer_.append(value.data(), value.size());

  //Step3
  last_key_.resize(shared);
  last_key_.append(key.data() + shared, non_shared);
  assert(Slice(last_key_) == key);
  counter_++;
}

Step1：如果当前重启点已经关联的key数量没有超过阈值（默认阈值为16），计算当前key和重启点key的共同前缀的长度(shared)和当前key独有的后缀长度(non_shared)。如果超过阈值就停用当前重启点，并把当前key设置为新的重启点。重启点是为了让多个前缀相同的key可以复用前缀，不用把相同的前缀存储多次。重启点的间隔是固定的，默认16个key为一组，组内第一个key为重启点。因为BlockBuilder插入的key一定是有序的，所以这里共同前缀是可以节省不少空间的。

Step2：使用变长编码分别把shared、non_shared、value_size写入buffer中。然后写入key的后缀和value（注意，这里没有存储前缀）。

Step3：把last_key设置为当前key，并把counter加1，即把当前重启点关联的key数量加1（重启点key本身也算一个关联key）。

重启点的逻辑确保了每组的第一个key的shared一定为0，即存储完整的key，这样后续的key才能只存储key后缀。

BlockBuilder::Finish

Finish只有在插入了全部的key之后才能调用，调用Finish后，就不能再调用Add了。Finish把重启点信息序列化到buffer中。

//源码文件：table/block_builder.h
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_);
}

把restarts_的每个元素逐个使用定长编码序列化到buffer中，并在最后写入重启点的数量。完成后把finished_设置为true，禁止继续Add

其他成员函数

BlockBuilder::Reset：重置BlockBuilder，清空数据，重置重启点，把finished_置为false。
BlockBuilder::CurrentSizeEstimate：返回buffer和重启点信息(含size)占用的总空间。
BlockBuilder::empty：返回buffer_是否为空。

block的最终结构

Finish被调用后，block即完成全部的序列化工作了，buffer最终结构如下图所示:

leveldb block存储格式

源码版本

https://github.com/google/leveldb/releases/tag/1.22

背景