（部分）可序列化快照隔离

现在，我们将在事务提交时添加冲突检测算法，以便使引擎具有一定程度的可序列化。

要运行测试用例：

cargo x copy-test --week 3 --day 6
cargo x scheck

让我们通过一个可序列化的例子。考虑我们在引擎中有两个事务：

txn1: put("key1", get("key2"))
txn2: put("key2", get("key1"))

数据库的初始状态是 key1=1, key2=2。可序列化意味着执行的结果与按某种顺序串行执行事务的结果相同。如果我们先执行 txn1 然后 txn2，我们将得到 key1=2, key2=2。如果我们先执行 txn2 然后 txn1，我们将得到 key1=1, key2=1。

然而，根据我们当前的实现，如果这两个事务的执行重叠：

txn1: get key2 <- 2
txn2: get key1 <- 1
txn1: put key1=2, commit
txn2: put key2=1, commit

我们将得到 key1=2, key2=1。这无法通过串行执行这两个事务产生。这种现象称为写偏斜。

通过可序列化验证，我们可以确保对数据库的修改对应于串行执行顺序，因此用户可以在需要可序列化执行的关键工作负载上运行系统。例如，如果用户在 Mini-LSM 上运行银行转账工作负载，他们希望任何时候的货币总和相同。没有可序列化检查，我们无法保证这个不变量。

可序列化验证的一种技术是记录系统中每个事务的读取集和写入集。我们在提交事务之前进行验证（乐观并发控制）。如果事务的读取集与其读取时间戳之后提交的任何事务重叠，那么验证失败，我们中止事务。

回到上面的例子，如果 txn1 和 txn2 都在时间戳 = 1 时开始。

txn1: get key2 <- 2
txn2: get key1 <- 1
txn1: put key1=2, commit ts = 2
txn2: put key2=1, start serializable verification

当我们验证 txn2 时，我们将遍历所有在其预期提交时间戳之前且在其读取时间戳之后开始的事务（在这种情况下，1 < ts < 3）。唯一满足条件的事务是 txn1。txn1 的写入集是 key1，txn2 的读取集是 key1。由于它们重叠，我们应该中止 txn2。

任务 1：在 Get 中跟踪读取集和写入集

在此任务中，你需要修改：

src/mvcc/txn.rs
src/mvcc.rs

当调用 get 时，你应该将键添加到事务的读取集中。在我们的实现中，我们存储键的哈希，以减少内存使用并使探测读取集更快，尽管当两个键具有相同哈希时可能会导致误报。你可以使用 farmhash::hash32 为键生成哈希。请注意，即使 get 返回键未找到，此键仍应被跟踪在读取集中。

在 LsmMvccInner::new_txn 中，如果 serializable=true，你应该为事务创建一个空的读/写集。

任务 2：在 Scan 中跟踪读取集

在此任务中，你需要修改：

src/mvcc/txn.rs

在本课程中，我们只保证 get 请求的完全可序列化。你仍然需要跟踪扫描的读取集，但在某些特定情况下，你可能仍然得到不可序列化的结果。

为了理解为什么这很困难，让我们看下面的例子。

txn1: put("key1", len(scan(..)))
txn2: put("key2", len(scan(..)))

如果数据库以 a=1,b=2 的初始状态开始，我们应该得到 a=1,b=2,key1=2,key2=3 或 a=1,b=2,key1=3,key2=2。然而，如果事务执行如下：

txn1: len(scan(..)) = 2
txn2: len(scan(..)) = 2
txn1: put key1 = 2, commit, read set = {a, b}, write set = {key1}
txn2: put key2 = 2, commit, read set = {a, b}, write set = {key2}

这通过了我们的可序列化验证，并且不对应于任何串行执行顺序！因此，一个完全工作的可序列化验证将需要跟踪键范围，并且如果只调用 get，使用键哈希可以加速可序列化检查。请参阅额外任务，了解如何正确实现可序列化检查。

任务 3：引擎接口和可序列化验证

在此任务中，你需要修改：

src/mvcc/txn.rs
src/lsm_storage.rs

现在，我们可以继续在提交阶段实现验证。每次我们处理事务提交时，你应该获取 commit_lock。这确保只有一个事务进入事务验证和提交阶段。

你需要遍历所有提交时间戳在范围 (read_ts, expected_commit_ts) 内的事务（两个都是排除边界），并查看当前事务的读取集是否与满足条件的任何事务的写入集重叠。如果我们可以提交事务，则提交一个写入批次，并将此事务的写入集插入到 self.inner.mvcc().committed_txns 中，其中键是提交时间戳。

如果 write_set 为空，可以跳过检查。只读事务总是可以提交。

你还应该修改 LsmStorageInner 中的 put、delete 和 write_batch 接口。我们建议你定义一个辅助函数 write_batch_inner 来处理写入批次。如果 options.serializable = true，put、delete 和用户面向的 write_batch 应创建事务而不是直接创建写入批次。你的写入批次辅助函数还应返回一个 u64 提交时间戳，以便 Transaction::Commit 可以正确地将已提交的事务数据存储到 MVCC 结构中。

任务 4：垃圾回收

在此任务中，你需要修改：

src/mvcc/txn.rs

当你提交事务时，你还可以清理已提交的事务映射，以移除水印以下的所有事务，因为它们不会参与任何未来的可序列化验证。

测试你的理解

• 如果你有一些构建关系数据库的经验，你可能会思考以下问题：假设我们基于 Mini-LSM 构建一个数据库，其中我们将关系表中的每一行存储为键值对（键：主键，值：序列化的行）并启用可序列化验证，数据库系统是否直接获得 ANSI 可序列化隔离级别能力？为什么或为什么不？
• 我们在这里实现的东西实际上是写快照隔离（参见对快照隔离的批评），它保证可序列化。是否有任何情况执行是可序列化的，但会被写快照隔离验证拒绝？
• 有些数据库声称它们通过只跟踪 gets 和 scans 中访问的键（而不是键范围）来支持可序列化快照隔离。它们真的能防止由幻读引起的写偏斜吗？（好吧…实际上，我说的是 BadgerDB。）

我们不提供问题的参考答案，欢迎在 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.