LevelDB原理探究和代码分析(下)

前端之家收集整理的这篇文章主要介绍了LevelDB原理探究和代码分析(下)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

3.文件结构


3.1 文件组成


Level DB包含一下几种文件

文件类型 说明
dbname/MANIFEST-[0-9]+ 清单文件
dbname/[0-9]+.log db日志文件
dbname/[0-9]+.sst dbtable文件
dbname/[0-9]+.dbtmp db临时文件
dbname/CURRENT 记录当前使用的清单文件
dbname/LOCK DB锁文件
dbname/LOG info log日志文件
dbname/LOG.old 旧的info log日志文件

上面的log文件,sst文件,临时文件,清单文件末尾都带着序列号,序号是单调递增的(随着next_file_number从1开始递增),以保证不会和之前的文件名重复。另外,注意区分db log与info log:前者是为了防止保障数据安全而实现的二进制Log,后者是打印引擎中间运行状态及警告等信息的文本log。
随着更新与Compaction的进行,LevelDB会不断生成文件,有时还会删除文件,所以需要一个文件来记录文件列表,这个列表就是清单文件的作用,清单会不断变化,DB需要知道最新的清单文件,必须将清单准备好后原子切换,这就是CURRENT文件的作用,Level DB的清单过程更新如下:
1. 递增清单序号,生成一个新的清单文件
2. 将此清单文件名称写入到一个临时文件中。
3. 将临时文件rename为CURRENT。
  1. Status SetCurrentFile(Env* env,const std::string& dbname,uint64_t descriptor_number) {
  2. // 创建一个新的清单文件
  3. std::string manifest = DescriptorFileName(dbname,descriptor_number);
  4. Slice contents = manifest;
  5. // 移除"dbname/"前缀
  6. assert(contents.starts_with(dbname + "/"));
  7. contents.remove_prefix(dbname.size() + 1);
  8. // 创建一个临时文件
  9. std::string tmp = TempFileName(dbname,descriptor_number);
  10. // 写入清单文件
  11. Status s = WriteStringToFile(env,contents.ToString() + "\n",tmp);
  12. if (s.ok()) {
  13. // 将临时文件改名为CURRENT
  14. s = env->RenameFile(tmp,CurrentFileName(dbname));
  15. }
  16. if (!s.ok()) {
  17. env->DeleteFile(tmp);
  18. }
  19. return s;
  20. }

3.2 Manifest

在介绍其他文件格式前,先了解清单文件,MANIFEST文件是Level DB的元信息文件,它主要包括下面一些信息:
1. Comparator的名称
2. 其的格式如下:


我们可以看看其序列化的代码
  1. void VersionEdit::EncodeTo(std::string* dst) const {
  2. if (has_comparator_) { // 记录Comparator名称
  3. PutVarint32(dst,kComdparator);
  4. PutLengthPrefixedSlice(dst,comparator_);
  5. }
  6. if (has_log_number_) { // 记录Log Numer
  7. PutVarint32(dst,kLogNumber);
  8. PutVarint64(dst,log_number_);
  9. }
  10. if (has_prev_log_number_) { // 记录Prev Log Number,现在已废弃,一般为0
  11. PutVarint32(dst,kPrevLogNumber);
  12. PutVarint64(dst,prev_log_number_);
  13. }
  14. if (has_next_file_number_) { // 记录下一个文件序号
  15. PutVarint32(dst,kNextFileNumber);
  16. PutVarint64(dst,next_file_number_);
  17. }
  18. if (has_last_sequence_) { // 记录最大的sequence num
  19. PutVarint32(dst,kLastSequence);
  20. PutVarint64(dst,last_sequence_);
  21. }
  22. // 记录每一级Level下次compaction的起始Key
  23. for (size_t i = 0; i < compact_pointers_.size(); i++) {
  24. PutVarint32(dst,kCompactPointer);
  25. PutVarint32(dst,compact_pointers_[i].first); // level
  26. PutLengthPrefixedSlice(dst,compact_pointers_[i].second.Encode());
  27. }
  28. // 记录每一级需要删除文件
  29. for (DeletedFileSet::const_iterator iter = deleted_files_.begin();
  30. iter != deleted_files_.end();
  31. ++iter) {
  32. PutVarint32(dst,kDeletedFile);
  33. PutVarint32(dst,iter->first); // level
  34. PutVarint64(dst,iter->second); // file number
  35. }
  36. // 记录每一级需要有效的sst以及其smallest与largest的key
  37. for (size_t i = 0; i < new_files_.size(); i++) {
  38. const FileMetaData& f = new_files_[i].second;
  39. PutVarint32(dst,kNewFile);
  40. PutVarint32(dst,new_files_[i].first); // level
  41. PutVarint64(dst,f.number);
  42. PutVarint64(dst,f.file_size);
  43. PutLengthPrefixedSlice(dst,f.smallest.Encode());
  44. PutLengthPrefixedSlice(dst,f.largest.Encode());
  45. }
  46. }

