LevelDB源码分析之十二:block

一.Block的存储格式

Block的种类很多,包括Data Block、Meta Block等,每个Block由三部分组成,如下图所示:


1.block data
block data是具体的KV对存储区域。虽然Block有好几种,但是block data都是有序的KV对,因此写入、读取block data的接口都是统一的。
2.type
type指明使用的是哪种压缩方式,当前支持none和snappy压缩。
3.crc32
数据校验位
LevelDB对block data的管理是读写分离的,读取后的遍历查询操作由Block类实现,block data的构建则由BlockBuilder类实现。
二.block data的结构
假设每一个KV对是一条记录(Record),则记录的格式如下。
——共享前缀长度                     shared_bytes:       varint32
——前缀之后的字符串长度     unshared_bytes:  varint32
——值的长度                             value_length:        varint32
——前缀之后的字符串             key_delta:             char[unshared_bytes]
——值                                         value:                     char[value_length]
对于重启点而言,shared_bytes = 0,重启点存储完整的key。
block data的结尾段格式是:
——restarts:             uint32[num_restarts]
——num_restarts:  uint32 
尾段存储的是重启点相关信息,包括重启点的位置和个数。元素restarts[i]存储的是block data第i个重启点距离block data首地址的偏移。很明显第一条记录,总是第一个重启点,也就是restarts[0] = 0。num_restarts是重启点的个数。

block data的结构图如下所示:


总体来看block data可分为KV存储区和重启点信息存储区两部分。

三.block data的构建
block data的构建是通过BlockBuilder实现的,BlockBuilder类的头文件如下所示。

class BlockBuilder {
 public:
  explicit BlockBuilder(const Options* options);

  // 重置BlockBuilder
  void Reset();

  // Add的调用应该在Reset之后,在Finish之前。
  // Add只添加KV对(一条记录),重启点信息部分由Finish添加。
  // 每次调用Add时,key应该越来越大。
  void Add(const Slice& key, const Slice& value);

  // 组建block data完成,返回block data
  Slice Finish();

  // 估算当前block data的大小
  size_t CurrentSizeEstimate() const;

  // 是否已经开始组建block data
  bool empty() const {
    return buffer_.empty();
  }

 private:
  const Options*        options_;     
  std::string           buffer_;      // 用于存放block data
  std::vector<uint32_t> restarts_;    // 用于存放重启点的位置信息
  int                   counter_;     // 从上个重启点遍历到下个重启点时的计数
  bool                  finished_;    // 是否调用了Finish
  std::string           last_key_;    // 记录最后Add的key

  // No copying allowed
  BlockBuilder(const BlockBuilder&);
  void operator=(const BlockBuilder&);
};
下面重点介绍BlockBuilder类中的方法。
1.构造函数
BlockBuilder::BlockBuilder(const Options* options)
    : options_(options),
      restarts_(),
      counter_(0),
      finished_(false) {
  assert(options->block_restart_interval >= 1);
  restarts_.push_back(0);   
}
options->block_restart_interval表示当前重启点(其实也是一条记录)和上个重启点之间间隔了多少条记录。
restarts_.push_back(0),表示第一个重启点距离block data起始位置的偏移为0,也就是说第一条记录就是重启点。
2.Add函数
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 {
    // 如果counter_=options_->block_restart_interval,说明这条记录就是重启点。
	// 将这条记录距离block data首地址的偏移添加到restarts_中,并使counter_ = 0,
    restarts_.push_back(buffer_.size());
    counter_ = 0;
  }
  const size_t non_shared = key.size() - shared;

  // 开始组建一条记录
  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());

  // 此时