LevelDB 设计介绍与源码分析

[sunjun]

LevelDB 设计介绍与源码分析

LevelDB 是一个由 Google 开发的高性能键值（Key-Value）存储库。它采用日志结构化合并树（Log-Structured Merge-Tree, LSM-Tree）作为其核心数据结构，旨在为写密集型应用提供高吞吐量。本文将深入介绍 LevelDB 的设计理念，并结合源码对其核心功能进行分析。

一、LevelDB 核心设计理念

LevelDB 的设计哲学可以概括为以下几点：

• LSM-Tree 架构: 这是 LevelDB 的基石。LSM-Tree 的核心思想是将离散的、随机的写操作转化为批量的、顺序的写操作，从而极大地提升写入性能。这对于机械硬盘（HDD）和固态硬盘（SSD）都非常友好。

• 顺序 I/O 优先: LevelDB 尽力将磁盘 I/O 操作转换为顺序读写。无论是日志写入、MemTable 到 SSTable 的持久化，还是后台的 Compaction 过程，都以顺序 I/O 为主，有效避免了昂贵的随机寻道。

• 多层次数据存储: 数据在 LevelDB 中并非存储在单一位置，而是分布在内存中的 MemTable、不可变 MemTable 以及磁盘上多层次的 SSTable 文件中。这种分层结构使得数据可以根据其新旧程度进行有效的组织和管理。

• 后台自动合并 (Compaction): 为了解决 LSM-Tree 读取性能下降和空间放大的问题，LevelDB 在后台通过专门的线程进行 Compaction 操作。该操作会合并不同层次的 SSTable 文件，清除冗余和已删除的数据，并保持数据有序。

• 数据压缩: LevelDB 支持对 SSTable 中的数据块进行压缩（默认为 Snappy），有效减少磁盘占用空间，并在一定程度上提升 I/O 性能。

• 快照与前缀压缩: LevelDB 支持创建数据快照，提供特定时间点的一致性视图。同时，在 SSTable 内部，通过对相邻的 Key 进行前缀压缩，进一步减小了存储空间。

二、LevelDB 整体架构

LevelDB 的整体架构主要由以下几个组件构成：

组件 | 位置 | 描述 -- | -- | -- Log (Write-Ahead Log) | 磁盘 | 预写日志文件（.log 文件）。任何写操作在写入 MemTable 之前，都会先以顺序追加的方式写入 Log 文件，确保了数据的持久性和崩溃恢复能力。 MemTable | 内存 | 一个可变的、内存中的数据结构，底层采用 SkipList（跳表）实现，用于保存最近的写操作。所有读写请求都会首先经过 MemTable。 Immutable MemTable | 内存 | 当 MemTable 的大小达到预设阈值（默认为 4MB）时，会转变为一个只读的 Immutable MemTable。后台线程会将其内容持久化到磁盘上的 SSTable 文件中。 SSTable (Sorted String Table) | 磁盘 | 有序字符串表文件（.ldb 文件），是 LevelDB 在磁盘上的主要数据存储形式。SSTable 内部的数据按 Key 有序排列，并且是不可变的。SSTable 分为多个层级（Level 0 到 Level N）。 MANIFEST | 磁盘 | 清单文件。记录了数据库的所有元数据信息，例如各个 SSTable 文件所属的层级、Key 的范围等。数据库每次状态变更（如 Compaction 完成）都会生成新的 MANIFEST 文件。 CURRENT | 磁盘 | 一个简单的文本文件，内容指向当前最新的 MANIFEST 文件的文件名。 后台线程 |   | 主要负责执行 Compaction 操作，将 Immutable MemTable 刷写到 Level 0，以及将上层 SSTable 合并到下层。

导出到 Google 表格

三、源码分析：核心流程

1. 写操作 (Put) 流程

当用户调用 db->Put(write_options, key, value) 时，其内部执行流程如下：

1. 构造 WriteBatch: Put 操作首先会被封装成一个 WriteBatch 对象。WriteBatch 可以包含一个或多个写操作（Put 或 Delete），保证了这些操作的原子性。

