Leveldb通过WriteBatch批量进行多次操作，将多次操作编码后交由WAL进行日志落盘，最后交给Memtable进行批量写入到内存，每次写入之前会调用MakeRoomForWrite来决定是否需要进行 Compation将Memtable变成SStable，那么SStable到底是什么呢? WriteLevel0Table就是其中最为关键的一个函数，通过这个函数将Memtable变成了SStable。 接下来让我们来看下这个 函数到底做了什么?

Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit,
                                Version* base) {
  mutex_.AssertHeld();
  const uint64_t start_micros = env_->NowMicros();
  // 1. 创建FileMetaData，用来描述产生的sstable文件
  FileMetaData meta;
  // 1.1 生成一个新的FileNumber，sstable文件的名字是有FileNumber组成的
  meta.number = versions_->NewFileNumber();
  pending_outputs_.insert(meta.number);
  // 1.2 创建Memtable迭代器准备写入到sstable文件中
  Iterator* iter = mem->NewIterator();
  Log(options_.info_log, "Level-0 table #%llu: started",
      (unsigned long long)meta.number);

  Status s;
  {
    mutex_.Unlock();
    // 2. 构建Table
    s = BuildTable(dbname_, env_, options_, table_cache_, iter, &meta);
    mutex_.Lock();
  }

  Log(options_.info_log, "Level-0 table #%llu: %lld bytes %s",
      (unsigned long long)meta.number, (unsigned long long)meta.file_size,
      s.ToString().c_str());
  delete iter;
  pending_outputs_.erase(meta.number);

  // Note that if file_size is zero, the file has been deleted and
  // should not be added to the manifest.
  // 3. 将文件添加到VersionEdit中
  int level = 0;
  if (s.ok() && meta.file_size > 0) {
    const Slice min_user_key = meta.smallest.user_key();
    const Slice max_user_key = meta.largest.user_key();
    if (base != nullptr) {
      level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);
    }
    edit->AddFile(level, meta.number, meta.file_size, meta.smallest,
                  meta.largest);
  }

  CompactionStats stats;
  stats.micros = env_->NowMicros() - start_micros;
  stats.bytes_written = meta.file_size;
  stats_[level].Add(stats);
  return s;
}

可以看到，构建sstable的核心在于BuildTable，构建好后会产生一个文件，这个文件的元信息则是通过FileMetaData来描述的，最后会将这个文件的元信息存入到VersionEdit中。然后Apply到Version中。关于Version和VersionEdit后面的重点分析，现在我们重点来看下BuildTable的实现。

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();
  // 1. 构造Table文件名
  std::string fname = TableFileName(dbname, meta->number);
  if (iter->Valid()) {
    WritableFile* file;
    s = env->NewWritableFile(fname, &file);
    if (!s.ok()) {
      return s;
    }

    TableBuilder* builder = new TableBuilder(options, file);
    meta->smallest.DecodeFrom(iter->key());
    Slice key;
    // 2. 遍历Memtable，将key/value存入到Table中
    // 因为Memtable是有序的，因此第一个key是最小的key，最后的key是最大的key
    // 将最小key和最大key这两个元信息存入到FileMeta中
    for (; iter->Valid(); iter->Next()) {
      key = iter->key();
      builder->Add(key, iter->value());
    }
    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
    // 3. 完成table构建后，开始进行文件sync，确保文件落盘
    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;
}

通过上面的代码我们可以知道TableBuilder就是用来构建sstable的核心，而sstable本质上就是一个文件，文件内容是一系列排序好的key/value进行编码后的内容，那么它的格式到底是如何的呢?

为了提高整体的读写效率，一个sstable文件按照固定大小进行块划分，默认每个块的大小为4KiB。每个Block中，除了存储数据以外，还会存储两个额外的辅助字段：压缩类型和CRC校验码，上图就是其整体的物理结构。进一步上面的Data部分又被分为了五类:

