前言

本课程教你如何在 Rust 中构建一个简单的 LSM-Tree 存储引擎。

什么是 LSM，为什么选择 LSM？

日志结构合并树是维护键值对的数据结构。这种数据结构广泛应用于分布式数据库系统，如 TiDB 和 CockroachDB，作为它们的底层存储引擎。RocksDB，基于 LevelDB，是 LSM-Tree 存储引擎的一个实现。它提供了许多键值访问功能，并在许多生产系统中使用。

一般来说，LSM 树是一种追加友好的数据结构。将 LSM 与其他键值数据结构（如 RB-Tree 和 B-Tree）进行比较更直观。对于 RB-Tree 和 B-Tree，所有数据操作都是原地进行的。也就是说，当你想更新键对应的值时，引擎会用新值覆盖其原始的内存或磁盘空间。但在 LSM 树中，所有写操作，即插入、更新、删除，都是延迟应用到存储中的。引擎将这些操作批量处理成 SST（排序字符串表）文件并将它们写入磁盘。一旦写入磁盘，引擎就不会直接修改它们。在一个称为合并的特殊后台任务中，引擎将合并这些文件以应用更新和删除。

这种架构设计使得 LSM 树易于使用。

数据在持久存储上是不可变的。并发控制更直接。将后台任务（合并）卸载到远程服务器是可能的。直接从云原生存储系统（如 S3）存储和服务数据也是可行的。
更改合并算法允许存储引擎在读放大、写放大和空间放大之间取得平衡。数据结构是多功能的，通过调整合并参数，我们可以针对不同的工作负载优化 LSM 结构。

本课程将教你如何在 Rust 编程语言中构建一个基于 LSM 树的存储引擎。

先决条件

你应该了解 Rust 编程语言的基础知识。阅读 Rust 书就足够了。
你应该了解键值存储引擎的基本概念，即为什么我们需要复杂的设计来实现持久化。如果你以前没有数据库系统和存储系统的经验，你可以在 PingCAP Talent Plan 中实现 Bitcask。
了解 LSM 树的基础知识不是必需的，但我们建议你阅读一些相关内容，例如 LevelDB 的整体思想。事先了解它们会让你熟悉可变和不可变内存表、SST、合并、WAL 等概念。

你期望从本课程中获得什么

完成本课程后，你应该深入理解基于 LSM 的存储系统如何工作，获得设计此类系统的实践经验，并将所学应用于你的学习和职业生涯中。你将理解此类存储系统中的设计权衡，并找到设计基于 LSM 的存储系统以满足工作负载要求/目标的最佳方法。这门非常深入的课程涵盖了现代存储系统（即 RocksDB）的所有基本实现细节和设计选择，基于作者在几个类似 LSM 的存储系统中的经验，你将能够直接将所学应用于工业界和学术界。

结构

本课程是一个包含多个部分（周）的广泛课程。每周有七章；你可以在 2 到 3 小时内完成每一章。每个部分的前六章将指导你构建一个可工作的系统，每周的最后一章将是一个零食时间章节，在你前六天构建的内容上实现一些简单的东西。每章都有必做任务、检查你的理解问题和额外任务。

测试

我们提供了一个完整的测试套件和一些 CLI 工具，供你验证你的解决方案是否正确。请注意，测试套件并不详尽，你的解决方案在通过所有测试用例后可能不是 100% 正确的。在实现系统的后续部分时，你可能需要修复早期的错误。我们建议你彻底思考你的实现，特别是在涉及多线程操作和竞争条件时。

解决方案

我们在 mini-lsm 主仓库中有一个解决方案，实现了课程中要求的所有功能。同时，我们还有一个 mini-lsm 解决方案检查点仓库，其中每个提交对应课程中的一章。

保持这样的检查点仓库与 mini-lsm 课程同步是具有挑战性的，因为每个错误修复或新功能都必须经过所有提交（或检查点）。因此，这个仓库可能不使用最新的起始代码或包含 mini-lsm 课程的最新功能。

TL;DR: 我们不保证解决方案检查点仓库包含正确的解决方案、通过所有测试或具有正确的文档注释。 对于正确的实现和实现所有内容后的解决方案，请查看主仓库中的解决方案。https://github.com/skyzh/mini-lsm/tree/main/mini-lsm。

如果你在课程的某个部分卡住了，或者不确定在哪里实现功能，你可以参考这个仓库寻求帮助。你可以比较提交之间的差异，以了解发生了什么变化。你可能需要在课程的不同章节中多次修改 mini-lsm 课程中的一些函数，你可以在这个仓库中了解每章具体需要实现什么。

你可以访问解决方案检查点仓库：https://github.com/skyzh/mini-lsm-solution-checkpoint。

反馈

我们非常感激你的反馈。我们根据学生的反馈在 2024 年从头重写了整个课程。请分享你的学习经验，帮助我们不断改进课程。欢迎加入 Discord 社区并分享你的经验。

为什么我们重写它的长故事：该课程最初计划作为一般指导，学生从一个空目录开始，根据我们的规范实现他们想要的任何东西。我们只有最少的测试来检查行为是否正确。然而，原始课程过于开放，给学习体验带来了巨大障碍。由于学生事先没有整个系统的概览，而且说明模糊，有时他们很难理解为什么做出设计决策以及他们需要实现什么目标。课程的某些部分非常紧凑，不可能在一章内交付预期的内容。因此，我们完全重新设计了课程，以获得更简单的学习曲线和更清晰的学习目标。原始的一周课程现在分为两周（第一周关于存储格式，第二周关于深入合并），并增加了关于 MVCC 的额外部分。我们希望你觉得这门课程有趣，并对你的学习和职业生涯有所帮助。我们要感谢在 Feedback after coding day 1 和 Hello, when is the next update plan for the course? 中评论的每个人——你的反馈极大地帮助我们改进了课程。

许可证

本课程的源代码根据 Apache 2.0 许可，而本书根据 CC BY-NC-SA 4.0 许可。

这门课程会永远免费吗？

是的！现在公开可用的所有内容将永远免费，并接收终身更新和错误修复。同时，我们可能会提供付费的代码审查和办公时间服务。对于 DLC 部分（后续内容章节），截至 2024 年，我们没有完成它们的计划，也尚未决定它们是否会公开可用。

社区

你可以加入 skyzh 的 Discord 服务器，与 mini-lsm 社区一起学习。

开始

现在，你可以在 Mini-LSM 课程概述中了解 LSM 结构的概述。

关于作者

截至撰写时（2024 年初），Chi 获得了卡内基梅隆大学的计算机科学硕士学位和上海交通大学的学士学位。他一直致力于各种数据库系统，包括 TiKV、AgateDB、TerarkDB、RisingWave 和 Neon。自 2022 年以来，他担任 CMU 的数据库系统课程的助教三个学期，在 BusTub 教育系统中，他为课程添加了许多新功能和更多挑战（查看重新设计的查询执行项目和超级挑战性的多版本并发控制项目）。除了在 BusTub 教育系统上工作外，他还维护 RisingLight 教育数据库系统。Chi 对探索 Rust 编程语言如何适应数据库世界感兴趣。如果你也对那个主题感兴趣，请查看他之前关于构建向量化表达式框架的课程 type-exercise-in-rust 和关于构建向量数据库的课程 write-you-a-vector-db。

我们非常感激你的反馈。欢迎加入我们的 Discord 社区。
发现问题？在 github.com/skyzh/mini-lsm 上创建问题/拉取请求。
mini-lsm-book © 2022-2025 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Mini-LSM 课程概述

课程结构

课程概述

本课程分为三个部分（周）。在第一周，我们将专注于 LSM 存储引擎的存储结构和存储格式。在第二周，我们将深入探讨合并操作并为存储引擎实现持久化支持。在第三周，我们将实现多版本并发控制。

第一周: Mini-LSM
第二周: 合并和持久化
第三周: 多版本并发控制

请查看环境设置来设置环境。

LSM 概述

一个 LSM 存储引擎通常包含三个部分：

预写日志，用于持久化临时数据以便恢复。
磁盘上的 SST，用于维护 LSM 树结构。
内存中的内存表，用于批量处理小写入。

存储引擎通常提供以下接口：

Put(key, value): 在 LSM 树中存储一个键值对。
Delete(key): 删除一个键及其对应的值。
Get(key): 获取与键对应的值。
Scan(range): 获取一个范围内的键值对。

为了确保持久性，

Sync(): 确保在 sync 之前的所有操作都持久化到磁盘。

一些引擎选择将 Put 和 Delete 合并为一个名为 WriteBatch 的操作，它接受一批键值对。

在本课程中，我们假设 LSM 树使用层级合并算法，这在现实世界的系统中很常见。

写入路径

LSM 的写入路径包含四个步骤：

将键值对写入预写日志，以便在存储引擎崩溃后可以恢复。
将键值对写入内存表。在完成 (1) 和 (2) 后，我们可以通知用户写入操作已完成。
（在后台）当内存表已满时，我们会将它们冻结为不可变内存表，并在后台将它们刷新到磁盘作为 SST 文件。
（在后台）引擎会将某些层级中的一些文件合并到较低的层级，以保持 LSM 树的良好形状，从而降低读放大。

读取路径

当我们想要读取一个键时，

我们将首先从最新到最旧地探测所有内存表。
如果未找到该键，我们将搜索包含 SST 的整个 LSM 树以查找数据。

有两种类型的读取：查找和扫描。查找在 LSM 树中查找一个键，而扫描则遍历存储引擎中某个范围内的所有键。我们将在整个课程中涵盖这两种类型。

环境设置

起始代码和参考解决方案可在 https://github.com/skyzh/mini-lsm 获取。

安装 Rust

更多信息请参见 https://rustup.rs。

克隆仓库

git clone https://github.com/skyzh/mini-lsm

起始代码

cd mini-lsm/mini-lsm-starter
code .

安装工具

你需要最新的稳定版 Rust 来编译这个项目。最低要求是 1.74。

cargo x install-tools

运行测试

cargo x copy-test --week 1 --day 1
cargo x scheck

现在，你可以继续开始第一周: Mini-LSM。

第一周概述: Mini-LSM

章节概述

在课程的第一周，你将构建存储引擎的必要存储格式、系统的读取路径和写入路径，并拥有一个基于 LSM 的键值存储的工作实现。这部分有 7 章（天）。

第 1 天: 内存表。你将实现系统的内存读取和写入路径。
第 2 天: 合并迭代器。你将扩展第 1 天构建的内容，并为你的系统实现一个 scan 接口。
第 3 天: 块编码。现在我们开始磁盘结构的第一步，构建块的编码/解码。
第 4 天: SST 编码。SST 由块组成，在这一天结束时，你将拥有 LSM 磁盘结构的基本构建块。
第 5 天: 读取路径。既然我们有了内存和磁盘结构，我们可以将它们组合在一起，为存储引擎提供一个完全工作的读取路径。
第 6 天: 写入路径。在第 5 天，测试框架生成结构，而在第 6 天，你将自行控制 SST 刷新。你将实现刷新到 level-0 SST，存储引擎就完成了。
第 7 天: SST 优化。我们将实现几种 SST 格式优化，并提高系统的性能。

在这一周结束时，你的存储引擎应该能够处理所有 get/scan/put 请求。唯一缺失的部分是将 LSM 状态持久化到磁盘，以及一种更有效的方式来组织磁盘上的 SST。你将拥有一个可工作的 Mini-LSM 存储引擎。

Memtables

Chapter Overview

在本章中，你将：

基于跳表实现内存表（memtable）。
实现冻结内存表的逻辑。
为内存表实现 LSM 读取路径 get。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 1 --day 1
cargo x scheck

任务 1：跳表内存表

在此任务中，你需要修改：

src/mem_table.rs

首先，让我们实现 LSM 存储引擎的内存结构——内存表。我们选择 crossbeam 的跳表实现作为内存表的数据结构，因为它支持无锁并发读写。我们不会深入探讨跳表的工作原理，简单来说，它是一个有序的键值映射，易于并发读写。

crossbeam-skiplist 提供了类似于 Rust 标准库 BTreeMap 的接口：insert、get 和 iter。唯一的区别是修改接口（即 insert）只需要对跳表的不可变引用，而不是可变引用。因此，在你的实现中，实现内存表结构时不应获取任何互斥锁。

你还会注意到 MemTable 结构没有 delete 接口。在 mini-lsm 实现中，删除操作表示为键对应一个空值。

在此任务中，你需要实现 MemTable::get 和 MemTable::put 以启用内存表的修改。注意，put 应该始终覆盖已存在的键。单个内存表中不会有多个相同键的条目。

我们使用 bytes 箱来存储内存表中的数据。bytes::Byte 类似于 Arc<[u8]>。当你克隆 Bytes 或获取 Bytes 的切片时，底层数据不会被复制，因此克隆是廉价的。相反，它只是创建对存储区域的新引用，当没有对该区域的引用时，存储区域将被释放。

任务 2：引擎中的单个内存表

在此任务中，你需要修改：

src/lsm_storage.rs

现在，我们将第一个数据结构——内存表，添加到 LSM 状态中。在 LsmStorageState::create 中，你会发现当创建 LSM 结构时，我们将初始化一个 id 为 0 的内存表。这是初始状态中的可变内存表。在任何时间点，引擎将只有一个可变内存表。内存表通常有大小限制（例如 256MB），当达到大小限制时，它将被冻结为不可变内存表。

查看 lsm_storage.rs，你会发现有两个结构表示存储引擎：MiniLSM 和 LsmStorageInner。MiniLSM 是 LsmStorageInner 的薄包装。你将在 LsmStorageInner 中实现大部分功能，直到第 2 周的压缩。

LsmStorageState 存储 LSM 存储引擎的当前结构。目前，我们只使用 memtable 字段，它存储当前的可变内存表。在此任务中，你需要实现 LsmStorageInner::get、LsmStorageInner::put 和 LsmStorageInner::delete。它们都应该直接将请求分派到当前内存表。

one memtable LSM

你的 delete 实现应该简单地为该键放入一个空切片，我们称之为删除墓碑。你的 get 实现应相应地处理这种情况。

要访问内存表，你需要获取 state 锁。由于我们的内存表实现只需要 put 的不可变引用，你只需要获取 state 的读锁就可以修改内存表。这允许多个线程并发访问内存表。

任务 3：写入路径 - 冻结内存表

在此任务中，你需要修改：

src/lsm_storage.rs
src/mem_table.rs

one memtable LSM

内存表不能无限增长，当达到大小限制时，我们需要冻结它们（稍后刷新到磁盘）。你可以在 LsmStorageOptions 中找到内存表大小限制，它等于 SST 大小限制（不是 num_memtables_limit）。这不是硬限制，你应该尽最大努力冻结内存表。

在此任务中，你需要在内存表中 put/delete 键时计算近似内存表大小。这可以通过简单地将调用 put 时键和值的总字节数相加来计算。如果一个键被放入两次，尽管跳表只包含最新的值，你可以在近似内存表大小中计算两次。一旦内存表达到限制，你应该调用 force_freeze_memtable 来冻结内存表并创建一个新的。

LsmStorageInner 中的 state: Arc<RwLock<Arc<LsmStorageState>>> 字段以这种方式结构化，以使用写时复制（CoW）策略并发且安全地管理 LSM 树的整体状态：

内部 Arc<LsmStorageState>：这保存了实际 LsmStorageState（包含内存表列表、SST 引用等）的不可变快照。克隆这个 Arc 非常廉价（只是一个原子引用计数递增），并为任何读者在其操作期间提供一致的、不变的状态视图。
RwLock<Arc<LsmStorageState>>：这个读写锁保护指向当前 Arc<LsmStorageState>（活动快照）的指针。
- 读者获取读锁，克隆 Arc<LsmStorageState>（获取对当前快照的自己的引用），然后快速释放读锁。然后他们可以在没有进一步锁定的情况下处理他们的快照。
- 写者（当修改状态时，例如冻结内存表）将：
  - 创建一个新的 LsmStorageState 实例，通常通过克隆当前快照的数据然后应用修改。
  - 将这个新状态包装在一个新的 Arc<LsmStorageState> 中。
  - 获取 RwLock 上的写锁。
  - 用新的替换旧的 Arc<LsmStorageState>。
  - 释放写锁。
外部 Arc<RwLock<...>>：这允许 RwLock 本身（以及访问和更新状态的机制）在可能需要与 LsmStorageInner 交互的多个线程或应用程序部分之间安全共享。

这种 CoW 方法确保读者始终看到有效、一致的状态快照，并经历最小的阻塞。写者通过交换整个状态快照来原子地更新状态，减少了持有关键锁的时间，从而提高了并发性。

因为可能有多个线程将数据放入存储引擎，force_freeze_memtable 可能从多个线程并发调用。你需要考虑在这种情况下如何避免竞态条件。

有多个地方你可能想要修改 LSM 状态：冻结可变内存表、将内存表刷新到 SST，以及 GC/压缩。在所有这些修改期间，可能有 I/O 操作。结构化锁定策略的直观方式是：

#![allow(unused)]
fn main() {
fn freeze_memtable(&self) {
    let state = self.state.write();
    state.immutable_memtable.push(/* something */);
    state.memtable = MemTable::create();
}
}

…你在 LSM 状态的写锁中修改所有内容。

这目前工作正常。然而，考虑你想要为创建的每个内存表创建预写日志文件的情况。

#![allow(unused)]
fn main() {
fn freeze_memtable(&self) {
    let state = self.state.write();
    state.immutable_memtable.push(/* something */);
    state.memtable = MemTable::create_with_wal()?; // <- 可能需要几毫秒
}
}

现在当我们冻结内存表时，其他线程几毫秒内都无法访问 LSM 状态，这会产生延迟峰值。

为了解决这个问题，我们可以将 I/O 操作放在锁区域之外。

#![allow(unused)]
fn main() {
fn freeze_memtable(&self) {
    let memtable = MemTable::create_with_wal()?; // <- 可能需要几毫秒
    {
        let state = self.state.write();
        state.immutable_memtable.push(/* something */);
        state.memtable = memtable;
    }
}
}

然后，我们在状态写锁区域内没有昂贵的操作。现在，考虑内存表即将达到容量限制的情况，两个线程成功地将两个键放入内存表，它们都在放入两个键后发现内存表达到容量限制。它们都会对内存表进行大小检查并决定冻结它。在这种情况下，我们可能会创建一个空的内存表，然后立即被冻结。