2. 写入 WAL (Log): 为了保证数据不丢失，WriteBatch 的内容会被序列化并以顺序追加的方式写入到当前的 log 文件中。这部分的核心实现在 DBImpl::Write() 中，它会调用 log_->AddRecord()。

   C++

   // db/db_impl.cc
   Status DBImpl::Write(const WriteOptions& options, WriteBatch* my_batch) {
     // ...
     // 1. Add to the Write-Ahead Log
     if (options.sync) {
       // ...
     }
     status = log_->AddRecord(WriteBatchInternal::Contents(my_batch));
     // ...
   }
   

3. 写入 MemTable: 在成功写入 WAL 之后，WriteBatch 的内容会被应用到内存中的 MemTable。MemTable 的底层是一个 SkipList，可以高效地支持插入和查找。

   C++

   // db/db_impl.cc -> Write()
   // 2. Insert into the MemTable
   if (status.ok() && my_batch != nullptr) {
     status = WriteBatchInternal::InsertInto(my_batch, mem_);
   }
   

   WriteBatchInternal::InsertInto 会遍历 WriteBatch 中的所有操作，并调用 mem_->Add() 将键值对插入到底层的跳表中。

4. MemTable 切换: 当 mem_ 的大小超过 options.write_buffer_size（默认为 4MB）时，会触发切换：

   • 当前的 mem_ 变为 imm_ (Immutable MemTable)。

   • 创建一个新的 log 文件和一个新的 mem_。

   • 后台 Compaction 线程被唤醒，将 imm_ 的内容刷写到磁盘的 SSTable 文件中（Level 0）。这个过程被称为 Minor Compaction。

2. 读操作 (Get) 流程

当用户调用 db->Get(read_options, key, &value) 时，查找过程遵循一个明确的顺序，以保证能读到最新的数据：

1. 查询 MemTable: 首先在当前可写的 mem_ 中查找 key。由于 MemTable 中保存的是最新的数据，如果找到，则直接返回结果。

2. 查询 Immutable MemTable: 如果在 mem_ 中未找到，则接着在 imm_ 中查找。imm_ 是一个只读的 MemTable，正在等待被持久化。

3. 查询 SSTable: 如果内存中都未找到，则需要从磁盘上的 SSTable 文件中查找。这个过程是分层进行的：

   • Level 0: 首先查找 Level 0 的所有 SSTable 文件。Level 0 的特殊之处在于，它的 SSTable 文件之间可能存在 Key 的重叠（因为它们是直接由 MemTable dump 产生的）。因此，需要依次查找 Level 0 的所有文件。

   • Level 1 及更高层级: 对于 Level 1 及以上的层级，其内部的 SSTable 文件保证了 Key 的范围互不重叠。因此，可以通过二分查找快速定位到 key 可能所在的那个 SSTable 文件。

   • 在 SSTable 内部查找: 定位到具体的 SSTable 文件后，会首先利用文件末尾的索引块（Index Block）快速定位到 key 可能所在的 数据块（Data Block）。然后将该数据块加载到内存中，在数据块内部进行查找。为了加速这个过程，LevelDB 还会使用布隆过滤器（Bloom Filter）来快速判断一个 SSTable 或一个 Data Block 中是否可能存在某个 key，从而避免不必要的磁盘读取。

   整个查找过程在 DBImpl::Get() 中实现，其核心是调用 version_->Get()，这里的 version_ 对象封装了当前所有 SSTable 文件的元数据信息。

   C++

   // db/version_set.cc
   void Version::Get(const ReadOptions& options, const LookupKey& k, std::string* value, Status* s) {
     // ...
     // Search sequence: memtable, immutable memtable, then files in level 0, then files in levels > 0.
     // ...
     for (int level = 0; level < config::kNumLevels; level++) {
       // ... search files in 'level' ...
     }
   }
   

3. Compaction 过程

