简单压缩策略

在本章中，你将：

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

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

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

任务 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 毫秒被调用，你需要：

1. 生成压缩任务，如果没有任务需要调度，返回 ok。
2. 运行压缩并获取新的 SST 列表。
3. 类似于你在上一章中实现的 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 社区中讨论它们。

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