Version records LevelDB metadata. LevelDB metadata is managed by Version control. A Version is a complete set of metadata records.

Why did LevelDB introduce version control? Normally, when version A is upgraded to version B, version A is the old version and can actually be deleted. LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB Version Dummy_versions_ is the header pointer of the bidirectional linked list, and Version* current_ is the latest Version. When a Version no longer serves read requests, it is removed from the bidirectional list.

Here are some concepts related to versioning: Version, VersionEdit, and VersionSet.

1, Version Version

class Version { VersionSet* vset_; // VersionSet to which this Version belongs Version* next_; // Next version in linked list Version* prev_; // Previous version in linked list int refs_; // Number of live refs to this version // List of files per level std::vector<FileMetaData*> files_[config::kNumLevels];  // Next file to compact based on seek stats. FileMetaData* file_to_compact_; int file_to_compact_level_; // Level that should be compacted next and its compaction score. // Score < 1 means compaction is not strictly needed. These fields // are initialized by Finalize(). double compaction_score_; int compaction_level_; };Copy the code

This is a static concept, and we can see that Version has a large number of member variables, which can be divided into several functions:

1) The Version bidirectional linked list of the first four member variables related to VersionSet: this links multiple versions together.

2) Each Version of Version records all files at each level it contains, that is: Files_ member variable STD ::vector<FileMetaData*> files_[config::kNumLevels], files_[config::kNumLevels], files_[config::kNumLevels], files_[config::kNumLevels], files_[config::kNumLevels] That is, all file metadata information contained in this level.

3) Information related to file compression: LevelDB generates a new Version by merging, so you need to specify how to merge in the current Version. When a file at the current level is merged with a file at the next level to create a new file, the next Version needs to record how the next Version is generated. This is done by combining the last four compaction member variables.

2. Version increment VersionEdit

class VersionEdit {
 private:
  friend class VersionSet;
  typedef std::set<std::pair<int, uint64_t>> DeletedFileSet;
  std::string comparator_;
  uint64_t log_number_;
  uint64_t prev_log_number_;
  uint64_t next_file_number_;
  SequenceNumber last_sequence_;
  bool has_comparator_;
  bool has_log_number_;
  bool has_prev_log_number_;
  bool has_next_file_number_;
  bool has_last_sequence_;
  std::vector<std::pair<int, InternalKey>> compact_pointers_;
  DeletedFileSet deleted_files_;
  std::vector<std::pair<int, FileMetaData>> new_files_;
};
Copy the code

This is a dynamic concept, delta type, which is incremental information relative to the current version, and also includes several features:

1) Records related to file serial numbers: Version When merged, the newly generated file will use the same serial number, so the serial number of the new file will also change. These file number changes also need to be recorded as part of the change, and the various HAS_XXX indicators indicate whether the number has changed. However, the serial number changes are not accumulated to the Version presentation, but directly affect the VersionSet.

Compact_pointers_ : Because an SSTable can have a large number of files, a merge doesn’t happen all at once, and an excessive Compaction Compaction Compaction Compaction Compaction Compaction occurs in stages. The compression pointer compact_pointers_ is recorded in the VersionEdit increment, not in Version. The location of the next merge for each Level is eventually recorded in compact_pointer_ in VersionSet.

When each Version needs to be merged, the position of the next merge of each Level will be calculated. When Apply() is merged, the Level recorded in compact_pointers_ is directly used as the index, because it is the Version of Apply. This means that a later version increment VersionEdit always overrides the merge location of the previous version increment VersionEdit, so you can assign directly to override compact_pointer_ in VersionSet.

3) Records related to file changes: new_files_ and deleted_files_, both member variables are STD ::pair<> objects, indicating which level of new and deleted file information.

So what is the relationship between Version and VersionEdit?

We know that there is an expression in mathematics: A + B = C, which expresses the addition of two numbers to produce another number. This idea is also reflected in the field of programming: Base + delta = new in LevelDB, the relationship between Version and VersionEdit is the same, if the description is in LevelDB’s language, it will be Version + VersionEdit = new Version. So what about the plus sign and the equal sign? That’s VersionSet::Builder. Let’s look at how VersionSet::Builder is defined:

