leveldb 源码分析(二) – Architecture

整体架构

leveldb 的架构图如下: image

LSM-Tree

leveldb 是以 LSM-tree 为模型实现的。LSM-tree 将随机写转换为顺序写从而获得更高的写性能,大致思路如下:

  • 数据分为2部分存储,共同维护一个有序的空间:
    • 内存中维护最新的写数据 memtable,所有的写操作都在内存中进行,同时顺序写 WAL
    • 磁盘上维护较老的数据 sstable
    • 读操作先读内存中的数据,然后读磁盘上的数据。
  • 在合适的时机进行 compaction:
    • 当内存中的数据大小超过阈值时,刷新到磁盘上。
    • 在合适的时机清理、合并磁盘上的数据。

LSM-tree 是一种设计思想,没有固定的实现方式,其中最重要的是 compaction 的实现,涉及到 compaction 的时机、 sstable 的组织方式、 memtablesstable 间的合并方式。compaction 对读写性能起着至关重要的影响,它会清理无用数据,能够降低磁盘空间使用并降低读的延迟,但是也会带来极大的 I/O 压力。 compaction 主要考虑如下几个因素:

  • 写放大: 要减少 compaction 时涉及到的无关数据量。
  • 读放大: 减少读数据时,读取的无关数据量。
  • 随机 I/O: 尽量减少随机 I/O

考虑最基本的情况,磁盘上维护一个大的 sstable,当 memtable 大小超过阈值时,就与磁盘上的 sstable 合并。可以是 in-place 的修改,可能伴随着很多随机 I/O,或者顺序写生成新的 sstable, 但可能要将整个 sstable 进行重写,会带来极大的写放大。现在只关注后面一种方式,一步步进行优化:

  1. 不是每次 memtable 大小超过阈值就与 sstable 合并,而是将 memtable 转储为 sstable,当到了一定数量后批量合并,从而减少合并的次数。同时需要控制 sstable 的数量,因为读可能需要读每个 sstable,数量太多会降低读的性能。
  2. 但每次合并仍有可能将整个 sstable 重写,为了降低写放大,将大的 sstable 划分为多个小的、不重叠的 sstable,这样 sstable 就分为2层:level-0memtable 直接转换而来,文件之间有重叠;level-1level-0 合并而来,文件之间无重叠。当 level-0 的文件个数达到上限时,只要挑选 level-1 中和 level-0 文件有重叠的合并即可,读 level-1 也只要读一个文件。 但仍有可能 level-1 中所有的 sstable 都需要合并,所以又要限制 level-1 的大小。
  3. level-1sstable 达到上限时,使用类似的方法 compactionlevel-2sstablelevel-2 达到上限,再 compactionlevel-3……

leveldb 就是类似上面的思路分层管理 sstable,所以叫 leveldb。现在看一下它的实现:

  • memtableskiplist 实现,只有追加操作,每个操作先顺序写到 log 中。
  • memtable 大小超过阈值时(默认为 4MB),变为 immutable memtable,在后台线程 compactionlevel-0sstable
  • sstable 的大小固定,默认为 2MB
  • 共分为 7 层:
    • level-0memtable 直接转化而来,文件之间有重叠。当 level-0sstable 数量到达阈值时,会将 level-0 中相互重叠的 sstablelevel-1 中重叠的 sstable 合并为新的 level-1sstable
    • 其余 level 由低层 compaction 而来,除最高层外,每层有大小限制,level-(N+1) 的大小限制是 level-N10 倍,其中level-110MB。相同 level 的文件之间无重叠。当 level-Nsstable 大小到达阈值时,会挑选一个文件(可能不止一个)和 level-(N+1) 中有重叠的 sstable 合并为新的 level-(N+1)sstable
  • 所有的写操作,包括 compacion 都是顺序写。
  • 读的顺序如下,只要读到对应的 key 就会停止:
    1. memtable
    2. immutable memtable
    3. level-0 中文件有重叠,从新到旧读取
    4. 其余 level 文件不重叠,每层最多只要读 1 个文件,按照层的顺序从低到高读取

并发控制

leveldb 使用 MVCC 实现并发控制,不支持事务,支持单个写操作和多个读操作同时执行:

  • 每个成功的写操作会更新 db 内部维护的顺序递增的 sequencesequence 会追加到 key 后一同保存。
  • 读操作会使用当前最新的 sequence(或者使用传入的 snapshot),只会读到小于等于自己的最大的 sequence 数据。

因为 compaction 会改变磁盘上文件的组织,为了不影响正在进行的操作,leveldb 使用 VersionSet 维护不同版本的 sstable 组织,每当有文件删除或增加时,就会创建新的 Version 插入到 VersionSet。只有当一个 sstable 不再被任意 Version 使用时才会进行删除。

数据恢复

leveldb 中每个 db 对应一个目录,目录名即 dbname。目录下有如下几种文件:

  • LOG: 记录操作日志。
  • *.log: 记录 memtableWAL
  • *.ldb(*.sst): sstable 文件。
  • MANIFEST-*: 记录元信息,如 sstable 的组织结构,每个 sstablekey range 等。
  • CURRENT: 记录当前的 MANIFEST 文件名。
  • LOCK: leveldb 不支持多个进程同时打开相同 db,会加文件锁。

数据恢复主要就是通过 CURRENT 文件找到当前的 MANIFEST 文件读取之后进行清理和恢复操作。

分类:

更新时间: