LevelDB 学习笔记-SSTable

SSTable(Sorted-String Table) 是排序字符串表的简称，也就是说 SSTable 内部的数据都是有序排列的。当 MemTable 中的数据大小超过某个阈值之后，会通过 Minor Compaction 写入到 SSTable 中。除了 Minor Compaction 会写入 SSTable，在 Major Compaction 的时候也会将多个 SSTable 文件合并生成新的 SSTable。这篇文章只关注 SSTable 的格式，所以不会展示 Compaction 的细节。

SSTable 文件格式

根据 LevelDB 的文档，可以知道 SSTable 的格式如下所示：

<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer]        (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

• 数据存储区 data block：存放实际的 key:value 数据
• 数据管理区：提供一些索引指针等管理数据，目的是更快速便捷地查找相应地记录
  • MetaBlock
    • filter Meta Block，存储一些过滤器相关的数据（布隆过滤器），如果不指定，不会存储任何内容。
    • stats Meta Block，存储了一些状态，key 是统计信息的名称，value 是统计信息。统计信息中包含了 data size, index size, number of entries, number of data blocks 等
  • Meta Index Block，存储 Meta Block 的索引信息（在 sst 中偏移量和数据长度），用于快速定位 Meta Block
  • 数据索引块 Index Block：每条记录是对某个 Data Block 建立的索引信息，记录大于等于 Data Block 最大 key 的 key、Data Block 在 sst 中的起始位置、Data Block 大小
  • 文件尾部块 Footer：包含 metaindex_handler 指出了 metaindex block 的起始位置和大小；index_handle（指出了 index block 的起始地址和大小）、填充、魔数

Data Block 格式

对于每个 block(不论是 Data Block 还是 Meta Block 还是其他 Block)，包含以下三个部分

• data: block 中的数据，不同 block 中存储的数据格式不同
• type: 压缩类型
• CRC: 校验码，用于校验数据

因为 SSTable 中的 key 是有序的，所以前缀压缩的方法可以有效地节省存储空间。但是这样在查找 key 的时候需要查找 key 的时候需要逆序回放，最坏情况下查找一个 key 需要回放整个 block。

比如一个 group 中需要存储 “app”, “apple”, “apply”，那么只需要存储 “app”, “le”, “y” 就行了。查找 apply 的时候需要从第一个 key “app” 开始回放。比如要查找 “apply”，就需要知道第一个 key “app”; 要查找 “apply” 就得知道第一个和二个 key

为了加速查找效率，Data Block 会对 key 进行分组，默认每组 16 个 key，每组中的 key 采用前缀压缩的方法存储。每组的第一个 key 称为 restart points，存储全量的 key。这样在查找的时候可以现在 Group 的 restart points 中查找，定位到 Group，然后再到 Group 中查找即可。为了快速找到 restart points，LevelDB 在 Data Block 中存储了一个 restart 数组，用来存放每个 Group 的第一个 key 的索引

Data Block 的格式：

+--------------+
|   record 1   |
|   record 2   |
|   ......     |
|   record 3   |
|--------------|
|   restarts   |
|   ......     |
|   restarts   |
|--------------|
| num restarts |
|--------------|
|   checksum   |
+--------------+

record 格式
+-----------------------------------------------------------------
| shared len | non_shared len | val len | non_shared key | value |
------------------------------------------------------------------

将 Immutable MemTable 写入 SSTable 的方法在 DBImpl::WriteLevel0Table 中，这个方法会嗲用 BuildTable 构建 SSTable。这使用的是构建者模式，调用者只需要传递一个迭代器，就可以构建 SSTable，而无需知道迭代器的具体实现，也不需要知道迭代器之上的存储结构，因此，即便将 MemTable 的 SkipList 替换成平衡树也不会有问题

Status BuildTable(const std::string& dbname, Env* env, const Options& options,
                  TableCache* table_cache, Iterator* iter, FileMetaData* meta) {
  Status s;
  meta->file_size = 0;
  iter->SeekToFirst();

  std::string fname = TableFileName(dbname, meta->number);
  if (iter->Valid()) {
    WritableFile* file;
    s = env->NewWritableFile(fname, &file);

    TableBuilder* builder = new TableBuilder(options, file);
    meta->smallest.DecodeFrom(iter->key());
    Slice key;
    // 遍历数据，加入 builder
    for (; iter->Valid(); iter->Next()) {
      key = iter->key();
      builder->Add(key, iter->value()); // 向 builder 中添加 key
    }
    if (!key.empty()) {
      meta->largest.DecodeFrom(key);
    }

    // Finish and check for builder errors
    s = builder->Finish();
    if (s.ok()) {
      meta->file_size = builder->FileSize();
      assert(meta->file_size > 0);
    }
    delete builder;

    // Finish and check for file errors
    if (s.ok()) {
      s = file->Sync(); // 刷盘
    }
    if (s.ok()) {
      s = file->Close();
    }
    delete file;
    file = nullptr;

    if (s.ok()) {
      // Verify that the table is usable
      Iterator* it = table_cache->NewIterator(ReadOptions(), meta->number,
                                              meta->file_size);
      s = it->status();
      delete it;
    }
  }

  // Check for input iterator errors
  if (!iter->status().ok()) {
    s = iter->status();
  }

  if (s.ok() && meta->file_size > 0) {
    // Keep it
  } else {
    env->RemoveFile(fname);
  }
  return s;
}

与构建相关的代码主要在 builder->Add 和 builder->Finish 中，其中 Add 是向构建器中添加一个 key，而 Finish 是为了完成收尾工作。需要注意的是，向 builder 中添加的 key 是 internal_key_size + internal_key， value 是 value_size + value

void TableBuilder::Add(const Slice& key, const Slice& value) {
  Rep* r = rep_;
  assert(!r->closed);
  if (!ok()) return;
  if (r->num_entries > 0) {
    assert(r->options.comparator->Compare(key, Slice(r->last_key)) > 0); // 确保有序性
  }

  if (r->pending_index_entry) {
    // data block 为空，即这是添加到当前 block 的第一个 key
    assert(r->data_block.empty());
    // 找到一个 key ∈ [last_key, key)，用于在 index block(上一个 block) 中快速查找
    r->options.comparator->FindShortestSeparator(&r->last_key, key);
    std::string handle_encoding;
    r->pending_handle.EncodeTo(&handle_encoding);
    // 向 index block 添加 last key
    r->index_block.Add(r->last_key, Slice(handle_encoding));
    r->pending_index_entry = false;
  }

  // 向 filter block 添加 key
  if (r->filter_block != nullptr) {
    r->filter_block->AddKey(key);
  }

  // 更新 last_key 为 key，并插入 key, value
  r->last_key.assign(key.data(), key.size());
  r->num_entries++;
  r->data_block.Add(key, value); // 插入 key

  // 如果当前 block 的大小大于阈值，将当前 block 中的数据写入文件，然后重置 block
  const size_t estimated_block_size = r->data_block.CurrentSizeEstimate();
  if (estimated_block_size >= r->options.block_size) {
    Flush();
  }
}

data_blcok.Add 会将 key，value 插入 Data Block 插入的格式按照上面所描述的一样，这里就不展示了。

Index Block

向 TableBuild::Add 方法中可以看到其也是调用的 index_block.Add 方法，不管是 data_block 还是index_block 都是 BlockBuilder 结构，会调用相同的方法，也就是说 Index Block 中记录的格式与 Data Block 中记录存储的格式相同，只不过 Index Block 中只存储每个 Data Block 中的last key 和 handle(offset + size)

$$Last_{curr\_block} \le last\_key \lt First_{next\_block}$$

last key 是大于等于 block 中最大 Key 并且小于下一个 Block 中的第一个 key。这是为了减少存储空间，因为 last key 只是为了定位 block 的范围，所以在这个区间内的 key 都是可以的，所以可以只存储这个区间内较短的 key 即可(以一定是最短的，只要比原 key 短都能节省空间。在 BytewiseComparator::FindShortSuccessor 中的做法是比较每个字节，如果有一个字节的二进制位不是全 1，就将该字节加一，并截断到该字节)

因为前面只将 Data Block 写入到了文件，所以需要调用 TableBUilder::Finish 最后会做一些收尾工作，比写入 Meta Block , Metaindex Block, Index Block 和 Footer(存储了 metaindex_block_handle, index_block_handle，是为了快速定位)

Filter Block

根据文档，可以知道 Filter Block 的结构如下：

[filter 0]
[filter 1]
[filter 2]
...
[filter N-1]

[offset of filter 0]                  : 4 bytes
[offset of filter 1]                  : 4 bytes
[offset of filter 2]                  : 4 bytes
...
[offset of filter N-1]                : 4 bytes

[offset of beginning of offset array] : 4 bytes
lg(base)                              : 1 byte

Filter Blokc 的数据是分段的，第 i 段会存储文件偏移量在 [ i*base … (i+1)*base-1 ] 的 key 的 filter 数据，这个 base 默认是 2KB。在 filters 的下面，是一个 offset 数组，这是为了有效地将 offset 映射到 data block 中而建立的。

Slice FilterBlockBuilder::Finish() {
  if (!start_.empty()) {
    GenerateFilter(); // 生成过滤器数据(这里的数据指的是还未加入到 filter block 中的数据)
  }

  // Append array of per-filter offsets
  const uint32_t array_offset = result_.size();
  for (size_t i = 0; i < filter_offsets_.size(); i++) { // 生成 offset 数组
    PutFixed32(&result_, filter_offsets_[i]);
  }

  PutFixed32(&result_, array_offset);
  result_.push_back(kFilterBaseLg);  // Save encoding parameter in result
  return Slice(result_);
}