1.1 时间戳分配

当事务开始时，它被分配一个读时间戳，等于最近提交的事务的提交时间戳。从高层来看，你可以将其理解为记录/记下最新一次原子写入数据库的时间戳。读时间戳决定了哪些数据可以被事务安全且正确地读取。换句话说，读时间戳决定了当前事务可以看到的元组的最新版本。

当事务提交时，它将被分配一个单调递增的提交时间戳。提交时间戳决定了事务的序列化顺序。由于这些提交时间戳是唯一的，我们也可以通过提交时间戳唯一地标识已提交的事务。

以下是表堆中对 4 个元组（A、B、C、D）进行多次写入/更新后的表堆和版本链示例：

在此图中，A1 指的是元组 A 的第一个版本，A3 指的是元组 A 的第三个版本。A4 指的是元组 A 的第四个版本，也是元组 A 最新或"真实"的版本。请注意，B4 和 C4 实际上分别是元组 B 和 C 的第三个版本，我们只是为了下面的解释方便才这样标注。

时间戳（ts=_）指的是每个元组所属事务的提交时间戳。因此 [A1, B1, C1] 属于提交时间戳 = 1 的事务（我们可以简称为事务 1），[A3, B3, D3] 属于提交时间戳 = 3 的事务（事务 3）。此图中最近提交的事务是提交时间戳 = 4 的事务，包含 [A4, B4, C4]。

假设我们有一个读时间戳为 3 的事务（意味着我们的事务在事务 3 提交之后、事务 4 提交之前开始，请确保你理解这一点）。我们的事务只能观察到 [A3, B3, C2, D3]。

对于 [A, B, C]，我们的事务无法观察到 [A4, B4, C4]，因为这些元组版本的时间戳都是 4（相对于我们读时间戳 3 来说是在未来）。我们的事务需要遍历每个元组的撤销日志，读取它遇到的第一个版本小于或等于 3 的版本。对于 A 和 B，它遇到的第一个版本分别是 A3 和 B3。对于 C，遇到的第一个版本是 C2。对于 D，由于元组的当前版本时间戳已经是 3，可以直接安全地读取。

另一个例子是，如果我们的读时间戳是 2，那么我们的事务只会看到 [A2, B1, C2]，因为 D 是在时间戳 3 时创建的（相对于我们的读时间戳 2 来说是在未来）。

你需要在此任务中为事务分配正确的读时间戳和提交时间戳。更多信息请参见 src/include/concurrency/transaction_manager.h 中的 TransactionManager::Begin 和 TransactionManager::Commit。我们已经提供了 TransactionManager::Abort 的起始代码，你不需要在 Abort 中做任何修改就能获得任务 #1 的全部分数。

1.2 水位线

水位线是所有尚未提交或中止的事务中最低的读时间戳。如果没有这样的事务，水位线就是最新的提交时间戳。计算水位线最简单的方法是遍历事务管理器映射中的所有事务，找到所有进行中事务的最小 read_ts。

然而，这种简单的策略效率非常低。在此任务中，你需要实现一个时间复杂度为 O(log N) 的算法来计算水位线。更多信息请参考 watermark.h 和 watermark.cpp。当事务开始/提交/中止时，你还需要调用 Watermark::AddTxn 和 Watermark::RemoveTxn。

有很多方法可以实现这一点。参考解决方案使用哈希表实现了一个均摊 O(1) 的算法，此外 C++ 标准库中还有一个有用的 容器，可能使 O(log N) 的实现变得非常简单。

此时你应该通过 TxnTimestampTest 套件中的所有测试用例。

2.1 元组重建

在此任务中，你将通过定义在 execution_common.cpp 中的 ReconstructTuple 函数实现元组重建算法。请注意，在本项目期间，你很可能会发现许多功能可以被系统中的不同组件共享。你可以在 execution_common.cpp 中定义辅助函数。

ReconstructTuple 接受 4 个参数：元组模式、基础元组及其元数据（两者都存储在表堆中），以及按从最近修改到最早修改排序的撤销日志列表。以下是重建元组的示例：

基础元组（在"表堆中最新版本"下方）始终存储其模式中每一列的值（换句话说，它们是完整且有效的元组）。然而，撤销日志只包含被操作更改的列。撤销日志还有一个 is_delete 标志，表示整个元组的删除。

