LevelDB 源代码阅读（五）：SSTable

在 LSM 结构的数据库中，SSTable 指的是数据落盘之后形成的文件。在 LevelDB 中，SSTable 是以 .sst 文件的形式存在的。本文将介绍 LevelDB 中 SSTable 的写过程和读过程。

SSTable 的总体结构

图中所示为 SSTable 文件的整体结构。文件的前部分为数据部分（DataBlock），文件的结尾部分为数据的索引。在索引部分，又分为了 Filter Block 、 Meta Index Block 、 Index Block 以及 Footer 。下面我们依次来介绍 SSTable 中每个结构的具体细节。

数据部分

数据部分由许多个 DataBlock 组成，在 LevelDB 中，一个 DataBlock 的大小默认设置为 4 KB 。每个 DataBlock 由三个部分组成：数据部分（Data）、压缩类型（CompressionType）以及校验和（CRC）。

Data 中存储的即是数据库的数据内容； CompressionType 中记录了对原始数据使用的压缩方式，在 LevelDB 中默认的压缩方式是 Snappy ； CRC 部分则记录了对 Data 以及 CompressionType 进行 CRC32 计算得到的结果，用来保证数据的正确性。

Data 部分有更加细微的结构：

图中每一个 Entry 就是一组 Key-Value 对，由于 DataBlock 在写入时，在一组键之间会寻找可以共享的长度（详见后面的写入过程），因此 Entry 块的后面会有若干个 Restart Point ，每个 Restart Point 会指向一个 Entry ，这个 Entry 不会与其前面的 Entry 有共享的键内容。每次读取数据时，都要从 Restart Point 指向的某个 Entry 开始往后读，直到读到目标键值对为止。最后，Data 中还标记了 Restart Point 的个数。前面提到，在编码是会对一组 Key 进行键值共享，因此一个 Entry 的结构为

索引部分

索引部分主要包含两大部分：数据的索引及元数据、布隆过滤器的索引及内容。

Filter Block

Filter Block 主要装载布隆过滤器的内容，所谓布隆过滤器就是一种用于快速模糊查找的数据结构，关于布隆过滤器的详细介绍可以查看这篇文章。

Filter Block 中的 Filter Data 块保存了布隆过滤器的具体内容；绿色部分的 Offset of Filter Data $i$ 则记录了第 $i$ 个 Filter Data 的偏移量；Offset of Filter Offset 则记录了 Offset of Filter Data 1 的偏移量；Base Lg 默认值为 11 ，表示每 2 KB 的数据创建一个新的过滤器来存放过滤数据。因此，Filter Data $i$ 就记录了文件中位置位于 [2KB $\times (i-1)$, 2KB $\times i$] 范围内数据的 Filter 数据。

Meta Index Block

Meta Index Block 用以记录 Filter Block 在整个 SSTable 中的位置，整个 Block 只记录了一组键值对，Key 为 “filter.” 与过滤器名称组成的常量字符串，值则为 Filter Block 的索引信息（包括 Filter Block 在 SSTable 中的偏移量以及 Filter Block 的数据长度）序列化后的内容。

Index Block

Index Block 记录了数据部分的索引信息。具体地，Index Block 由多个 <Max Key><Offset><Length> 这样的三元组构成。一个三元组对应了数据部分的一个 DataBlock ，三元组中的信息分别记录了其最大键值、在文件中的偏移量以及大小三个信息。

在写入 DataBlock 的过程中，不同的 DataBlock 和 DataBlock 内部都是严格有序的（因为 MemTable 中的 SkipList 也是有序的），因此在查询时可以通过 IndexBlock 中记录的 MaxKey信息进行快速查找，然后根据 Offset 和 Length 信息将找到的 DataBlock 读取出来，再进行下一步的处理。

Footer

Footer 的大小是固定的，为 48 个字节，其存储了 MetaIndexBlock 的 offset、 IndexBlock 的 offset 以及一串 Magic Word ，内容为 “http://code.google.com/p/leveldb/“ 字符串 sha1 哈希的前 8 个字节。

