LevelDB 启动

之前就听LevelDB是所有搞存储的人都会读的一个代码库。最近正好忙完了搞完了毕设的代码，稍微闲了一些，于是也打算看看LevelDB的源码。

这是LevelDB源码阅读笔记第一章，有关LevelDB的启动流程。本文并不是step by step的源码阅读教程，而是仅仅作为我的学习笔记，简单记录我的问题与思考。

带注释的代码库之后应该也会放在github上供大家学习参考。

预备知识

数据库文件

编码和命名等等等设计的相关的细节暂时不论（我也没看到那部分），先专注与文件的意义与作用

1
2
3
4
5
6
7
8


├── 000005.ldb
├── 000008.ldb  // sst or ldb 都是 sst文件
├── 000009.log  // WAL
├── CURRENT  // 记录了使用的manifest文件的名字也用于表示数据库存在
├── LOCK  // 空文件，用于保证只有一个db实例操作数据库
├── LOG  // level打印的日志
├── LOG.old 
└── MANIFEST-000007   // descriptor_file, 元数据文件

值得深究的问题，之后也许会写相关博客，暂时先抛出：

LOCK怎么保证只有一个DB实例持有数据库

其实本质上是利用fcntl系统调用，在LOCK文件上设置写锁

各种文件的编码问题

之后会有相关博客说说leveldb的编码设计

DB State

Leveldb是一种嵌入式数据库，一般作为一些应用的组件存在（比如用于分布式存储系统中元数据节点的数据落盘）。这些应用可能会crush或者优雅退出，此时会有遗留的leveldb数据文件存在，所以我们一般需要在启动时恢复原先数据库的状态。故而我们需要明确一个db实例的状态信息，以便在使用时确保这些数据crush save，在启动时能及时回复数据状态机。

那么第一个问题是DB state应该包括什么？leveldb是一个LSM存储引擎，本质上是LSM Tree 数据结构 + 各种读写和存储优化，基于此，结合leveldb的文档，DB state包含的需要持久化信息至少有：

每层Level对应相关的sst文件，每个sst文件对应的key range

key range 主要是为了避免不必要的IO
全局逻辑时钟，last_seq_number

数据更新都有个seq_num 标记更新操作的新旧, 并与排序相关
compaction相关的参数 (file_to_compact, score, point)

compact 相关, 以便在crush之后出发compaction
cmp name

db初始化后，数据的排序逻辑就确定了，不允许被更改，用此名字作为凭证
log_number, next_file_number

wal的编号和下一个可用的file编号
deleted_files 和 add_files

compaction 或者 ref == 0 等原因导致的需要删除和添加的sst文件

具体实现上，每次leveldb的元数据变更行为（一般由Compact导致）都会被记录在VersionEdit这个数据结构之中，所以leveldb的DB State实际上是初始状态 + list of Applied VersionEdit。

版本控制

既然说到了VersionEdit, 那就顺带说一说启动流程里有关LevelDB的版本控制相关的设计，主要涉及Version, VersionEdit,VersionSet三种数据结构。

为什么需要版本控制？简单来说就是leveldb使用了MVCC机制来避免使用大锁来提高性能。

命令记录级别的快照读是通过sequence_number来实现的，所有操作都会附带当前的sequence_number，以此判断当前操作允许读取的数据，大于命令seq_number的记录对于操作将不可见。

sst文件级别的MVCC是通过Version链实现的，主要为了避免以下场景的冲突：正在读取某个文件时，而后台major compaction试图删除此文件。

相关数据结构

与启动流程相关的主要是sst级别的MVCC，主要有Version，VersionEdit，VersionSet三个数据结构。

Version

每次启动时或者Compact之后最新的数据状态。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class 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 and meta per level
      std::vector<FileMetaData*> files_[config::kNumLevels];

      // Next file to compact based on seek stats. （allowed_seek耗尽导致的compact）
      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_;  // score表示数据不均衡的程度，score越大表示该level数据越不均衡，需要有限compact
      int compaction_level_;
}

VersionSet

管理整个db的当前运行时状态。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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_;
    uint64_t prev_log_number_;  // 0 or backing store for memtable being compacted

    // Opened lazily
    WritableFile* descriptor_file_; // descriptor_ is for manifest file
    log::Writer* descriptor_log_; // descriptor_ is for manifest file
    Version dummy_versions_;  // Head of circular doubly-linked list of versions. 正在使用的version的链表
    Version* current_;        // == dummy_versions_.prev_

    // Per-level key at which the next compaction at that level should start.
    // Either an empty string, or a valid InternalKey.
    std::string compact_pointer_[config::kNumLevels];
}

VersionEdit

元数据变更行为的数据与操作的封装。这样的封装可以缩小Version切换的时间窗口。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class VersionEdit {
  /** other code */
    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_;
};

Manifest Content

上文我们说到Manifest是leveldb的元数据文件，保存了数据库需要持久化的状态。leveldb在启动流程中，可能需要通过已有的数据文件回复原有db的状态。除此之外，但出现版本变更时，leveldb会生成VersionEdit, VersionEdit记录的元数据变动也需要及时持久化到manifest中，以此保证leveldb MVCC多版本状态的Crush Safe。所以Manifest的中编码布局十分重要。

在Manifest内部，元数据状态机编码成SnapshotSessionRecord +list of SessionRecords，本质上是初始状态 + list of Applied VersionEdit 。