为了解决这个问题，所有状态修改都应该通过状态锁同步。

#![allow(unused)]
fn main() {
fn put(&self, key: &[u8], value: &[u8]) {
    // 将内容放入内存表，检查容量，并释放 LSM 状态的读锁
    if memtable_reaches_capacity_on_put {
        let state_lock = self.state_lock.lock();
        if /* 再次检查当前内存表达到容量 */ {
            self.freeze_memtable(&state_lock)?;
        }
    }
}
}

你将在未来的章节中经常看到这种模式。例如，对于 L0 刷新：

#![allow(unused)]
fn main() {
fn force_flush_next_imm_memtable(&self) {
    let state_lock = self.state_lock.lock();
    // 获取最旧的内存表并释放 LSM 状态的读锁
    // 将内容写入磁盘
    // 获取 LSM 状态的写锁并更新状态
}
}

这确保只有一个线程能够修改 LSM 状态，同时仍然允许对 LSM 存储的并发访问。

在此任务中，你需要修改 put 和 delete 以尊重内存表的软容量限制。当达到限制时，调用 force_freeze_memtable 来冻结内存表。注意，我们没有针对这种并发场景的测试用例，你需要自己考虑所有可能的竞态条件。此外，记得检查锁区域以确保关键部分是最小必需的。

你可以简单地将下一个内存表 id 分配为 self.next_sst_id()。注意，imm_memtables 从最新的内存表到最早的内存表存储内存表。也就是说，imm_memtables.first() 应该是最后冻结的内存表。

任务 4：读取路径 - Get

在此任务中，你需要修改：

src/lsm_storage.rs

现在你有了多个内存表，你可以修改读取路径 get 函数以获取键的最新版本。确保你从最新的内存表到最早的内存表探测内存表。

测试你的理解

为什么内存表不提供 delete API？
内存表存储所有写操作而不是仅存储键的最新版本是否有意义？例如，用户将 a->1、a->2 和 a->3 放入同一个内存表。
是否可以使用其他数据结构作为 LSM 中的内存表？使用跳表的优缺点是什么？
为什么我们需要 state 和 state_lock 的组合？我们能否只使用 state.read() 和 state.write()？
存储和探测内存表的顺序为什么重要？如果一个键出现在多个内存表中，你应该向用户返回哪个版本？
内存表的内存布局是否高效/是否具有良好的数据局部性？（思考 Byte 是如何实现并存储在跳表中的…）有哪些可能的优化可以使内存表更高效？
我们在这个课程中使用 parking_lot 锁。它的读写锁是公平锁吗？如果有一个写者等待现有读者停止，尝试获取锁的读者可能会发生什么？
冻结内存表后，是否可能某些线程仍然持有旧的 LSM 状态并写入这些不可变内存表？你的解决方案如何防止这种情况发生？
有几个地方你可能首先获取状态的读锁，然后释放它并获取写锁（这两个操作可能在不同的函数中，但由于一个函数调用另一个而顺序发生）。这与直接将读锁升级为写锁有何不同？是否有必要升级而不是获取和释放，升级的成本是什么？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

更多内存表格式。 你可以实现其他内存表格式。例如，BTree 内存表、向量内存表和 ART 内存表。

合并迭代器

Chapter Overview

在本章中，你将：

实现内存表迭代器。
实现合并迭代器。
为内存表实现 LSM 读取路径 scan。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 1 --day 2
cargo x scheck

任务 1：内存表迭代器

在本章中，我们将实现 LSM scan 接口。scan 使用迭代器 API 按顺序返回一系列键值对。在上一章中，你已经实现了 get API 和创建不可变内存表的逻辑，你的 LSM 状态现在应该有多个内存表。你需要首先在单个内存表上创建迭代器，然后在所有内存表上创建合并迭代器，最后为迭代器实现范围限制。

在此任务中，你需要修改：

src/mem_table.rs

所有 LSM 迭代器都实现 StorageIterator trait。它有 4 个函数：key、value、next 和 is_valid。如果你熟悉 Rust 标准库的 Iterator trait，你可能会发现 StorageIterator 有点不同。相反，StorageIterator 采用基于游标的 API，这是数据库系统中常见的设计模式，尤其受到 RocksDB 迭代器的启发（参见 iterator_base.h 和 iterator.h 作为参考）。

当迭代器创建时，它的游标会停在某个元素上，key / value 将返回内存表/块/SST 中满足起始条件（即起始键）的第一个键。这两个接口将返回一个 &[u8] 以避免复制。

从调用者的角度来看，典型的使用模式是：

#![allow(unused)]
fn main() {
let mut iter: impl StorageIterator = ...;
while iter.is_valid() {
    let key = iter.key();
    let value = iter.value();
    // 处理键和值
    iter.next()?; // 前进到下一个项目，处理潜在错误
}
}

StorageIterator 的核心方法语义不同：

next()：此方法仅负责尝试将游标移动到下一个元素。它返回一个 Result 来报告在此前进过程中遇到的任何错误（例如 I/O 问题）。它不固有地保证新位置有效，只保证尝试移动。
is_valid()：此方法指示迭代器的当前游标是否指向有效的数据元素。它不推进迭代器。

因此，作为 StorageIterator 的实现者，在每次调用 next() 之后（即使它成功且 next() 操作本身没有错误），你有责任更新内部状态，以便 is_valid() 正确反映新游标位置是否实际指向有效项目。

总之，next 将游标移动到下一个位置。is_valid 返回迭代器是否已到达末尾或出错。你可以假设 next 只会在 is_valid 返回 true 时被调用。将有一个 FusedIterator 包装器，用于在迭代器无效时阻止对 next 的调用，以避免用户误用迭代器。

回到内存表迭代器。你应该已经发现迭代器没有任何与之关联的生命周期。想象一下，你创建一个 Vec<u64> 并调用 vec.iter()，迭代器类型将类似于 VecIterator<'a>，其中 'a 是 vec 对象的生命周期。这同样适用于 SkipMap，其 iter API 返回一个带有生命周期的迭代器。然而，在我们的情况下，我们不希望迭代器上有这样的生命周期，以避免使系统过于复杂（并且难以编译…）。

如果迭代器没有生命周期泛型参数，我们应该确保每当使用迭代器时，底层跳表对象不会被释放。实现这一点的唯一方法是将 Arc<SkipMap> 对象放入迭代器本身。要定义这样的结构：

#![allow(unused)]
fn main() {
pub struct MemtableIterator {
    map: Arc<SkipMap<Bytes, Bytes>>,
    iter: SkipMapRangeIter<'???>,
}
}

好的，这里有问题：我们想表达迭代器的生命周期与结构中的 map 相同。我们该怎么做？

这是你在这个课程中遇到的第一个也是最棘手的 Rust 语言问题——自引用结构。如果可以写这样的东西：

#![allow(unused)]
fn main() {
pub struct MemtableIterator { // <- 带有生命周期 'this
    map: Arc<SkipMap<Bytes, Bytes>>,
    iter: SkipMapRangeIter<'this>,
}
}

那么问题就解决了！你可以借助一些第三方库如 ouroboros 来实现。它提供了一种定义自引用结构的简单方法。也可以使用不安全的 Rust 来实现（实际上，ouroboros 本身在内部使用不安全的 Rust…）

我们已利用 ouroboros 为你定义了自引用的 MemtableIterator 字段。你需要基于这个提供的结构实现 MemtableIterator 逻辑和 Memtable::scan API。

任务 2：合并迭代器

在此任务中，你需要修改：

src/iterators/merge_iterator.rs

现在你有了多个内存表，你将创建多个内存表迭代器。你需要合并来自内存表的结果，并将每个键的最新版本返回给用户。

MergeIterator 在内部维护一个二叉堆。考虑将 n 个有序序列（我们的迭代器）合并为单个有序输出的挑战；二叉堆在这里很自然，因为它有效地帮助识别哪个序列当前持有整体最小的元素。你会看到二叉堆的排序方式是，具有最低头部键值的迭代器排在前面。当多个迭代器具有相同的头部键值时，最新的迭代器排在前面。注意，你需要处理错误（即当迭代器无效时），并确保键值对的最新版本出现。

例如，如果我们有以下数据：

iter1: b->del, c->4, d->5
iter2: a->1, b->2, c->3
iter3: e->4

合并迭代器输出的序列应该是：

a->1, b->del, c->4, d->5, e->4

合并迭代器的构造函数接受一个迭代器向量。我们假设索引较低的迭代器（即第一个）具有最新的数据。

使用 Rust 二叉堆时，你可能会发现 peek_mut 函数很有用。

#![allow(unused)]
fn main() {
let Some(mut inner) = heap.peek_mut() {
    *inner += 1; // <- 对内部项目进行一些修改
}
// 当 PeekMut 引用被丢弃时，二叉堆会自动重新排序。

let Some(mut inner) = heap.peek_mut() {
    PeekMut::pop(inner) // <- 从堆中弹出它
}
}

一个常见的陷阱是错误处理。例如：

#![allow(unused)]
fn main() {
let Some(mut inner_iter) = self.iters.peek_mut() {
    inner_iter.next()?; // <- 会导致问题
}
}

如果 next 返回错误（即由于磁盘故障、网络故障、校验和错误等），它就不再有效。然而，当我们退出 if 条件并将错误返回给调用者时，PeekMut 的 drop 将尝试在堆内移动元素，这会导致访问无效的迭代器。因此，你需要自己处理所有错误，而不是在 PeekMut 的作用域内使用 ?。

我们想尽可能避免动态分发，因此我们在系统中不使用 Box<dyn StorageIterator>。相反，我们更喜欢使用泛型进行静态分发。还要注意 StorageIterator 使用泛型关联类型（GAT），因此它可以同时支持 KeySlice 和 &[u8] 作为键类型。我们将在第 3 周将时间戳添加到 KeySlice 中，现在使用单独的类型可以使过渡更平滑。

从本节开始，我们将使用 Key<T> 来表示 LSM 键类型，并在类型系统中将它们与值区分开来。你应该使用 Key<T> 提供的 API，而不是直接访问内部值。我们将在第 3 部分向此键类型添加时间戳，使用键抽象将使过渡更平滑。目前，KeySlice 等同于 &[u8]，KeyVec 等同于 Vec<u8>，KeyBytes 等同于 Bytes。

任务 3：LSM 迭代器 + 融合迭代器

在此任务中，你需要修改：

src/lsm_iterator.rs

我们使用 LsmIterator 结构来表示内部 LSM 迭代器。在整个课程中，当更多迭代器添加到系统中时，你将需要多次修改此结构。目前，因为我们只有多个内存表，它应该定义为：

#![allow(unused)]
fn main() {
type LsmIteratorInner = MergeIterator<MemTableIterator>;
}

你可以继续实现 LsmIterator 结构，它调用相应的内部迭代器，并跳过已删除的键。

我们在此任务中不测试 LsmIterator。任务 4 中将有一个集成测试。

然后，我们希望在迭代器上提供额外的安全性，以避免用户误用它们。当迭代器无效时，用户不应调用 key、value 或 next。同时，如果 next 返回错误，他们不应再使用迭代器。FusedIterator 是迭代器的包装器，用于规范化所有迭代器的行为。你可以继续自己实现它。

任务 4：读取路径 - Scan

在此任务中，你需要修改：

src/lsm_storage.rs

我们终于到了——使用你实现的所有迭代器，你终于可以实现 LSM 引擎的 scan 接口了。你可以简单地用内存表迭代器构造一个 LSM 迭代器（记得将最新的内存表放在合并迭代器的前面），你的存储引擎将能够处理扫描请求。

测试你的理解

使用你的合并迭代器的时间/空间复杂度是多少？
为什么我们需要自引用结构用于内存表迭代器？
如果一个键被删除（有一个删除墓碑），你需要将其返回给用户吗？你在哪里处理了这个逻辑？
如果一个键有多个版本，用户会看到所有版本吗？你在哪里处理了这个逻辑？
如果我们想摆脱自引用结构并在内存表迭代器上有一个生命周期（即 MemtableIterator<'a>，其中 'a = 内存表或 LsmStorageInner 生命周期），是否仍然可以实现 scan 功能？
如果（1）我们在跳表内存表上创建一个迭代器（2）有人向内存表中插入新键（3）迭代器会看到新键吗？
如果你的键比较器不能给二叉堆实现提供稳定的顺序会发生什么？
为什么我们需要确保合并迭代器按迭代器构造顺序返回数据？
是否可以为 LSM 迭代器实现 Rust 风格的迭代器（即 next(&self) -> (Key, Value)）？优缺点是什么？
scan 接口类似于 fn scan(&self, lower: Bound<&[u8]>, upper: Bound<&[u8]>)。如何使此 API 与 Rust 风格的范围（即 key_a..key_b）兼容？如果你实现了这个，尝试将完整范围 .. 传递给接口，看看会发生什么。
起始代码提供了合并迭代器接口来存储 Box<I> 而不是 I。这背后的原因可能是什么？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

前台迭代器。 在本课程中，我们假设所有操作都很短，因此我们可以在迭代器中持有对内存表的引用。如果用户长时间持有迭代器，整个内存表（可能为 256MB）将保留在内存中，即使它已被刷新到磁盘。为了解决这个问题，我们可以向用户提供 ForegroundIterator / LongIterator。迭代器将定期创建新的底层存储迭代器，以便允许资源的垃圾回收。

块

Chapter Overview

在本章中，你将：

实现 SST 块编码。
实现 SST 块解码和块迭代器。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 1 --day 3
cargo x scheck

任务 1：块构建器

在前两章中，你已经实现了 LSM 存储引擎的所有内存结构。现在是时候构建磁盘结构了。磁盘结构的基本单位是块。块通常为 4-KB 大小（大小可能因存储介质而异），这相当于操作系统中的页面大小和 SSD 上的页面大小。块存储有序的键值对。SST 由多个块组成。当内存表数量超过系统限制时，它将把内存表刷新为 SST。在本章中，你将实现块的编码和解码。

在此任务中，你需要修改：

src/block/builder.rs
src/block.rs

我们课程中的块编码格式如下：

----------------------------------------------------------------------------------------------------
|             Data Section             |              Offset Section             |      Extra      |
----------------------------------------------------------------------------------------------------
| Entry #1 | Entry #2 | ... | Entry #N | Offset #1 | Offset #2 | ... | Offset #N | num_of_elements |
----------------------------------------------------------------------------------------------------

每个条目是一个键值对。

-----------------------------------------------------------------------
|                           Entry #1                            | ... |
-----------------------------------------------------------------------
| key_len (2B) | key (keylen) | value_len (2B) | value (varlen) | ... |
-----------------------------------------------------------------------

键长度和值长度都是 2 字节，这意味着它们的最大长度为 65535。（内部存储为 u16）

我们假设键永远不会为空，值可以为空。空值意味着在系统其他部分的视图中，相应的键已被删除。对于 BlockBuilder 和 BlockIterator，我们只是按原样处理空值。

在每个块的末尾，我们将存储每个条目的偏移量和条目总数。例如，如果第一个条目位于块的第 0 个位置，第二个条目位于块的第 12 个位置。

------------------------------
|offset|offset|num_of_elements|
------------------------------
|   0  |  12  |       2       |
------------------------------

块的页脚将如上所示。每个数字都存储为 u16。

块有一个大小限制，即 target_size。除非第一个键值对超过目标块大小，否则你应该确保编码后的块大小始终小于或等于 target_size。（在提供的代码中，这里的 target_size 本质上是 block_size）

当调用 build 时，BlockBuilder 将生成数据部分和未编码的条目偏移量。这些信息将存储在 Block 结构中。由于键值条目以原始格式存储，偏移量存储在单独的向量中，这减少了解码数据时不必要的内存分配和处理开销——你需要做的只是将原始块数据复制到 data 向量中，并每 2 字节解码条目偏移量，而不是创建类似 Vec<(Vec<u8>, Vec<u8>)> 的东西来在内存中存储一个块中的所有键值对。这种紧凑的内存布局非常高效。

在 Block::encode 和 Block::decode 中，你需要按照上述格式编码/解码块。

任务 2：块迭代器

在此任务中，你需要修改：

src/block/iterator.rs

现在我们有了编码的块，我们需要实现 BlockIterator 接口，以便用户可以查找/扫描块中的键。

BlockIterator 可以用 Arc<Block> 创建。如果调用 create_and_seek_to_first，它将被定位在块中的第一个键。如果调用 create_and_seek_to_key，迭代器将被定位在第一个 >= 提供的键的键。例如，如果 1, 3, 5 在一个块中。

#![allow(unused)]
fn main() {
let mut iter = BlockIterator::create_and_seek_to_key(block, b"2");
assert_eq!(iter.key(), b"3");
}

上面的 seek 2 将使迭代器定位在 2 的下一个可用键，在这种情况下是 3。

迭代器应该从块中复制 key 并将其存储在迭代器内部（未来我们将有键压缩，你将不得不这样做）。对于值，你应该只存储迭代器中的开始/结束偏移量，而不复制它们。

当调用 next 时，迭代器将移动到下一个位置。如果我们到达块的末尾，我们可以将 key 设置为空并从 is_valid 返回 false，以便调用者可以在可能的情况下切换到另一个块。

测试你的理解

在块中查找键的时间复杂度是多少？
在你的实现中，当你查找一个不存在的键时，游标停在哪里？
所以 Block 只是原始数据的向量和偏移量的向量。我们能否将它们更改为 Byte 和 Arc<[u16]>，并将所有迭代器接口更改为返回 Byte 而不是 &[u8]？（假设我们使用 Byte::slice 返回块的切片而不复制。）优缺点是什么？
在你的实现中，写入块中的数字的字节序是什么？
你的实现是否容易受到恶意构建的块的影响？如果用户故意构造一个无效的块，是否会有无效的内存访问或 OOM？
一个块可以包含重复的键吗？
如果用户添加一个大于目标块大小的键会发生什么？
考虑 LSM 引擎构建在对象存储服务（S3）上的情况。你将如何优化/更改块格式和参数以使其适合此类服务？
你喜欢珍珠奶茶吗？为什么喜欢或不喜欢？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

反向迭代器。 你可以为你的 BlockIterator 实现 prev，以便你能够反向迭代键值对。你也可以有反向合并迭代器和反向 SST 迭代器（在下一章中）的变体，以便你的存储引擎可以进行反向扫描。

排序字符串表（SST）