请注意，基础元组元数据和撤销日志都会有 is_delete 标志，它们并不总是相等的。在任务 4.2 中，你将需要在一个已存在的 RID 上"插入"一个元组，因此你需要在 UndoLog 中使用这个 is_delete 标志来执行此类操作（想象在一个循环中反复插入和删除同一个元组）。下面展示了 is_delete 标志如何工作的示例。请确保你理解这些撤销日志是在时间上倒退的。作为一个练习，尝试推断出可能导致这个特定版本链的操作序列：

ReconstructTuple 应该应用提供给函数的所有修改，不需要查看元数据或撤销日志中的时间戳。它不需要访问函数参数列表之外的数据。换句话说，确保你没有传递过多的撤销日志给 ReconstructTuple。

下面是 UndoLog 结构的图示：

UndoLog 表示对某个元组的部分修改（在由 ts_ 字段决定的某个时间点）。UndoLog 中的 modified_fields_ 成员是一个 bool 向量，其长度与表模式中列的数量相同。如果其中一个布尔值设置为 true，则表示元组中的对应字段已被该 UndoLog 更新。例如，如果 modified_fields_ 向量的第 3 个元素（索引 2）设置为 true，则表示元组的第三列被更新了。

tuple_ 字段包含部分 Tuple，它的值/列数应该与 modified_fields_ 向量中 true 的数量相同。要从部分元组中检索值，你需要根据表模式和已修改的字段构建一个部分 Schema。然后你可以使用该部分 Schema 从部分 Tuple 中提取值。

时间戳（ts_）是该 UndoLog 对应的提交时间戳。我们还存储了指向下一个 UndoLog 的链接（prev_version_ 通过 UndoLink 存储）。如果 UndoLog 是版本链中的最后一个，TxnId（对应代码中 UndoLink 内部的 prev_txn_）将被设置为 INVALID_TXN。你可以使用 prev_version_.IsValid() 辅助函数来快速检查这一点。提醒一下，你在 ReconstructTuple 中不需要使用甚至检查时间戳（ts_）字段和前一版本（prev_version_）字段，因为 prev_version_ 应该只由 ReconstructTuple 的调用者使用，以确定将哪些 UndoLog 放入输入向量中。

在上面的示例中，我们存储的是具有 4 列的元组。这个特定的 UndoLog 表示对第 2 和第 3 个字段的修改。尝试（在纸上）写出伪代码，说明如何将这 2 个特定字段改回以重建过去的元组。然后，尝试将该算法推广到任意类型的输入元组、任意数量的修改字段以及任意数量的撤销日志。完成这些之后，你就可以编写 ReconstructTuple 了！

2.2 顺序扫描（元组检索）

在此任务中，你需要重写 项目 #3 中的顺序扫描执行器，以支持从过去检索数据（基于事务的读时间戳）。

对于新的顺序扫描执行器从表堆中扫描的每个元组，它应该检索该元组直到事务读时间戳的所有撤销日志，重建过去的元组版本，然后输出该过去的元组。你需要在 execution_common.cpp 中实现 CollectUndoLogs 辅助函数。该函数返回重建元组所需的所有撤销日志，相对于给定事务的读时间戳。

给定当前事务的读时间戳，你需要处理 3 种情况：

1. 表堆中的元组相对于读时间戳是最新的数据。你可以通过检查元组元数据中的时间戳来判断。在这种情况下，不需要执行撤销操作，CollectUndoLogs 应返回一个空向量。
2. 表堆中的元组已被另一个未提交的事务修改，或者它比事务读时间戳更新。在这种情况下，你需要遍历版本链以收集读时间戳之后的所有撤销日志。
3. 表堆中的元组包含当前事务的修改。换句话说，我们正在读取一个自己修改过的元组。这种情况的解释如下。

为了在不修改时间戳结构（它们只是 int64_t）的情况下支持情况 3，我们将使用时间戳的高位作为标签来表示”临时”时间戳。在 BusTub 中，提交时间戳在 0 到 TXN_START_ID - 1 之间是有效的。TXN_START_ID 被定义为 64 位整数的第二高位（1 << 62）。

如果时间戳的第二高位设置为 1（& 1 << 62），则表示该元组已被某个事务修改，且该事务尚未提交。我们称此时间戳为”临时事务时间戳”，通过 TXN_START_ID + txn_human_readable_id = temp_txn_id 计算得出。我们采用这种方法来区分具有提交时间戳的已提交元组和某个特定事务 ID 下的未提交元组。请注意，UndoLog 中不应包含临时事务时间戳（我们将在后面的章节中解释）。

我们不使用实际的最高位（1 << 63）的原因是，这样我们可以继续以简单的方式使用 < 和 > 比较临时时间戳。设置最高位会导致时间戳变为负数。

