in LevelDB 分布式数据库 ~ read.

LevelDB读取

LevelDB读取

数据的读取

从 LevelDB 中读取数据其实并不复杂,memtable 和 imm 更像是两级缓存,它们在内存中提供了更快的访问速度,如果能直接从内存中的这两处直接获取到响应的值,那么它们一定是最新的数据。

LevelDB 总会将新的键值对写在最前面,并在数据压缩时删除历史数据。

LevelDB-Read-Processes

数据的读取是按照 MemTable、Immutable MemTable 以及不同层级的 SSTable 的顺序进行的,前两者都是在内存中,后面不同层级的 SSTable 都是以 *.ldb 文件的形式持久存储在磁盘上,而正是因为有着不同层级的 SSTable,所以我们的数据库的名字叫做 LevelDB。

精简后的读操作方法的实现代码是这样的,方法的脉络非常清晰,作者相信这里也不需要过多的解释:

Status DBImpl::Get(const ReadOptions& options, const Slice& key, std::string* value) {
  LookupKey lkey(key, versions_->LastSequence());
  if (mem_->Get(lkey, value, NULL)) {
    // Done
  } else if (imm_ != NULL && imm_->Get(lkey, value, NULL)) {
    // Done
  } else {
    versions_->current()->Get(options, lkey, value, NULL);
  }

  MaybeScheduleCompaction();
  return Status::OK();
}

C++

当 LevelDB 在 memtable 和 imm 中查询到结果时,如果查询到了数据并不一定表示当前的值一定存在,它仍然需要判断 ValueType 来确定当前记录是否被删除。

多层级的 SSTable

当 LevelDB 在内存中没有找到对应的数据时,它才会到磁盘中多个层级的 SSTable 中进行查找,这个过程就稍微有一点复杂了,LevelDB 会在多个层级中逐级进行查找,并且不会跳过其中的任何层级;在查找的过程就涉及到一个非常重要的数据结构 FileMetaData

FileMetaData

FileMetaData 中包含了整个文件的全部信息,其中包括键的最大值和最小值、允许查找的次数、文件被引用的次数、文件的大小以及文件号,因为所有的 SSTable 都是以固定的形式存储在同一目录下的,所以我们可以通过文件号轻松查找到对应的文件。

LevelDB-Level0-Laye

查找的顺序就是从低到高了,LevelDB 首先会在 Level0 中查找对应的键。但是,与其他层级不同,Level0 中多个 SSTable 的键的范围有重合部分的,在查找对应值的过程中,会依次查找 Level0 中固定的 4 个 SSTable。

LevelDB-LevelN-Layers

但是当涉及到更高层级的 SSTable 时,因为同一层级的 SSTable 都是没有重叠部分的,所以我们在查找时可以利用已知的 SSTable 中的极值信息 smallest/largest 快速查找到对应的 SSTable,再判断当前的 SSTable 是否包含查询的 key,如果不存在,就继续查找下一个层级直到最后的一个层级 kNumLevels(默认为 7 级)或者查询到了对应的值。

SSTable 的『合并』

既然 LevelDB 中的数据是通过多个层级的 SSTable 组织的,那么它是如何对不同层级中的 SSTable 进行合并和压缩的呢;与 Bigtable 论文中描述的两种 Compaction 几乎完全相同,LevelDB 对这两种压缩的方式都进行了实现。

无论是读操作还是写操作,在执行的过程中都可能调用 MaybeScheduleCompaction 来尝试对数据库中的 SSTable 进行合并,当合并的条件满足时,最终都会执行 BackgroundCompaction 方法在后台完成这个步骤。

LevelDB-BackgroundCompaction-Processes

这种合并分为两种情况,一种是 Minor Compaction,即内存中的数据超过了 memtable 大小的最大限制,改 memtable 被冻结为不可变的 imm,然后执行方法 CompactMemTable() 对内存表进行压缩。

void DBImpl::CompactMemTable() {
  VersionEdit edit;
  Version* base = versions_->current();
  WriteLevel0Table(imm_, &edit, base);
  versions_->LogAndApply(&edit, &mutex_);
  DeleteObsoleteFiles();
}

C++

CompactMemTable 会执行 WriteLevel0Table 将当前的 imm 转换成一个 Level0 的 SSTable 文件,同时由于 Level0 层级的文件变多,可能会继续触发一个新的 Major Compaction,在这里我们就需要在这里选择需要压缩的合适的层级:

Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base) {
  FileMetaData meta;
  meta.number = versions_->NewFileNumber();
  Iterator* iter = mem->NewIterator();
  BuildTable(dbname_, env_, options_, table_cache_, iter, &meta);

  const Slice min_user_key = meta.smallest.user_key();
  const Slice max_user_key = meta.largest.user_key();
  int level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);
  edit->AddFile(level, meta.number, meta.file_size, meta.smallest, meta.largest);
  return Status::OK();
}

C++