Chapter Overview

在本章中，你将：

实现 SST 编码和元数据编码。
实现 SST 解码和迭代器。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 1 --day 4
cargo x scheck

任务 1：SST 构建器

在此任务中，你需要修改：

src/table/builder.rs
src/table.rs

SST 由存储在磁盘上的数据块和索引块组成。通常，数据块是延迟加载的——直到用户请求时才会加载到内存中。索引块也可以按需加载，但在本课程中，我们做出简单假设，即所有 SST 索引块（元块）都可以放入内存（实际上我们没有专门的索引块实现）。通常，SST 文件大小为 256MB。

SST 构建器类似于块构建器——用户将在构建器上调用 add。你应该在 SST 构建器内部维护一个 BlockBuilder，并在必要时拆分块。此外，你还需要维护块元数据 BlockMeta，其中包括每个块中的第一个/最后一个键以及每个块的偏移量。build 函数将编码 SST，使用 FileObject::create 将所有内容写入磁盘，并返回一个 SsTable 对象。

SST 的编码如下：

-------------------------------------------------------------------------------------------
|         Block Section         |          Meta Section         |          Extra          |
-------------------------------------------------------------------------------------------
| data block | ... | data block |            metadata           | meta block offset (u32) |
-------------------------------------------------------------------------------------------

你还需要实现 SsTableBuilder 的 estimated_size 函数，以便调用者知道何时可以开始新的 SST 来写入数据。该函数不需要非常准确。鉴于数据块包含的数据比元块多得多，我们可以简单地返回数据块的大小作为 estimated_size。

除了 SST 构建器，你还需要完成块元数据的编码/解码，以便 SsTableBuilder::build 可以生成有效的 SST 文件。

任务 2：SST 迭代器

在此任务中，你需要修改：

src/table/iterator.rs
src/table.rs

与 BlockIterator 类似，你需要在 SST 上实现一个迭代器。注意，你应该按需加载数据。例如，如果你的迭代器在块 1 处，它不应该在内存中持有任何其他块内容，直到它到达下一个块。

SsTableIterator 应该实现 StorageIterator trait，以便将来可以与其他迭代器组合。

需要注意的一点是 seek_to_key 函数。基本上，你需要在块元数据上进行二分查找，以找到可能包含该键的块。该键可能不存在于 LSM 树中，因此块迭代器在查找后可能立即无效。例如：

--------------------------------------
| block 1 | block 2 |   block meta   |
--------------------------------------
| a, b, c | e, f, g | 1: a/c, 2: e/g |
--------------------------------------

我们建议仅使用每个块的第一个键进行二分查找，以减少实现的复杂性。如果我们在该 SST 中执行 seek(b)，这很简单——使用二分查找，我们可以知道块 1 包含键 a <= keys < e。因此，我们加载块 1 并将块迭代器查找到相应位置。

但是如果我们执行 seek(d)，我们将定位到块 1，如果我们只使用第一个键作为二分查找标准，但在块 1 中查找 d 将到达块的末尾。因此，我们应该在查找后检查迭代器是否无效，并在必要时切换到下一个块。或者你可以利用最后一个键元数据直接定位到正确的块，这取决于你。

任务 3：块缓存

在此任务中，你需要修改：

src/table/iterator.rs
src/table.rs

你可以在 SsTable 上实现一个新的 read_block_cached 函数。

我们使用 moka-rs 作为我们的块缓存实现。块以 (sst_id, block_id) 作为缓存键进行缓存。你可以使用 try_get_with 从缓存中获取块（如果缓存命中）/填充缓存（如果缓存未命中）。如果有多个请求读取同一个块且缓存未命中，try_get_with 将只向磁盘发出单个读取请求，并将结果广播给所有请求。

此时，你可以将表迭代器更改为使用 read_block_cached 而不是 read_block，以利用块缓存。

测试你的理解

在 SST 中查找键的时间复杂度是多少？
在你的实现中，当你查找一个不存在的键时，游标停在哪里？
是否可能（或必要）对 SST 文件进行原地更新？
SST 通常很大（例如 256MB）。在这种情况下，复制/扩展 Vec 的成本将很高。你的实现是否为 SST 构建器预先分配了足够的空间？你是如何实现的？
查看 moka 块缓存，为什么它返回 Arc<Error> 而不是原始的 Error？
使用块缓存是否保证内存中最多有固定数量的块？例如，如果你有一个 4GB 的 moka 块缓存和 4KB 的块大小，内存中是否会有超过 4GB/4KB 数量的块同时存在？
是否可以在 LSM 引擎中存储列式数据（即 100 个整数列的表）？当前的 SST 格式仍然是一个好的选择吗？
考虑 LSM 引擎构建在对象存储服务（即 S3）上的情况。你将如何优化/更改 SST 格式/参数和块缓存以使其适合此类服务？
目前，我们将所有 SST 的索引加载到内存中。假设你为索引保留了 16GB 内存，你能估计你的 LSM 系统可以支持的数据库的最大大小吗？（这就是为什么你需要索引缓存！）

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

探索不同的 SST 编码和布局。 例如，在 Lethe: Enabling Efficient Deletes in LSMs 论文中，作者向 SST 添加了辅助键支持。
- 或者你可以使用 B+ 树作为 SST 格式，而不是排序块。
索引块。 将块索引和块元数据拆分为索引块，并按需加载它们。
索引缓存。 为索引使用单独的缓存，与数据块缓存分开。
I/O 优化。 将块对齐到 4KB 边界，并使用直接 I/O 绕过系统页面缓存。

读取路径

Chapter Overview

在本章中，你将：

将 SST 集成到 LSM 读取路径中。
使用 SST 实现 LSM 读取路径 get。
使用 SST 实现 LSM 读取路径 scan。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 1 --day 5
cargo x scheck

任务 1：双合并迭代器

在此任务中，你需要修改：

src/iterators/two_merge_iterator.rs

你已经实现了一个合并迭代器，用于合并相同类型的迭代器（即内存表迭代器）。现在我们已经实现了 SST 格式，我们既有磁盘上的 SST 结构，也有内存中的内存表。当我们从存储引擎扫描时，我们需要将来自内存表迭代器和 SST 迭代器的数据合并为一个。在这种情况下，我们需要一个 TwoMergeIterator<X, Y> 来合并两种不同类型的迭代器。

你可以在 two_merge_iterator.rs 中实现 TwoMergeIterator。由于我们这里只有两个迭代器，我们不需要维护二叉堆。相反，我们可以简单地使用一个标志来指示读取哪个迭代器。与 MergeIterator 类似，如果在两个迭代器中都找到相同的键，第一个迭代器优先。

任务 2：读取路径 - Scan

在此任务中，你需要修改：

src/lsm_iterator.rs
src/lsm_storage.rs

实现 TwoMergeIterator 后，我们可以将 LsmIteratorInner 更改为以下类型：

#![allow(unused)]
fn main() {
type LsmIteratorInner =
    TwoMergeIterator<MergeIterator<MemTableIterator>, MergeIterator<SsTableIterator>>;
}

这样我们的 LSM 存储引擎的内部迭代器将是一个结合了内存表和 SST 数据的迭代器。

目前，我们的 SST 迭代器不支持扫描的结束边界。为了解决这个问题，你需要在 LsmIterator 本身内实现此边界检查。这涉及更新 LsmIterator::new 构造函数以接受 end_bound 参数：

#![allow(unused)]
fn main() {
pub(crate) fn new(iter: LsmIteratorInner, end_bound: Bound<Bytes>) -> Result<Self> {}
}

然后你需要修改 LsmIterator 的迭代逻辑，以确保当内部迭代器的键达到或超过指定的 end_bound 时停止。

我们的测试用例将在 l0_sstables 中生成一些内存表和 SST，你需要在此任务中正确扫描所有这些数据。你不需要刷新 SST，直到下一章。因此，你可以继续修改你的 LsmStorageInner::scan 接口，以在所有内存表和 SST 上创建合并迭代器，从而完成存储引擎的读取路径。

因为 SsTableIterator::create 涉及 I/O 操作并且可能很慢，我们不希望在 state 关键部分中执行此操作。因此，你应该首先读取 state 并克隆 LSM 状态快照的 Arc。然后，你应该释放锁。之后，你可以遍历所有 L0 SST 并为每个 SST 创建迭代器，然后创建一个合并迭代器来检索数据。

#![allow(unused)]
fn main() {
fn scan(&self) {
    let snapshot = {
        let guard = self.state.read();
        Arc::clone(&guard)
    };
    // 创建迭代器并查找它们
}
}

在 LSM 存储状态中，我们只在 l0_sstables 向量中存储 SST id。你需要从 sstables 哈希映射中检索实际的 SST 对象。

任务 3：读取路径 - Get

在此任务中，你需要修改：

src/lsm_storage.rs

对于 get 请求，它将在内存表中进行查找，然后在 SST 上进行扫描。你可以在探测所有内存表后，在所有 SST 上创建合并迭代器。你可以查找到用户想要查找的键。查找有两种可能性：键与用户探测的相同，以及键不相同/不存在。只有当键存在且与探测的键相同时，你才应将值返回给用户。你还应该像上一节一样减少状态锁的关键部分。还要记得处理已删除的键。

测试你的理解

考虑用户有一个迭代器迭代整个存储引擎的情况，存储引擎大小为 1TB，因此扫描所有数据需要约 1 小时。如果用户这样做会有什么问题？（这是一个好问题，我们将在课程的不同时间点多次询问它…）
一些 LSM 树存储引擎提供的另一个流行接口是多获取（或向量化获取）。用户可以传递他们想要检索的键列表。接口返回每个键的值。例如，multi_get(vec!["a", "b", "c", "d"]) -> a=1,b=2,c=3,d=4。显然，一个简单的实现是简单地对每个键执行单个 get。你将如何实现多获取接口，以及你可以进行哪些优化以使其更高效？（提示：get 过程中的某些操作只需要对所有键执行一次，除此之外，你可以考虑改进的磁盘 I/O 接口以更好地支持此多获取接口）。

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

动态分发的成本。 实现合并迭代器的 Box<dyn StorageIterator> 版本，并进行基准测试以查看性能差异。
并行查找。 创建合并迭代器需要加载所有底层 SST 的第一个块（当你创建 SSTIterator 时）。你可以并行化创建迭代器的过程。

写入路径

Chapter Overview

在本章中，你将：

使用 L0 刷新实现 LSM 写入路径。
实现正确更新 LSM 状态的逻辑。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 1 --day 6
cargo x scheck

任务 1：将内存表刷新到 SST

此时，我们已经准备好了所有内存中的内容和磁盘上的文件，存储引擎能够读取和合并所有这些结构中的数据。现在，我们将实现将数据从内存移动到磁盘的逻辑（即刷新），并完成 Mini-LSM 第 1 周的课程。

在此任务中，你需要修改：

src/lsm_storage.rs
src/mem_table.rs

你需要修改 LSMStorageInner::force_flush_next_imm_memtable 和 MemTable::flush。在 LSMStorageInner::open 中，如果 LSM 数据库目录不存在，你需要创建它。要将内存表刷新到磁盘，我们需要做三件事：

选择一个内存表进行刷新。
创建一个对应于内存表的 SST 文件。
从不可变内存表列表中移除内存表，并将 SST 文件添加到 L0 SST 中。

我们尚未解释什么是 L0（第 0 级）SST。通常，它们是作为内存表刷新结果直接创建的 SST 文件集。在本课程的第 1 周，我们只在磁盘上有 L0 SST。我们将在第 2 周深入探讨如何使用分层或分级结构在磁盘上高效地组织它们。

注意，创建 SST 文件是一个计算密集且昂贵的操作。同样，我们不希望长时间持有 state 读/写锁，因为它可能会阻塞其他操作并在 LSM 操作中产生巨大的延迟峰值。此外，我们使用 state_lock 互斥锁来序列化 LSM 树中的状态修改操作。在此任务中，你需要仔细思考如何使用这些锁来使 LSM 状态修改无竞态条件，同时最小化关键部分。

我们没有并发测试用例，你需要仔细思考你的实现。此外，请记住，不可变内存表列表中的最后一个内存表是最早的，也是你应该刷新的那个。

剧透：刷新 L0 伪代码

#![allow(unused)]
fn main() {
fn flush_l0(&self) {
    let _state_lock = self.state_lock.lock();

    let memtable_to_flush;
    let snapshot = {
        let guard = self.state.read();
        memtable_to_flush = guard.imm_memtables.last();
    };

    let sst = memtable_to_flush.flush()?;

    {
        let guard = self.state.write();
        guard.imm_memtables.pop();
        guard.l0_sstables.insert(0, sst);
    };

}
}

任务 2：刷新触发器

在此任务中，你需要修改：

src/lsm_storage.rs
src/compact.rs

当内存中的内存表数量（不可变 + 可变）超过 LSM 存储选项中的 num_memtable_limit 时，你应该将最早的内存表刷新到磁盘。这是由后台的刷新线程完成的。刷新线程将随 MiniLSM 结构启动。我们已经实现了必要的代码来启动线程并正确停止线程。

在此任务中，你需要在 compact.rs 中实现 LsmStorageInner::trigger_flush，并在 lsm_storage.rs 中实现 MiniLsm::close。trigger_flush 将每 50 毫秒执行一次。如果内存表数量超过限制，你应该调用 force_flush_next_imm_memtable 来刷新内存表。当用户调用 close 函数时，你应该等待刷新线程（以及第 2 周的压缩线程）完成。

任务 3：过滤 SST

现在你有了一个完全工作的存储引擎，你可以使用 mini-lsm-cli 与你的存储引擎交互。

cargo run --bin mini-lsm-cli -- --compaction none

然后：

fill 1000 3000
get 2333
flush
fill 1000 3000
get 2333
flush
get 2333
scan 2000 2333

如果你填充更多数据，你可以看到你的刷新线程工作并自动刷新 L0 SST，而无需使用 flush 命令。

最后，在结束本周之前，让我们实现一个简单的优化，在过滤 SST 方面。基于用户提供的键范围，我们可以轻松过滤掉一些不包含键范围的 SST，这样我们就不需要在合并迭代器中读取它们。

在此任务中，你需要修改：