BusTub 中的第一个事务 ID 是 TXN_START_ID，ID 是单调递增的。请确保你理解事务 ID 与提交时间戳不是相同的，即使两者都是单调递增的。由于 TXN_START_ID 是一个非常大的数字，难以直接解读，我们将在记录和调试时通过去掉最高位来生成一个人类可读的 ID。你不需要手动计算未提交事务的临时时间戳，可以使用现有的辅助函数 GetTransactionTempTs 来返回此事务的临时时间戳（src/include/concurrency/transaction.h ）。

我们将使用 txn*** 的表示法，其中 *** 是人类可读的 ID，来表示事务 ID。例如，txn42 表示 ID 为 TXN_START_ID + 42 的事务，即人类可读 ID 为 42 的事务。假设当前事务的人类可读 ID 为 3，它扫描到一个时间戳为 TXN_START_ID + 3 的基础元组。该事务就知道自己是该元组最近的修改者。处理情况 3 的这个子情况等同于处理情况 1。思考一下如果它看到一个不同的未提交事务的临时事务时间戳会发生什么。

示例

这是另一个例子：假设 txn9 更新了元组 A，这意味着元组 A 的时间戳将被设置为 TXN_START_ID + 9。当 txn9 最终提交时，元组 A 的时间戳将被替换为 txn9 的提交时间戳。在代码中，这看起来如下：

• txn9 修改元组 A。
• txn9 使用 GetTransactionTempTs 将元组 A 的时间戳设置为 TXN_START_ID + 9。
• 当 txn9 提交时，它通过 GetCommitTs 将元组 A 的时间戳替换为新的提交时间戳。
• 其他事务可以使用元组 A 的时间戳来区分它是否已被已提交或未提交的事务修改。
• 你可以通过简单地将时间戳与 TXN_START_ID 比较来做到这一点。

下面是 SeqScanExecutor 的最终示例。为了使图示更容易理解，下面示例中的 TXN_START_ID 将是 1000 而不是（1 << 62）。因此，1009 表示事务 ID 为 9 的临时事务时间戳（在此示例中 TXN_START_ID + 9 = 1009）。

让我们看一下下面的示例，其中我们遍历版本链来收集撤销日志以构造用户请求的元组：

假设我们有一个 ID 为 9、读时间戳为 3 的事务。txn9 尚未提交（因为存在临时事务时间戳 1009）。txn9 中对表的顺序扫描结果应该是：[(A, 9), (B, 9), (C, 2), (D, 9)]。对于除 (C, 2) 之外的所有元组，事务 9 是已经修改它们的事务，所以它不需要遍历撤销日志。然而，(C, 2) 的提交时间戳为 4，大于我们的读时间戳 3。事务 9 然后需要遍历撤销日志以找到该元组的第一个提交时间戳小于或等于 3 的版本。

考虑另一个读时间戳为 4 的事务。该事务的顺序扫描结果将是：[(A, 3), (B, 3), (C, 4)]。对于 (A, 3) 和 (B, 3)，表堆包含来自 txn9 的待处理更新，因此该事务需要遍历版本链以获取时间戳 4 之前/之时的最后一次更新。(C, 4) 是读时间戳 4 时的最新更新。(D, 9) 是事务 9 的待处理更新，由于它没有版本链，我们不需要返回它。一般来说，如果在给定读时间戳处没有元组的先前版本，则事务应将其视为元组不存在。

与测试用例相比，这些示例过于简化。在实现 SeqScanExecutor 时，你还需要考虑 NULL 数据和整数以外的数据类型。

一旦你完成了 CollectUndoLogs 和 ReconstructTuple 的实现，如何使用这两个函数完成 SeqScanExecutor 的 MVCC 版本应该就很清楚了。请注意，基础元组、元组元数据和属于该元组的第一个撤销链接可以通过 GetTupleAndUndoLink 获取。

我们的测试用例将手动设置一些事务和表堆内容。你不需要实现插入执行器来测试你的顺序扫描实现。此时，你应该通过 TxnScanTest 中的所有测试用例。

3.1 插入执行器

你的插入执行器实现应该与 项目 #3 中的非常相似。你可以在表堆中创建一个新的元组，并且需要正确构造元组的元数据。表堆中的时间戳应设置为事务临时时间戳，如 任务 2.2 中所述。此时你还应通过 AppendWriteSet 将 RID 添加到写入集中。以下是 txn9 将 (D, 3) 插入表中的简单图示：

