零食时间：压缩过滤器

恭喜！你做到了！在上一章中，你使 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

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

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