第 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 天：压缩过滤器。在本周结束时，我们将把压缩时垃圾回收逻辑泛化为压缩过滤器，根据用户要求在压缩时移除数据。
我们非常感激你的反馈。欢迎加入我们的 Discord 社区。
发现问题？在 github.com/skyzh/mini-lsm 上创建问题/拉取请求。
mini-lsm-book © 2022-2025 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.