class VersionSet::Builder {
 private:
  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];
};
Copy the code

A + B = C A + B = C

Version* v = new Version(this); { Builder builder(this, current_); // add current_ as the base item builder.apply (edit); // Edit: current_ + Edit Builder.saveto (v); // Save the result to the new version v: current_ + edit = v}Copy the code

LevelState Levels_ [config::kNumLevels], and then generate a new Version, Version, along with the existing Version recorded in the Current Version.

How do you merge (+)? Let’s look at the implementation of Builder.apply (Edit).

1) Update the current compression pointer in vset_ : record the position of the compression pointer in the incremental version to vset_.

2) Record the deleted file file in the incremental version to the deleted file in Builder.levels_.

3) Log the new file file in the incremental version to the added file in Builder.levels_.

Code:

// Apply all of the edits in *edit to the current state. void Apply(VersionEdit* edit) { // Update compaction pointers The incremental version of compression in the pointer to the location of the record vset_ | - for (size_t I = 0; i < edit->compact_pointers_.size(); i++) { const int level = edit->compact_pointers_[i].first; vset_->compact_pointer_[level] = edit->compact_pointers_[i].second.Encode().ToString(); | -} / / Delete files to Delete files in the incremental version file records to Builder. The levels_ deleted file | - for (const auto & deleted_file_set_kvp: edit->deleted_files_) { const int level = deleted_file_set_kvp.first; const uint64_t number = deleted_file_set_kvp.second; levels_[level].deleted_files.insert(number); | -} / / Add new files to the new files in the incremental version file records to Builder. The levels_ added file | - for (size_t I = 0; i < edit->new_files_.size(); i++) { const int level = edit->new_files_[i].first; FileMetaData* f = new FileMetaData(edit->new_files_[i].second); f->refs = 1; f->allowed_seeks = static_cast<int>((f->file_size / 16384U)); // To improve read performance, divide the file size by 16K to obtain an allowable number of seek operations. If this number exceeds, the file compacts. if (f->allowed_seeks < 100) f->allowed_seeks = 100; levels_[level].deleted_files.erase(f->number); levels_[level].added_files->insert(f); | -}Copy the code

We look at the implementation of Builder.saveto (v)

Iterate through all levels:

1) Merge the ordered arrays base_files and ADDED together.

2) Iterate over the new and base files: see if file is in the list of files to be deleted. If not, add it to the list of files at the level corresponding to version V.

Code:

// Save the current state in *v. void SaveTo(Version* v) { BySmallestKey cmp; //[ZLL]: This object's operator returns the bool of whether the key is smaller. for (int level = 0; level < config::kNumLevels; Level ++) {//[ZLL]: Merge the set of added files with the set of pre-existing files. // Drop any deleted files. Store the result in *v. const std::vector<FileMetaData*>& base_files = base_->files_[level]; //[ZLL]: existing files in the Current version of each level. std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin(); std::vector<FileMetaData*>::const_iterator base_end = base_files.end(); const FileSet* added_files = levels_[level].added_files; V ->files_[level].reserve(base_files.size() + added_files->size()); //[ZLL]: File files_ in the Version to be saved is extended to existing files in the Current Version + newly added files in the incremental Version. for (const auto& added_file : *added_files) {//[ZLL]: echo these new files // Add all smaller files listed in base_ for (STD ::vector<FileMetaData*>::const_iterator  bpos = std::upper_bound(base_iter, base_end, added_file, cmp); //[ZLL]: find the first file that does not satisfy the CMP rule, i.e., base_iter! = bpos; ++base_iter) { MaybeAddFile(v, level, *base_iter); //[ZLL]: append these smaller files to the Version to be saved} MaybeAddFile(v, level, added_file); //[ZLL]: Add remaining Base files for (; base_iter ! = base_end; ++base_iter) { MaybeAddFile(v, level, *base_iter); //[ZLL]: append the file from CurrentVersion to Version}}}Copy the code

