in LevelDB 分布式数据库 ~ read.

LevelDB

LevelDB

LevelDB

LevelDB ,LevelDB 是对 Bigtable 论文中描述的键值存储系统的单机版的实现,它提供了一个极其高速的键值存储系统,并且由 Bigtable 的作者 Jeff DeanSanjay 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 方法,只是在上层为调用者提供了两个不同的选择。

GetPut 是 LevelDB 为上层提供的用于读写的接口。

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

架构

![Architect](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb.md/33711315243858.png =716x)

  • 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 减少引用计数。
      ![Version](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb.md/281930915219826.png =437x)

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

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

  • Current

    记录当前Manifest文件的名字。