时间戳键编码 + 重构

在本章中，你将：

重构你的实现以使用 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）。我们将在接下来的两章中使引擎完全多版本并通过所有测试用例。

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

Keyboard shortcuts