水印和垃圾回收

在本章中，你将实现必要的结构来跟踪用户正在使用的最低读取时间戳，并在执行压缩时从 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) 的水印结构。

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