我们提供了辅助函数 UpdateTupleInPlace 和 UpdateUndoLink 来分别更新表堆中的元组和撤销链接。这些函数模拟了原子的比较并交换操作，你需要提供一个 check 函数。这两个函数的伪代码如下：

UpdateUndoLink(rid, new_undo_link, check_function) {
  take the table heap lock / undo link lock
  retrieve the data from table heap / undo link
  call user-provided check function, if check failed, return false
  update the data and return true
}

补充说明

此任务的所有测试用例都是单线程的，因此你可以简单地向 check 参数传递 nullptr 以跳过检查，并分别使用 UpdateTupleInPlace 和 UpdateUndoLink。请记住，对于未来的并发测试用例，你需要原子地获取/更新 Tuple 和 UndoLink，以便其他事务不能更改另一个事务的中间结果。考虑以下场景：

1. txn1 调用 GetTuple 检查是否可以更新一个元组。
2. txn2 修改了该元组及其 UndoLink。
3. txn1 然后调用 GetUndoLink 并获取了错误的 UndoLink。
4. txn1 基于错误的信息更新了元组和 UndoLink。

在此示例中，你可能想要使用 UpdateTupleAndUndoLink 和 GetTupleAndUndoLink 来原子地获取/设置（src/concurrency/transaction_manager_impl.cpp ）。从 任务 4.2 开始，你可能需要实现 check 逻辑来检测多个线程并发更新元组及其元数据/UndoLink 时的写-写冲突。

3.2 提交

一次只允许一个事务执行 Commit 函数，你应该通过使用事务管理器中的 commit_mutex_ 来确保这一点。在此任务中，你需要在事务管理器中扩展你的 Commit 实现，添加事务提交逻辑。以下是一些粗略的伪代码：

1. 获取提交互斥锁。
2. 获取提交时间戳（你可能需要在这里执行 .load() + 1 而不是 .fetch_add(1)，思考一下与 Begin 的关系）。
3. 遍历该事务修改过的每个元组（通过写入集），将基础元组的时间戳设置为提交时间戳。请注意，你需要在所有修改执行器（插入、更新、删除）中维护写入集。
4. 将事务设置为 COMMITTED 状态。
5. 更新事务的提交时间戳。
6. 更新 last_committed_ts_（你可以在这里执行 .fetch_add(1)）。

你应该已经作为任务 1 的一部分实现了上述大部分逻辑，所以你只需要添加遍历表的逻辑。

TxnMgrDbg

此时，我们强烈建议你实现调试函数 TxnMgrDbg。该函数应该打印出表堆内容和每个元组的版本链。如果你在没有编写此函数的情况下来找我们，我们会要求你先实现它。

我们的测试用例将在每次重要操作之后调用你的调试函数，你可以打印任何你想要的内容来检查版本链。这个调试函数在调试未来测试的实现时将非常有用。我们的参考解决方案中有一个调试函数的示例，可以在 BusTub Web Shell 中使用命令 \dbgmvcc {table_name} 运行（你可以在 Chrome 中按 F12 找到开发者控制台）。

RID=0/0 ts=1 tuple=(1, 1.000000, <NULL>)
RID=0/1 ts=2 tuple=(2, 2.000000, <NULL>)
  txn1@0 (1, 1.000000, _) ts=1
RID=0/2 ts=3 tuple=(3, 3.000000, <NULL>)
  txn3@0 (2, 2.000000, _) ts=2
  txn1@1 (1, 1.000000, _) ts=1
RID=0/3 ts=3 tuple=(3, 3.000000, <NULL>)
RID=0/4 ts=4 tuple=(4, 4.000000, <NULL>)
  txn4@0 (3, 3.000000, _) ts=3
RID=0/5 ts=4 <del marker> tuple=(2, 2.000000, <NULL>)
  txn4@1 (2, 2.000000, _) ts=2
RID=0/6 ts=4 tuple=(4, 4.000000, <NULL>)
  txn4@2 <del> ts=2
  txn1@2 (1, 1.000000, <NULL>) ts=1
RID=0/7 ts=txn2 tuple=(100, 100.000000, <NULL>)
RID=0/8 ts=txn2 tuple=(100, 100.000000, <NULL>)
  txn2@0 (1, 1.000000, _) ts=1
RID=0/9 ts=txn5 tuple=(400, 400.000000, <NULL>)
  txn5@0 (4, 4.000000, _) ts=4
  txn1@3 (1, 1.000000, _) ts=1

┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 0      │ ts = 1                                   │ (1, 1.000000, <NULL>)                                  │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 1      │ ts = 2                                   │ (2, 2.000000, <NULL>)                                  │
│ ──────────────── │ ──────────────────────────────────────── │ ────────────────────────────────────────────────────── │
│                  │ ts = 1           │ txn 1 @ [0]           │ (1, 1.000000, _)                                       │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 2      │ ts = 3                                   │ (3, 3.000000, <NULL>)                                  │
│ ──────────────── │ ──────────────────────────────────────── │ ────────────────────────────────────────────────────── │
│                  │ ts = 2           │ txn 3 @ [0]           │ (2, 2.000000, _)                                       │
│                  │ ts = 1           │ txn 1 @ [1]           │ (1, 1.000000, _)                                       │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 3      │ ts = 3                                   │ (3, 3.000000, <NULL>)                                  │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 4      │ ts = 4                                   │ (4, 4.000000, <NULL>)                                  │
│ ──────────────── │ ──────────────────────────────────────── │ ────────────────────────────────────────────────────── │
│                  │ ts = 3           │ txn 4 @ [0]           │ (3, 3.000000, _)                                       │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 5      │ ts = 4                                   │ <DELETED> (2, 2.000000, <NULL>)                        │
│ ──────────────── │ ──────────────────────────────────────── │ ────────────────────────────────────────────────────── │
│                  │ ts = 2           │ txn 4 @ [1]           │ (2, 2.000000, _)                                       │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 6      │ ts = 4                                   │ (4, 4.000000, <NULL>)                                  │
│ ──────────────── │ ──────────────────────────────────────── │ ────────────────────────────────────────────────────── │
│                  │ ts = 2           │ txn 4 @ [2]           │ <deleted>                                              │
│                  │ ts = 1           │ txn 1 @ [2]           │ (1, 1.000000, _)                                       │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 7      │ ts = txn 2                               │ (100, 100.000000, <NULL>)                              │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 8      │ ts = txn 2                               │ (100, 100.000000, <NULL>)                              │
│ ──────────────── │ ──────────────────────────────────────── │ ────────────────────────────────────────────────────── │
│                  │ ts = 1           │ txn 2 @ [0]           │ (1, 1.000000, _)                                       │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ RID = 0 / 9      │ ts = txn 5                               │ (400, 400.000000, <NULL>)                              │
│ ──────────────── │ ──────────────────────────────────────── │ ────────────────────────────────────────────────────── │
│                  │ ts = 4           │ txn 5 @ [0]           │ (4, 4.000000, _)                                       │
│                  │ ts = 1           │ txn 1 @ [3]           │ (1, 1.000000, _)                                       │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

交互式测试

以下是使用 BusTub Web Shell 将你的实现与我们的实现进行比较的示例。

make -j`nproc` shell && ./bin/bustub-shell
bustub> CREATE TABLE t1(v1 int, v2 int);
bustub> INSERT INTO t1 VALUES (1, 1), (2, 2), (3, 3);
bustub> \dbgmvcc t1 -- call your `TxnMgrDbg` function to dump the version chain
bustub> BEGIN;
txn?> INSERT INTO t1 VALUES (4, 4);
txn?> \txn -1
bustub> SELECT * FROM t1; -- the newly-inserted row should not be visible to other txns
bustub> \txn ? -- use the id you see before
txn?> COMMIT;

你也可以使用 BusTub Netcat shell 来启动一个带事务的交互式会话。 你需要安装 nc（netcat）才能使用此交互式 shell。

make -j`nproc` nc-shell && ./bin/bustub-nc-shell
bustub> CREATE TABLE t1(v1 int, v2 int);
bustub> INSERT INTO t1 VALUES (1, 1), (2, 2), (3, 3);
bustub> \dbgmvcc t1 -- call your `TxnMgrDbg` function to dump the version chain
# in another terminal
nc 127.0.0.1 23333
bustub> INSERT INTO t1 VALUES (4, 4);
# in yet another terminal
nc 127.0.0.1 23333
bustub> SELECT * FROM t1; -- the newly-inserted row should not be visible to this txn
bustub> COMMIT;

我们在 BusTub Web Shell 中提供了在浏览器中运行的参考解决方案。

从此任务开始，我们所有的测试用例都是用 SQL 编写的。只要你的 SQL 查询结果与参考输出匹配，你就可以获得该测试用例的全部分数。我们不检查版本链的确切内容，但我们会检查 UndoLog 的数量和表堆元组的数量，以确保你正确且高效地维护版本链。我们还将使用你的 ReconstructTuple 来验证你生成的 UndoLog 的正确性。

3.3 生成撤销日志