SSTable 的写流程

在 LevelDB 中，Level 0 级的 SSTable 由内存中的 Immutable MemTable 写出得到，这个过程在 db_impl.cc 中的 WriteLevel0Table 中和主线程异步地执行。

// db_impl.cc
Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit,
                                Version* base) {
  mutex_.AssertHeld();
  const uint64_t start_micros = env_->NowMicros();
  // 生成文件元数据
  FileMetaData meta;
  meta.number = versions_->NewFileNumber();
  pending_outputs_.insert(meta.number);
  Iterator* iter = mem->NewIterator();
  Log(options_.info_log, "Level-0 table #%llu: started",
      (unsigned long long)meta.number);

  Status s;
  {
    mutex_.Unlock();
    // 将 Immutable MemTable 写入到文件中
    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.
  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) {
      // 在所有无文件和该 SSTable 不发生 key 重叠的 Level 中
      // 选择一个最大的 Level 插入该文件
      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;
}

将 MemTable 中的内容写入到 SSTable 中的过程在 BuildTable 中

// builder.cc
Status BuildTable(const std::string& dbname, Env* env, const Options& options,
                  TableCache* table_cache, Iterator* iter, FileMetaData* meta) {
  Status s;
  meta->file_size = 0;
  // 移动到 SkipList 中第一个元素的位置
  iter->SeekToFirst();

  // 创建文件
  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);
    // SkipList 中的数据是按照顺序排列的
    // 因此第一个键就是其最小的键
    meta->smallest.DecodeFrom(iter->key());
    Slice key;
    // 不断地将 SkipList 中的数据插入到 TableBuilder 中
    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
    // Finish 时会写入索引部分的数据
    // 包括 FilterBlock、MetaIndexBlock、IndexBlock 以及 Footer
    s = builder->Finish();
    
    // 一些检查文件状态的代码
    ...
  return s;
}

在 BuildTable 函数中， MemTable 中的内容被不断添加到 TableBuilder 中。当 MemTable 中的数据都被添加到了 TableBuilder 中后，SSTable 中数据部分就已经写入完成了。随后调用 TableBuilder 的 Finish 函数，这个函数会写入索引部分的块，包括 FilterBlock（可选）、 MetaIndexBlock、 IndexBlock 以及 Footer 。写入完成后，程序会对新生成文件的状态进行一些检查，通过检查后文件会被添加到内存的文件列表中，供查询使用。

下面我们看看数据在 TableBuilder 中是如何被编码的：

// table_builder.cc
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);
  }

  // 如果当前内存中的 Block 是空的，那么就为这个 Block 生成一个 IndexKey
  // 这个 IndexKey 不一定会出现在用户写入的数据中，而是根据计算得出的
  // 可以将这个 Block 和上一个 Block 分开的最短的 Key
  // 例如上一个 Block 的 IndexKey 是 "the great"， 当前 Block 插入的第一个
  // key 为 "the hello" ，那么这个 IndexKey 需要满足
  // "the great" < IndexKey <= "the hello"
  // 例如，其值可能是 "the h"
  if (r->pending_index_entry) {
    assert(r->data_block.empty());
    r->options.comparator->FindShortestSeparator(&r->last_key, key);
    std::string handle_encoding;
    r->pending_handle.EncodeTo(&handle_encoding);
    // 将这个 IndexKey 记录到 index block 中
    r->index_block.Add(r->last_key, Slice(handle_encoding));
    r->pending_index_entry = false;
  }

  // 如果需要生成 BloomFilter ，则将这个数据编码进 BloomFilter 中
  if (r->filter_block != nullptr) {
    r->filter_block->AddKey(key);
  }

  r->last_key.assign(key.data(), key.size());
  r->num_entries++;
  // 将数据编码进 DataBlock 中
  r->data_block.Add(key, value);

  const size_t estimated_block_size = r->data_block.CurrentSizeEstimate();
  // 如果 DataBlock 的大小大于阈值（默认为 4KB），则将这个 DataBlock 刷到磁盘上
  if (estimated_block_size >= r->options.block_size) {
    Flush();
  }
}

