基本概念
数据库主要包括cache、日志文件、数据文件、CURRENT文件和manifest文件几大块。
所有文件都是依照类型+文件号的命名规则,文件号非常重要,类似oracle的sequence#。
其中cache是当前写入的数据缓存,写入数据时
1 将数据写入日志文件
2 将数据放入cache
当达到一定条件,如cache里的数据够多时
1 将cache转成只读cache,供查询用。
2 新建一个读写cache和一个新日志文件。
3 将只读cache里的数据写到数据文件里,这种新生成的数据文件称为level 0。
由于每次写文件后都会启用新的cache,写入的key可能和已有数据重复,将来也会落地成文件。
因此leveldb会对文件进行“压缩
”,在多个level 0文件中给key去重,称为level 1。
随着数据库运行,level 1还会进一步和level n+1的文件合并,以此类推。
每次合并后删除老文件。
这样做的结果就是从level 1开始,每层的文件不会有重复的key,层与层之间的文件也不会有重复的key,大大提高从文件查询的效率。
由于所有文件的内容都是排序的,并且记录了key的范围,因此这些操作的成本非常可控。
当数据库重启时会根据日志文件重新构建cache并将cache里的数据写到level 0文件里。
上述所有信息称为数据库的一个Version。
Version的增量叫VersionEdit,VersionEdit记录了增加哪些文件,减少哪些文件,以及文件的概要信息等。
version1 + versionedit1 = version2
数据库里可能会保存多个version信息,所有version的载体是VersionSet。
这些信息还记录在manifest文件内,相当于oracle的控制文件。
CURRENT文件记录数据库当前manifest文件的文件名。
数据库宕机后,实例恢复的流程就是
1 根据文件命名规则,在文件夹寻找之前的CURRENT
2 寻找之前的manifest
3 定位logfile
4 将logfile数据复原到cache
5 将cache里的数据写到level 0数据文件
下面看代码
初始化数据库包括新建数据库和打开已关闭的数据库两种情况
功能入口是DB::Open
-
Status DB::Open(const Options& options, const std::string& dbname,
-
DB** dbptr) {
-
*dbptr = NULL;
-
-
-
/*
-
DBImpl是leveldb的“主类”,初始化配置信息
-
dbname是数据库的所在目录
-
*/
-
DBImpl* impl = new DBImpl(options, dbname);
-
impl->mutex_.Lock();
-
-
-
/*
-
打开数据库,如果不存在就创建。
-
如果存在就检查manifest文件,并根据其中的信息创建一个VersionEdit,用这个VersionEdit还原数据库的Version。
-
*/
-
VersionEdit edit;
-
Status s = impl->Recover(&edit); // Handles create_if_missing, error_if_exists
-
if (s.ok()) {
-
uint64_t new_log_number = impl->versions_->NewFileNumber();
-
WritableFile* lfile;
-
-
-
/*
-
以w选项打开一个新logfile。
-
lfile就是打开的文件,类型是PosixWritableFile,封装了一些IO操作。
-
*/
-
s = options.env->NewWritableFile(LogFileName(dbname, new_log_number),
-
&lfile);
-
if (s.ok()) {
-
// 初始化当前logfile文件号
-
edit.SetLogNumber(new_log_number);
-
impl->logfile_ = lfile;
-
impl->logfile_number_ = new_log_number;
-
// log::Writer用来写日志,公共函数就一个AddRecord
-
impl->log_ = new log::Writer(lfile);
-
-
-
/*
-
1 结合VersionSet,进一步设置VersionEdit,
-
2 根据当前logfile号创建一个新version作为current version
-
3 创建manifest文件
-
4 创建一个snapshot
-
*/
-
s = impl->versions_->LogAndApply(&edit, &impl->mutex_);
-
}
-
if (s.ok()) {
-
// 根据文件号等条件,删除不再需要的文件。
-
impl->DeleteObsoleteFiles();
-
// 进行一次压缩,把重复键值的文件由低级向高级合并。
-
impl->MaybeScheduleCompaction();
-
}
-
}
-
impl->mutex_.Unlock();
-
if (s.ok()) {
-
*dbptr = impl;
-
} else {
-
delete impl;
-
}
-
return s;
-
}
下面是Open函数一上来调用的构造函数
-
DBImpl::DBImpl(const Options& raw_options, const std::string& dbname)
-
/*
-
leveldb将系统相关的操作封装到env里,
-
linux版的env是PosixEnv类,在util/env_posix.cc里
-
*/
-
: env_(raw_options.env),
-
// comparator用来比较key的大小,可以自己实现,也可以用leveldb默认的
-
internal_comparator_(raw_options.comparator),
-
// 定义过滤数据的算法,比如布隆过滤等
-
internal_filter_policy_(raw_options.filter_policy),
-
// SanitizeOptions函数用来对参数raw_options的选项进行必要的处理,并封装成一个处理后的Options
-
options_(SanitizeOptions(dbname, &internal_comparator_,
-
&internal_filter_policy_, raw_options)),
-
owns_info_log_(options_.info_log != raw_options.info_log),
-
owns_cache_(options_.block_cache != raw_options.block_cache),
-
// dbname其实是指定数据库的文件夹,所有数据文件都会放到这个文件夹下。
-
dbname_(dbname),
-
-
-
// 用于锁文件,linux的是PosixFileLock类,里面有一个文件描述符和一个字符串
-
db_lock_(NULL),
-
shutting_down_(NULL),
-
-
-
// 管理后台线程的并发
-
bg_cv_(&mutex_),
-
-
-
/*
-
下面两个memtable,是对SkipList类的封装。
-
关于SkipList, 参考我之前的博客 http://blog.itpub.net/26239116/viewspace-1839630/
-
具体封装方式是在memtable.h里定义typedef,并设置为成员变量
-
typedef SkipList<const char*, KeyComparator> Table;
-
...
-
Table table_;
-
*/
-
mem_(new MemTable(internal_comparator_)),
-
imm_(NULL),
-
logfile_(NULL),
-
logfile_number_(0),
-
log_(NULL),
-
seed_(0),
-
// 文件IO的工具
-
tmp_batch_(new WriteBatch),
-
bg_compaction_scheduled_(false),
-
manual_compaction_(NULL) {
-
mem_->Ref();
-
has_imm_.Release_Store(NULL);
-
-
-
// Reserve ten files or so for other uses and give the rest to TableCache.
-
/*
-
最大文件数减去预留的辅助文件数,需要维护数据的文件数
-
在创建TableCache的时候,这个文件数对应的是TableCache里lrucache的数量
-
关于lrucache,参考文献之前的博客 http://blog.itpub.net/26239116/viewspace-1842049/
-
*/
-
const int table_cache_size = options_.max_open_files - kNumNonTableCacheFiles;
-
table_cache_ = new TableCache(dbname_, &options_, table_cache_size);
-
-
-
// 初始化VersionSet,用于存放数据库里所有version
-
versions_ = new VersionSet(dbname_, &options_, table_cache_,
-
&internal_comparator_);
-
}
构造函数里调的SanitizeOptions的具体内容。对option做了一下预处理
-
Options SanitizeOptions(const std::string& dbname,
-
const InternalKeyComparator* icmp,
-
const InternalFilterPolicy* ipolicy,
-
const Options& src) {
-
// 复制一份调用者提供的Options,做返回值用。
-
Options result = src;
-
result.comparator = icmp;
-
result.filter_policy = (src.filter_policy != NULL) ? ipolicy : NULL;
-
-
-
// 校验数值型参数,太大的设置为最大值,太小的设置为最小值
-
ClipToRange(&result.max_open_files, 64 + kNumNonTableCacheFiles, 50000);
-
ClipToRange(&result.write_buffer_size, 64<<10, 1<<30);
-
ClipToRange(&result.block_size, 1<<10, 4<<20);
-
-
-
// 如果没有指定日志,创建一个。
-
if (result.info_log == NULL) {
-
// Open a log file in the same directory as the db
-
src.env->CreateDir(dbname); // In case it does not exist
-
/*
-
日志文件的命名规则是 dbname + "/LOG",
-
创建之前需要先原有的重命名为 dbname + "/LOG.old"
-
*/
-
src.env->RenameFile(InfoLogFileName(dbname), OldInfoLogFileName(dbname));
-
-
-
/*
-
创建一个logger,对于linux平台,是创建一个PosixLogger
-
*/
-
Status s = src.env->NewLogger(InfoLogFileName(dbname), &result.info_log);
-
if (!s.ok()) {
-
// No place suitable for logging
-
result.info_log = NULL;
-
}
-
}
-
-
-
/*
-
创建一个lru cache
-
关于lru cache,参考我前面的博客 http://blog.itpub.net/26239116/viewspace-1842049/
-
*/
-
if (result.block_cache == NULL) {
-
result.block_cache = NewLRUCache(8 << 20);
-
}
-
return result;
-
}
数据库初始化的主要工作由DBImpl::Recover函数完成
-
Status DBImpl::Recover(VersionEdit* edit) {
-
mutex_.AssertHeld();
-
-
-
// Ignore error from CreateDir since the creation of the DB is
-
// committed only when the descriptor is created, and this directory
-
// may already exist from a previous failed creation attempt.
-
env_->CreateDir(dbname_);
-
assert(db_lock_ == NULL);
-
-
-
/*
-
创建文件锁,格式是"dbname_/LOC"
-
linux版的env是env_posix.cc
-
大致过程是
-
1 对文件信息进行一系列记录,如记录到PosixFileLock类里。
-
2 创建一个“锁”文件,写入flock结构体写进去。flock定义在fcntl.h里。
-
*/
-
Status s = env_->LockFile(LockFileName(dbname_), &db_lock_);
-
if (!s.ok()) {
-
return s;
-
}
-
-
/*
-
判断current文件是否存在,格式是“dbname_/CURRENT”
-
用来记录当前的manifest文件名,madifest文件里记录当前数据库的概要信息,类似oracle的控制文件
-
*/
-
if (!env_->FileExists(CurrentFileName(dbname_))) {
-
if (options_.create_if_missing) {
-
// 初始化一个新的VersionEdit,设置logfile信息,然后写入manifest文件。
-
s = NewDB();
-
if (!s.ok()) {
-
return s;
-
}
-
} else {
-
return Status::InvalidArgument(
-
dbname_, "does not exist (create_if_missing is false)");
-
}
-
} else {
-
if (options_.error_if_exists) {
-
return Status::InvalidArgument(
-
dbname_, "exists (error_if_exists is true)");
-
}
-
}
-
-
-
// 如果之前存在这个数据库,打开时需要做恢复工作,manifest文件里的信息应用的当前version。
-
s = versions_->Recover();
-
if (s.ok()) {
-
SequenceNumber max_sequence(0);
-
-
-
// Recover from all newer log files than the ones named in the
-
// descriptor (new log files may have been added by the previous
-
// incarnation without registering them in the descriptor).
-
//
-
// Note that PrevLogNumber() is no longer used, but we pay
-
// attention to it in case we are recovering a database
-
// produced by an older version of leveldb.
-
const uint64_t min_log = versions_->LogNumber();
-
const uint64_t prev_log = versions_->PrevLogNumber();
-
std::vector<std::string> filenames;
-
s = env_->GetChildren(dbname_, &filenames);
-
if (!s.ok()) {
-
return s;
-
}
-
std::set<uint64_t> expected;
-
-
-
// 从所有version里获得所有文件号
-
versions_->AddLiveFiles(&expected);
-
uint64_t number;
-
FileType type;
-
std::vector<uint64_t> logs;
-
-
-
/*
-
从文件夹内所有文件名中提取文件类型和文件号
-
从versions_提取的expected中移除这些文件号
-
同时记录其中有哪些log文件
-
*/
-
for (size_t i = 0; i < filenames.size(); i++) {
-
if (ParseFileName(filenames[i], &number, &type)) {
-
expected.erase(number);
-
if (type == kLogFile && ((number >= min_log) || (number == prev_log)))
-
logs.push_back(number);
-
}
-
}
-
-
-
// 如果expected的内容么有全部清空,说明丢失文件了。
-
if (!expected.empty()) {
-
char buf[50];
-
snprintf(buf, sizeof(buf), "%d missing files; e.g.",
-
static_cast<int>(expected.size()));
-
return Status::Corruption(buf, TableFileName(dbname_, *(expected.begin())));
-
}
-
-
-
// 按顺序逐个恢复log文件
-
// Recover in the order in which the logs were generated
-
std::sort(logs.begin(), logs.end());
-
for (size_t i = 0; i < logs.size(); i++) {
-
s = RecoverLogFile(logs[i], edit, &max_sequence);
-
-
-
// The previous incarnation may not have written any MANIFEST
-
// records after allocating this log number. So we manually
-
// update the file number allocation counter in VersionSet.
-
versions_->MarkFileNumberUsed(logs[i]);
-
}
-
-
-
if (s.ok()) {
-
if (versions_->LastSequence() < max_sequence) {
-
versions_->SetLastSequence(max_sequence);
-
}
-
}
-
}
-
-
-
return s;
-
}
由于DBImpl::Recover前面已经判断过CURRENT文件是否存在,如果不存在就创建新数据库了,
因此这里就是要处理新的或者曾经关闭过的数据库。
-
Status VersionSet::Recover() {
-
struct LogReporter : public log::Reader::Reporter {
-
Status* status;
-
virtual void Corruption(size_t bytes, const Status& s) {
-
if (this->status->ok()) *this->status = s;
-
}
-
};
-
-
-
// Read "CURRENT" file, which contains a pointer to the current manifest file
-
std::string current;
-
// 从CURRENT文件把当前的manifest文件名读到字符串里current里
-
Status s = ReadFileToString(env_, CurrentFileName(dbname_), ¤t);
-
if (!s.ok()) {
-
return s;
-
}
-
-
-
/*
-
CURRENT文件应该只有一行,就是当前manifest文件名。
-
要求CURRENT文件必须以换行符结尾
-
这样resize后就只剩文件名了。
-
*/
-
if (current.empty() || current[current.size()-1] != '\n') {
-
return Status::Corruption("CURRENT file does not end with newline");
-
}
-
current.resize(current.size() - 1);
-
-
// 打开manifest文件
-
std::string dscname = dbname_ + "/" + current;
-
SequentialFile* file;
-
s = env_->NewSequentialFile(dscname, &file);
-
if (!s.ok()) {
-
return s;
-
}
-
-
// 初始化logfile信息,构建一个新的Version作为current version
-
bool have_log_number = false;
-
bool have_prev_log_number = false;
-
bool have_next_file = false;
-
bool have_last_sequence = false;
-
uint64_t next_file = 0;
-
uint64_t last_sequence = 0;
-
uint64_t log_number = 0;
-
uint64_t prev_log_number = 0;
-
-
-
/*
-
此时的current_,也就是current version是之前在构造函数里初始化的
-
AppendVersion(new Version(this));
-
在AppendVersion中会把新初始化的Version作为current version
-
current_ = v;
-
因此到builder这一步,一切都值是初始化,还没有正式开始真正恢复操作
-
*/
-
Builder builder(this, current_);
-
-
-
{
-
LogReporter reporter;
-
reporter.status = &s;
-
log::Reader reader(file, &reporter, true/*checksum*/, 0/*initial_offset*/);
-
Slice record;
-
std::string scratch;
-
// 解析manifest的内容,还原出上次关闭的数据库的logfile等信息,装入VersionEdit
-
while (reader.ReadRecord(&record, &scratch) && s.ok()) {
-
/*
-
创建一个edit,要改变Version的状态,就需要用VersionEdit
-
version1 + edit1 = verion2
-
*/
-
VersionEdit edit;
-
-
-
/*
-
leveldb的存储是按一定格式的,需要decode还原
-
将manifest中读到的信息decode后放入edit,后面恢复会用到。
-
只是概要信息,比如新文件,删除了哪些文件等。
-
*/
-
s = edit.DecodeFrom(record);
-
if (s.ok()) {
-
if (edit.has_comparator_ &&
-
edit.comparator_ != icmp_.user_comparator()->Name()) {
-
s = Status::InvalidArgument(
-
edit.comparator_ + " does not match existing comparator ",
-
icmp_.user_comparator()->Name());
-
}
-
}
-
-
-
if (s.ok()) {
-
/*
-
将edit的内容封装到builder里。
-
*/
-
builder.Apply(&edit);
-
}
-
-
-
if (edit.has_log_number_) {
-
log_number = edit.log_number_;
-
have_log_number = true;
-
}
-
-
-
if (edit.has_prev_log_number_) {
-
prev_log_number = edit.prev_log_number_;
-
have_prev_log_number = true;
-
}
-
-
-
if (edit.has_next_file_number_) {
-
next_file = edit.next_file_number_;
-
have_next_file = true;
-
}
-
-
-
if (edit.has_last_sequence_) {
-
last_sequence = edit.last_sequence_;
-
have_last_sequence = true;
-
}
-
}
-
}
-
delete file;
-
file = NULL;
-
-
-
if (s.ok()) {
-
if (!have_next_file) {
-
s = Status::Corruption("no meta-nextfile entry in descriptor");
-
} else if (!have_log_number) {
-
s = Status::Corruption("no meta-lognumber entry in descriptor");
-
} else if (!have_last_sequence) {
-
s = Status::Corruption("no last-sequence-number entry in descriptor");
-
}
-
-
-
if (!have_prev_log_number) {
-
prev_log_number = 0;
-
}
-
-
-
MarkFileNumberUsed(prev_log_number);
-
MarkFileNumberUsed(log_number);
-
}
-
-
-
if (s.ok()) {
-
// 利用builder的信息封装一个新的version,追加到VersionSet里
-
Version* v = new Version(this);
-
-
-
/*
-
builder前面从edit里读了manifest文件,
-
SaveTo会将从manifest文件里读到的文件添加到Version.files_里
-
在打开数据库操作的后面步骤里,会读取files_里的文件信息,与目录下的实体文件进行对照,看文件全不全。
-
这个过程就是version + edit,只不过这个version是新建的空version。
-
最终得到的是上次关闭的数据库version
-
*/
-
builder.SaveTo(v);
-
// Install recovered version
-
// 根据各level的文件大小计算一个“得分”,以后影响压缩行为
-
Finalize(v);
-
// 将新封装好的Version放到VersionSet里,作为current version
-
AppendVersion(v);
-
manifest_file_number_ = next_file;
-
next_file_number_ = next_file + 1;
-
last_sequence_ = last_sequence;
-
log_number_ = log_number;
-
prev_log_number_ = prev_log_number;
-
}
-
-
-
return s;
-
}
逐个恢复logfile
-
Status DBImpl::RecoverLogFile(uint64_t log_number,
-
VersionEdit* edit,
-
SequenceNumber* max_sequence) {
-
struct LogReporter : public log::Reader::Reporter {
-
Env* env;
-
Logger* info_log;
-
const char* fname;
-
Status* status; // NULL if options_.paranoid_checks==false
-
virtual void Corruption(size_t bytes, const Status& s) {
-
Log(info_log, "%s%s: dropping %d bytes; %s",
-
(this->status == NULL ? "(ignoring error) " : ""),
-
fname, static_cast<int>(bytes), s.ToString().c_str());
-
if (this->status != NULL && this->status->ok()) *this->status = s;
-
}
-
};
-
-
-
mutex_.AssertHeld();
-
-
-
// Open the log file
-
std::string fname = LogFileName(dbname_, log_number);
-
SequentialFile* file;
-
// 只读打开logfile
-
Status status = env_->NewSequentialFile(fname, &file);
-
if (!status.ok()) {
-
MaybeIgnoreError(&status);
-
return status;
-
}
-
-
-
// Create the log reader.
-
LogReporter reporter;
-
reporter.env = env_;
-
reporter.info_log = options_.info_log;
-
reporter.fname = fname.c_str();
-
reporter.status = (options_.paranoid_checks ? &status : NULL);
-
// We intentionally make log::Reader do checksumming even if
-
// paranoid_checks==false so that corruptions cause entire commits
-
// to be skipped instead of propagating bad information (like overly
-
// large sequence numbers).
-
log::Reader reader(file, &reporter, true/*checksum*/,
-
0/*initial_offset*/);
-
Log(options_.info_log, "Recovering log #%llu",
-
(unsigned long long) log_number);
-
-
-
// Read all the records and add to a memtable
-
std::string scratch;
-
Slice record;
-
WriteBatch batch;
-
MemTable* mem = NULL;
-
/*
-
逐行读取logfile
-
将得到的数据放入memtable mm里
-
*/
-
while (reader.ReadRecord(&record, &scratch) &&
-
status.ok()) {
-
if (record.size() < 12) {
-
reporter.Corruption(
-
record.size(), Status::Corruption("log record too small"));
-
continue;
-
}
-
WriteBatchInternal::SetContents(&batch, record);
-
-
-
if (mem == NULL) {
-
mem = new MemTable(internal_comparator_);
-
mem->Ref();
-
}
-
status = WriteBatchInternal::InsertInto(&batch, mem);
-
MaybeIgnoreError(&status);
-
if (!status.ok()) {
-
break;
-
}
-
const SequenceNumber last_seq =
-
WriteBatchInternal::Sequence(&batch) +
-
WriteBatchInternal::Count(&batch) - 1;
-
if (last_seq > *max_sequence) {
-
*max_sequence = last_seq;
-
}
-
-
// 当memtable使用量超过设置的值时,将数据刷到level 0 数据文件里。
-
// 这样在恢复过程中不会将内存撑爆
-
if (mem->ApproximateMemoryUsage() > options_.write_buffer_size) {
-
status = WriteLevel0Table(mem, edit, NULL);
-
if (!status.ok()) {
-
// Reflect errors immediately so that conditions like full
-
// file-systems cause the DB::Open() to fail.
-
break;
-
}
-
mem->Unref();
-
mem = NULL;
-
}
-
}
-
-
-
if (status.ok() && mem != NULL) {
-
status = WriteLevel0Table(mem, edit, NULL);
-
// Reflect errors immediately so that conditions like full
-
// file-systems cause the DB::Open() to fail.
-
}
-
-
-
if (mem != NULL) mem->Unref();
-
delete file;
-
return status;
-
}
来自 “ ITPUB博客 ” ,链接:https://blog.itpub.net/26239116/viewspace-1846192/
,如需转载,请注明出处,否则将追究法律责任。