src/lsm_storage.rs
src/iterators/*
src/lsm_iterator.rs

你需要更改读取路径函数，以跳过不可能包含键/键范围的 SST。你需要为迭代器实现 num_active_iterators，以便测试用例可以检查你的实现是否正确。对于 MergeIterator 和 TwoMergeIterator，它是所有子迭代器的 num_active_iterators 之和。注意，如果你没有修改 MergeIterator 起始代码中的字段，记得也要考虑 MergeIterator::current。对于 LsmIterator 和 FusedIterator，只需从内部迭代器返回活动迭代器的数量。

你可以实现像 range_overlap 和 key_within 这样的辅助函数来简化你的代码。

测试你的理解

如果用户请求删除一个键两次会发生什么？
当迭代器初始化时，同时加载到内存中的内存（或块数）是多少？
一些疯狂的用户想要分叉他们的 LSM 树。他们想要启动引擎以摄取一些数据，然后分叉它，以便他们获得两个相同的数据集，然后分别对它们进行操作。一个简单但低效的实现方法是简单地将所有 SST 和内存结构复制到一个新目录并启动引擎。然而，请注意，我们从不修改磁盘上的文件，实际上我们可以重用父引擎的 SST 文件。你认为如何在不复制数据的情况下高效地实现此分叉功能？（查看 Neon Branching）。
想象你正在构建一个多租户 LSM 系统，在单个 128GB 内存的机器上托管 10k 个数据库。内存表大小限制设置为 256MB。对于此设置，你需要多少内存用于内存表？
- 显然，你没有足够的内存用于所有这些内存表。假设每个用户仍然有自己的内存表，你如何设计内存表刷新策略以使其工作？让所有这些用户共享同一个内存表（即通过将租户 ID 编码为键前缀）是否有意义？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

实现写入/L0 暂停。 当内存表数量超过最大数量太多时，你可以阻止用户写入存储引擎。你也可以在第 2 周实现压缩后为 L0 表实现写入暂停。
前缀扫描。 你可以通过实现前缀扫描接口并使用前缀信息来过滤更多 SST。

零食时间：SST 优化

Chapter Overview

在上一章中，你已经构建了一个支持 get/scan/put 的存储引擎。在本周结束时，我们将实现一些简单但重要的 SST 格式优化。欢迎来到 Mini-LSM 第 1 周的零食时间！

在本章中，你将：

在 SST 上实现布隆过滤器并集成到 LSM 读取路径 get 中。
在 SST 块格式中实现键压缩。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 1 --day 7
cargo x scheck

任务 1：布隆过滤器

布隆过滤器是维护一组键的概率数据结构。你可以向布隆过滤器添加键，并且你可以知道添加到布隆过滤器中的键集中哪些键可能存在/一定不存在。

你通常需要一个哈希函数来构建布隆过滤器，一个键可以有多个哈希值。让我们看下面的例子。假设我们已经有一些键的哈希值，并且布隆过滤器有 7 位。

[注意：如果你想更好地理解布隆过滤器，请查看这里]

hash1 = ((character - a) * 13) % 7
hash2 = ((character - a) * 11) % 7
b -> 6 4
c -> 5 1
d -> 4 5
e -> 3 2
g -> 1 3
h -> 0 0

如果我们插入 b, c, d 到 7 位布隆过滤器中，我们将得到：

    bit  0123456
insert b     1 1
insert c  1   1
insert d     11
result   0101111

当探测布隆过滤器时，我们为键生成哈希值，并查看相应的位是否已设置。如果所有位都设置为 true，则该键可能存在于布隆过滤器中。否则，该键一定不存在于布隆过滤器中。

对于 e -> 3 2，由于位 2 未设置，它不应在原始集合中。对于 g -> 1 3，因为两个位都已设置，它可能存在或不存在于集合中。对于 h -> 0 0，两个位（实际上是一个位）都未设置，因此它不应在原始集合中。

b -> 可能（实际：是）
c -> 可能（实际：是）
d -> 可能（实际：是）
e -> 一定不（实际：否）
g -> 可能（实际：否）
h -> 一定不（实际：否）

记住在上一章结束时，我们基于键范围实现了 SST 过滤。现在，在 get 读取路径上，我们也可以使用布隆过滤器来忽略不包含用户想要查找的键的 SST，从而减少需要从磁盘读取的文件数量。

在此任务中，你需要修改：

src/table/bloom.rs

在实现中，你将从键哈希（u32 数字）构建布隆过滤器。对于每个哈希，你需要设置 k 位。位通过以下方式计算：

#![allow(unused)]
fn main() {
let delta = (h >> 17) | (h << 15); // h 是键哈希
for _ in 0..k {
    // TODO: 使用哈希设置相应的位
    h = h.wrapping_add(delta);
}
}

我们提供了所有用于神奇数学的骨架代码。你只需要实现构建布隆过滤器和探测布隆过滤器的过程。

任务 2：在读取路径上集成布隆过滤器

在此任务中，你需要修改：

src/table/builder.rs
src/table.rs
src/lsm_storage.rs

对于布隆过滤器编码，你可以将布隆过滤器附加到 SST 文件的末尾。你需要在文件末尾存储布隆过滤器偏移量，并相应地计算元偏移量。

-----------------------------------------------------------------------------------------------------
|         Block Section         |                            Meta Section                           |
-----------------------------------------------------------------------------------------------------
| data block | ... | data block | metadata | meta block offset | bloom filter | bloom filter offset |
|                               |  varlen  |         u32       |    varlen    |        u32          |
-----------------------------------------------------------------------------------------------------

我们使用 farmhash 箱来计算键的哈希值。构建 SST 时，你还需要通过使用 farmhash::fingerprint32 计算键哈希来构建布隆过滤器。你需要使用块元编码/解码布隆过滤器。你可以为布隆过滤器选择 0.01 的误报率。除了起始代码中提供的字段外，你可能需要根据需要向结构添加新字段。

之后，你可以修改 get 读取路径以基于布隆过滤器过滤 SST。

我们没有此部分的集成测试，你需要确保你的实现仍然通过所有先前章节的测试。

任务 3：键前缀编码 + 解码

在此任务中，你需要修改：

src/block/builder.rs
src/block/iterator.rs

由于 SST 文件按顺序存储键，用户可能存储相同前缀的键，我们可以在 SST 编码中压缩前缀以节省空间。

我们将当前键与块中的第一个键进行比较。我们按如下方式存储键：

key_overlap_len (u16) | rest_key_len (u16) | key (rest_key_len)

key_overlap_len 表示与块中第一个键相同的字节数。例如，如果我们看到一个记录：5|3|LSM，其中块中的第一个键是 mini-something，我们可以将当前键恢复为 mini-LSM。

完成编码后，你还需要在块迭代器中实现解码。除了起始代码中提供的字段外，你可能需要根据需要向结构添加新字段。

测试你的理解

布隆过滤器如何帮助 SST 过滤过程？它可以告诉你关于键的什么信息？（可能不存在/可能存在/一定存在/一定不存在）
考虑我们需要反向迭代器的情况。我们的键压缩是否影响反向迭代器？
你可以在扫描上使用布隆过滤器吗？
与块中的第一个键相比，对相邻键进行键前缀编码的优缺点可能是什么？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

第 2 周概述：压缩和持久化

Chapter Overview

在上周，你已经实现了 LSM 存储引擎的所有必要结构，你的存储引擎已经支持读写接口。在本周，我们将深入探讨 SST 文件的磁盘组织，并研究在系统中实现性能和成本效率的最佳方式。我们将花 4 天时间学习不同的压缩策略，从最简单到最复杂的，然后实现存储引擎持久化的剩余部分。在本周结束时，你将拥有一个功能齐全且高效的 LSM 存储引擎。

本部分有 7 章（天）：

第 1 天：压缩实现。你将把所有 L0 SST 合并为一个排序运行。
第 2 天：简单分级压缩。你将实现经典的分级压缩算法，并使用压缩模拟器查看其效果。
第 3 天：分层/通用压缩。你将实现 RocksDB 通用压缩算法并理解其优缺点。
第 4 天：分级压缩。你将实现 RocksDB 分级压缩算法。此压缩算法还支持部分压缩，以减少峰值空间使用。
第 5 天：清单。你将在磁盘上存储 LSM 状态并从状态恢复。
第 6 天：预写日志（WAL）。用户请求将同时路由到内存表和 WAL，以便所有操作都将被持久化。
第 7 天：写入批次和校验和。你将实现写入批次 API（为第 3 周 MVCC 做准备）以及所有存储格式的校验和。

压缩和读放大

让我们先谈谈压缩。在上一部分中，你简单地将内存表刷新到 L0 SST。想象一下，你已经写入了千兆字节的数据，现在你有 100 个 SST。每个读取请求（无过滤）将需要从这些 SST 中读取 100 个块。这种放大是读放大——为一个 get 操作需要发送到磁盘的 I/O 请求数量。

为了减少读放大，我们可以将所有 L0 SST 合并为一个更大的结构，这样可能只读取一个 SST 和一个块来检索请求的数据。假设我们仍然有这 100 个 SST，现在，我们对这 100 个 SST 进行归并排序以产生另外 100 个 SST，每个 SST 包含不重叠的键范围。这个过程是压缩，这 100 个不重叠的 SST 是一个排序运行。

为了使这个过程更清晰，让我们看一个具体示例：

SST 1: 键范围 00000 - 键 10000, 1000 个键
SST 2: 键范围 00005 - 键 10005, 1000 个键
SST 3: 键范围 00010 - 键 10010, 1000 个键

我们在 LSM 结构中有 3 个 SST。如果我们需要访问键 02333，我们将需要探测所有这 3 个 SST。如果我们进行压缩，我们可能会得到以下 3 个新 SST：

SST 4: 键范围 00000 - 键 03000, 1000 个键
SST 5: 键范围 03001 - 键 06000, 1000 个键
SST 6: 键范围 06000 - 键 10010, 1000 个键

这 3 个新 SST 是通过合并 SST 1、2 和 3 创建的。我们可以得到一个排序的 3000 个键，然后将它们拆分为 3 个文件，以避免有一个超大的 SST 文件。现在我们的 LSM 状态有 3 个不重叠的 SST，我们只需要访问 SST 4 来找到键 02333。

压缩的两个极端和写放大

因此，从上面的例子中，我们有 2 种处理 LSM 结构的简单方法——完全不进行压缩，以及在新 SST 刷新时始终进行完全压缩。

压缩是一个耗时的操作。它需要从一些文件中读取所有数据，并将相同数量的文件写入磁盘。此操作占用大量 CPU 资源和 I/O 资源。完全不进行压缩会导致高读放大，但不需要写入新文件。始终进行完全压缩减少了读放大，但需要不断重写磁盘上的文件。

刷新到磁盘的内存表数量与写入磁盘的总数据量之比是写放大。也就是说，不压缩的写放大比为 1 倍，因为一旦 SST 刷新到磁盘，它们将留在那里。始终进行压缩具有非常高的写放大。如果我们每次得到一个 SST 都进行完全压缩，写入磁盘的数据量将是刷新 SST 数量的平方。例如，如果我们刷新了 100 个 SST 到磁盘，我们将进行 2 个文件、3 个文件、…、100 个文件的压缩，其中我们实际写入磁盘的总数据量约为 5000 个 SST。在这种情况下写入 100 个 SST 后的写放大将是 50 倍。

一个好的压缩策略可以平衡读放大、写放大和空间放大（我们很快会谈到）。在通用 LSM 存储引擎中，通常不可能找到一种策略能在所有这 3 个因素中实现最低放大，除非引擎可以使用一些特定的数据模式。LSM 的好处是，我们可以在理论上分析压缩策略的放大，并且所有这些事情都在后台发生。我们可以选择压缩策略并动态更改它们的一些参数，以将我们的存储引擎调整到最佳状态。压缩策略都是关于权衡的，基于 LSM 的存储引擎使我们能够在运行时选择要权衡的内容。

行业中的一个典型工作负载是：用户首先批量将数据摄取到存储引擎中，通常在启动产品时每秒千兆字节。然后，系统上线，用户开始在系统上进行小事务。在第一阶段，引擎应该能够快速摄取数据，因此我们可以使用最小化写放大的压缩策略来加速此过程。然后，我们调整压缩算法的参数以使其针对读放大进行优化，并进行完全压缩以重新排序现有数据，以便系统上线时能够稳定运行。

如果工作负载类似于时间序列数据库，用户可能总是按时间填充和截断数据。因此，即使没有压缩，这些仅追加的数据仍然可以在磁盘上具有低放大。因此，在现实生活中，你应该观察用户的模式或特定要求，并使用这些信息来优化你的系统。

压缩策略概述

压缩策略通常旨在控制排序运行的数量，以便将读放大保持在合理的数量。压缩策略通常有两类：分级和分层。

在分层压缩中，引擎将通过合并它们或让新 SST 刷新为新排序运行（一个层）来动态调整排序运行的数量，以最小化写放大。在这种策略中，你通常会看到引擎合并两个大小相等的排序运行。如果压缩策略选择不合并层，则层数可能很高，从而使读放大很高。在本课程中，我们将实现 RocksDB 的通用压缩，这是一种分层压缩策略。

tiered compaction

空间放大

计算空间放大的最直观方法是将 LSM 引擎实际使用的空间除以用户空间使用量（即数据库大小、数据库中的行数等）。引擎将需要存储删除墓碑，有时如果压缩发生不够频繁，同一键的多个版本，从而导致空间放大。

在引擎端，通常很难知道用户存储的确切数据量，除非我们扫描整个数据库并查看引擎中有多少死版本。因此，估计空间放大的一种方法是将总存储文件大小除以最后一级的大小。这种估计方法背后的假设是，在用户填充初始数据后，工作负载的插入和删除率应该相同。我们假设用户端数据大小不变，因此最后一级包含某个时间点的用户数据快照，而上层包含新更改。当压缩将所有内容合并到最后一级时，使用此估计方法我们可以得到 1 倍的空间放大因子。

注意，压缩也占用空间——在压缩完成之前，你不能删除正在压缩的文件。如果你对数据库进行完全压缩，你将需要与当前引擎文件大小一样多的空闲存储空间。

在本部分中，我们将有一个压缩模拟器来帮助你可视化压缩过程和压缩算法的决策。我们提供最少的测试用例来检查压缩算法的属性，你应该密切关注压缩模拟器的统计数据和输出，以了解压缩算法的效果。

持久化

实现压缩算法后，我们将在系统中实现两个关键组件：清单，这是一个存储 LSM 状态的文件；以及 WAL，它在内存表刷新为 SST 之前将内存表数据持久化到磁盘。完成这两个组件后，存储引擎将具有完整的持久化支持，并可用于你的产品。

如果你不想深入探讨压缩，你也可以完成第 2.1 和 2.2 章来实现一个非常简单的分级压缩算法，然后直接进入持久化部分。实现完整的分级压缩和通用压缩不是在第 2 周构建工作存储引擎所必需的。

零食时间

实现压缩和持久化后，我们将有一个简短的章节来实现批量写入接口和校验和。

压缩实现

Chapter Overview

在本章中，你将：

实现合并一些文件并产生新文件的压缩逻辑。
实现更新 LSM 状态和管理文件系统上 SST 文件的逻辑。
更新 LSM 读取路径以整合 LSM 级别。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 2 --day 1
cargo x scheck

在阅读本章之前，查看第 2 周概述可能有助于对压缩有一个总体了解。

任务 1：压缩实现

在此任务中，你将实现执行压缩的核心逻辑——将一组 SST 文件归并排序为一个排序运行。你需要修改：

src/compact.rs

具体来说，force_full_compaction 和 compact 函数。force_full_compaction 是决定压缩哪些文件并更新 LSM 状态的压缩触发器。compact 执行实际的压缩工作，合并一些 SST 文件并返回一组新的 SST 文件。

你的压缩实现应该获取存储引擎中的所有 SST，使用 MergeIterator 对它们进行合并，然后使用 SST 构建器将结果写入新文件。如果文件太大，你需要拆分 SST 文件。压缩完成后，你可以更新 LSM 状态，将所有新的排序运行添加到 LSM 树的第一级。并且，你需要移除 LSM 树中未使用的文件。在你的实现中，SST 应该只存储在两个地方：L0 SST 和 L1 SST。也就是说，LSM 状态中的 levels 结构应该只有一个向量。在 LsmStorageState 中，我们已经初始化 LSM 在 levels 字段中具有 L1。

压缩不应阻塞 L0 刷新，因此你不应在合并文件时持有状态锁。你应该只在压缩过程结束时更新 LSM 状态时持有状态锁，并在完成状态修改后立即释放锁。

你可以假设用户将确保只有一次压缩在进行。force_full_compaction 在任何时候只会在一个线程中被调用。放入第 1 级的 SST 应按其第一个键排序，并且不应有重叠的键范围。

剧透：压缩伪代码

#![allow(unused)]
fn main() {
fn force_full_compaction(&self) {
    let ssts_to_compact = {
        let state = self.state.read();
        state.l0_sstables + state.levels[0]
    };
    let new_ssts = self.compact(FullCompactionTask(ssts_to_compact))?;
    {
        let state_lock = self.state_lock.lock();
        let state = self.state.write();
        state.l0_sstables.remove(/* 正在压缩的那些 */);
        state.levels[0] = new_ssts; // 新 SST 添加到 L1
    };
    std::fs::remove(ssts_to_compact)?;
}
}

在你的压缩实现中，目前只需要处理 FullCompaction，其中任务信息包含你需要压缩的 SST。你还需要确保 SST 的顺序正确，以便键的最新版本被放入新的 SST。

因为我们总是压缩所有 SST，如果我们找到一个键的多个版本，我们可以简单地保留最新的一个。如果最新版本是删除标记，我们不需要将其保留在产生的 SST 文件中。这不适用于接下来几章中的压缩策略。

有一些事情你可能需要考虑。

你的实现如何处理与压缩并行的 L0 刷新？（执行压缩时不持有状态锁，还需要考虑压缩进行时产生的新 L0 文件。）
如果你的实现在压缩完成后立即移除原始 SST 文件，会导致系统出现问题吗？（通常在 macOS/Linux 上不会，因为操作系统在没有任何文件句柄持有之前不会实际删除文件。）

任务 2：连接迭代器

在此任务中，你需要修改：

src/iterators/concat_iterator.rs

现在你已经在系统中创建了排序运行，可以对读取路径进行简单的优化。你并不总是需要为 SST 创建合并迭代器。如果 SST 属于一个排序运行，你可以创建一个连接迭代器，简单地按顺序迭代每个 SST 中的键，因为一个排序运行中的 SST 不包含重叠的键范围，并且它们按第一个键排序。我们不想提前创建所有 SST 迭代器（因为这将导致一个块读取），因此我们只在此迭代器中存储 SST 对象。

任务 3：与读取路径集成

在此任务中，你需要修改：

src/lsm_iterator.rs
src/lsm_storage.rs
src/compact.rs

现在你的 LSM 树有了两级结构，你可以更改读取路径以使用新的连接迭代器来优化读取路径。

你需要更改 LsmStorageIterator 的内部迭代器类型。之后，你可以构造一个双合并迭代器来合并内存表和 L0 SST，以及另一个合并迭代器来合并该迭代器与 L1 连接迭代器。

你也可以更改压缩实现以利用连接迭代器。

你需要为连接迭代器实现 num_active_iterators，以便测试用例可以测试你的实现是否使用了连接迭代器，它应该始终为 1。

要交互式地测试你的实现：

cargo run --bin mini-lsm-cli-ref -- --compaction none # 参考解决方案
cargo run --bin mini-lsm-cli -- --compaction none # 你的解决方案

然后：

fill 1000 3000
flush
fill 1000 3000
flush
full_compaction
fill 1000 3000
flush
full_compaction
get 2333
scan 2000 2333

测试你的理解

读取/写入/空间放大的定义是什么？（这在概述章节中已涵盖）
准确计算读取/写入/空间放大的方法有哪些，估计它们的方法有哪些？
即使用户请求删除一个键，该键仍会占用一些存储空间，这是正确的吗？
鉴于压缩占用大量写入带宽和读取带宽，并可能干扰前台操作，当有大量写入流时推迟压缩是一个好主意。在这种情况下甚至停止/暂停现有的压缩任务是有益的。你对此有何看法？（阅读 SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores 论文！）
为压缩使用/填充块缓存是一个好主意吗？还是在压缩时完全绕过块缓存更好？
在系统中拥有 struct ConcatIterator<I: StorageIterator> 有意义吗？
一些研究人员/工程师提议将压缩卸载到远程服务器或无服务器 lambda 函数。远程压缩的好处是什么，以及远程压缩可能带来的潜在挑战和性能影响是什么？（思考压缩完成时以及下一个读取请求时块缓存会发生什么…）

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

简单压缩策略

Chapter Overview

在本章中，你将：

实现一个简单的分级压缩策略，并在压缩模拟器上进行模拟。
将压缩作为后台任务启动，并在系统中实现压缩触发器。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 2 --day 2
cargo x scheck

在阅读本章之前，查看第 2 周概述可能有助于对压缩有一个总体了解。

任务 1：简单分级压缩

在本章中，我们将实现我们的第一个压缩策略——简单分级压缩。在此任务中，你需要修改：

src/compact/simple_leveled.rs

简单分级压缩类似于原始 LSM 论文的压缩策略。它为 LSM 树维护多个级别。当一个级别（>= L1）太大时，它将合并该级别的所有 SST 与下一级别。压缩策略由 SimpleLeveledCompactionOptions 中定义的 3 个参数控制。

size_ratio_percent：较低级别文件数 / 较高级别文件数。实际上，我们应该计算文件的实际大小。然而，我们简化了方程以使用文件数，以便更容易进行模拟。当比率太低（较高级别有太多文件）时，我们应该触发压缩。
level0_file_num_compaction_trigger：当 L0 中的 SST 数量大于或等于此数字时，触发 L0 和 L1 的压缩。
max_levels：LSM 树中的级别数（不包括 L0）。

假设 size_ratio_percent=200（较低级别应具有较高级别 2 倍的文件数），max_levels=3，level0_file_num_compaction_trigger=2，让我们看下面的例子。

假设引擎刷新了两个 L0 SST。这达到了 level0_file_num_compaction_trigger，你的控制器应触发 L0->L1 压缩。

--- 刷新后 ---
L0 (2): [1, 2]
L1 (0): []
L2 (0): []
L3 (0): []
--- 压缩后 ---
L0 (0): []
L1 (2): [3, 4]
L2 (0): []
L3 (0): []