3.3 Sortedtable


Level DB间歇性地将内存中的SkipList对应的数据集合Dump到磁盘上,生成一个sst的文件,这个文件的格式如下:


按照SSTable的结构,可以正向遍历,也可以逆向遍历,但是逆向遍历的代价要远远高于正向遍历的代价,因为每条record都是变长的,且其没有记录前一条记录的偏移,因此逆向Group遍历时,只能先回到group(代码中称为一个restart,为了便于理解,下面都称为group)开头(一个Data Block的group一般为16条记录,每个Data Block的尾部有group起始位置偏移索引),然后从头开始正向遍历,直至找到其前一条记录,如果当前位置为group的第一条记录,则需要回到上一个group的开头,遍历到其最后一条记录。另外,内存中跳表反向的遍历效率也远远不如正向遍历。

3.4 Sparse Index

一个sst文件内部除了Data Block,还有Index Block,Index Block的结构与Data Block一样,只不过每个group只包含一条记录,即Data Block的最大Key与偏移。其实这里说最大Key并不是很准确,理论上,只要保存最大Key就可以实现二分查找,但是Level DB在这里做了个优化,它并保存最大key,而是保存一个能分隔两个Data Block的最短Key,如:假定Data Block1的最后一个Key为“abcdefg”,Data Block2的第一个Key为“abzxcv”,则index可以记录Data Block1的索引key为“abd”;这样的分割串可以有很多,只要保证Data Block1中的所有Key都小于等于此索引,Data Block2中的所有Key都大于此索引即可。这种优化缩减了索引长度,查询时可以有效减小比较次数。我们可以看看默认comparator如何实现这种分割的:
  1. void BytewiseComparatorImpl::FindShortestSeparator(
  2. std::string* start,const Slice& limit) const {
  3. // 先比较获得最大公共前缀
  4. size_t min_length = std::min(start->size(),limit.size());
  5. size_t diff_index = 0;
  6. while ((diff_index < min_length) &&
  7. ((*start)[diff_index] == limit[diff_index])) {
  8. diff_index++;
  9. }
  10. if (diff_index >= min_length) {
  11. // 如果start就是limit的前缀,则只能使用start本身作为分割
  12. } else {
  13. uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
  14. // 将第一个不同字符+1,并确保其不会溢出,同时比limit小
  15. if (diff_byte < static_cast<uint8_t>(0xff) &&
  16. diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
  17. (*start)[diff_index]++;
  18. start->resize(diff_index + 1);
  19. assert(Compare(*start,limit) < 0);
  20. }
  21. }
  22. }

从上面可以看出,FindShortestSeparator方法并不严格,有些时候没有找出最短分割的key(比如第一个不等的字符已经为0xFF时),它只是一种优化,我们自定义Comparator时,既可以实现,也可以不实现,如果不实现,将始终使用Data Block的最大Key作为索引,并不影响功能正确性。


4. Operations


在介绍了数据结构后,我们看看LevelDB一些基本操作的实现:

4.1 创建一个新表


