leveldb学习之version

double MaxBytesForLevel(int level) { // Note: the result for level zero is not really used since we set // the level-0 compaction threshold based on number of files. double result = 10 * 1048576.0; // Result for both level-0 and level-1 while (level > 1) { result *= 10; level--; } return result; } static uint64_t MaxFileSizeForLevel(int level) { return kTargetFileSize; // We could vary per level to reduce number of files? }

关于不同level中sstable文件的最大大小，kTargetFileSize 是静态常量，设为2 * 1048576。

version

leveldb将每次compact后的最新数据状态定义为Version，也就是当前db信息以及每个level上具有最新数据状态的sstable集合。

class version{
  VersionSet* vset_;            // VersionSet to which this Version belongs
//表示所属的versionset,version是数据库的版本，那versionset就是version的集合

  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];
  //每个level的所有sstable信息

  // Next file to compact based on seek stats.
  FileMetaData* file_to_compact_;
  int file_to_compact_level_;
  //需要compact的文件

  // 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_;
}

但是由于某些时候compact会在某个level上新加入或者删除一些sstable，如果这个时候，这些sstable正在被读，为了处理这样的读写竞争，基于sstable一旦生成就不会改动的特点，每个version加入引用计数refs_，这样db中可能有多个version同时存在，他们通过链表链接。当version的引用计数为0并且不是当前最新的version，他会从链表中移除，对应的，该version的sstable就可以删除了。

Version不会修改其管理的sstable文件，只有读取操作。先来看一个结构，FileMetaData结构：保存sstable的元信息。

struct FileMetaData {
  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
  FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) { }
};

smallest、largest可以帮助定位target所在文件。遍历version::file_容器数组，即可找到目标关键字所在文件。
version内定义了迭代器类LevelFileNumIterator，通过NewConcatenatingIterator成员函数返回文件迭代器，一般用于表示查找的结果。

int FindFile(const InternalKeyComparator& icmp,
             const std::vector<FileMetaData*>& files,
             const Slice& key)

完成的是在中一个level查找（使用二分法），会被version中有关定位文件的函数调用。

SomeFileOverlapsRange函数用于判断sstable的key范围是否溢出smallest_user_key和largest_user_key范围之间。

bool SomeFileOverlapsRange(
    const InternalKeyComparator& icmp,
    bool disjoint_sorted_files,
    const std::vector<FileMetaData*>& files,
    const Slice* smallest_user_key,
    const Slice* largest_user_key)

Get函数，version内的key查询操作，先看声明

Status Version::Get(const ReadOptions& options,
                    const LookupKey& k,
                    std::string* value,
                    GetStats* stats)

由于level-0的sstable是memtable直接dump到磁盘，所以可能overlap，而level-0以上全是由compact生成，不存在overlap，即不同的sstable存储的数据，key的范围没有交集，目的是为了提高读得性能。所以在函数里，对于level-0和level-n区别对待：
level-0：会遍历level-0的FileMetaData数组，并且对找到use_key的sstable文件按照从新到旧排序
level-n：则调用FindFile函数处理，找到即返回结果

发现在某个sstable找到key，则去内存中有无此table的缓存cache，并加载进内存。

s = vset_->table_cache_->Get(options, f->number, f->file_size,ikey, &saver, SaveValue);

get函数有一个GetStats参数，这是一个保存查找关键词结果的结构，内含entry的key和value以及所在的sstable的信息。leveldb会对每一次的查找做一个记录，并以查找结果更新version。

version更新函数

bool Version::UpdateStats(const GetStats& stats) {
  FileMetaData* f = stats.seek_file;
  if (f != NULL) {
    f->allowed_seeks--;
    if (f->allowed_seeks <= 0 && file_to_compact_ == NULL) {
      file_to_compact_ = f;
      file_to_compact_level_ = stats.seek_file_level;
      return true;
    }
  }
  return false;
}

如果一个sstable被频繁查寻访问（查询次数高达allowed_seeks次），则将该sstable记录成version的file_to_compact_，sstable的level也会跟新，file_to_compact_level_ = stats.seek_file_level。这个策略只是leveldb为了保持磁盘中levels-sstables结构的平衡性策略的一部分，相关函数RecordReadSample、ForEachOverlapping。

其他函数：
Ref、Unref就是前面解决读写竞争的引用计数功能。当refs_为0 时，此version即可被delete。

版权声明：本文为博主原创文章，未经博主允许不得转载。

leveldb学习之version

标签：leveldb   version   compact   版本控制