在实现更新和删除执行器之前，你需要实现 GenerateNewUndoLog 和 GenerateUpdatedUndoLog。给定原始基础元组和修改后的目标元组，你应该返回应存储在做出修改的事务中的 UndoLog。

确保你理解 GenerateNewUndoLog 和 GenerateUpdatedUndoLog 之间的区别。假设一个事务多次更新同一个元组。我们期望在特定事务中每次更新只产生一个 UndoLog。GenerateNewUndoLog 用于每个元组的第一次修改。之后，使用 GenerateUpdatedUndoLog 将多次修改合并为一个 UndoLog。

有三种情况需要考虑：

1. 更新：在这种情况下，根据基础元组和目标元组生成 UndoLog。如果这不是此事务中的第一次更新，则通过 GenerateUpdatedUndoLog 将其与原始 UndoLog 合并。请注意，一个事务对每个 RID 最多应持有一个撤销日志。如果一个事务需要两次更新同一个元组，它应该只更新基础元组及其当前的撤销日志。
2. 删除：在这种情况下，你需要在 UndoLog 中存储整个元组，以便可以重建整个元组。思考一下如何在事务中进行多次修改来实现这一点。
3. 插入：你在任务 3.1 中实现的插入操作总是在表堆中创建一个具有新 RID 的新元组。换句话说，你永远不需要为插入操作创建 UndoLog。然而，在任务 4.2 中，你可能需要将一个元组插入回一个已删除的元组位置。当 base_tuple 为 nullptr 时，你就知道这是一个插入情况。

你会发现 Tuple::IsTupleContentEqual 和 Value::CompareExactlyEquals 在计算 UndoLog 时很有用。

3.4 更新与删除执行器

在此任务中，你需要实现实际生成 UndoLog 并更新表堆基础元组的逻辑。更新和删除执行器非常相似。

在更新或删除元组之前，你需要检查写-写冲突。有几种情况需要注意。如果一个元组正在被一个未提交的事务修改，则不允许其他事务修改它。如果这样做了，就会出现写-写冲突，与先前事务冲突的事务应该被中止。另一种写-写冲突的情况是：事务 A 删除了一个元组并提交，另一个事务 B 在事务 A 提交之后开始，删除了同一个元组。当检测到写-写冲突时，事务状态应设置为 TAINTED，你需要抛出 ExecutionException 以将 SQL 语句标记为失败。如果存在执行异常，ExecuteSqlTxn 将返回 false。此时，我们不要求你实现实际的中止逻辑。此任务中的测试用例不会调用 Abort 函数。

你的更新执行器应该实现为流水线断路器：它应该首先将子执行器中的所有元组存储到本地缓冲区，然后再写入任何更新。之后，它应该从本地缓冲区中提取元组，计算更新后的元组，然后在表堆上执行更新。

此时，所有测试用例都是单线程的，因此你不需要过多考虑更新/删除过程中可能出现的竞争条件。检测写-写冲突的唯一条件是检查基础元组元数据的时间戳。

让我们来看上面的示例，其中展示了在做任何更改之前你需要处理的 3 种不同情况。

• 在情况 (1) 中，txn10 已经删除了 (A, 2) 元组且尚未提交。假设 txn9 的读时间戳为 3。txn9 仍然可以读取元组的旧版本 (A, 2)。
• 在情况 (2) 中，如果除 txn9 之外的任何事务尝试更新/删除这个 B 元组，它们都需要中止。例如，如果 txn10 最终需要更新/删除该元组，txn10 应该因写-写冲突而被中止。
• 在情况 (3) 中，有另一个事务将 (C, 2) 更新为 (C, 4)，提交时间戳为 4。txn9 可以读取元组的旧版本 (C, 2)。同样，如果 txn9 最终需要更新/删除该元组，txn9 应该因写-写冲突而被中止，因为在事务读时间戳之后有一个更新的更新。
• 还有第 4 种情况，即一个事务想要更新自己做的修改（自修改）。如果一个元组已经被当前事务修改过，你不应该将其视为写-写冲突。

在检查写-写冲突之后（你应该为此编写一个辅助函数），你可以继续实现更新/删除逻辑：

• 通过 GenerateNewUndoLog 或 GenerateUpdatedUndoLog 创建修改的撤销日志。
• 更新元组的下一个撤销链接，使其指向新的撤销日志。
• 更新表堆中的基础元组和元数据（此步骤可以使用 UpdateTupleAndUndoLink 与上一步原子地完成）。

以下是说明删除操作的示例：

以下是说明更新操作的示例：