创建一个新的表大概分为几步,包括建立各类文件以及内存中的数据结构,线程同步对象等,关键代码如下:

  1. // DBImpl在构造时会初始化互斥体与信号量,创建一个空的memtable,并根据配置设置Comparator及LRU缓冲
  2. DBImpl::DBImpl(const Options& options,const std::string& dbname)
  3. : env_(options.env),internal_comparator_(options.comparator),// 初始化Comparator
  4. options_(SanitizeOptions(dbname,&internal_comparator_,options)),// 检查参数是否合法
  5. owns_info_log_(options_.info_log != options.info_log),// 是拥有自己info log,还是使用用户提供的
  6. owns_cache_(options_.block_cache != options.block_cache),// 是否拥有自己的LRU缓冲,或者使用用户提供的
  7. dbname_(dbname),// 数据表名称
  8. db_lock_(NULL),// 不创建也不锁定文件
  9. shutting_down_(NULL),bg_cv_(&mutex_),// 用于与后台线程交互的条件信号
  10. mem_(new MemTable(internal_comparator_)),// 创建一个新的跳表
  11. imm_(NULL),// 用于双缓冲的缓冲跳表开始时为NULL
  12. logfile_(NULL),// log文件
  13. logfile_number_(0),// log文件的序号
  14. log_(NULL),// log writer
  15. logger_(NULL),// 用于在多线程环境中记录Owner logger的一个指针
  16. logger_cv_(&mutex_),// 用于与Logger交互的条件信号
  17. bg_compaction_scheduled_(false),// 没打开表时不起动后台的compaction线程
  18. manual_compaction_(NULL) {
  19. // 增加memtable的引用计数
  20. mem_->Ref();
  21. has_imm_.Release_Store(NULL);
  22.  
  23. // 根据Option创建一个LRU的缓冲对象,如果options中指定了Cache空间,则使用用户
  24. // 提供的Cache空间,否则会在内部确实创建8MB的Cache,另外,LRU的Entry数目不能超过max_open_files-10
  25. const int table_cache_size = options.max_open_files - 10;
  26. table_cache_ = new TableCache(dbname_,&options_,table_cache_size);
  27.  
  28. // 创建一个Version管理器
  29. versions_ = new VersionSet(dbname_,table_cache_,&internal_comparator_);
  30. }
  31.  
  32. Options SanitizeOptions(const std::string& dbname,const InternalKeyComparator* icmp,const Options& src) {
  33. Options result = src;
  34. result.comparator = icmp;
  35. ClipToRange(&result.max_open_files,20,50000);
  36. ClipToRange(&result.write_buffer_size,64<<10,1<<30);
  37. ClipToRange(&result.block_size,1<<10,4<<20);
  38. // 如果用户未指定info log文件(用于打印状态等文本信息的日志文件),则由引擎自己创建一个info log文件
  39. if (result.info_log == NULL) {
  40. // Open a log file in the same directory as the db
  41. src.env->CreateDir(dbname); // 如果目录不存在则创建
  42. // 如果已存在以前的info log文件,则将其改名为LOG.old,然后创建新的log文件与日志的writer
  43. src.env->RenameFile(InfoLogFileName(dbname),OldInfoLogFileName(dbname));
  44. Status s = src.env->NewLogger(InfoLogFileName(dbname),&result.info_log);
  45. if (!s.ok()) {
  46. result.info_log = NULL;
  47. }
  48. }
  49. // 如果用户没指定LRU缓冲,则创建8MB的LRU缓冲
  50. if (result.block_cache == NULL) {
  51. result.block_cache = NewLRUCache(8 << 20);
  52. }
  53. return result;
  54. }
  55.  
  56. Status DBImpl::NewDB() {
  57. // 创建version管理器
  58. VersionEdit new_db;
  59. // 设置Comparator
  60. new_db.SetComparatorName(user_comparator()->Name());
  61. new_db.SetLogNumber(0);
  62. // 下一个序号从2开始,1留给清单文件
  63. new_db.SetNextFile(2);
  64. new_db.SetLastSequence(0);
  65. // 创建一个清单文件,MANIFEST-1
  66. const std::string manifest = DescriptorFileName(dbname_,1);
  67. WritableFile* file;
  68. Status s = env_->NewWritableFile(manifest,&file);
  69. if (!s.ok()) {
  70. return s;
  71. }
  72. {
  73. // 写入清单文件
  74. log::Writer log(file);
  75. std::string record;
  76. new_db.EncodeTo(&record);
  77. s = log.AddRecord(record);
  78. if (s.ok()) {
  79. s = file->Close();
  80. }
  81. }
  82. delete file;
  83. if (s.ok()) {
  84. // 设置CURRENT文件,使其指向清单文件
  85. s = SetCurrentFile(env_,dbname_,1);
  86. } else {
  87. env_->DeleteFile(manifest);
  88. }
  89. return s;
  1. }