所有对当前 SSTable 数据的修改由一个统一的 VersionEdit 对象记录和管理,我们会在后面介绍这个对象的作用和实现,如果成功写入了就会返回这个文件的元数据 FileMetaData,最后调用 VersionSet 的方法 LogAndApply 将文件中的全部变化如实记录下来,最后做一些数据的清理工作。

当然如果是 Major Compaction 就稍微有一些复杂了,不过整理后的 BackgroundCompaction 方法的逻辑非常清晰:

void DBImpl::BackgroundCompaction() {
  if (imm_ != NULL) {
    CompactMemTable();
    return;
  }

  Compaction* c = versions_->PickCompaction();
  CompactionState* compact = new CompactionState(c);
  DoCompactionWork(compact);
  CleanupCompaction(compact);
  DeleteObsoleteFiles();
}

C++

我们从当前的 VersionSet 中找到需要压缩的文件信息,将它们打包存入一个 Compaction 对象,该对象需要选择两个层级的 SSTable,低层级的表很好选择,只需要选择大小超过限制的或者查询次数太多的 SSTable;当我们选择了低层级的一个 SSTable 后,就在更高的层级选择与该 SSTable 有重叠键的 SSTable 就可以了,通过 FileMetaData 中数据的帮助我们可以很快找到待压缩的全部数据。

查询次数太多的意思就是,当客户端调用多次 Get 方法时,如果这次 Get 方法在某个层级的 SSTable 中找到了对应的键,那么就算做上一层级中包含该键的 SSTable 的一次查找,也就是这次查找由于不同层级键的覆盖范围造成了更多的耗时,每个 SSTable 在创建之后的 allowed_seeks 都为 100 次,当 allowed_seeks < 0 时就会触发该文件的与更高层级和合并,以减少以后查询的查找次数。

LevelDB-Pick-Compactions

LevelDB 中的 DoCompactionWork 方法会对所有传入的 SSTable 中的键值使用归并排序进行合并,最后会在高高层级(图中为 Level2)中生成一个新的 SSTable。

LevelDB-After-Compactions

这样下一次查询 17~40 之间的值时就可以减少一次对 SSTable 中数据的二分查找以及读取文件的时间,提升读写的性能。

存储 db 状态的 VersionSet

LevelDB 中的所有状态其实都是被一个 VersionSet 结构所存储的,一个 VersionSet 包含一组 Version 结构体,所有的 Version 包括历史版本都是通过双向链表连接起来的,但是只有一个版本是当前版本。

VersionSet-Version-And-VersionEdit

当 LevelDB 中的 SSTable 发生变动时,它会生成一个 VersionEdit 结构,最终执行 LogAndApply 方法:

Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) {
  Version* v = new Version(this);
  Builder builder(this, current_);
  builder.Apply(edit);
  builder.SaveTo(v);

  std::string new_manifest_file;
  new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
  env_->NewWritableFile(new_manifest_file, &descriptor_file_);

  std::string record;
  edit->EncodeTo(&record);
  descriptor_log_->AddRecord(record);
  descriptor_file_->Sync();

  SetCurrentFile(env_, dbname_, manifest_file_number_);
  AppendVersion(v);

  return Status::OK();
}

C++

该方法的主要工作是使用当前版本和 VersionEdit 创建一个新的版本对象,然后将 Version 的变更追加到 MANIFEST 日志中,并且改变数据库中全局当前版本信息。

MANIFEST 文件中记录了 LevelDB 中所有层级中的表、每一个 SSTable 的 Key 范围和其他重要的元数据,它以日志的格式存储,所有对文件的增删操作都会追加到这个日志中。

SSTable 的格式

SSTable 中其实存储的不只是数据,其中还保存了一些元数据、索引等信息,用于加速读写操作的速度,虽然在 Bigtable 的论文中并没有给出 SSTable 的数据格式,不过在 LevelDB 的实现中,我们可以发现 SSTable 是以这种格式存储数据的:

SSTable-Format

当 LevelDB 读取 SSTable 存在的 ldb 文件时,会先读取文件中的 Footer 信息。

SSTable-Foote

整个 Footer 在文件中占用 48 个字节,我们能在其中拿到 MetaIndex 块和 Index 块的位置,再通过其中的索引继而找到对应值存在的位置。

TableBuilder::Rep 结构体中就包含了一个文件需要创建的全部信息,包括数据块、索引块等等:

struct TableBuilder::Rep {
  WritableFile* file;
  uint64_t offset;
  BlockBuilder data_block;
  BlockBuilder index_block;
  std::string last_key;
  int64_t num_entries;
  bool closed;
  FilterBlockBuilder* filter_block;
  ...
}

C++

到这里,我们就完成了对整个数据读取过程的解析了;对于读操作,我们可以理解为 LevelDB 在它内部的『多级缓存』中依次查找是否存在对应的键,如果存在就会直接返回,唯一与缓存不同可能就是,在数据『命中』后,它并不会把数据移动到更近的地方,而是会把数据移到更远的地方来减少下一次的访问时间,虽然这么听起来却是不可思议,不过仔细想一下确实是这样。