在开始实现执行器之前，请确保你理解这些图示。如果你有任何问题，请向我们询问 clarification！

在下面的示例中，txn9 首先将元组更新为 (A, 4)，然后更新为 (A, 5)，然后更新为 (B, 5)，然后更新为 (A, 5)，最后删除它。在整个过程中，txn9 为该元组恰好保留一个 UndoLog。请注意，当我们将 (B, 5) 更新为 (A, 5) 时，我们本可以一直回到事务的开始来计算部分更新 (_, 5)（因为组合所有增量可以从 (A,3) 得到 (A, 5)）。然而，我们建议简单地将修改添加到现有的 UndoLog 中（使其包含完整的更改 (A, 5)），这将使处理并发问题变得更容易。换句话说，确保你只在撤销日志中添加/更新数据，不要删除数据。

在下一个示例中，txn9 插入了一个元组，进行了多次修改，然后删除了它。在这种情况下，你可以直接修改表堆元组而不需要生成任何撤销日志。

请注意，我们在最后将提交时间戳设置为 0，因为这个元组是由 txn9 插入并由 txn9 删除的，这意味着它实际上从未存在过。如果版本链确实包含撤销日志，则应将其设置为实际的提交时间戳而不是 0，以便具有较低读时间戳的事务可以访问撤销日志。你也可以忽略这种情况，遵循通常的提交逻辑。只要你能在每个时间戳读取正确的数据，这在 奖励任务 #2 之前并不重要。

在本项目中，我们将始终使用固定大小的类型，因此 UpdateTupleInPlace 应该始终成功而不抛出异常。

将所有更新/删除操作整合在一起，你应该：

• 从子执行器获取 RID。
• 生成更新后的元组。
• 对于自修改，更新表堆元组，如果当前事务中有撤销日志则可选地更新它。
• 否则，生成撤销日志并将它们链接在一起。

此时，你应该通过 TxnExecutorTest 中除垃圾回收测试用例之外的所有测试。

任务 3.5 全局停止垃圾回收

在我们给你的代码中，一旦我们将事务添加到事务映射中，就永远不会删除它。我们这样做是因为具有较低读时间戳的事务可能需要读取先前已提交或已中止事务中存储的撤销日志。然而，想象一下如果我们有成千上万甚至数百万个事务。很可能许多过去的事务已经完全被更新的事务覆盖，我们不再需要存储它们的撤销日志。在此任务中，你需要实现一个简单的垃圾回收策略来删除未使用的事务。

垃圾回收在调用 GarbageCollection 时手动触发。测试用例只会在所有事务都暂停时调用此函数。因此，在进行垃圾回收时你不需要过多担心竞争条件。在 任务 1 中，你已经实现了一个计算水位线（系统中最低的读时间戳）的算法。在此任务中，你需要删除所有不包含任何对具有最低读时间戳的事务可见的撤销日志的事务。

你需要遍历表堆和版本链，以识别仍然可以被具有最低读时间戳的事务访问的撤销日志（确保你理解这一点：对该事务不可见的撤销日志应该对所有事务都不可见）。如果一个事务已提交/已中止，并且不包含任何对具有最低读时间戳的事务可见的撤销日志，你可以简单地将其从事务映射中删除。

下面的示例说明了水位线时间戳为 3 且 txn1、txn2 和 txn9 已提交的情况。txn1 的撤销日志不再可访问，因为每个提交时间戳为 1 的撤销日志都已被提交时间戳小于或等于 3 的更新覆盖。因此我们可以直接删除 txn1。txn2 对元组 (A, 2) 的撤销日志不可访问，但其对元组 (C, 2) 的撤销日志仍然可访问，因为没有额外的更新，所以我们现在不能删除它。

删除 txn1 后，将会有指向已删除撤销日志的悬空指针，如虚线所示。你不需要更新先前的撤销日志来修改悬空指针并使其成为无效指针，在本项目中将其留在那里是可以的。如果你的实现中所有内容都是正确的，你的顺序扫描执行器甚至不应该尝试解引用这些悬空指针，因为它们在水位线以下。然而，我们仍然建议你在代码中添加一些断言来确保这不会发生。

此时，你应该通过 TxnExecutorTest。

4.1 索引插入

你需要修改插入执行器以正确处理主键索引。同时，你还需要考虑多个事务从多个线程插入相同主键的情况。插入索引可以通过以下步骤完成：