在这里，数据还是没有被直接编码，而是被插入到了 DataBlock 中。如果一个 DataBlock 的大小超过了阈值（默认为 4KB），那么它就会被刷到文件中。除了插入数据，Add 函数还做了其他的事情：在 IndexBlock 中为本 DataBlock 生成一个 IndexKey ，这个 IndexKey 不一定会出现在用户插入的数据中，而是一个计算出来的最短的可以区别两个 DataBlock 的 key 。如果用户在配置中开启了布隆过滤器，那么在这个函数中也会将 key 编码到 FilterBlock 中。

在 DataBlock 的 Add 函数中，真正执行了对数据的编码。下面我们来看看这个函数是如何执行的。

// block_builder.cc
// BlockBuilder 会寻找不同 key 之间可以共享的部分，以此进行压缩
// 压缩只会对 key 进行，不会对 value 进行
// 压缩后的格式为
// <与前一个 key 的共享长度><不共享的长度><value 的长度><key 不共享的部分><value>
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 {
    // Restart compression
    restarts_.push_back(buffer_.size());
    counter_ = 0;
  }
  // 当前键和上一个键不重叠的大小
  const size_t non_shared = key.size() - shared;

  // 将 "<shared><non_shared><value_size>" 编码到 buffer_ 中
  PutVarint32(&buffer_, shared);
  PutVarint32(&buffer_, non_shared);
  PutVarint32(&buffer_, value.size());

  // 将当前键不共享的部分以及 value 的内容编码到 buffer_ 中
  buffer_.append(key.data() + shared, non_shared);
  buffer_.append(value.data(), value.size());

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

在 BlockBuilder 中，所有的数据都被一起编码到一个 buffer 中。但是中编码之前，程序会对 key 进行一次压缩。这个压缩是通过寻找当前 key 和上一个 key 之间共同的长度来完成的。当然，这个共享不会无限进行下去，每隔若干个 key ，程序会就重新开始计算共享键。例如，如果系统设置的共享键数目是 16 （默认值），那么第 1 个到第 16 个 key 之间是有内容共享的，第 16 个和第 17 个键则不计算其共享的内容，第 17 个键到第 32 键之间又继续计算其共享内容。这是因为最终数据会被编码成

<SharedKeyLength> <NonSharedKeyLength> <ValueLength> <NonSharedKeyContent> <ValueContent>

的形式，因此读取一个键时，只能知道它与前一个键不共享部分的内容，如果要读取其完整值，则必须知道它与前一个键共享的内容。因此，我们需要一直往前找，直到找到一个 SharedKeyLength 为 0 的 key ，然后往后读，一直读到我们需要的 key 为止。如果整个 DataBlock 都一起共享键，那么每次我们读取一个键都要从这个 DataBlock 的第一个键开始读，效率非常低。为了避免这种情况， DataBlock 中键值的共享在每一个 Entry 中进行，每 16 个键（默认值）保存在一个 Entry 中，并且为每个 Entry 在文件中维护了一个 Restart Point ，用于指向这个 Entry 。这样，在读取一个 Key 时，只需要找到这个 Key 所在的 Entry ，然后从这个 Entry 的第一个 Key 开始读即可。这样在读取一个 Key 时既不会读取太多其他的 Key ，也可以有效压缩 Key 的大小 。最后需要注意的是，这里通过共享值的压缩方法只会对 Key 进行，对于 Value 则是不做任何处理直接编码进 buffer 中。

SSTable 的读流程

SSTable 的读流程其实就是写流程的逆过程。读流程的入口在 table_cache.cc 中的 FindTable 函数中。