现在，L2 为空而 L1 有两个文件。L1 和 L2 的大小比率百分比为 (L2/L1) * 100 = (0/2) * 100 = 0 < size_ratio_percent (200)。因此，我们将触发 L1+L2 压缩以将数据推送到更低的 L2。同样适用于 L2，这两个 SST 将在 2 次压缩后被放置在最底层。

--- 压缩后 ---
L0 (0): []
L1 (0): []
L2 (2): [5, 6]
L3 (0): []
--- 压缩后 ---
L0 (0): []
L1 (0): []
L2 (0): []
L3 (2): [7, 8]

继续刷新 SST，我们将发现：

L0 (0): []
L1 (0): []
L2 (2): [13, 14]
L3 (2): [7, 8]

此时，L3/L2= (1 / 1) * 100 = 100 < size_ratio_percent (200)。因此，我们需要触发 L2 和 L3 之间的压缩。

--- 压缩后 ---
L0 (0): []
L1 (0): []
L2 (0): []
L3 (4): [15, 16, 17, 18]

当我们刷新更多 SST 时，我们可能会最终达到以下状态：

--- 刷新后 ---
L0 (2): [19, 20]
L1 (0): []
L2 (0): []
L3 (4): [15, 16, 17, 18]
--- 压缩后 ---
L0 (0): []
L1 (0): []
L2 (2): [23, 24]
L3 (4): [15, 16, 17, 18]

因为 L3/L2 = (4 / 2) * 100 = 200 >= size_ratio_percent (200)，我们不需要合并 L2 和 L3，并将以上述状态结束。简单分级压缩策略总是压缩一个完整级别，并在级别之间保持扇出大小，以便较低级别总是较高级别的某个倍数。

我们已经初始化 LSM 状态以具有 max_level 级别。你应该首先实现 generate_compaction_task，根据上述 3 个标准生成压缩任务。之后，实现 apply_compaction_result。我们建议你先实现 L0 触发器，运行压缩模拟，然后实现大小比率触发器，再运行压缩模拟。要运行压缩模拟：

cargo run --bin compaction-simulator-ref simple # 参考解决方案
cargo run --bin compaction-simulator simple # 你的解决方案

模拟器将刷新一个 L0 SST 到 LSM 状态，运行你的压缩控制器以生成压缩任务，然后应用压缩结果。每次刷新新的 SST 时，它将重复调用控制器，直到不需要调度压缩，因此你应该确保你的压缩任务生成器会收敛。

在你的压缩实现中，你应该尽可能减少活动迭代器的数量（即使用连接迭代器）。此外，记住合并顺序很重要，当出现一个键的多个版本时，你需要确保创建的迭代器以正确的顺序产生键值对。

另外，注意实现中的一些参数是基于 0 的，而一些是基于 1 的。当你使用 level 作为向量中的索引时要小心。

注意：我们没有为此部分提供细粒度的单元测试。你可以运行压缩模拟器并与参考解决方案的输出进行比较，以查看你的实现是否正确。

任务 2：压缩线程

在此任务中，你需要修改：

src/compact.rs

现在你已经实现了压缩策略，你需要在后台线程中运行它，以便在后台压缩文件。在 compact.rs 中，trigger_compaction 将每 50 毫秒被调用，你需要：

生成压缩任务，如果没有任务需要调度，返回 ok。
运行压缩并获取新的 SST 列表。
类似于你在上一章中实现的 force_full_compaction，更新 LSM 状态。

任务 3：与读取路径集成

在此任务中，你需要修改：

src/lsm_storage.rs

现在你有了多个级别的 SST，你可以修改读取路径以包含来自新级别的 SST。你需要更新 scan/get 函数以包含 L1 以下的所有级别。此外，你可能需要再次更改 LsmStorageIterator 内部类型。

要交互式地测试你的实现：

cargo run --bin mini-lsm-cli-ref -- --compaction simple # 参考解决方案
cargo run --bin mini-lsm-cli -- --compaction simple # 你的解决方案

然后：

fill 1000 3000
flush
fill 1000 3000
flush
fill 1000 3000
flush
get 2333
scan 2000 2333

当压缩器触发压缩时，你可以打印一些信息，例如压缩任务信息。

测试你的理解

分级压缩的估计写放大是多少？
分级压缩的估计读放大是多少？
只有当用户请求删除一个键并且它已在最底层被压缩时，该键才会从 LSM 树中清除，这是正确的吗？
定期对 LSM 树进行完全压缩是一个好策略吗？为什么或为什么不？
主动选择一些旧文件/级别进行压缩，即使它们不违反级别放大器，会是一个好选择吗？（查看 Lethe 论文！）
如果存储设备可以实现可持续的 1GB/s 写入吞吐量，并且 LSM 树的写放大为 10 倍，用户可以从 LSM 键值接口获得多少吞吐量？
如果 L2 中有 SST 文件，你可以直接合并 L1 和 L3 吗？它仍然产生正确的结果吗？
到目前为止，我们假设我们的 SST 文件使用单调递增的 id 作为文件名。使用 <level>_<begin_key>_<end_key>.sst 作为 SST 文件名可以吗？这可能会有什么潜在问题？（你可以在第 3 周问自己同样的问题…）
你所在城市最喜欢的珍珠奶茶店是哪家？（如果你在第 1 周第 3 天回答了是…）

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

分层压缩策略

Chapter Overview

在本章中，你将：

实现分层压缩策略并在压缩模拟器上进行模拟。
将分层压缩策略整合到系统中。

我们在本章讨论的分层压缩与 RocksDB 的通用压缩相同。我们将交替使用这两个术语。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 2 --day 3
cargo x scheck

在阅读本章之前，查看第 2 周概述可能有助于对压缩有一个总体了解。

任务 1：通用压缩

在本章中，你将实现 RocksDB 的通用压缩，它属于分层压缩策略家族。类似于简单分级压缩策略，我们在此压缩策略中仅使用文件数作为指标。当我们触发压缩作业时，我们总是包含一个完整的排序运行（层）在压缩作业中。

任务 1.0：前提条件

在此任务中，你需要修改：

src/compact/tiered.rs

在通用压缩中，我们不使用 LSM 状态中的 L0 SST。相反，我们直接将新的 SST 刷新到一个排序运行（称为层）。在 LSM 状态中，levels 现在将包含所有层，其中最低索引是最新刷新的 SST。levels 向量中的每个元素存储一个元组：级别 ID（用作层 ID）和该级别中的 SST。每次刷新 L0 SST 时，你应该将 SST 刷新到向量前面的一个层中。压缩模拟器基于第一个 SST id 生成层 id，你应该在实现中做同样的事情。

通用压缩只会在层数（排序运行）达到 num_tiers 时触发任务。否则，它不会触发任何压缩。

任务 1.1：由空间放大比率触发

通用压缩的第一个触发器是空间放大比率。正如我们在概述章节中讨论的，空间放大可以通过 engine_size / last_level_size 来估计。在我们的实现中，我们通过 除最后一级外的所有级别大小 / 最后一级大小 来计算空间放大比率，以便比率可以缩放到 [0, +∞) 而不是 [1, +∞]。这也与 RocksDB 实现一致。

我们这样计算空间放大比率的原因是因为我们以这样的方式建模引擎：它存储固定数量的用户数据（即假设为 100GB），并且用户通过写入引擎不断更新值。因此，最终，所有键都被推送到最底层，最底层的大小应该等同于数据量（100GB），上层包含尚未压缩到最底层的数据更新。

当 除最后一级外的所有级别大小 / 最后一级大小 >= max_size_amplification_percent * 1% 时，我们需要触发完全压缩。例如，如果我们有一个 LSM 状态如下：

层 3: 1
层 2: 1 ; 除最后一级外的所有级别大小 = 2
层 1: 1 ; 最后一级大小 = 1, 2/1=2

假设 max_size_amplification_percent = 200，我们现在应该触发完全压缩。

实现此触发器后，你可以运行压缩模拟器。你将看到：

cargo run --bin compaction-simulator tiered --iterations 10

=== 迭代 2 ===
--- 刷新后 ---
L3 (1): [3]
L2 (1): [2]
L1 (1): [1]
--- 压缩任务 ---
压缩由空间放大比率触发: 200
L3 [3] L2 [2] L1 [1] -> [4, 5, 6]
--- 压缩后 ---
L4 (3): [3, 2, 1]

使用此触发器，我们只会在达到空间放大比率时触发完全压缩。在模拟结束时，你将看到：

cargo run --bin compaction-simulator tiered

=== 迭代 7 ===
--- 刷新后 ---
L8 (1): [8]
L7 (1): [7]
L6 (1): [6]
L5 (1): [5]
L4 (1): [4]
L3 (1): [3]
L2 (1): [2]
L1 (1): [1]
--- 压缩任务 ---
--- 压缩任务 ---
压缩由空间放大比率触发: 700
L8 [8] L7 [7] L6 [6] L5 [5] L4 [4] L3 [3] L2 [2] L1 [1] -> [9, 10, 11, 12, 13, 14, 15, 16]
--- 压缩后 ---
L9 (8): [8, 7, 6, 5, 4, 3, 2, 1]
--- 压缩任务 ---
此迭代中触发 1 次压缩
--- 统计 ---
写放大: 16/8=2.000x
最大空间使用: 16/8=2.000x
读放大: 1x

=== Iteration 49 ===
--- After Flush ---
L82 (1): [82]
L81 (1): [81]
L80 (1): [80]
L79 (1): [79]
L78 (1): [78]
L77 (1): [77]
L76 (1): [76]
L75 (1): [75]
L74 (1): [74]
L73 (1): [73]
L72 (1): [72]
L71 (1): [71]
L70 (1): [70]
L69 (1): [69]
L68 (1): [68]
L67 (1): [67]
L66 (1): [66]
L65 (1): [65]
L64 (1): [64]
L63 (1): [63]
L62 (1): [62]
L61 (1): [61]
L60 (1): [60]
L59 (1): [59]
L58 (1): [58]
L57 (1): [57]
L33 (24): [32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 9, 10, 11, 12, 13, 14, 15, 16]
--- Compaction Task ---
--- Compaction Task ---
no compaction triggered
--- Statistics ---
Write Amplification: 82/50=1.640x
Maximum Space Usage: 50/50=1.000x
Read Amplification: 27x

压缩模拟器中的 num_tiers 设置为 8。然而，LSM 状态中的层数远超过 8，这导致较大的读放大。

当前触发器仅减少空间放大。我们需要向压缩算法添加新触发器以减少读放大。

任务 1.2：由大小比率触发

下一个触发器是大小比率触发器。该触发器维护层之间的大小比率。从第一层开始，我们计算 此层大小 / 所有先前层的总和。对于第一个遇到的值 > (100 + size_ratio) * 1% 的层，我们将压缩除当前层外的所有先前层。我们只在有超过 min_merge_width 个层要合并时才进行此压缩。

例如，给定以下 LSM 状态，并假设 size_ratio = 1，min_merge_width = 2。当比率值 > 101% 时，我们应该压缩：

层 3: 1
层 2: 1 ; 1 / 1 = 1
层 1: 1 ; 1 / (1 + 1) = 0.5, 未触发压缩

示例 2：

层 3: 1
层 2: 1 ; 1 / 1 = 1
层 1: 3 ; 3 / (1 + 1) = 1.5, 压缩层 2+3

层 4: 2
层 1: 3

示例 3：

层 3: 1
层 2: 2 ; 2 / 1 = 2, 然而，仅压缩一个层没有意义；还要注意 min_merge_width=2
层 1: 4 ; 4 / 3 = 1.33, 压缩层 2+3

层 4: 3
层 1: 4

使用此触发器，你将在压缩模拟器中观察到以下情况：

cargo run --bin compaction-simulator tiered

=== 迭代 49 ===
--- 刷新后 ---
L119 (1): [119]
L118 (1): [118]
L114 (4): [113, 112, 111, 110]
L105 (5): [104, 103, 102, 101, 100]
L94 (6): [93, 92, 91, 90, 89, 88]
L81 (7): [80, 79, 78, 77, 76, 75, 74]
L48 (26): [47, 46, 45, 44, 43, 37, 38, 39, 40, 41, 42, 24, 25, 26, 27, 28, 29, 30, 9, 10, 11, 12, 13, 14, 15, 16]
--- 压缩任务 ---
--- 压缩任务 ---
未触发压缩
--- 统计 ---
写放大: 119/50=2.380x
最大空间使用: 52/50=1.040x
读放大: 7x

将会有更少的 1-SST 层，压缩算法将通过大小比率维护层具有从小到大的大小。然而，当 LSM 状态中有更多 SST 时，仍然会有我们拥有超过 num_tiers 个层的情况。为了限制层数，我们需要另一个触发器。

任务 1.3：减少排序运行

如果之前的触发器都没有产生压缩任务，我们将进行主要压缩，将前 max_merge_tiers 个层的 SST 文件合并为一个层，以减少层数。

启用此压缩触发器后，你将看到：

cargo run --bin compaction-simulator-ref tiered --iterations 200 --size-only

=== 迭代 199 ===
--- 刷新后 ---
级别: 0 1 1 4 5 21 28 140
未触发压缩
--- 统计 ---
写放大: 742/200=3.710x
最大空间使用: 280/200=1.400x
读放大: 7x

注意：我们没有为此部分提供细粒度的单元测试。你可以运行压缩模拟器并与参考解决方案的输出进行比较，以查看你的实现是否正确。

任务 2：与读取路径集成

在此任务中，你需要修改：

src/compact.rs
src/lsm_storage.rs

由于分层压缩不使用 LSM 状态的 L0 级别，你应该直接将内存表刷新到新层，而不是作为 L0 SST。你可以使用 self.compaction_controller.flush_to_l0() 来知道是否刷新到 L0。你可以使用第一个输出 SST id 作为新排序运行的级别/层 id。你还需要修改压缩过程以为分层压缩作业构建合并迭代器。

测试你的理解

层级压缩的估计写放大是多少？（好吧，这很难估计…但如果没有最后的减少排序运行触发器呢？）
层级压缩的估计读放大是多少？
与简单分级/分层压缩相比，通用压缩的优缺点是什么？
运行通用压缩需要多少存储空间（与用户数据大小相比）？
如果两个层在 LSM 状态中不相邻，我们可以合并它们吗？
如果压缩速度跟不上分层压缩的 SST 刷新会发生什么？
如果系统并行调度多个压缩任务，可能需要考虑什么？
SSD 也写入自己的日志（基本上它是一个日志结构存储）。如果 SSD 的写放大为 2 倍，整个系统的端到端写放大是多少？相关：ZNS: Avoiding the Block Interface Tax for Flash-based SSDs。
考虑用户选择为分层压缩保留大量排序运行（即 300）的情况。为了使读取路径更快，保留一些数据结构来帮助减少在每个层中为某些键范围查找要读取的 SST 的时间复杂度（即到 O(log n)）是一个好主意吗？注意，通常，你需要在每个排序运行中进行二分查找以找到需要读取的键范围。（查看 Neon 的层映射实现！）

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

层级压缩策略

Chapter Overview

在本章中，你将：

实现层级压缩策略并在压缩模拟器上进行模拟。
将层级压缩策略整合到系统中。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 2 --day 4
cargo x scheck

在阅读本章之前，查看第 2 周概述可能有助于对压缩有一个总体了解。

任务 1：层级压缩

在第 2 周第 2 天，你已经实现了简单的层级压缩策略。然而，该实现存在一些问题：

压缩总是包含一个完整的级别。请注意，在完成压缩之前不能移除旧文件，因此，在压缩进行时，你的存储引擎可能会使用 2 倍的存储空间（如果是完全压缩）。分层压缩存在相同的问题。在本章中，我们将实现部分压缩，即我们从上层选择一个 SST 进行压缩，而不是整个级别。
SST 可能会跨空级别进行压缩。正如你在压缩模拟器中看到的，当 LSM 状态为空，并且引擎刷新一些 L0 SST 时，这些 SST 将首先压缩到 L1，然后从 L1 到 L2，等等。最优策略是直接将 SST 从 L0 放置到尽可能低的级别，以避免不必要的写放大。

在本章中，你将实现一个生产就绪的层级压缩策略。该策略与 RocksDB 的层级压缩相同。你需要修改：

src/compact/leveled.rs

要运行压缩模拟器：

cargo run --bin compaction-simulator leveled

任务 1.1：计算目标大小

在此压缩策略中，你需要知道每个 SST 的第一个/最后一个键以及 SST 的大小。压缩模拟器将为你设置一些模拟 SST 以供访问。

你需要计算级别的目标大小。假设 base_level_size_mb 是 200MB，级别数（除 L0 外）是 6。当 LSM 状态为空时，目标大小将是：

[0 0 0 0 0 200MB]

在底层超过 base_level_size_mb 之前，所有其他中间级别的目标大小都为 0。这个想法是，当数据总量较小时，创建中间级别是浪费的。

当底层达到或超过 base_level_size_mb 时，我们将通过从大小除以 level_size_multiplier 来计算其他级别的目标大小。假设底层包含 300MB 数据，且 level_size_multiplier=10。

0 0 0 0 30MB 300MB

此外，最多一个级别可以在 base_level_size_mb 以下具有正的目标大小。假设我们现在在最后一级有 30GB 的文件，目标大小将是：

0 0 30MB 300MB 3GB 30GB

注意在这种情况下，L1 和 L2 的目标大小为 0，L3 是唯一在 base_level_size_mb 以下具有正目标大小的级别。

任务 1.2：决定基础级别

现在，让我们解决简单层级压缩策略中 SST 可能跨空级别压缩的问题。当我们压缩 L0 SST 与较低级别时，我们不直接将其放入 L1。相反，我们将其与第一个 target size > 0 的级别压缩。例如，当目标级别大小为：

0 0 0 0 30MB 300MB

如果 L0 SST 的数量达到 level0_file_num_compaction_trigger 阈值，我们将压缩 L0 SST 与 L5 SST。

现在，你可以生成 L0 压缩任务并运行压缩模拟器。

--- After Flush ---
L0 (1): [23]
L1 (0): []
L2 (0): []
L3 (2): [19, 20]
L4 (6): [11, 12, 7, 8, 9, 10]

...

--- After Flush ---
L0 (2): [102, 103]
L1 (0): []
L2 (0): []
L3 (18): [42, 65, 86, 87, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 61, 62, 52, 34]
L4 (6): [11, 12, 7, 8, 9, 10]