Check to see if file is in the list to delete, if not, then add it to the list of files corresponding to the level of version V.

void MaybeAddFile(Version* v, int level, FileMetaData* f) { if (levels_[level].deleted_files.count(f->number) > 0) { // File is deleted: do nothing } else { std::vector<FileMetaData*>* files = &v->files_[level]; if (level > 0 && ! files->empty()) { // Must not overlap assert(vset_->icmp_.Compare((*files)[files->size() - 1]->largest, f->smallest) < 0); } f->refs++; files->push_back(f); }}};Copy the code

3. FileMetaData FileMetaData

struct FileMetaData {
  FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) {}
  int refs;
  int allowed_seeks;  // Seeks allowed until compaction
  uint64_t number;
  uint64_t file_size;    // File size in bytes
  InternalKey smallest;  // Smallest internal key served by table
  InternalKey largest;   // Largest internal key served by table
};
Copy the code

The metadata information of a file is simple, including the file number, file size, minimum key, maximum key, allowed search times, and reference count. The smallest key and the largest key are the most important keys for searching a file. If you can find a key in a file, you can find it quickly by checking whether the key is in the [largest, largest] range.

4. Version onset

class VersionSet { Env* const env_; const std::string dbname_; const Options* const options_; TableCache* const table_cache_; const InternalKeyComparator icmp_; uint64_t next_file_number_; // In the manifest, uint64_t manifest_file_number_; // Manifest file number, incremented uint64_t last_sequence_; // Sequence number, used for snapshot, incremented uint64_t log_number_ for each write operation; //WAL log file number uint64_t prev_log_number_; // 0 or backing store for memtable being compacted // Opened lazily WritableFile* descriptor_file_; log::Writer* descriptor_log_; Version dummy_versions_; // Head of circular doubly-linked list of versions. Version* current_; // == dummy_versions_.prev_ // Per-level key at which the next compaction at that level should start. // Either an empty  string, or a valid InternalKey. std::string compact_pointer_[config::kNumLevels]; };Copy the code

It is used to manage all versions. When new versions are generated, it needs to Append to VersionSet. When the old Version is no longer available for reading requests, the Version will be removed from the bidirectional linked list. Version* current_ is used to not be removed. VersionSet also includes several functions:

1) Compaction information related to Compaction: the location of the next Compaction for each Level is eventually recorded in the VersionSet compact_pointer_.

2) SSTable LRU cache: TableCache* const table_cache_

3) InternalKey comparator: InternalKeyComparator ICMP_

4) Record the latest value of the serial number of the new file after the VersionEdit merge.

5) MANIFEST file WritableFile* descriptor_file_

6) WAL log file log::Writer* descriptor_log_

7) Version list: Normally, when version A is upgraded to version B, version A is the old version and can actually be deleted. LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB: LevelDB Version Dummy_versions_ is the header pointer of the bidirectional linked list, and Version* current_ is the latest Version. When a Version no longer serves read requests, it is removed from the bidirectional list.

The linked list pointer in the Version structure looks like this:

class Version { VersionSet* vset_; // VersionSet to which this Version belongs Version* next_; // Next version in linked list Version* prev_; // Previous version in linked list int refs_; // Number of live refs to this version... ... };Copy the code

Note that the current version current_ always points to the last element of the bidirectional list.

Code:

void VersionSet::AppendVersion(Version* v) { // Make "v" current assert(v->refs_ == 0); assert(v ! = current_); if (current_ ! = nullptr) { current_->Unref(); } current_ = v; V ->Ref(); V ->prev_ = dummy_versions_. Prev_; v->next_ = &dummy_versions_; v->prev_->next_ = v; v->next_->prev_ = v; }Copy the code

So far, the close and complex relationship between Version, Version increment VersionEdit, Version set VersionSet, and VersionSet::Builder has been sorted out, and the overall feeling is that LevelDB’s Version handling is still a bit messy.