// table_cache.cc
Status TableCache::FindTable(uint64_t file_number, uint64_t file_size,
                             Cache::Handle** handle) {
  Status s;
  char buf[sizeof(file_number)];
  EncodeFixed64(buf, file_number);
  Slice key(buf, sizeof(buf));
  // 在 Cache 中查找是否缓存 SSTable 的 handle
  *handle = cache_->Lookup(key);
  if (*handle == nullptr) {
  	// 如果没有缓存，就从磁盘中打开这个 SSTable
    std::string fname = TableFileName(dbname_, file_number);
    RandomAccessFile* file = nullptr;
    Table* table = nullptr;
    s = env_->NewRandomAccessFile(fname, &file);
    if (!s.ok()) {
      std::string old_fname = SSTTableFileName(dbname_, file_number);
      if (env_->NewRandomAccessFile(old_fname, &file).ok()) {
        s = Status::OK();
      }
    }
    if (s.ok()) {
    	// 打开文件，读取内容
      s = Table::Open(options_, file, file_size, &table);
    }

    // some check codes
    ...
  }
  return s;
}

在读取一个文件之前，程序首先会在 TableCache 查找有无该文件的 handle ，如果没有，才会从磁盘中读取这个文件。 Table::Open 函数从磁盘上读取这个文件的 Footer 和 IndexBlock ，如果文件有 FilterBlock，也会将 MetaIndexBlock 读入内存中。当这些数据都被读完后，程序会对读取的状态进行一些检查，通过检查后这个文件的 handle 就会被缓存在 TableCache 中，供其他过程使用。

// table.cc
Status Table::Open(const Options& options, RandomAccessFile* file,
                   uint64_t size, Table** table) {
  *table = nullptr;
  if (size < Footer::kEncodedLength) {
    return Status::Corruption("file is too short to be an sstable");
  }

  // 读取 footer
  char footer_space[Footer::kEncodedLength];
  Slice footer_input;
  Status s = file->Read(size - Footer::kEncodedLength, Footer::kEncodedLength,
                        &footer_input, footer_space);
  if (!s.ok()) return s;

  Footer footer;
  s = footer.DecodeFrom(&footer_input);
  if (!s.ok()) return s;

  // 读取 index block
  BlockContents index_block_contents;
  ReadOptions opt;
  if (options.paranoid_checks) {
    opt.verify_checksums = true;
  }
  s = ReadBlock(file, opt, footer.index_handle(), &index_block_contents);

  if (s.ok()) {
    // We've successfully read the footer and the index block: we're
    // ready to serve requests.
    Block* index_block = new Block(index_block_contents);
    Rep* rep = new Table::Rep;
    rep->options = options;
    rep->file = file;
    rep->metaindex_handle = footer.metaindex_handle();
    rep->index_block = index_block;
    rep->cache_id = (options.block_cache ? options.block_cache->NewId() : 0);
    rep->filter_data = nullptr;
    rep->filter = nullptr;
    // 生成新的 Table 对象，并且读取 BloomFilter
    *table = new Table(rep);
    (*table)->ReadMeta(footer);
  }

  return s;
}

上面是在 Open 函数中读取文件 Footer 和 IndexBlock 的代码，在 table->ReadMeta 中会读取文件的 MetaIndexBlock（如果存在的话）。

至此，一个文件的索引部分（除了 FilterBlock ）已经被加载到了内存中。下面让我们看看当我们需要从已经加载到了内存中的文件里读取一个具体的 Key 需要经过怎样的流程。

// table.cc
Status Table::InternalGet(const ReadOptions& options, const Slice& k, void* arg,
                          void (*handle_result)(void*, const Slice&,
                                                const Slice&)) {
  Status s;
  // 从 IndexBlock 中找到可能保存搜索键 k 的 dataBlock 对应的 IndexKey
  Iterator* iiter = rep_->index_block->NewIterator(rep_->options.comparator);
  iiter->Seek(k);
  if (iiter->Valid()) {
    Slice handle_value = iiter->value();
    FilterBlockReader* filter = rep_->filter;
    BlockHandle handle;
    if (filter != nullptr && handle.DecodeFrom(&handle_value).ok() &&
        !filter->KeyMayMatch(handle.offset(), k)) {
    	// 如果 bloomFilter 存在，并且 BloomFilter 指示不存在这个 key ，查找失败
      // Not found
    } else {
    	// 构建一个前面在 IndexBlock 中找到的目标 Block 的 iterator
      Iterator* block_iter = BlockReader(this, options, iiter->value());
      // 通过 block iterator 查找键
      block_iter->Seek(k);
      if (block_iter->Valid()) {
        (*handle_result)(arg, block_iter->key(), block_iter->value());
      }
      s = block_iter->status();
      delete block_iter;
    }
  }
  if (s.ok()) {
    s = iiter->status();
  }
  delete iiter;
  return s;
}

