LevelDB 多版本和压缩

1
2
3
4
5
6
7
8
9

enum FileType {
  kLogFile,
  kDBLockFile,
  kTableFile,
  kDescriptorFile,
  kCurrentFile,
  kTempFile,
  kInfoLogFile  // Either the current one, or an old one
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

struct FileMetaData {
  FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) {}

  int refs;
  int allowed_seeks;     // Compaction时会介绍这个字段
  uint64_t number;
  uint64_t file_size;    // 文件大小
  InternalKey smallest;  // 文件里最小的internal key
  InternalKey largest;   // 文件里最大的internal key
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Version {
  VersionSet* vset_;  // 版本集的引用
  Version* next_;     // 版本在版本集里的next_指针
  Version* prev_;     // 版本在版本集里的prev_指针
  int refs_;          // 引用计数

  // SSTable的信息，每一项代表相应Level的SSTable信息
  // 除了Level 0外，每个Level里的文件都是按照最小键的顺序排列的，并且没有重叠
  // 通过这个数据项，搜索SSTable时，就可以从Level 0开始搜索
  std::vector<FileMetaData*> files_[config::kNumLevels];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class VersionEdit {
    typedef std::set<std::pair<int, uint64_t>> DeletedFileSet;

    std::string comparator_;             // 比较器的名称，持久化后，下次打开时需要对比一致
    uint64_t log_number_;                // 日志文件的编号
    uint64_t next_file_number_;          // ldb、log和MANIFEST下一个文件的编号
    SequenceNumber last_sequence_;       // 上一个使用的SequenceNumber
    bool has_comparator_;                // 记录上面4个字段是否存在，存在才会持久化的MANIFEST中
    bool has_log_number_;
    bool has_next_file_number_;
    bool has_last_sequence_

    // 和VersionSet里面的compact_pointers_相同
    std::vector<std::pair<int, InternalKey>> compact_pointers_;
    // 有哪些文件被删除，就是Version里哪些SSTable被删除
    DeletedFileSet deleted_files_;
    // 有哪些文件被增加，pair的第一个参数是Level，第二个参数是文件的元信息
    std::vector<std::pair<int, FileMetaData>> new_files_;
};

1
2

Status VersionEdit::DecodeFrom(const Slice& src)
void VersionEdit::EncodeTo(std::string* dst) const

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

    Env* const env_;                      // 封装部分操作系统调用，包括文件、线程操作等
    const std::string dbname_;            // 数据库名称，Open时传入
    const Options* const options_;        // 数据库选项，Open时传入
    TableCache* const table_cache_;       // 打开的SSTable的缓存，Open时创建
    const InternalKeyComparator icmp_;    // 根据User Key生成的Internal Key的Comparator
    uint64_t next_file_number_;           // ldb、log和MANIFEST生成新文件时都有一个序号单调递增
    uint64_t manifest_file_number_;       // 当前的MANIFEST的编号
    uint64_t last_sequence_;              // 上一个使用的SequenceNumber
    uint64_t log_number_;                 // 当前的日志的编号

    WritableFile* descriptor_file_;       // MANIFEST打开的文件描述符
    log::Writer* descriptor_log_;         // MANIFEST实际存储的格式是WAL日志的格式，所以这里用来写入数据
    Version dummy_versions_;              // Version链表的头结点
    Version* current_;                    // 当前的Version

    // 这是用来记录Compact的进度，Compact总是从某一Level的最小的键开始到某个键结束，
    // 下次再从下一个键开始，所以这个就是下一次这个Level从哪个键开始Compact
    std::string compact_pointer_[config::kNumLevels];

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  struct BySmallestKey {
    const InternalKeyComparator* internal_comparator;

    bool operator()(FileMetaData* f1, FileMetaData* f2) const {
      int r = internal_comparator->Compare(f1->smallest, f2->smallest);
      if (r != 0) {
        return (r < 0);
      } else {
        // Break ties by file number
        return (f1->number < f2->number);
      }
    }
  };

  typedef std::set<FileMetaData*, BySmallestKey> FileSet;
  struct LevelState {
    std::set<uint64_t> deleted_files;
    FileSet* added_files;
  };

  VersionSet* vset_;
  Version* base_;
  LevelState levels_[config::kNumLevels];

1
2
3
4
5
6

  const InternalKeyComparator icmp_;
  const std::vector<FileMetaData*>* const flist_;
  uint32_t index_;

  // Backing store for value().  Holds the file number and size.
  mutable char value_buf_[16];

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Iterator* Version::NewConcatenatingIterator(const ReadOptions& options, int level) const {
  return NewTwoLevelIterator(new LevelFileNumIterator(vset_->icmp_, &files_[level]),
	&GetFileIterator, vset_->table_cache_, options);
}

static Iterator* GetFileIterator(void* arg, const ReadOptions& options,
                                 const Slice& file_value) {
	TableCache* cache = reinterpret_cast<TableCache*>(arg);
	return cache->NewIterator(options, DecodeFixed64(file_value.data()),
                              DecodeFixed64(file_value.data() + 8));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// db/version_set.h

class Compaction {
    int level_;                      // Compaction文件所在的Level
    uint64_t max_output_file_size_;  // 生成的文件的最大值
    Version* input_version_;         // Compaction发生时的Version
    VersionEdit edit_;               // Compaction结果保存的VersionEdit

  // Each compaction reads inputs from "level_" and "level_+1"
  std::vector<FileMetaData*> inputs_[2];  // The two sets of inputs

  // State used to check for number of overlapping grandparent files
  // (parent == level_ + 1, grandparent == level_ + 2)
  std::vector<FileMetaData*> grandparents_;
  size_t grandparent_index_;  // Index in grandparent_starts_
  bool seen_key_;             // Some output key has been seen
  int64_t overlapped_bytes_;  // Bytes of overlap between current output
                              // and grandparent files

  // State for implementing IsBaseLevelForKey

  // level_ptrs_ holds indices into input_version_->levels_: our state
  // is that we are positioned at one of the file ranges for each
  // higher level than the ones involved in this compaction (i.e. for
  // all L >= level_ + 2).
  size_t level_ptrs_[config::kNumLevels];
}

1
2
3
4
5
6
7
8

  // Information for a manual compaction
  struct ManualCompaction {
    int level;
    bool done;
    const InternalKey* begin;  // null means beginning of key range
    const InternalKey* end;    // null means end of key range
    InternalKey tmp_storage;   // Used to keep track of compaction progress
  };

1

void DBImpl::TEST_CompactRange(int level, const Slice* begin, const Slice* end)