4.2 打开一个已存在的表


上面的步骤中,其实还遗漏了一个的重要流程,那就是DB的Open方法。LevelDB无论是创建表,还是打开现有的表,都是使用Open方法代码如下:

  1. Status DB::Open(const Options& options,DB** dbptr) {
  2. *dbptr = NULL;
  3.  
  4. DBImpl* impl = new DBImpl(options,dbname);
  5. impl->mutex_.Lock();
  6. VersionEdit edit;
  7. // 如果存在表数据,则Load表数据,并对日志进行恢复,否则,创建新表
  8. Status s = impl->Recover(&edit);
  9. if (s.ok()) {
  10. // 从VersionEdit获取一个新的文件序号,所以如果是新建数据表,则第一个LOG的序号为2(1已经被MANIFEST占用)
  11. uint64_t new_log_number = impl->versions_->NewFileNumber();
  12. // 记录日志文件号,创建新的log文件及Writer对象
  13. WritableFile* lfile;
  14. s = options.env->NewWritableFile(LogFileName(dbname,new_log_number),&lfile);
  15. if (s.ok()) {
  16. edit.SetLogNumber(new_log_number);
  17. impl->logfile_ = lfile;
  18. impl->logfile_number_ = new_log_number;
  19. impl->log_ = new log::Writer(lfile);
  20. // 如果存在原来的log,则回放log
  21. s = impl->versions_->LogAndApply(&edit,&impl->mutex_);
  22. }
  23. if (s.ok()) {
  24. // 删除废弃的文件(如果存在)
  25. impl->DeleteObsoleteFiles();
  26. // 检查是否需要Compaction,如果需要,则让后台启动Compaction线程
  27. impl->MaybeScheduleCompaction();
  28. }
  29. }
  30. impl->mutex_.Unlock();
  31. if (s.ok()) {
  32. *dbptr = impl;
  33. } else {
  34. delete impl;
  35. }
  36. return s;
  37. }