Table::InternalGet 函数完成了在 SSTable 中查找的过程。首先程序会从 IndexBlock 找到可能保存搜索键 k 的 DataBlock 的 IndexKey （因为 DataBlock 是有序存放的，因此用二分查找即可找到），然后检查是否有布隆过滤器，有的话检查布隆过滤器中是否编码了这个键，如果没编码，那么代表这个数据不存在于这个 SSTable 中，查找失败；否则，如果布隆过滤器不存在或者布隆过滤器中编码了这一个 key ，那么就对前面在 IndexBlock 查找到的指向的 DataBlock 新建一个 iterator ，然后通过这个 iterator 找到这个键。

// block.cc
void Seek(const Slice& target) override {
  // Binary search in restart array to find the last restart point
  // with a key < target
  uint32_t left = 0;
  uint32_t right = num_restarts_ - 1;
  int current_key_compare = 0;

  // 如果已经进行过查找了，那么就检查上一轮查找最终结束的位置是在当前 key 的左边还是右边
  if (Valid()) {
    // If we're already scanning, use the current position as a starting
    // point. This is beneficial if the key we're seeking to is ahead of the
    // current position.
    current_key_compare = Compare(key_, target);
    if (current_key_compare < 0) {
      // key_ is smaller than target
      left = restart_index_;
    } else if (current_key_compare > 0) {
      right = restart_index_;
    } else {
      // We're seeking to the key we're already at.
      return;
    }
  }

  // 使用二分查找寻找这个 key 所在的位置
  while (left < right) {
    uint32_t mid = (left + right + 1) / 2;
    uint32_t region_offset = GetRestartPoint(mid);
    uint32_t shared, non_shared, value_length;
    const char* key_ptr =
        DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,
                    &non_shared, &value_length);
    if (key_ptr == nullptr || (shared != 0)) {
      CorruptionError();
      return;
    }
    Slice mid_key(key_ptr, non_shared);
    if (Compare(mid_key, target) < 0) {
      // Key at "mid" is smaller than "target".  Therefore all
      // blocks before "mid" are uninteresting.
      left = mid;
    } else {
      // Key at "mid" is >= "target".  Therefore all blocks at or
      // after "mid" are uninteresting.
      right = mid - 1;
    }
  }

  // We might be able to use our current position within the restart block.
  // This is true if we determined the key we desire is in the current block
  // and is after than the current key.
  assert(current_key_compare == 0 || Valid());
  // 如果我们当前已经在这个 RestartPoint 指向的 Entry 里了（上一次查找）
  // 并且我们要找的键就在这个 Entry 中，那么我们就可以不用 seek
  bool skip_seek = left == restart_index_ && current_key_compare < 0;
  if (!skip_seek) {
  	// 跳转到 key 所在的 RestartPoint 指向的 Entry
    SeekToRestartPoint(left);
  }
  // 在一个 Entry 中从头往后读
  // Linear search (within restart block) for first key >= target
  while (true) {
    if (!ParseNextKey()) {
      return;
    }
    if (Compare(key_, target) >= 0) {
      return;
    }
  }
}

上面这段代码就是在 BlockIterator 中查找搜索 key 的过程。函数的主体是一个二分搜索，找到这个 key 所在的 Entry ，然后从这个 Entry 的第一个键开始顺序地往下读，直到读到我们要查找的 key 为止。

到这里 SSTable 的读写过程就解析完了，这里值得体会的是对文件分块分层次组织的过程，从 SSTable 到 DataBlock 再到 Entry ，多个数据层次使得文件写和文件读可以更高效。同时，将索引和数据放在一个文件里，使得索引和数据在删除与移动时都是一体的。