压缩模拟器中的级别数为 4。因此，SST 应直接刷新到 L3/L4。

任务 1.3：决定级别优先级

现在我们需要处理 L0 以下的压缩。L0 压缩始终具有最高优先级，因此如果达到阈值，应首先压缩 L0 与其他级别。之后，我们可以通过 current_size / target_size 计算每个级别的压缩优先级。我们只压缩此比率 > 1.0 的级别。具有最大比率的级别将被选择与较低级别进行压缩。例如，如果我们有：

L3: 200MB, target_size=20MB
L4: 202MB, target_size=200MB
L5: 1.9GB, target_size=2GB
L6: 20GB, target_size=20GB

压缩的优先级将是：

L3: 200MB/20MB = 10.0
L4: 202MB/200MB = 1.01
L5: 1.9GB/2GB = 0.95

L3 和 L4 需要分别与它们的较低级别压缩，而 L5 不需要。L3 具有较大的比率，因此我们将生成 L3 和 L4 的压缩任务。压缩完成后，我们可能会安排 L4 和 L5 的压缩。

任务 1.4：选择要压缩的 SST

现在，让我们解决简单层级压缩策略中压缩总是包含一个完整级别的问题。当我们决定压缩两个级别时，我们总是从上层的 SST 中选择最旧的 SST。你可以通过比较 SST id 来知道 SST 产生的时间。

还有其他选择压缩 SST 的方法，例如，通过查看删除标记的数量。你可以将此作为额外任务的一部分实现。

选择上层 SST 后，你需要找到较低级别中与上层 SST 键重叠的所有 SST。然后，你可以生成一个压缩任务，其中恰好包含上层的一个 SST 和较低级别的重叠 SST。

压缩完成后，你需要从状态中移除 SST，并将新的 SST 插入到正确的位置。请注意，除了 L0 外，你应该在所有级别中保持 SST id 按第一个键排序。

运行压缩模拟器，你应该看到：

--- After Compaction ---
L0 (0): []
L1 (4): [222, 223, 208, 209]
L2 (5): [206, 196, 207, 212, 165]
L3 (11): [166, 120, 143, 144, 179, 148, 167, 140, 189, 180, 190]
L4 (22): [113, 85, 86, 36, 46, 37, 146, 100, 147, 203, 102, 103, 65, 81, 105, 75, 82, 95, 96, 97, 152, 153]

级别的大小应保持在级别乘数比率以下。压缩任务：

Upper L1 [224.sst 7cd080e..=33d79d04]
Lower L2 [210.sst 1c657df4..=31a00e1b, 211.sst 31a00e1c..=46da9e43] -> [228.sst 7cd080e..=1cd18f74, 229.sst 1cd18f75..=31d616db, 230.sst 31d616dc..=46da9e43]

…应该只包含上层的一个 SST。

注意：我们没有为此部分提供细粒度的单元测试。你可以运行压缩模拟器并与参考解决方案的输出进行比较，以查看你的实现是否正确。

任务 2：与读取路径集成

在此任务中，你需要修改：

src/compact.rs
src/lsm_storage.rs

实现应类似于简单层级压缩。记得更改 get/scan 读取路径和压缩迭代器。

测试你的理解

层级压缩的估计写放大是多少？
层级压缩的估计读放大是多少？
为压缩找到一个好的键分割点可能会减少写放大，还是完全无关紧要？（考虑用户写入以某些前缀开头的键的情况，00 和 01。这两个前缀下的键数量不同，它们的写入模式也不同。如果我们总是可以将 00 和 01 分割到不同的 SST 中…）
想象一个用户之前使用分层（通用）压缩，现在想要迁移到层级压缩。这种迁移可能面临什么挑战？如何进行迁移？
如果我们反向操作，如果用户想要从层级压缩迁移到分层压缩呢？
如果压缩速度跟不上层级压缩的 SST 刷新会发生什么？
如果系统并行调度多个压缩任务，可能需要考虑什么？
层级压缩的峰值存储使用量是多少？与通用压缩相比呢？
较低的 level_size_multiplier 是否总是能获得较低的写放大？
如果完全不使用压缩的用户决定迁移到层级压缩，需要做什么？
有些人建议在将 L0 表推送到较低层之前进行 L0 内部压缩（压缩 L0 表并仍将它们放在 L0 中）。这样做可能有什么好处？（可能相关：PebblesDB SOSP’17）
考虑上层有两个表 [100, 200], [201, 300]，下层有 [50, 150], [151, 250], [251, 350] 的情况。在这种情况下，你仍然想一次压缩上层的一个文件吗？为什么？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

SST 摄取。LSM 树中数据迁移/批量导入的常见优化是要求上游生成其数据的 SST 文件，并直接将这些文件放置在 LSM 状态中，而不经过写入路径。
SST 选择。除了选择最旧的 SST，你可以考虑其他启发式方法来选择要压缩的 SST。

清单

Chapter Overview

在本章中，你将：

实现清单文件的编码和解码。
系统重启时从清单恢复。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 2 --day 5
cargo x scheck

任务 1：清单编码

系统使用清单文件记录引擎中发生的所有操作。目前，只有两种类型：压缩和 SST 刷新。当引擎重启时，它将读取清单文件，重建状态，并加载磁盘上的 SST 文件。

存储 LSM 状态有很多方法。最简单的方法之一是将完整状态存储到 JSON 文件中。每次我们进行压缩或刷新新的 SST 时，我们可以将整个 LSM 状态序列化到文件中。这种方法的问题是，当数据库变得非常大（即 10k SST）时，将清单写入磁盘将非常慢。因此，我们将清单设计为仅追加文件。

在此任务中，你需要修改：

src/manifest.rs

我们使用 JSON 编码清单记录。你可以使用 serde_json::to_vec 将清单记录编码为 json，将其写入清单文件，并进行 fsync。从清单文件读取时，你可以使用 serde_json::Deserializer::from_slice，它将返回记录流。你不需要存储记录长度等，因为 serde_json 可以自动找到记录的分割。

清单格式如下：

| JSON 记录 | JSON 记录 | JSON 记录 | JSON 记录 |

再次注意，我们不记录每个记录有多少字节的信息。

引擎运行几个小时后，清单文件可能会变得非常大。那时，你可以定期压缩清单文件以存储当前快照并截断日志。这是你可以作为额外任务的一部分实现的优化。

任务 2：写入清单

现在你可以继续修改 LSM 引擎以在必要时写入清单。在此任务中，你需要修改：

src/lsm_storage.rs
src/compact.rs

目前，我们只使用两种类型的清单记录：SST 刷新和压缩。SST 刷新记录存储刷新到磁盘的 SST id。压缩记录存储压缩任务和产生的 SST id。每次你将一些新文件写入磁盘时，首先同步文件和存储目录，然后写入清单并同步清单。清单文件应写入 <path>/MANIFEST。

要同步目录，你可以实现 sync_dir 函数，其中可以使用 File::open(dir).sync_all()? 来同步它。在 Linux 上，目录是一个包含目录中文件列表的文件。通过对目录进行 fsync，你将确保如果断电，新写入（或移除）的文件对用户可见。

记得为后台压缩触发器（分级/简单/通用）和用户请求进行强制压缩时都写入压缩清单记录。

任务 3：关闭时刷新

在此任务中，你需要修改：

src/lsm_storage.rs

你需要实现 close 函数。如果 self.options.enable_wal = false（我们将在下一章介绍 WAL），你应该在停止存储引擎之前将所有内存表刷新到磁盘，以便所有用户更改都将被持久化。

任务 4：从状态恢复

在此任务中，你需要修改：

src/lsm_storage.rs

现在，你可以修改 open 函数以从清单文件恢复引擎状态。要恢复它，你需要首先生成需要加载的 SST 列表。你可以通过调用 apply_compaction_result 并恢复 LSM 状态中的 SST id 来做到这一点。之后，你可以迭代状态并加载所有 SST（更新 sstables 哈希映射）。在此过程中，你需要计算最大 SST id 并更新 next_sst_id 字段。之后，你可以使用该 id 创建一个新的内存表，并将 id 递增一。

如果你实现了分级压缩，你可能每次应用压缩结果时都对 SST 进行排序。然而，使用清单恢复，你的排序逻辑将被破坏，因为在恢复过程中，你无法知道每个 SST 的起始键和结束键。为了解决这个问题，你需要读取 apply_compaction_result 函数的 in_recovery 标志。在恢复过程中，你不应尝试检索 SST 的第一个键。LSM 状态恢复且所有 SST 打开后，你可以在恢复过程结束时进行排序。

可选地，你可以在清单中包含每个 SST 的起始键和结束键。此策略用于 RocksDB/BadgerDB，因此你不需要在压缩应用过程中区分恢复模式和正常模式。

你可以使用 mini-lsm-cli 测试你的实现。

cargo run --bin mini-lsm-cli
fill 1000 2000
close
cargo run --bin mini-lsm-cli
get 1500

测试你的理解

你何时需要调用 fsync？为什么需要同步目录？
你需要在哪些地方写入清单？
考虑 LSM 引擎的替代实现，它不使用清单文件。相反，它在每个文件的头部记录级别/层信息，每次重启时扫描存储目录，并仅从目录中存在的文件恢复 LSM 状态。在此实现中是否可能正确维护 LSM 状态，以及这可能有什么问题/挑战？
目前，我们在创建合并迭代器之前创建所有 SST/连接迭代器，这意味着我们必须在开始扫描过程之前将所有级别中第一个 SST 的第一个块加载到内存中。我们在清单中有起始/结束键，是否可以利用此信息延迟数据块的加载，并使返回第一个键值对的时间更快？
是否可以不将层/级别信息存储在清单中？即，我们只在清单中存储拥有的 SST 列表而不包含级别信息，并使用键范围和时间戳信息（SST 元数据）重建层/级别。

额外任务

清单压缩。 当清单文件中的日志数量变得太大时，你可以重写清单文件以仅存储当前快照，并将新日志追加到该文件。
并行打开。 收集要打开的 SST 列表后，你可以并行打开和解码它们，而不是一个一个地做，从而加速恢复过程。

预写日志（WAL）

Chapter Overview

在本章中，你将：

实现预写日志文件的编码和解码。
系统重启时从 WAL 恢复内存表。

要将测试用例复制到起始代码并运行它们：

cargo x copy-test --week 2 --day 6
cargo x scheck

任务 1：WAL 编码

在此任务中，你需要修改：

src/wal.rs

在上一章中，我们已经实现了清单文件，以便 LSM 状态可以被持久化。并且我们实现了 close 函数以在停止引擎之前将所有内存表刷新到 SST。现在，如果系统崩溃（即断电）怎么办？我们可以将内存表修改记录到 WAL（预写日志），并在重启数据库时恢复 WAL。WAL 仅在 self.options.enable_wal = true 时启用。

WAL 编码简单来说就是键值对列表。

| key_len | key | value_len | value |

你还需要实现 recover 函数以读取 WAL 并恢复内存表的状态。

注意，我们使用 BufWriter 来写入 WAL。使用 BufWriter 可以减少进入操作系统的系统调用次数，从而减少写入路径的延迟。当用户修改键时，不保证数据已写入磁盘。相反，引擎只保证在调用 sync 时数据被持久化。为了正确地将数据持久化到磁盘，你需要首先通过调用 flush() 将数据从缓冲写入器刷新到文件对象，然后使用 get_mut().sync_all() 对文件进行 fsync。注意，你只需要在引擎的 sync 被调用时进行 fsync。你不需要每次写入数据时都进行 fsync。

任务 2：集成 WAL

在此任务中，你需要修改：

src/mem_table.rs
src/wal.rs
src/lsm_storage.rs

MemTable 有一个 WAL 字段。如果 wal 字段设置为 Some(wal)，你需要在更新内存表时追加到 WAL。在你的 LSM 引擎中，如果 enable_wal = true，你需要创建 WAL。你还需要在创建新内存表时使用 ManifestRecord::NewMemtable 记录更新清单。

你可以使用 create_with_wal 函数创建带有 WAL 的内存表。WAL 应写入存储目录中的 <memtable_id>.wal。如果此内存表作为 L0 SST 刷新，内存表 id 应与 SST id 相同。

任务 3：从 WAL 恢复

在此任务中，你需要修改：

src/lsm_storage.rs

如果启用了 WAL，你需要在加载数据库时基于 WAL 恢复内存表。你还需要实现数据库的 sync 函数。sync 的基本保证是引擎确定数据已持久化到磁盘（并在重启时将恢复）。为了实现这一点，你可以简单地同步与当前内存表对应的 WAL。

cargo run --bin mini-lsm-cli -- --enable-wal

记得从状态恢复正确的 next_sst_id，应该是 max{内存表 id, sst id} + 1。在你的 close 函数中，如果 enable_wal 设置为 true，你不应将内存表刷新到 SST，因为 WAL 本身提供持久性。你应该等待所有压缩和刷新线程退出后再关闭数据库。

测试你的理解

你应该何时在引擎中调用 fsync？如果你调用 fsync 太频繁（即每次 put 键请求）会发生什么？
在 SSD（固态硬盘）上，fsync 操作通常有多昂贵？
你何时可以告诉用户他们的修改（put/delete）已被持久化？
如何处理 WAL 中的损坏数据？
是否可能设计一个没有 WAL 的 LSM 引擎（即使用 L0 作为 WAL）？这种设计会有什么影响？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

批量写入和校验和

在上一章中，你已经构建了一个完整的基于 LSM 的存储引擎。在本周结束时，我们将实现存储引擎的一些简单但重要的优化。欢迎来到 Mini-LSM 第 2 周的零食时间！

在本章中，你将：

实现批量写入接口。
向块、SST 元数据、清单和 WAL 添加校验和。

注意：我们没有本章的单元测试。只要你通过所有之前的测试并确保校验和在你的文件格式中正确编码，就可以了。

任务 1：写入批次接口

在此任务中，我们将通过添加写入批次 API 为本周的第 3 天做准备。你需要修改：

src/lsm_storage.rs

用户提供 write_batch 以及一批要写入数据库的记录。记录是 WriteBatchRecord<T: AsRef<[u8]>>，因此它可以是 Bytes、&[u8] 或 Vec<u8>。有两种类型的记录：删除和放入。你可以以与 put 和 delete 函数相同的方式处理它们。

之后，你可以重构原始的 put 和 delete 函数以调用 write_batch。

实现此功能后，你应该通过之前章节的所有测试用例。

任务 2：块校验和

在此任务中，你需要在编码 SST 时在每个块的末尾添加块校验和。你需要修改：

src/table/builder.rs
src/table.rs

SST 的格式将更改为：

---------------------------------------------------------------------------------------------------------------------------
|                   Block Section                     |                            Meta Section                           |
---------------------------------------------------------------------------------------------------------------------------
| data block | checksum | ... | data block | checksum | metadata | meta block offset | bloom filter | bloom filter offset |
|   varlen   |    u32   |     |   varlen   |    u32   |  varlen  |         u32       |    varlen    |        u32          |
---------------------------------------------------------------------------------------------------------------------------

我们使用 crc32 作为校验和算法。你可以在构建块后使用 crc32fast::hash 为块生成校验和。

通常，当用户在存储选项中指定目标块大小时，大小应包括块内容和校验和。例如，如果目标块大小为 4096，校验和占用 4 字节，实际块内容目标大小应为 4092。然而，为了避免破坏之前的测试用例并为了简单起见，在我们的课程中，我们仍然使用目标块大小作为目标内容大小，并简单地在块末尾附加校验和。

读取块时，你应该在 read_block 中验证校验和正确生成块内容的切片。实现此功能后，你应该通过之前章节的所有测试用例。

任务 3：SST 元校验和

在此任务中，你需要为布隆过滤器和块元数据添加块校验和：

src/table.rs
src/table/bloom.rs
src/table/builder.rs

----------------------------------------------------------------------------------------------------------
|                                                Meta Section                                            |
----------------------------------------------------------------------------------------------------------
| no. of block | metadata | checksum | meta block offset | bloom filter | checksum | bloom filter offset |
|     u32      |  varlen  |    u32   |        u32        |    varlen    |    u32   |        u32          |
----------------------------------------------------------------------------------------------------------

你需要在 Bloom::encode 和 Bloom::decode 中的布隆过滤器末尾添加校验和。注意，我们的大多数 API 接受实现将写入的现有缓冲区，例如 Bloom::encode。因此，你应该在写入编码内容之前记录布隆过滤器开始的偏移量，并且只校验布隆过滤器本身而不是整个缓冲区。

之后，你可以在块元数据末尾添加校验和。你可能会发现在部分开头添加元数据长度也很有帮助，这样在解码块元数据时更容易知道在哪里停止。

任务 4：WAL 校验和

在此任务中，你需要修改：

src/wal.rs

我们将在预写日志中进行每记录校验和。为此，你有两个选择：

生成键值记录的缓冲区，并使用 crc32fast::hash 一次性计算校验和。
一次写入一个字段（例如，键长度、键切片），并使用 crc32fast::Hasher 在每个字段上增量计算校验和。

这取决于你的选择，你需要选择你自己的冒险。只要正确处理小端序/大端序，两种方法都应产生完全相同的结果。新的 WAL 编码应如下所示：

| key_len | key | value_len | value | checksum |

任务 5：清单校验和

最后，让我们在清单文件上添加校验和。清单类似于 WAL，除了之前我们不存储每个记录的长度。为了使实现更容易，我们现在在记录开头添加记录长度的头部，并在记录末尾添加校验和。

新的清单格式如下：

| len | JSON 记录 | checksum | len | JSON 记录 | checksum | len | JSON 记录 | checksum |

实现所有内容后，你应该通过所有之前的测试用例。我们在本章中没有提供新的测试用例。

测试你的理解

考虑 LSM 存储引擎只提供 write_batch 作为写入接口（而不是单个 put + delete）的情况。是否可以如下实现：有一个带有 mpsc 通道接收器的单个写入线程来获取更改，所有线程将写入批次发送到写入线程。写入线程是写入数据库的唯一点。这种实现的优缺点是什么？（如果你这样做，恭喜你得到了 BadgerDB！）
将所有块校验和一起放在 SST 文件的末尾而不是与块一起存储可以吗？为什么？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

损坏时恢复。 如果存在校验和错误，以安全模式打开数据库，以便无法执行写入，但仍可以检索未损坏的数据。

第 3 周概述：多版本并发控制