Compaction 是 LevelDB 的灵魂，它负责垃圾回收、减少读放大和空间放大。Compaction 分为两种：

• Minor Compaction: 将 Immutable MemTable dump 成 Level 0 的 SSTable 文件。

• Major Compaction: 合并上下两层 SSTable 文件的过程。

触发时机:

• 当 Level 0 的文件数量超过某个阈值（kL0_CompactionTrigger，通常是 4）。

• 当某个非 Level 0 的层级（Level L）的总大小超过其预设目标大小（10^L MB）。

执行流程:

1. 选择 Compaction 文件:

   • 对于从 Level 0 开始的 Compaction，会选择 Level 0 中所有与 Level 1 有重叠 Key 范围的 SSTable 文件。

   • 对于从 Level L (L > 0) 开始的 Compaction，会从 Level L 中选择一个文件，并找出所有在 Level L+1 中与它有 Key 范围重叠的文件。

2. 执行合并:

   • 后台线程会创建一个迭代器（MergingIterator），该迭代器可以同时遍历所有被选中的 SSTable 文件，并按 Key 的顺序逐个返回键值对。

   • 遍历 MergingIterator，将有效的（未被更高层或更新的 Key 覆盖或删除的）键值对写入到新的 SSTable 文件中（位于 Level L+1）。

   • 在这个过程中，被删除的键（带有删除标记）和旧版本的键值对会被自然地丢弃。

3. 安装新版本:

   • 当新的 SSTable 文件生成后，LevelDB 会创建一个新的 Version。这个 Version 会记录：

     • 删除了哪些旧的 SSTable 文件。

     • 添加了哪些新的 SSTable 文件。

   • 这个变更会被记录到新的 MANIFEST 文件中。

   • 最后，原子地将 CURRENT 文件指向新的 MANIFEST 文件。一旦 CURRENT 文件更新成功，所有新的读操作都将使用这个新的 Version。

   Compaction 的核心逻辑在 DBImpl::BackgroundCompaction() 中，它会构建一个 Compaction 对象来封装单次合并的所有信息。

   C++

   // db/db_impl.cc
   void DBImpl::BackgroundCompaction() {
     // ...
     Compaction* c = versions_->PickCompaction();
     // ...
     if (c != nullptr) {
       Status s = DoCompactionWork(c);
       // ...
       CleanupCompaction(c);
       versions_->LogAndApply(c->edit());
       // ...
     }
   }
   

四、SSTable 文件结构

SSTable 文件是 LevelDB 持久化存储的核心。其内部结构经过精心设计，以支持高效的查找。一个 SSTable 文件（.ldb 文件）通常包含以下几个部分：

• Data Blocks: 若干个数据块，是存储实际键值对的地方。块内部的 Key 是有序的，并且可能采用了前缀压缩。

• Filter Block: 存储了所有 Data Block 的布隆过滤器数据，用于快速排除不含目标 Key 的 Data Block。

• Meta Index Block: 索引块的索引，用于定位 Filter Block 等元数据块。

• Index Block: 数据块的索引。它的每一条记录格式为 <lastKey, BlockHandle>，其中 lastKey 是对应 Data Block 中最大的 Key，BlockHandle 则包含了该 Data Block 在文件中的偏移量和大小。

• Footer: 文件末尾的定长区域，包含了 Meta Index Block 和 Index Block 的 BlockHandle，是读取 SSTable 的入口点。

总结

LevelDB 通过其精巧的 LSM-Tree 设计，成功地将随机写转换为顺序写，提供了卓越的写入性能。其分层存储、后台自动合并、以及优化的 SSTable 文件格式，共同构成了一个高效、可靠的键值存储引擎。虽然其读操作可能需要查询多个文件，但通过布隆过滤器、多级索引和操作系统的文件缓存，LevelDB 在大多数场景下也能提供良好的读取性能。对 LevelDB 设计与源码的理解，不仅有助于更好地使用它，也为我们学习和构建其他存储系统提供了宝贵的经验。