1. 首先，检查元组是否已存在于索引中。如果存在，中止*该事务。
   • 这仅适用于 任务 4.1。如果你要实现 任务 4.2，那么索引可能指向一个已删除的元组，在这种情况下，你不应该中止。
   • 在 任务 4 中，你只需要将事务状态设置为 TAINTED。TAINTED 表示事务即将被中止，但数据尚未被清理。你不需要实现实际的中止过程，这是一个奖励任务。被污染的事务会在表堆中留下一些元组，你不需要清理它们。当另一个事务插入到同一位置并检测到写-写冲突时，仍然应该视为冲突。将事务设置为 TAINTED 状态后，你还需要抛出 ExecutionException，以便 ExecuteSql 返回 false，测试用例就会知道该事务/SQL 已被中止。
2. 接下来，在表堆上创建一个具有临时事务时间戳的元组。
3. 之后，将元组插入索引。如果违反了唯一键约束，你的索引应该返回 false。

在步骤 (1) 和 (3) 之间，其他事务可能也在做同样的事情。在当前事务创建索引条目之前，索引中可能已经创建了一个新条目。在这种情况下，你需要中止该事务，并且表堆中会有一个不被索引中任何条目引用的元组。

在此示例中，让我们分别看一下 txn9 尝试插入 A、B 和 C 的情况（假设元组的唯一列是主键）。假设 A 已经存在于索引中，C 已被一个未提交的事务插入。为了清晰起见，我们移除了图示中的 PageVersionInfo 结构。

• 插入 A：键已存在于索引中，违反了主键的唯一性要求，因此中止事务。
• 插入 B：由于索引中没有冲突，首先在表堆中创建一个元组，然后将新创建的元组的 RID 插入索引。
• 插入 C：我们假设这里有另一个 txn10 也在尝试插入 C。txn9 首先检测到索引中没有冲突并在表堆中创建了一个元组。然后，在后台，txn10 完成了步骤 (2) 和 (3)，创建了一个元组并更新了索引。当 txn9 在步骤 (4) 中尝试插入索引时，索引会报告唯一键冲突，因此 txn9 应该进入 TAINTED 状态。

此时你不需要实现 MVCC 索引扫描执行器。我们的测试用例将使用范围查询而不是等值查询，以避免触发顺序扫描到索引扫描的规则，这样顺序扫描就不会被转换为索引扫描。

完成这些后，你应该通过本项目中的第一个并发测试用例，其中我们测试当多个线程插入相同键时你的实现是否正常工作。

4.2 索引扫描、删除与更新

在此任务中，你需要为删除和更新执行器添加索引支持，以及 MVCC 索引扫描执行器。

一旦在索引中创建了一个条目，它将始终指向同一个 RID，即使元组被标记为删除也不会被移除。我们这样做是为了让较早的事务仍然可以通过索引扫描执行器访问历史记录。为了支持这一点，你需要重新审视你的插入执行器。考虑插入执行器插入到一个已被删除执行器移除的元组的情况。你的实现应该更新已删除的元组，而不是创建新条目，因为索引条目一旦创建就始终指向同一个 RID。你需要正确处理写-写冲突检测和唯一约束检测。

在此示例中，元组 (B, 2) 已被提交时间戳为 3 的事务删除。当元组被删除时，我们不会从索引中移除条目，因此索引可能指向一个删除标记，并且一旦存在就始终指向同一个 RID。当 txn9 使用插入执行器将 (B, 3) 插入表中时，它不应该创建新的元组。相反，它应该将删除标记更新为插入的元组，就像一次更新操作一样。

此时你还需要考虑其他竞争条件。例如，如果多个事务同时更新 UndoLink。你应该正确地中止其中一些事务，让恰好一个事务继续执行而不丢失任何数据。从此任务开始，你需要使用原子辅助函数 UpdateTupleAndUndoLink/GetTupleAndUndoLink 并传入 check 函数来避免竞争条件。

你应该观察到在上面的示例中，会有一小段时间表堆包含一个与第一个撤销日志具有相同时间戳的（已删除）元组。在实现了更新和删除之后，你的顺序扫描执行器也应该正确处理这种情况。

4.3 主键更新

你需要处理主键被更新的情况。在这种情况下，更新应该实现为对原始键的删除和对新键的插入。

让我们按顺序看一下 txn9 执行 UPDATE table SET col1 = col1 + 1 的情况，其中 col1 是主键。txn9 首先将 (2, B)（以及任何具有新主键的元组）插入表中：

现在我们开始使用 col1 = col1 + 1 更新表，其中我们删除所有将被更新的元组：

接下来，我们将更新后的元组以新的主键插入回表中：

最后，我们提交更改：

就是这样！