1. data block 用来存储具体的key value数据
2. filter block 用来存储一些过滤器相关的数据
3. meta index block 用来存储filter block的索引信息(也就是filter block在sstable文件中的偏移量，以及数据的长度)
4. index block 用来存储每个data block的索引信息
5. footer 用来存储meta index block和index block的索引信息

首先我们来看下data block的数据格式，如下图:

可以看到一个datablock内部包含了多个Entry，每一个Entry就是一个要存取的数据条目，也就是用户存入的key/value，让我们来看下Entry的编码格式，如下图

一个Entry包含了5个部分，他们分别是:

1. 与前一条记录key共享部分的长度；
2. 与前一条记录key不共享部分的长度；
3. value长度；
4. 与前一条记录key非共享的内容；
5. value内容；

可以看到，一个Entry并非包含了完整的key，而是和前一个key的共享前缀，因此编码和解码的时候都需要保存上一个key的信息，才能对key进行编码或解码。这种编码方式可以有效的避免key重复内容的存储，因为key总是有序的，所以可以最大程度的通过共享前缀的部分来节省key存储的成本，但是带来的问题也是显而易见意见的，如果要从这个文件中检索一个key的话需要完整的将所有的key都解析出来。为此leveldb设计了Restart point，也就是每间隔若干个keyvalue对，将为该条记录重新存储一个完整的key。重复该过程（默认间隔值为16），每个重新存储完整key的点称之为Restart point。有了Restart point就可以通过这些完整的key快速定位目标key所在的区域。然后通过完整的key就可以还原这个区域中所有的key信息了。为了快速找到每一个Restart point，leveldb会在data block的末尾存储一系列的索引信息，和长度，方便我们在加载data block的时候就可以把这些Restart point加载到内存中进行快速查找，接下来我们通过下面的代码再次验证上面描述到的原理。

这个思想和skiplist有点类似，都是按照一定方式从原始数据进行抽样，典型的统计学原理。

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;
  // 1. 没有到Restart point的间隔，因此这里需要计算共享前缀
  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 {
    // 2. 达到了Restart point的间隔了，因此这里需要存储完整的key/value，还需要记录索引信息(也就是restart poont的offset信息)
    // Restart compression
    restarts_.push_back(buffer_.size());
    // 计数器清零
    counter_ = 0;
  }
  const size_t non_shared = key.size() - shared;

  // 3. 开始写入共享部分的长度、非共享部分的长度、value的长度
  // Add "<shared><non_shared><value_size>" to buffer_
  PutVarint32(&buffer_, shared);
  PutVarint32(&buffer_, non_shared);
  PutVarint32(&buffer_, value.size());

  // 4. 写入共享部分的key内容、写入value的内容
  // Add string delta to buffer_ followed by value
  buffer_.append(key.data() + shared, non_shared);
  buffer_.append(value.data(), value.size());

  // 5. 更新last key，用于下一个key计算前缀
  // Update state
  last_key_.resize(shared);
  last_key_.append(key.data() + shared, non_shared);
  assert(Slice(last_key_) == key);
  counter_++;
}

每次添加key时产生的Restart point都存在了restarts_中，这是一个std::vector<uint32_t>类型，存储了每一个Restart point在data block中的offset。在构建完Restart point后会将这些索引信息写入到data block中的尾部。

Slice BlockBuilder::Finish() {
  // Append restart array
  for (size_t i = 0; i < restarts_.size(); i++) {
    PutFixed32(&buffer_, restarts_[i]);
  }
  PutFixed32(&buffer_, restarts_.size());
  finished_ = true;
  return Slice(buffer_);
}

到此为止data block的构建就分析完了，通过Restart point可以让我们快速定位要查询的数据在data block中的位置，但是这一切的前提是我们已经知道这个data block中存在我们要查询的数据。 否则我们依然先需要遍历每一个data block。如果我们能高效的先过滤处包含要查询数据的data block那该多棒啊。Leveldb中设计了filter block帮助我们实现这个能力。接下来让我们看看filter block的格式，以及设计filter block是如何帮助我们快速查询的吧。