以RocksDB为存储引擎的MyRocks是近几年流行起来的MySQL分支，在Facebook等公司广泛使用，网易杭研的数据库内核团队从2018年初开始系统研究MyRocks，目前已在内部进行小范围推广使用，效果比较理想。

在调研、测试和试用期间，积累了一些经验，包括技术实现等。本系列想跟大家分享我们组内小伙伴做的LevelDB调研输出，这是第五篇，也是最后一篇，详细介绍LevelDB MVCC机制、备份和恢复等场景。

第四篇链接：

温正湖：LevelDB设计与实现 - Compactionzhuanlan.zhihu.com

MVCC

Version相关的数据结构有3个，Version VersionEdit and VersionSet。其中VersionEdit顾名思义，是编辑或修改Version，它记录的是两个Version之间的差异。

sequence number 是一个由VersionSet直接持有的全局的编号，每次写入（注意批量写入时sequence number是相同的），就会递增。根据我们之前对写入操作的分析，当插入一条key的时候，实际参与排序的key和sequence number以及type组成的 InternalKey。

当我们进行Get操作时，我们只需要找到目标key，同时其sequence number 小于等于sequence number：

普通的读取，sepcific sequence number =last sequence number
snapshot读取，sepcific sequenc number =snapshot sequence number

snapshot 其实就是一个sequence number，获取snapshot，即获取当前的last sequence number。

sstable级别的MVCC就是利用Version实现的。

只有一个current version，持有最新的sstable集合。
VersionEdit 代表一次更新，新增了哪些sstable file，以及删除了哪些sstable file
Version保存了各个level下每个sstable的FileMetaData

Version的结构如下图所示：

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

next、prev分别指向前后版本，DB中所有的Version构成了一个环，此环中只有一个当前版本如图13所示。file_保存了每层sstable的元数据FileMetaData,Version类还记录了下一次参与Compaction的文件。

MANIFEST是跟版本变更有关的磁盘文件，MANIFEST文件的内容就是VersionEdit序列化后的内容，可用来恢复。MANIFEST中record存储的方式跟log存储方式一样。VersionEdit类的主要成员如下：

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

这些数据成员都会序列化后写入MANIFEST文件。这些字段不一定必然存在。

LevelDB在写入每个字段之前，都会先写入一个varint型数字来标记后面的字段类型。在读取时，先读取此字段，根据类型解析后面的信息。一共有9种类型：

// Tag numbers for serialized VersionEdit.  
enum Tag {
  kComparator           = 1,
  kLogNumber            = 2,
  kNextFileNumber       = 3,
  kLastSequence         = 4,
  kCompactPointer       = 5,
  kDeletedFile          = 6,
  kNewFile              = 7,
  // 8 was used for large value refs
  kPrevLogNumber        = 9
};

MANIFEST的内容如下图所示：

一次版本的变更信息保存在VersionEdit中，VersionEdit中的信息经过Encode后形成Record，一个Record有可能很大，MANIFEST存储Record的方式与WAL日志中存储Record方式一样，也分为：KFullType、KFirstType、KMiddleType、KLastType。随着系统不断的运行，发生版本变化的次数会越来越多，MANIFEST文件数也会变多，需要一个类似指针的东西指向当前使用的MANIFEST，CURRENT文件就充当这个指针的作用，它存储了当前使用的MANIFEST的文件名。

Recovery and Repair

每次启动数据库都会调用一个Recover函数，其功能是当数据库在运行中因为某些原因突然down掉后，恢复DB到宕机前的状态，以及memtable甚至immutabl memtable中还未持久化到sstable中的数据。我们知道LevelDB采用的是WAL的方式存储日志，那么对于LevelDB中的版本变化信息存储在MANIFEST文件中，通过读取MANIFEST中记录的内容，然后在结合WAL中的信息就可以恢复到最新状态；而memtable和immutable memtable中的数据恢复主要就是将未持久化到sstable的数据从log中读取出来重做到memtable，在这个过程中也可能发生compaction操作，把immutable memtable持久化成sstable文件。

Recover的恢复是轻量级的恢复，如果MANIFEST文件损坏或者sstable损坏就需要Repair了，这个是当LevelDB不能正常启动的时候需要手动进行的。整个Repair流程如图16所示。

备份

LevelDB在调研的过程中没有发现原生支持物理备份，RocksDB是加入了物理备份的，RocksDB备份的过程如下：

Disable file deletions
Get live files(包括：表文件、CURRENT文件、MANIFEST文件)
Copy live files to the backup directory.如果在备份目录已经存在了表文件，就不copy了，因为表文件是不可修改的而且文件名也是唯一的，CURRENT文件、MANIFEST文件还是需要都复制的。
如果flush_before_backup设置了false,还要copy日志文件，GetSortedWalFiles()函数copy日志文件到备份目录。
Re-enable file deletions。

RocksDB备份的实现在BackupEngine接口类和BackupEngineImpl实现类中，具体使用方法见以下链接：

https://github.com/facebook/rocksdb/wiki/How-to-backup-RocksDB%3F。

MyRocks提供了一个热备的工具“myrocks_hotbackup”，原理和使用方法见以下链接：

https://github.com/facebook/mysql-5.6/wiki/Physical-backup-with-myrocks_hotbackup。

本系列结束。

参考资料：

1、RocksDB官方wiki；

2、网上公开的第三发资料，包括知乎及其他博客平台；

3、LevelDB、RocksDB源码；

ITPub博客

LevelDB设计与实现 - MVCC等

最新文章