leveldb的整体框架如下图所示leveldb 的实现方式与单个 Bigtable tablet 的实现方式5.3 节在本质上类似。但是leveldb的文件组织方式略有不同。每个db都由存储在目录中的一组文件表示。日志文件wal日志文件.log 存储了最近的一系列更新。数据写入时会首先将写入内容追加到当前日志文件中。当日志文件达到预定大小默认约为 4MB时它对于的memtable会被转换为sorted table并创建一个新的日志文件用于记录后续的更新。单曲日志文件的副本保存在memtable中memtable时一个内存态的数据结构。Sorted tablesSorted tables.ldb存储按键排序的一系列条目。每个条目要么是该键的值要么是该键的删除标记。LevelDB 通过多层级管理排序表。随着数据的写入直接由日志文件生成的sorted table存放在level-0层。当level-0层达到了上限默认为4个所有的level-0层的文件都会和与level-0文件由交集的level-1层文件进行合并生成新的level-1文件。合并到level-1以及后面的levellevel-L之后如果文件大小超过阈值level-L的阈值为 (10^L) MB。会选取该超过阈值的文件和 Level-(L1) 层中所有与它 Key 范围有交集 的文件进行合并生成新的level-(L1)层文件。ManifestManifest中存储了每层的Sorted tables、相应的key范围以及其他重要的元数据。每次db重新打开时都会创建一个新的 MANIFEST 文件文件名中包含一个新的编号。MANIFEST 文件采用日志格式服务状态的更改例如添加或删除文件都会追加到此日志中。CurrentCURRENT 中包含最新 MANIFEST 文件的名称。LogLeveldb的运行日志会打印到名为 LOG 和 LOG.old 的文件中。Level 0当wal达到阈值默认时4MB后会创建全新的memtable和wal文件用来记录后续的写入记录老的memtable会变为Immutable MemTable不在进行写入。后续的处理流程如下后台异步流程将Immutable MemTable内容写入到sstable中删除Immutable MemTable和wal日志把这个新生成的 SSTable 放入到 Level-0中CompactionsL层的文件和L1层的文件进行compaction对于新的L1层文件由一下限制当当前输出文件达到目标文件大小2MB后我们会切换到生成新的 L1 级文件。当当前输出文件的键值范围增长到足以覆盖超过十个 L2 级文件时我们也会切换到生成新的输出文件。每个层级的compaction会在key中轮换进行。对于每个层级 L我们会记住上一次在该层级compaction的结束key。下一次针对层级 L 的compaction操作会选择该key之后的第一个文件如果不存在这样的文件则会循环回到最小的key。compaction会删除被覆盖的值。如果在更高层级的文件中都没有包含当前 Key则compaction还会删除删除标记。耗时Level-0 的Compaction会从 Level-0 读取最多 4 个 1MB 的文件在最坏情况下还会把 Level-1 的所有文件共 10MB全部读进来。也就是说我们总共需要读取 14MB 并写入 14MB 的数据。除了特殊的 Level-0 Compaction之外对于其他层级我们会从 Level-L 中挑出一个 2MB 的文件。在最坏情况下这个文件会与 Level-(L1) 层的大约 12 个文件发生重叠。因此这种合并将需要读取 26MB 并写入 26MB。假设磁盘的 I/O 速率为 100MB/s现代硬盘的常规大体范围最坏情况下的合并耗时大约为 0.5 秒。如果我们把后台写入的速率限制在一个很小的值比如限制到满速 100MB/s 的 10%即 10MB/s那么一次合并可能会耗时高达 5 秒。此时如果用户正以 10MB/s 的速度高强度写入系统内部可能就会堆积出大量的 Level-0 文件大约需要 50 个文件才能装下这 5 秒内产生的5×10MB5 \times 10\text{MB}5×10MB数据。由于每次读取操作都需要把堆积的文件进行多路归并合并这将会显著暴增用户的查询/读取成本。解决方案可以在 Level-0 文件数量过多时选择增大日志滚动的阈值即调大 MemTable 的刷盘边界。不过这种做法的副作用是这个阈值设置得越大我们就需要消耗越多的物理内存来容纳与之相对应的 MemTable。可以在 Level-0 文件数量不断飙升时主动限制前台用户的写入速率。对于主要目的是降低超多文件参与的大规模归并所带来的性能开销。可以让绝大多数 Level-0 文件的 Data Block 以未压缩的状态常驻在 Block Cache缓存中这样在多路归并迭代时我们只需要承受排序迭代器本身原生的O(N)O(N)O(N)复杂度开销即可。文件数量对于总是生成 2MB 的文件我们可以针对更高层级生成更大的文件以减少文件总数但这会增加Compaction的读写放大。我们也可以将文件集分片到多个目录中。Recover恢复流程首先读取CURRENT文件从中获取最新提交的MANIFEST元数据清单的文件名。读取该指定的MANIFEST文件在内存中重建数据库各层级 SSTable 的版本控制骨架。清理掉磁盘上的所有过期、残存的废弃文件如上次合并进行到一半崩了留下的残渣。可以在这一步就把所有的 SSTable.ldb文件全部打开但更优雅、更推荐的做法是进行“延迟加载/懒加载Lazy Open”……将未落盘的旧日志分片即崩溃前遗留的 WAL 日志里的残留数据转换成一个全新的 Level-0 层 SSTable 文件。基于恢复出来的最新序列号Sequence Number创建一个全新的 WAL 日志文件开始引导并接收后续的所有新写入请求回收旧文件RemoveObsoleteFiles()会在每一次Compaction结束时以及数据库恢复Recovery结束时被调用。它会扫描并找出数据库目录下的所有文件名。随后它会物理删除所有不是当前正在使用的WAL 日志文件同时它还会物理删除所有既没有被任何层级Level所引用、又不是当前正在进行的合并操作所输出的SSTable 文件。leveldb 的实现方式与单个 Bigtable tablet 的实现方式5.3 节在本质上类似。但是leveldb的文件组织方式略有不同。每个db都由存储在目录中的一组文件表示。日志文件wal日志文件.log 存储了最近的一系列更新。数据写入时会首先将写入内容追加到当前日志文件中。当日志文件达到预定大小默认约为 4MB时它对于的memtable会被转换为sorted table并创建一个新的日志文件用于记录后续的更新。单曲日志文件的副本保存在memtable中memtable时一个内存态的数据结构。Sorted tablesSorted tables.ldb存储按键排序的一系列条目。每个条目要么是该键的值要么是该键的删除标记。LevelDB 通过多层级管理排序表。随着数据的写入直接由日志文件生成的sorted table存放在level-0层。当level-0层达到了上限默认为4个所有的level-0层的文件都会和与level-0文件由交集的level-1层文件进行合并生成新的level-1文件。合并到level-1以及后面的levellevel-L之后如果文件大小超过阈值level-L的阈值为 (10^L) MB。会选取该超过阈值的文件和 Level-(L1) 层中所有与它 Key 范围有交集 的文件进行合并生成新的level-(L1)层文件。ManifestManifest中存储了每层的Sorted tables、相应的key范围以及其他重要的元数据。每次db重新打开时都会创建一个新的 MANIFEST 文件文件名中包含一个新的编号。MANIFEST 文件采用日志格式服务状态的更改例如添加或删除文件都会追加到此日志中。CurrentCURRENT 中包含最新 MANIFEST 文件的名称。LogLeveldb的运行日志会打印到名为 LOG 和 LOG.old 的文件中。Level 0当wal达到阈值默认时4MB后会创建全新的memtable和wal文件用来记录后续的写入记录老的memtable会变为Immutable MemTable不在进行写入。后续的处理流程如下后台异步流程将Immutable MemTable内容写入到sstable中删除Immutable MemTable和wal日志把这个新生成的 SSTable 放入到 Level-0中CompactionsL层的文件和L1层的文件进行compaction对于新的L1层文件由一下限制当当前输出文件达到目标文件大小2MB后我们会切换到生成新的 L1 级文件。当当前输出文件的键值范围增长到足以覆盖超过十个 L2 级文件时我们也会切换到生成新的输出文件。每个层级的compaction会在key中轮换进行。对于每个层级 L我们会记住上一次在该层级compaction的结束key。下一次针对层级 L 的compaction操作会选择该key之后的第一个文件如果不存在这样的文件则会循环回到最小的key。compaction会删除被覆盖的值。如果在更高层级的文件中都没有包含当前 Key则compaction还会删除删除标记。耗时Level-0 的Compaction会从 Level-0 读取最多 4 个 1MB 的文件在最坏情况下还会把 Level-1 的所有文件共 10MB全部读进来。也就是说我们总共需要读取 14MB 并写入 14MB 的数据。除了特殊的 Level-0 Compaction之外对于其他层级我们会从 Level-L 中挑出一个 2MB 的文件。在最坏情况下这个文件会与 Level-(L1) 层的大约 12 个文件发生重叠。因此这种合并将需要读取 26MB 并写入 26MB。假设磁盘的 I/O 速率为 100MB/s现代硬盘的常规大体范围最坏情况下的合并耗时大约为 0.5 秒。如果我们把后台写入的速率限制在一个很小的值比如限制到满速 100MB/s 的 10%即 10MB/s那么一次合并可能会耗时高达 5 秒。此时如果用户正以 10MB/s 的速度高强度写入系统内部可能就会堆积出大量的 Level-0 文件大约需要 50 个文件才能装下这 5 秒内产生的5×10MB5 \times 10\text{MB}5×10MB数据。由于每次读取操作都需要把堆积的文件进行多路归并合并这将会显著暴增用户的查询/读取成本。解决方案可以在 Level-0 文件数量过多时选择增大日志滚动的阈值即调大 MemTable 的刷盘边界。不过这种做法的副作用是这个阈值设置得越大我们就需要消耗越多的物理内存来容纳与之相对应的 MemTable。可以在 Level-0 文件数量不断飙升时主动限制前台用户的写入速率。对于主要目的是降低超多文件参与的大规模归并所带来的性能开销。可以让绝大多数 Level-0 文件的 Data Block 以未压缩的状态常驻在 Block Cache缓存中这样在多路归并迭代时我们只需要承受排序迭代器本身原生的O(N)O(N)O(N)复杂度开销即可。文件数量对于总是生成 2MB 的文件我们可以针对更高层级生成更大的文件以减少文件总数但这会增加Compaction的读写放大。我们也可以将文件集分片到多个目录中。Recover恢复流程首先读取CURRENT文件从中获取最新提交的MANIFEST元数据清单的文件名。读取该指定的MANIFEST文件在内存中重建数据库各层级 SSTable 的版本控制骨架。清理掉磁盘上的所有过期、残存的废弃文件如上次合并进行到一半崩了留下的残渣。可以在这一步就把所有的 SSTable.ldb文件全部打开但更优雅、更推荐的做法是进行“延迟加载/懒加载Lazy Open”……将未落盘的旧日志分片即崩溃前遗留的 WAL 日志里的残留数据转换成一个全新的 Level-0 层 SSTable 文件。基于恢复出来的最新序列号Sequence Number创建一个全新的 WAL 日志文件开始引导并接收后续的所有新写入请求回收旧文件RemoveObsoleteFiles()会在每一次Compaction结束时以及数据库恢复Recovery结束时被调用。它会扫描并找出数据库目录下的所有文件名。随后它会物理删除所有不是当前正在使用的WAL 日志文件同时它还会物理删除所有既没有被任何层级Level所引用、又不是当前正在进行的合并操作所输出的SSTable 文件。