LevelDB

LevelDB

LevelDB ，LevelDB 是对 Bigtable 论文中描述的键值存储系统的单机版的实现，它提供了一个极其高速的键值存储系统，并且由 Bigtable 的作者 Jeff Dean 和 Sanjay Ghemawat 共同完成，可以说高度复刻了 Bigtable 论文中对于其实现的描述。

概述

LevelDB 作为一个键值存储的『仓库』，它提供了一组非常简单的增删改查接口：

class DB {
 public:
  virtual Status Put(const WriteOptions& options, const Slice& key, const Slice& value) = 0;
  virtual Status Delete(const WriteOptions& options, const Slice& key) = 0;
  virtual Status Write(const WriteOptions& options, WriteBatch* updates) = 0;
  virtual Status Get(const ReadOptions& options, const Slice& key, std::string* value) = 0;
}

C++

Put 方法在内部最终会调用 Write 方法，只是在上层为调用者提供了两个不同的选择。

Get 和 Put 是 LevelDB 为上层提供的用于读写的接口。

LevelDB是一个写性能十分优秀的存储引擎，LSM树(Log Structured-Merge Tree)实现。LSM树的核心思想就是放弃部分读的性能，换取最大的写入能力。写性能高的原理，参考BigTable，尽量减少随机写的次数。对于每次写入操作，并不是直接将最新的数据驻留在磁盘中，而是将其拆分成（1）一次日志文件的顺序写（2）一次内存中的数据插入。

架构


• MemTable

  MemTable就是一个在内存中进行数据组织与维护的结构，通过跳表实现。MemTable 中，所有的数据按用户定义的排序方法排序之后按序存储，等到其存储内容的容量达到阈值时（默认为4MB），便将其转换成一个不可修改的MemTable，与此同时创建一个新的MemTable，供用户继续进行读写操作。

• Immutable MemTable

  只读的MemTable，后台压缩线程会将它持久到磁盘SST文件。

• Log

  数据写入内存前，先将写操作写入日志（WAL），异常发生时可通过日志恢复（redo）。
  顺序写入日志，替代了直接写入磁盘（随机写入），因此写入性能更高。

  1. 写log期间进程异常 ---> 写入失败
  2. 写log完成，写内存未完成 ---> redo恢复
  3. write动作完成（即log、内存写入都完成）后，进程异常 ---> redo恢复
  4. Immutable memtable持久化过程中进程异常 ---> redo恢复
  5. 其他压缩异常 ---> redo恢复

• SSTable

  内存中，所有的数据都是按序排列的，但是当多个MemTable数据持久化到磁盘后，对应的不同的sstable之间是存在交集的(不同批次写入的数据的顺序有交集)，在读操作时，需要对所有的sstable文件进行遍历，严重影响了读取效率。因此后台会“定期“整合这些sstable文件，该过程也称为compaction。随着compaction的进行，sstable文件在逻辑上被分成若干层，由内存数据直接dump出来的文件称为level 0层文件，后期整合而成的文件为level i 层文件，这也是leveldb这个名字的由来。

  所有的sstable文件本身的内容是不可修改的，这种设计哲学为leveldb带来了许多优势，简化了很多设计。

• Manifest

  Manifest文件保存了整个LevelDB示例的全部元数据，记录不同Level分布了哪些SST文件，单个SST文件的最大最小key，以及其他一些LevelDB需要的元信息。

  本质上是一个Log文件，每一个log record的内容就是VersionEdit。

  • VersionEdit

    表示一次元数据变更，内容如下：

    std::string comparator_;  // 比较器的名称，创建 LevelDB 的时候就确定了，以后都不能修改
    uint64_t log_number_;  // 最小的有效 log number。小于 log_numbers_ 的 log 文件都可以删除
    uint64_t prev_log_number_;  // 兼容旧版本
    uint64_t next_file_number_;  // 下一个文件的编号
    SequenceNumber last_sequence_;  // SSTable 中的最大的 sequence number
    
    std::vector<std::pair<int, InternalKey> > compact_pointers_;  // 每层进行下次compaction的起始 key
    DeletedFileSet deleted_files_;  // 可以删除的 SSTable（level-no -> file-no）
    std::vector<std::pair<int, FileMetaData> > new_files_;  // 新增的 SSTable
    

    通过EncodeTo序列化后，内容大致如下：

    kComparator comparator_
    kLogNumber log_number_
    kPrevLogNumber prev_log_number_
    kNextFileNumber next_file_number_
    kLastSequence last_sequence_
    kCompactPointer level internal_key kCompactPointer level internal_key ...
    kDeletedFile level fileno kDeletedFile level fileno ...
    kNewFile level fileno file-size smallest largest kNewFile level fileno file-size smallest largest ...
    

  • Version

    Version 是 VersionEdit 进行 apply 之后得到的数据库状态——当前版本包含哪些 SSTable，并通过引用计数保证多线程并发访问的安全性。读操作要读取 SSTable 之前需要调用 Version::Ref 增加引用计数，不使用时需要调用 Version::UnRef 减少引用计数。
    

  • VersionSet
    VersionSet 是一个 Version 的集合，用链表维护，每生成一个Version在尾部插入一个节点（AppendVersion）。

    随着数据库状态的变化，LevelDB 内部会不停地生成 VersionEdit——进而产生新的 Version。此时，旧的 Version 可能还在被正在执行的请求使用。所以，同一时刻可能存在多个 Version。

• Current

  记录当前Manifest文件的名字。