leveldb 使用 version 來保存數據庫的狀態。
先看看一個重要的數據結果，sst file的META info
<db/version_edit.h>
struct FileMetaData {
int refs; //引用計數
int allowed_seeks; //允許的seeks次數
uint64_t number;//文件編號
uint64_t file_size; //文件大小
InternalKey smallest; //最小的key
InternalKey largest; //最大的key
FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) { }
};
這里面有一個很有意思的字段: allowed_seeks,代表了可以seek的次數，為0的時候表示這個文件需要被compaction.如何設置seeks次數呢？文件大小除以16k，不到100算100。
f->allowed_seeks = (f->file_size / 16384);
if (f->allowed_seeks < 100) f->allowed_seeks = 100;
原因，請看leveldb的注釋：
// We arrange to automatically compact this file after a certain number of seeks. Let's assume:
// (1) One seek costs 10ms
// (2) Writing or reading 1MB costs 10ms (100MB/s)
// (3) A compaction of 1MB does 25MB of IO:
// 1MB read from this level
// 10-12MB read from next level (boundaries may be misaligned)
// 10-12MB written to next level
// This implies that 25 seeks cost the same as the compaction
// of 1MB of data. I.e., one seek costs approximately the
// same as the compaction of 40KB of data. We are a little
// conservative and allow approximately one seek for every 16KB
// of data before triggering a compaction.
接下來看Version的定義，version其實就是一系列的SST file的集合。
class Version {
public:
//生成iterator用于遍歷
void AddIterators(const ReadOptions&, std::vector<Iterator*>* iters);
//根據key來查詢，若沒有查到，更新GetStats
struct GetStats {
FileMetaData* seek_file;
int seek_file_level;
};
Status Get(const ReadOptions&, const LookupKey& key, std::string* val,
GetStats* stats);
//是否需要進行compaction
bool UpdateStats(const GetStats& stats);
//引用計算，避免在被引用時候刪除
void Ref();
void Unref();
//查詢和key range有關的files
void GetOverlappingInputs(
int level,
const InternalKey* begin, // NULL means before all keys
const InternalKey* end, // NULL means after all keys
std::vector<FileMetaData*>* inputs);
//計算是否level對某個key range是否有overlap
bool OverlapInLevel(int level,
const Slice* smallest_user_key,
const Slice* largest_user_key);
//memtable output應該放到哪個level
int PickLevelForMemTableOutput(const Slice& smallest_user_key,
const Slice& largest_user_key);
//某個level的文件個數
int NumFiles(int level) const { return files_[level].size(); }
// Return a human readable string that describes this version's contents.
std::string DebugString() const;
private:
friend class Compaction;
friend class VersionSet;
class LevelFileNumIterator;
Iterator* NewConcatenatingIterator(const ReadOptions&, int level) const;
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
//sst files
std::vector<FileMetaData*> files_[config::kNumLevels];
//下一個要被compaction的文件
FileMetaData* file_to_compact_;
int file_to_compact_level_;
//compaction score:>1表示要compaction
double compaction_score_;
int compaction_level_;
explicit Version(VersionSet* vset)
: vset_(vset), next_(this), prev_(this), refs_(0),
file_to_compact_(NULL),
file_to_compact_level_(-1),
compaction_score_(-1),
compaction_level_(-1) {
}
~Version();
// No copying allowed
Version(const Version&);
void operator=(const Version&);
};
那VersionSet呢？VersionSet 是version組成一個雙向循環鏈表。
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_;
uint64_t manifest_file_number_;
uint64_t last_sequence_;
uint64_t log_number_;
WritableFile* descriptor_file_;
log::Writer* descriptor_log_;
Version dummy_versions_; // Head of circular doubly-linked list of versions.
Version* current_; // == dummy_versions_.prev_
//每層都有一個compact pointer用于指示下次從哪里開始compact,以用于實現循環compact
std::string compact_pointer_[config::kNumLevels];
//. . .
}
VersionEdit是version對象的變更記錄，用于寫入manifest.這樣通過原始的version加上一系列的versionedit的記錄，就可以恢復到最新狀態。
class VersionEdit {
public:
VersionEdit() { Clear(); }
~VersionEdit() { }
void Clear();
void SetComparatorName(const Slice& name) {
has_comparator_ = true;
comparator_ = name.ToString();
}
void SetLogNumber(uint64_t num) {
has_log_number_ = true;
log_number_ = num;
}
void SetPrevLogNumber(uint64_t num) {
has_prev_log_number_ = true;
prev_log_number_ = num;
}
void SetNextFile(uint64_t num) {
has_next_file_number_ = true;
next_file_number_ = num;
}
void SetLastSequence(SequenceNumber seq) {
has_last_sequence_ = true;
last_sequence_ = seq;
}
void SetCompactPointer(int level, const InternalKey& key) {
compact_pointers_.push_back(std::make_pair(level, key));
}
//添加meta file
void AddFile(int level, uint64_t file,
uint64_t file_size,
const InternalKey& smallest,
const InternalKey& largest) {
FileMetaData f;
f.number = file;
f.file_size = file_size;
f.smallest = smallest;
f.largest = largest;
new_files_.push_back(std::make_pair(level, f));
}
//刪除特定的文件
void DeleteFile(int level, uint64_t file) {
deleted_files_.insert(std::make_pair(level, file));
}
//編碼，解碼：用于寫入manifest
void EncodeTo(std::string* dst) const;
Status DecodeFrom(const Slice& src);
std::string DebugString() const;
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_;
};