在本部分中，你将在前两周构建的 LSM 引擎上实现 MVCC。我们将在键中添加时间戳编码以维护一个键的多个版本，并更改引擎的某些部分以确保旧数据根据是否有用户读取旧版本而被保留或垃圾回收。

本课程中 MVCC 部分的一般方法受到 BadgerDB 的启发并部分基于它。

MVCC 的关键是在存储引擎中存储和访问一个键的多个版本。因此，我们需要将键格式更改为 user_key + timestamp (u64)。在用户界面方面，我们需要新的 API 来帮助用户访问历史版本。总之，我们将向键添加一个单调递增的时间戳。

在前面的部分中，我们假设较新的键在 LSM 树的上层，较旧的键在 LSM 树的下层。在压缩期间，如果在多个级别中找到多个版本，我们只保留键的最新版本，并且压缩过程通过仅合并相邻级别/层来确保较新的键将保留在上层。在 MVCC 实现中，具有较大时间戳的键是最新的键。在压缩期间，只有当没有用户访问数据库的旧版本时，我们才能移除键。虽然不将键的最新版本保留在上层可能仍然为 MVCC LSM 实现产生正确的结果，但在我们的课程中，我们选择保持不变量，并且如果一个键有多个版本，较晚的版本将始终出现在上层。

通常，有两种方式利用支持 MVCC 的存储引擎。如果用户将引擎用作独立组件并且不想手动分配键的时间戳，他们将使用事务 API 从存储引擎存储和检索数据。时间戳对用户是透明的。另一种方式是将存储引擎集成到系统中，用户自己管理时间戳。为了比较这两种方法，我们可以查看它们提供的 API。我们使用 BadgerDB 的术语来描述这两种用法：隐藏时间戳的是非托管模式，给用户完全控制的是托管模式。

托管模式 API

get(key, read_timestamp) -> (value, write_timestamp)
scan(key_range, read_timestamp) -> iterator<key, value, write_timestamp>
put/delete/write_batch(key, timestamp)
set_watermark(timestamp) # 我们很快会讨论水印！

非托管/普通模式 API

get(key) -> value
scan(key_range) -> iterator<key, value>
start_transaction() -> txn
txn.put/delete/write_batch(key, timestamp)

如你所见，托管模式 API 要求用户在操作时提供时间戳。时间戳可能来自某些集中式时间戳系统，或来自其他系统的日志（即 Postgres 逻辑复制日志）。用户需要指定一个水印，这是引擎可以移除的版本以下的时间戳。

对于非托管 API，它与我们之前实现的相同，只是用户需要通过创建事务来写入和读取数据。当用户创建事务时，他们可以获得数据库的一致状态（这是一个快照）。即使其他线程/事务将数据写入数据库，这些数据对正在进行的事务也是不可见的。存储引擎在内部管理时间戳，不向用户暴露。

在本周，我们将首先花 3 天时间对表格式和内存表进行重构。我们将键格式更改为键切片和时间戳。之后，我们将实现必要的 API 以提供一致的快照和事务。

本部分有 7 章（天）：

第 1 天：时间戳键重构。你将更改 key 模块为 MVCC 版本，并重构系统以使用带时间戳的键。
第 2 天：快照读取 - 内存表和时间戳。你将重构内存表和写入路径以支持多版本读取/写入。
第 3 天：快照读取 - 事务 API。你将实现事务 API 并完成读取/写入路径的其余部分，以支持快照读取。
第 4 天：水印和垃圾回收。你将实现水印计算算法，并在压缩时实现垃圾回收以移除旧版本。
第 5 天：事务和乐观并发控制。你将为所有事务创建私有工作空间，并批量提交它们，以便事务的修改对其他事务不可见。
第 6 天：可序列化快照隔离。你将实现 OCC 可序列化检查，以确保对数据库的修改是可序列化的，并中止违反可序列化的事务。
第 7 天：压缩过滤器。在本周结束时，我们将把压缩时垃圾回收逻辑泛化为压缩过滤器，根据用户要求在压缩时移除数据。

时间戳键编码 + 重构

在本章中，你将：

重构你的实现以使用 key+ts 表示。
使你的代码使用新的键表示编译。

要运行测试用例：

cargo x copy-test --week 3 --day 1
cargo x scheck

注意：MVCC 子系统直到第 3 周第 2 天才完全实现。你只需要在本天结束时通过第 3 周第 1 天的测试和所有第 1 周的测试。由于压缩，第 2 周的测试将无法工作。

任务 0：使用 MVCC 键编码

你需要将键编码模块替换为 MVCC 版本。我们从原始键模块中移除了一些接口，并为键实现了新的比较器。如果你遵循了前面章节的说明并且没有在键上使用 into_inner，你应该在所有重构后通过第 3 天的所有测试用例。否则，你需要仔细查看只比较键而不查看时间戳的地方。

具体来说，键类型定义已从：

#![allow(unused)]
fn main() {
pub struct Key<T: AsRef<[u8]>>(T);
}

…更改为：

#![allow(unused)]
fn main() {
pub struct Key<T: AsRef<[u8]>>(T /* 用户键 */, u64 /* 时间戳 */);
}

…其中我们有一个与键关联的时间戳。我们只在系统内部使用此键表示。在用户界面方面，我们不要求用户提供时间戳，因此某些结构在引擎中仍然使用 &[u8] 而不是 KeySlice。我们稍后将介绍需要更改函数签名的地方。目前，你只需要运行：

cp mini-lsm-mvcc/src/key.rs mini-lsm-starter/src/

还有其他存储时间戳的方式。例如，我们仍然可以使用 pub struct Key<T: AsRef<[u8]>>(T); 表示，但假设键的最后 8 个字节是时间戳。你也可以将此作为额外任务的一部分实现。

替代键表示：| 用户键 (varlen) | ts (8 字节) | 在单个切片中
我们的键表示：| 用户键切片 | ts (u64) |

在 key+ts 编码中，具有最小用户键和最大时间戳的键将首先排序。例如：

("a", 233) < ("a", 0) < ("b", 233) < ("b", 0)

任务 1：在块中编码时间戳

你首先会注意到的是，在替换键模块后，你的代码可能无法编译。在本章中，你需要做的就是使其编译。在此任务中，你需要修改：

src/block.rs
src/block/builder.rs
src/block/iterator.rs

你会注意到 raw_ref() 和 len() 已从键 API 中移除。相反，我们有 key_ref 来检索用户键的切片，以及 key_len 来检索用户键的长度。你需要重构块构建器和解码实现以使用新的 API。此外，你需要更改块编码以编码时间戳。在 BlockBuilder::add 中，你应该这样做。新的块条目记录将如下所示：

key_overlap_len (u16) | remaining_key_len (u16) | key (remaining_key_len) | timestamp (u64)

你可以使用 raw_len 来估计键所需的空间，并在用户键之后存储时间戳。

更改块编码后，你需要相应地更改 block.rs 和 iterator.rs 中的解码。

任务 2：在 SST 中编码时间戳

然后，你可以继续修改表格式：

src/table.rs
src/table/builder.rs
src/table/iterator.rs

具体来说，你需要更改块元编码以包含键的时间戳。所有其他代码保持不变。由于我们在所有函数的签名中使用 KeySlice（即 seek、add），新的键比较器应自动按用户键和时间戳对键进行排序。

在你的表构建器中，你可以直接使用 key_ref() 来构建布隆过滤器。这自然地为你的 SST 创建了一个前缀布隆过滤器。

任务 3：LSM 迭代器

由于我们使用关联泛型类型使大多数迭代器适用于不同的键类型（即 &[u8] 和 KeySlice<'_>），如果正确实现，我们不需要修改合并迭代器和连接迭代器。LsmIterator 是我们从内部键表示中剥离时间戳并将键的最新版本返回给用户的地方。在此任务中，你需要修改：

src/lsm_iterator.rs

目前，我们不修改 LsmIterator 的逻辑以仅保留键的最新版本。我们只是通过将时间戳附加到用户键上（当将键传递给内部迭代器时）并从键中剥离时间戳（当返回给用户时）来使其编译。目前，你的 LSM 迭代器的行为应该是向用户返回同一键的多个版本。

任务 4：内存表

目前，我们保留内存表的逻辑。我们向用户返回一个键切片，并使用 TS_DEFAULT 刷新 SST。我们将在下一章中将内存表更改为 MVCC。在此任务中，你需要修改：

src/mem_table.rs

任务 5：引擎读取路径

在此任务中，你需要修改：

src/lsm_storage.rs

现在我们键中有了时间戳，当创建迭代器时，我们需要查找带有时间戳的键，而不仅仅是用户键。你可以使用 TS_RANGE_BEGIN（最大的 ts）创建一个键切片。

当你检查用户键是否在表中时，你可以简单地比较用户键而不比较时间戳。

此时，你应该构建你的实现并通过所有第 1 周的测试用例。系统中存储的所有键将使用 TS_DEFAULT（即时间戳 0）。我们将在接下来的两章中使引擎完全多版本并通过所有测试用例。

快照读取 - 内存表和时间戳

在本章中，你将：

重构你的内存表/WAL 以存储一个键的多个版本。
实现新的引擎写入路径为每个键分配时间戳。
使你的压缩过程感知多版本键。
实现新的引擎读取路径以返回键的最新版本。

在重构期间，你可能需要根据需要将某些函数的签名从 &self 更改为 self: &Arc<Self>。

要运行测试用例：

cargo x copy-test --week 3 --day 2
cargo x scheck

注意：完成本章后，你还需要通过所有 <= 2.4 的测试。

任务 1：内存表、预写日志和读取路径

在此任务中，你需要修改：

src/wal.rs
src/mem_table.rs
src/lsm_storage.rs

我们已经使引擎中的大多数键成为 KeySlice，它包含一个字节键和一个时间戳。然而，我们系统的某些部分仍未考虑时间戳。在我们的第一个任务中，你需要修改你的内存表和 WAL 实现以考虑时间戳。

你需要首先更改内存表中存储的 SkipMap 类型。

#![allow(unused)]
fn main() {
pub struct MemTable {
    // map: Arc<SkipMap<Bytes, Bytes>>,
    map: Arc<SkipMap<KeyBytes, Bytes>>, // Bytes -> KeyBytes
    // ...
}
}

之后，你可以继续修复所有编译器错误以完成此任务。

MemTable::get

我们保留 get 接口，以便测试用例仍然可以探测内存表中键的特定版本。完成此任务后，此接口不应在你的读取路径中使用。考虑到我们在跳表中存储 KeyBytes，即 (Bytes, u64)，而用户探测的是 KeySlice，即 (&[u8], u64)。我们必须找到一种方法将后者转换为前者的引用，以便我们可以在跳表中检索数据。

为此，你可以使用不安全代码将 &[u8] 强制转换为静态，并使用 Bytes::from_static 从静态切片创建字节对象。这是安全的，因为 Bytes 不会尝试释放切片的内存，因为它被假定为静态的。

剧透：将 u8 切片转换为 Bytes

#![allow(unused)]
fn main() {
Bytes::from_static(unsafe { std::mem::transmute(key.key_ref()) })
}

这不是问题，因为我们之前有的是 Bytes 和 &[u8]，其中 Bytes 实现了 Borrow<[u8]>。

MemTable::put

签名应更改为 fn put(&self, key: KeySlice, value: &[u8])，你需要在实现中将键切片转换为 KeyBytes。

MemTable::scan

签名应更改为 fn scan(&self, lower: Bound<KeySlice>, upper: Bound<KeySlice>) -> MemTableIterator。你需要将 KeySlice 转换为 KeyBytes 并将这些用作 SkipMap::range 参数。

MemTable::flush

现在，在将内存表刷新到 SST 时，你应该使用键的时间戳而不是默认时间戳。

MemTableIterator

它现在应该存储 (KeyBytes, Bytes)，返回的键类型应为 KeySlice。

Wal::recover 和 Wal::put

预写日志现在应该接受键切片而不是用户键切片。在序列化和反序列化 WAL 记录时，你应该将时间戳放入 WAL 文件，并对时间戳和你之前拥有的所有其他字段进行校验和。

WAL 格式如下：

| key_len (exclude ts len) (u16) | key | ts (u64) | value_len (u16) | value | checksum (u32) |

LsmStorageInner::get

之前，我们将 get 实现为首先探测内存表，然后扫描 SST。现在我们已经将内存表更改为使用新的 key-ts API，我们需要重新实现 get 接口。最简单的方法是创建一个合并迭代器，覆盖我们拥有的一切——内存表、不可变内存表、L0 SST 和其他级别 SST，与你之前在 scan 中所做的相同，只是我们在 SST 上进行了布隆过滤器过滤。

LsmStorageInner::scan

你需要合并新的内存表 API，并且应将扫描范围设置为 (user_key_begin, TS_RANGE_BEGIN) 和 (user_key_end, TS_RANGE_END)。请注意，当你处理排除边界时，你需要正确地将迭代器定位到下一个键（而不是相同时间戳的当前键）。

任务 2：写入路径

在此任务中，你需要修改：

src/lsm_storage.rs

我们在 LsmStorageInner 中有一个 mvcc 字段，其中包含本周多版本并发控制所需的所有数据结构。当你打开目录并初始化存储引擎时，你需要创建该结构。

在你的 write_batch 实现中，你需要为写入批次中的所有键获取一个提交时间戳。你可以通过使用 self.mvcc().latest_commit_ts() + 1 在逻辑开始时获取时间戳，并在逻辑结束时使用 self.mvcc().update_commit_ts(ts) 来递增下一个提交时间戳。为确保所有写入批次具有不同的时间戳并且新键放置在旧键之上，你需要在函数开始时持有写锁 self.mvcc().write_lock.lock()，以便一次只有一个线程可以写入存储引擎。

任务 3：MVCC 压缩

在此任务中，你需要修改：

src/compact.rs

我们在前面章节中所做的是只保留键的最新版本，并在压缩键到底层时移除键（如果键被删除）。使用 MVCC，我们现在有了与键关联的时间戳，我们不能对压缩使用相同的逻辑。

在本章中，你可以简单地移除删除键的逻辑。你可以暂时忽略 compact_to_bottom_level，并且你应该在压缩期间保留键的所有版本。

此外，你需要以这样的方式实现压缩算法：即使超过 SST 大小限制，具有不同时间戳的相同键也会放在同一个 SST 文件中。这确保了如果一个键在某个级别的 SST 文件中找到，它不会在该级别的其他 SST 文件中，从而简化了系统许多部分的实现。

任务 4：LSM 迭代器

在此任务中，你需要修改：

src/lsm_iterator.rs

在上一章中，我们实现了 LSM 迭代器，将具有不同时间戳的相同键视为不同的键。现在，我们需要重构 LSM 迭代器，以便如果从子迭代器检索到键的多个版本，只返回键的最新版本。

你需要在迭代器中记录 prev_key。如果我们已经将键的最新版本返回给用户，我们可以跳过所有旧版本并继续下一个键。

此时，你应该通过前面章节的所有测试，除了持久性测试（2.5 和 2.6）。

测试你的理解

MVCC 引擎中的 get 与你第 2 周构建的引擎有什么区别？
在第 2 周，当 get 时，你在找到键的第一个内存表/级别处停止。在 MVCC 版本中，你能做同样的事情吗？
如何将 KeySlice 转换为 &KeyBytes？这是一个安全/合理的操作吗？
为什么我们需要在写入路径中获取写锁？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

内存表获取的早期停止。与其创建覆盖所有内存表和 SST 的合并迭代器，我们可以如下实现 get：如果我们在内存表中找到键的版本，我们可以停止搜索。对于 SST 也是如此。

快照读取 - 引擎读取路径和事务 API

在本章中，你将：

基于前一章完成读取路径以支持快照读取。
实现事务 API 以支持快照读取。
实现引擎恢复过程以正确恢复提交时间戳。

在本天结束时，你的引擎将能够为用户提供存储键空间的一致视图。

在重构期间，你可能需要根据需要将某些函数的签名从 &self 更改为 self: &Arc<Self>。

要运行测试用例：

cargo x copy-test --week 3 --day 3
cargo x scheck

注意：完成本章后，你还需要通过 2.5 和 2.6 的测试用例。

任务 1：带有读取时间戳的 LSM 迭代器

本章的目标是拥有类似这样的东西：

#![allow(unused)]
fn main() {
let snapshot1 = engine.new_txn();
// 向引擎写入一些东西
let snapshot2 = engine.new_txn();
// 向引擎写入一些东西
snapshot1.get(/* ... */); // 我们可以检索引擎先前状态的一致快照
}

为了实现这一点，我们可以在创建事务时记录读取时间戳（这是最新的提交时间戳）。当我们在事务上执行读取操作时，我们将只读取低于或等于读取时间戳的所有键版本。

在此任务中，你需要修改：

src/lsm_iterator.rs

为此，你需要在 LsmIterator 中记录一个读取时间戳。

#![allow(unused)]
fn main() {
impl LsmIterator {
    pub(crate) fn new(
        iter: LsmIteratorInner,
        end_bound: Bound<Bytes>,
        read_ts: u64,
    ) -> Result<Self> {
        // ...
    }
}
}

你需要更改 LSM 迭代器的 next 逻辑以找到正确的键。

任务 2：多版本扫描和获取

在此任务中，你需要修改：

src/mvcc.rs
src/mvcc/txn.rs
src/lsm_storage.rs

现在我们在 LSM 迭代器中有了 read_ts，我们可以在事务结构上实现 scan 和 get，以便我们可以在存储引擎的给定点读取数据。

我们建议你在 LsmStorageInner 结构中创建辅助函数，如 scan_with_ts(/* 原始参数 */, read_ts: u64) 和 get_with_ts（如果需要）。存储引擎上的原始 get/scan 应实现为创建事务（快照）并在该事务上执行 get/scan。调用路径将类似于：

LsmStorageInner::scan -> new_txn 和 Transaction::scan -> LsmStorageInner::scan_with_ts

要在 LsmStorageInner::scan 中创建事务，我们需要向事务构造函数提供 Arc<LsmStorageInner>。因此，我们可以将 scan 的签名更改为接受 self: &Arc<Self> 而不是简单的 &self，这样我们就可以使用 let txn = self.mvcc().new_txn(self.clone(), /* ... */) 创建事务。