从上面可以看出,其实到底是新建表还是打开表都是取决与DBImpl::Recover()这个方法的行为,它的流程如下:
  1. Status DBImpl::Recover(VersionEdit* edit) {
  2. mutex_.AssertHeld();
  3.  
  4. // 创建DB目录,不关注错误
  5. env_->CreateDir(dbname_);
  6. // 在DB目录下打开或创建(如果不存在)LOCK文件并锁定它,防止其他进程打开此表
  7. Status s = env_->LockFile(LockFileName(dbname_),&db_lock_);
  8. if (!s.ok()) {
  9. return s;
  10. }
  11. if (!env_->FileExists(CurrentFileName(dbname_))) {
  12. // 如果DB目录下不存在CURRENT文件且允许在表不存在时创建表,则新建一个表返回
  13. if (options_.create_if_missing) {
  14. s = NewDB();
  15. if (!s.ok()) {
  16. return s;
  17. }
  18. } else {
  19. return Status::InvalidArgument(
  20. dbname_,"does not exist (create_if_missing is false)");
  21. }
  22. } else {
  23. if (options_.error_if_exists) {
  24. return Status::InvalidArgument(
  25. dbname_,"exists (error_if_exists is true)");
  26. }
  27. }
  28. // 如果运行到此,表明表已经存在,需要load,第一步是从MANIFEST文件中恢复VersionSet
  29. s = versions_->Recover();
  30. if (s.ok()) {
  31. SequenceNumber max_sequence(0);
  32. // 获取MANIFEST中获取最后一次持久化清单时在使用LOG文件序号,注意:这个LOG当时正在使用,
  33. // 表明数据还在memtable中,没有形成sst文件,所以数据恢复需要从这个LOG文件开始(包含这个LOG)。
  34. // 另外,prev_log是早前版本level_db使用的机制,现在以及不再使用,这里只是为了兼容
  35. const uint64_t min_log = versions_->LogNumber();
  36. const uint64_t prev_log = versions_->PrevLogNumber();
  37. // 扫描DB目录,记录下所有比MANIFEST中记录的LOG更加新的LOG文件
  38. std::vector<std::string> filenames;
  39. s = env_->GetChildren(dbname_,&filenames);
  40. if (!s.ok()) {
  41. return s;
  42. }
  43. uint64_t number;
  44. FileType type;
  45. std::vector<uint64_t> logs;
  46. for (size_t i = 0; i < filenames.size(); i++) {
  47. if (ParseFileName(filenames[i],&number,&type)
  48. && type == kLogFile
  49. && ((number >= min_log) || (number == prev_log))) {
  50. logs.push_back(number);
  51. }
  52. }
  53. // 将LOG文件安装从小到大排序
  54. std::sort(logs.begin(),logs.end());
  55. // 逐个LOG文件回放 for (size_t i = 0; i < logs.size(); i++) {
  56. // 回放LOG时,记录被插入到memtable,如果超过write buffer,则还会dump出level 0的sst文件
  57. // 此方法会将日志种每条记录的sequence num与max_sequence进行比较,以记录下最大的sequence num。
  58. s = RecoverLogFile(logs[i],edit,&max_sequence);
  59. // 更新最大的文件序号,因为MANIFEST文件中没有记录这些LOG文件占用的序号;
  60. // 当然,也可能LOG的序号小于MANIFEST中记录的最大文件序号,这时不需要更新。
  61. versions_->MarkFileNumberUsed(logs[i]);
  62. }
  63. if (s.ok()) {
  64. // 比较日志回放前后的最大sequence num,如果回放记录中有超过LastSequence()的记录,则替换
  65. if (versions_->LastSequence() < max_sequence) {
  66. versions_->SetLastSequence(max_sequence);
  67. }
  68. }
  69. }
  70. return s;
  71. }

4.3 关闭一个已打开的表

Level DB设计成只要删除DB对象就可以关闭表,其关键流程如下:
  1. DBImpl::~DBImpl() {
  2. // 通知后台线程,DB即将关闭
  3. mutex_.Lock();
  4. // 后台线程会间歇性地检查shutting_down_对象的指针,一旦不为NULL就会退出
  5. shutting_down_.Release_Store(this);
  6. // 注意:这里必须循环通知,直至compaction线程获得信号并设置了bg_compaction_scheduled_为false
  7. while (bg_compaction_scheduled_) {
  8. bg_cv_.Wait();
  9. }
  10. mutex_.Unlock();
  11.  
  12. // 如果锁定了文件锁,则释放文件
  13. if (db_lock_ != NULL) {
  14. env_->UnlockFile(db_lock_);
  15. }
  16.  
  17. delete versions_;
  18. // 减去memtable的引用计数
  19. if (mem_ != NULL) mem_->Unref();
  20. if (imm_ != NULL) imm_->Unref();
  21. // 销毁db log相关对象以及表缓冲对象
  22. delete log_;
  23. delete logfile_;
  24. delete table_cache_;
  25.  
  26. // 如果info log与cache是引擎自己构建,则需要销毁它们
  27. if (owns_info_log_) {
  28. delete options_.info_log;
  29. }
  30. if (owns_cache_) {
  31. delete options_.block_cache;
  32. }
  33. }

由上可见,delete一个db对象可能会阻塞调用线程一段时间,必须让其完成一些必须完成的工作,才能进一步保障数据的安全。

4.4 随机查询

Level DB可能dump多个sst文件,这些文件的key范围可能重叠。按照Level DB的设计,其会将sst分为7个等级,可以视为代龄,其中,只有Level 0中的sst可能存在key的区间重叠的情况,而level1 - level6中,同一level中的sst可以保证不重叠,但不同level之间的sst依然可能key重叠。因此,如果查询一个key,其最多可能在6+n个sst中同时存在,n为level0中sst的个数;同时,由于这些文件生成有先后关系,查询时还需要注意顺序,Get一个key的流程如下:

猜你在找的NoSQL相关文章