你还需要更改 scan 函数以返回 TxnIterator。我们必须确保快照在用户迭代引擎时是活动的，因此 TxnIterator 存储快照对象。在 TxnIterator 内部，我们现在可以存储一个 FusedIterator<LsmIterator>。当我们实现 OCC 时，我们稍后会将其更改为其他东西。

你现在不需要实现 Transaction::put/delete，所有修改仍将通过引擎进行。

任务 3：在 SST 中存储最大时间戳

在此任务中，你需要修改：

src/table.rs
src/table/builder.rs

在你的 SST 编码中，你应该在块元数据之后存储最大时间戳，并在加载 SST 时恢复它。这将帮助系统在恢复系统时决定最新的提交时间戳。

任务 4：恢复提交时间戳

现在我们在 SST 中有了最大时间戳信息，在 WAL 中有了时间戳信息，我们可以获取引擎启动之前提交的最大时间戳，并在创建 mvcc 对象时使用该时间戳作为最新的提交时间戳。

如果未启用 WAL，你可以简单地通过查找 SST 中的最大时间戳来计算最新的提交时间戳。如果启用了 WAL，你应该进一步迭代所有恢复的内存表并找到最大时间戳。

在此任务中，你需要修改：

src/lsm_storage.rs

我们没有此部分的测试用例。完成此部分后，你应该通过前面章节的所有持久性测试（包括 2.5 和 2.6）。

测试你的理解

到目前为止，我们假设我们的 SST 文件使用单调递增的 id 作为文件名。使用 <level>_<begin_key>_<end_key>_<max_ts>.sst 作为 SST 文件名可以吗？这可能会有什么潜在问题？
考虑事务/快照的替代实现。在我们的实现中，我们在迭代器和事务上下文中拥有 read_ts，因此用户始终可以基于时间戳访问数据库一个版本的一致视图。将当前 LSM 状态直接存储在事务上下文中以获得一致快照是否可行？（即所有 SST id、它们的级别信息以及所有内存表 + ts）这样做的优缺点是什么？如果引擎没有内存表怎么办？如果引擎在像 S3 对象存储这样的分布式存储系统上运行怎么办？
假设你正在实现 MVCC Mini-LSM 引擎的备份实用程序。仅仅复制所有 SST 文件而不备份 LSM 状态是否足够？为什么或为什么不？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

水印和垃圾回收

在本章中，你将实现必要的结构来跟踪用户正在使用的最低读取时间戳，并在执行压缩时从 SST 中收集未使用的版本。

要运行测试用例：

cargo x copy-test --week 3 --day 4
cargo x scheck

任务 1：实现水印

在此任务中，你需要修改：

src/mvcc/watermark.rs

水印是跟踪系统中最低 read_ts 的结构。当创建新事务时，它应调用 add_reader 添加其读取时间戳进行跟踪。当事务中止或提交时，它应从水印中移除自身。当调用 watermark() 时，水印结构返回系统中的最低 read_ts。如果没有正在进行的事务，它只返回 None。

你可以使用 BTreeMap 实现水印。它为每个 read_ts 维护一个计数器，记录有多少快照正在使用此读取时间戳。你不应在 b-tree 映射中有条目数为 0 的条目。

任务 2：在事务中维护水印

在此任务中，你需要修改：

src/mvcc/txn.rs
src/mvcc.rs

你需要在事务开始时将 read_ts 添加到水印，并在事务调用 drop 时移除它。

任务 3：压缩中的垃圾回收

在此任务中，你需要修改：

src/compact.rs

现在我们有了系统的水印，我们可以在压缩过程中清理未使用的版本。

如果键的版本在水印以上，保留它。
对于水印以下或等于水印的所有键版本，保留最新版本。

例如，如果我们有水印=3 和以下数据：

a@4=del <- 水印以上
a@3=3   <- 水印以下或等于水印的最新版本
a@2=2   <- 可以移除，没有人会读取它
a@1=1   <- 可以移除，没有人会读取它
b@1=1   <- 水印以下或等于水印的最新版本
c@4=4   <- 水印以上
d@3=del <- 如果压缩到底层，可以移除
d@2=2   <- 可以移除

如果我们对这些键进行压缩，我们将得到：

a@4=del
a@3=3
b@1=1
c@4=4
d@3=del (如果压缩到底层，可以移除)

假设这些是引擎中的所有键。如果我们在 ts=3 进行扫描，我们将在压缩前/后得到 a=3,b=1,c=4。如果我们在 ts=4 进行扫描，我们将在压缩前/后得到 b=1,c=4。压缩不会且不应影响读取时间戳 >= 水印的事务。

测试你的理解

在我们的实现中，我们通过 Transaction 的生命周期自己管理水印（所谓的非托管模式）。如果用户打算自己管理键时间戳和水印（即当他们有自己的时间戳生成器时），你需要在 write_batch/get/scan API 中做什么来验证他们的请求？我们是否有任何架构假设在这种情况下可能难以维护？
为什么我们需要在事务迭代器中存储 Transaction 的 Arc？
从 SST 文件中完全移除键的条件是什么？
目前，我们只在压缩到底层时才移除键。是否有其他时间可以移除键？（提示：你知道所有级别中每个 SST 的开始/结束键。）
考虑用户创建长时间运行的事务并且我们无法垃圾回收任何内容的情况。用户不断更新单个键。最终，单个 SST 文件中可能有一个具有数千个版本的键。这将如何影响性能，你将如何处理？

额外任务

O(1) 水印。你可以通过使用哈希映射或循环队列实现摊销 O(1) 的水印结构。

事务和乐观并发控制

在本章中，你将实现 Transaction 的所有接口。你的实现将为事务内的修改维护一个私有工作空间，并批量提交它们，以便事务的所有修改在提交前只对事务本身可见。我们只在提交时检查冲突（即可序列化冲突），这是乐观并发控制。

要运行测试用例：

cargo x copy-test --week 3 --day 5
cargo x scheck

任务 1：本地工作空间 + Put 和 Delete

在此任务中，你需要修改：

src/mvcc/txn.rs

你现在可以通过将相应的键/值插入到 local_storage 来实现 put 和 delete，这是一个没有键时间戳的跳表内存表。请注意，对于删除，你仍然需要将其实现为插入空值，而不是从跳表中移除值。

任务 2：Get 和 Scan

在此任务中，你需要修改：

src/mvcc/txn.rs

对于 get，你应该首先探测本地存储。如果找到值，则返回值或 None，具体取决于它是否是删除标记。对于 scan，你将需要为跳表实现一个 TxnLocalIterator，就像在第 1.1 章中为没有键时间戳的内存表实现迭代器一样。你将需要在 TxnIterator 中存储一个 TwoMergeIterator<TxnLocalIterator, FusedIterator<LsmIterator>>。最后，鉴于 TwoMergeIterator 将保留子迭代器中的删除标记，你将需要修改 TxnIterator 实现以正确处理删除。

任务 3：提交

在此任务中，你需要修改：

src/mvcc/txn.rs

我们假设事务只会在单个线程上使用。一旦你的事务进入提交阶段，你应该将 self.committed 设置为 true，以便用户无法在事务上执行任何其他操作。如果你的 put、delete、scan 和 get 实现应该出错，如果事务已经提交。

你的提交实现应该简单地从本地存储收集所有键值对，并向存储引擎提交一个写入批次。

任务 4：原子 WAL

在此任务中，你需要修改：

src/wal.rs
src/mem_table.rs
src/lsm_storage.rs

请注意，commit 涉及生成一个写入批次，目前写入批次不保证原子性。你将需要更改 WAL 实现以为写入批次生成头部和尾部。

新的 WAL 编码如下：

|   HEADER   |                          BODY                                      |  FOOTER  |
|     u32    |   u16   | var | u64 |    u16    |  var  |           ...            |    u32   |
| batch_size | key_len | key | ts  | value_len | value | more key-value pairs ... | checksum |

batch_size 是 BODY 部分的大小。checksum 是 BODY 部分的校验和。

没有测试用例来验证你的实现。只要你通过所有现有测试用例并实现上述 WAL 格式，一切都应该没问题。

你应该实现 Wal::put_batch 和 MemTable::put_batch。原始的 put 函数应将单个键值对视为一个批次。也就是说，此时，你的 put 函数应调用 put_batch。

一个批次应在同一个内存表和同一个 WAL 中处理，即使它超过内存表大小限制。

测试你的理解

根据我们到目前为止实现的所有内容，系统是否满足快照隔离？如果不满足，我们还需要做什么来支持快照隔离？（注意：快照隔离不同于我们将在下一章讨论的可序列化快照隔离）
如果用户想要批量导入数据（即 1TB？），如果他们使用事务 API 来执行此操作，你会给他们什么建议？是否有机会优化这种情况？
什么是乐观并发控制？如果我们在 Mini-LSM 中实现悲观并发控制，系统会是什么样子？
如果你的系统崩溃并在磁盘上留下损坏的 WAL，会发生什么？你如何处理这种情况？
当你提交事务时，是否有必要将一切批量放入内存表，或者你可以简单地逐个键放入？为什么？

额外任务

溢出到磁盘。如果事务的私有工作空间变得太大，你可以将一些数据刷新到磁盘。

（部分）可序列化快照隔离

现在，我们将在事务提交时添加冲突检测算法，以便使引擎具有一定程度的可序列化。

要运行测试用例：

cargo x copy-test --week 3 --day 6
cargo x scheck

让我们通过一个可序列化的例子。考虑我们在引擎中有两个事务：

txn1: put("key1", get("key2"))
txn2: put("key2", get("key1"))

数据库的初始状态是 key1=1, key2=2。可序列化意味着执行的结果与按某种顺序串行执行事务的结果相同。如果我们先执行 txn1 然后 txn2，我们将得到 key1=2, key2=2。如果我们先执行 txn2 然后 txn1，我们将得到 key1=1, key2=1。

然而，根据我们当前的实现，如果这两个事务的执行重叠：

txn1: get key2 <- 2
txn2: get key1 <- 1
txn1: put key1=2, commit
txn2: put key2=1, commit

我们将得到 key1=2, key2=1。这无法通过串行执行这两个事务产生。这种现象称为写偏斜。

通过可序列化验证，我们可以确保对数据库的修改对应于串行执行顺序，因此用户可以在需要可序列化执行的关键工作负载上运行系统。例如，如果用户在 Mini-LSM 上运行银行转账工作负载，他们希望任何时候的货币总和相同。没有可序列化检查，我们无法保证这个不变量。

可序列化验证的一种技术是记录系统中每个事务的读取集和写入集。我们在提交事务之前进行验证（乐观并发控制）。如果事务的读取集与其读取时间戳之后提交的任何事务重叠，那么验证失败，我们中止事务。

回到上面的例子，如果 txn1 和 txn2 都在时间戳 = 1 时开始。

txn1: get key2 <- 2
txn2: get key1 <- 1
txn1: put key1=2, commit ts = 2
txn2: put key2=1, start serializable verification

当我们验证 txn2 时，我们将遍历所有在其预期提交时间戳之前且在其读取时间戳之后开始的事务（在这种情况下，1 < ts < 3）。唯一满足条件的事务是 txn1。txn1 的写入集是 key1，txn2 的读取集是 key1。由于它们重叠，我们应该中止 txn2。

任务 1：在 Get 中跟踪读取集和写入集

在此任务中，你需要修改：

src/mvcc/txn.rs
src/mvcc.rs

当调用 get 时，你应该将键添加到事务的读取集中。在我们的实现中，我们存储键的哈希，以减少内存使用并使探测读取集更快，尽管当两个键具有相同哈希时可能会导致误报。你可以使用 farmhash::hash32 为键生成哈希。请注意，即使 get 返回键未找到，此键仍应被跟踪在读取集中。

在 LsmMvccInner::new_txn 中，如果 serializable=true，你应该为事务创建一个空的读/写集。

任务 2：在 Scan 中跟踪读取集

在此任务中，你需要修改：

src/mvcc/txn.rs

在本课程中，我们只保证 get 请求的完全可序列化。你仍然需要跟踪扫描的读取集，但在某些特定情况下，你可能仍然得到不可序列化的结果。

为了理解为什么这很困难，让我们看下面的例子。

txn1: put("key1", len(scan(..)))
txn2: put("key2", len(scan(..)))

如果数据库以 a=1,b=2 的初始状态开始，我们应该得到 a=1,b=2,key1=2,key2=3 或 a=1,b=2,key1=3,key2=2。然而，如果事务执行如下：

txn1: len(scan(..)) = 2
txn2: len(scan(..)) = 2
txn1: put key1 = 2, commit, read set = {a, b}, write set = {key1}
txn2: put key2 = 2, commit, read set = {a, b}, write set = {key2}

这通过了我们的可序列化验证，并且不对应于任何串行执行顺序！因此，一个完全工作的可序列化验证将需要跟踪键范围，并且如果只调用 get，使用键哈希可以加速可序列化检查。请参阅额外任务，了解如何正确实现可序列化检查。

任务 3：引擎接口和可序列化验证

在此任务中，你需要修改：

src/mvcc/txn.rs
src/lsm_storage.rs

现在，我们可以继续在提交阶段实现验证。每次我们处理事务提交时，你应该获取 commit_lock。这确保只有一个事务进入事务验证和提交阶段。

你需要遍历所有提交时间戳在范围 (read_ts, expected_commit_ts) 内的事务（两个都是排除边界），并查看当前事务的读取集是否与满足条件的任何事务的写入集重叠。如果我们可以提交事务，则提交一个写入批次，并将此事务的写入集插入到 self.inner.mvcc().committed_txns 中，其中键是提交时间戳。

如果 write_set 为空，可以跳过检查。只读事务总是可以提交。

你还应该修改 LsmStorageInner 中的 put、delete 和 write_batch 接口。我们建议你定义一个辅助函数 write_batch_inner 来处理写入批次。如果 options.serializable = true，put、delete 和用户面向的 write_batch 应创建事务而不是直接创建写入批次。你的写入批次辅助函数还应返回一个 u64 提交时间戳，以便 Transaction::Commit 可以正确地将已提交的事务数据存储到 MVCC 结构中。

任务 4：垃圾回收

在此任务中，你需要修改：

src/mvcc/txn.rs

当你提交事务时，你还可以清理已提交的事务映射，以移除水印以下的所有事务，因为它们不会参与任何未来的可序列化验证。

测试你的理解

如果你有一些构建关系数据库的经验，你可能会思考以下问题：假设我们基于 Mini-LSM 构建一个数据库，其中我们将关系表中的每一行存储为键值对（键：主键，值：序列化的行）并启用可序列化验证，数据库系统是否直接获得 ANSI 可序列化隔离级别能力？为什么或为什么不？
我们在这里实现的东西实际上是写快照隔离（参见对快照隔离的批评），它保证可序列化。是否有任何情况执行是可序列化的，但会被写快照隔离验证拒绝？
有些数据库声称它们通过只跟踪 gets 和 scans 中访问的键（而不是键范围）来支持可序列化快照隔离。它们真的能防止由幻读引起的写偏斜吗？（好吧…实际上，我说的是 BadgerDB。）

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

只读事务。启用可序列化后，我们将需要跟踪事务的读取集。
精度/谓词锁定。读取集可以使用范围而不是单个键来维护。当用户扫描完整键空间时，这将很有用。这也将启用扫描的可序列化验证。

零食时间：压缩过滤器

恭喜！你做到了！在上一章中，你使 LSM 引擎具备多版本能力，用户可以使用事务 API 与存储引擎交互。在本周结束时，我们将实现存储引擎的一些简单但重要的功能。欢迎来到 Mini-LSM 第 3 周的零食时间！

在本章中，我们将泛化压缩垃圾回收逻辑，使其成为压缩过滤器。

目前，我们的压缩将简单地保留水印以上的键和水印以下键的最新版本。我们可以向压缩过程添加一些魔法，以帮助用户自动收集一些未使用的数据作为后台作业。

考虑一个用户使用 Mini-LSM 存储数据库表的情况。表中的每一行都以表名作为前缀。例如：

table1_key1 -> 行
table1_key2 -> 行
table1_key3 -> 行
table2_key1 -> 行
table2_key2 -> 行

现在用户执行 DROP TABLE table1。引擎需要清理所有以 table1 开头的数据。

有很多方法可以实现这个目标。Mini-LSM 的用户可以扫描所有以 table1 开头的键，并请求引擎删除它们。然而，扫描一个非常大的数据库可能很慢，并且它将生成与现有键相同数量的删除墓碑。因此，扫描和删除不会释放被删除表占用的空间——相反，它将向引擎添加更多数据，并且空间只有在墓碑到达引擎底层时才能被回收。

或者，他们可以创建列族（我们将在你的余生章节中讨论）。他们将每个表存储在一个列族中，这是一个独立的 LSM 状态，当用户删除表时直接移除与列族对应的 SST 文件。

在本课程中，我们将实现第三种方法：压缩过滤器。压缩过滤器可以在运行时动态添加到引擎中。在压缩期间，如果找到匹配压缩过滤器的键，我们可以在后台静默移除它。因此，用户可以将 prefix=table1 的压缩过滤器附加到引擎，所有这些键将在压缩期间被移除。

任务 1：压缩过滤器

在此任务中，你需要修改：

src/compact.rs

你可以迭代 LsmStorageInner::compaction_filters 中的所有压缩过滤器。如果水印以下的键的第一个版本匹配压缩过滤器，只需移除它而不是将其保留在 SST 文件中。

要运行测试用例：

cargo x copy-test --week 3 --day 7
cargo x scheck

你可以假设用户不会获取前缀过滤器范围内的键。并且，他们不会扫描前缀范围内的键。因此，当用户请求前缀过滤器范围内的键时返回错误的值是可以的（即未定义行为）。

你的余生（待定）

这是一个高级部分，深入探讨 LSM 存储引擎的优化和应用，将使你的实现更加生产就绪。我们仍在规划内容，此部分在不久的将来不会公开提供。

周 + 章	主题	解决方案	起始代码	文档
4.1	基准测试
4.2	块压缩
4.3	琐碎移动和并行压缩
4.4	替代块编码
4.5	速率限制器和 I/O 优化
4.6	构建你自己的块缓存
4.7	构建你自己的跳表
4.8	异步引擎
4.9	基于 IO-uring 的 I/O 引擎
4.10	预取
4.11	键值分离
4.12	列族
4.13	分片
4.14	压缩优化
4.15	基于 Mini-LSM 的 SQL

Keyboard shortcuts

一周学会 LSM