CMU 15-445 Bustub Project 4 - Concurrency Control - Note

本文最后更新于 2026年10月21日 下午

前言

这次写之前就开个文档记录，到时候不至于全忘了）

毕竟扫了一眼，P4 的 spec 是相当之长，不记录的话肯定会出现写了后面忘了前面的现象。

不过其实对应的 lecture 我还没看呢，所以这里也先记录一下学习知识的 note。

这次试着纯用 LLM，但是搭配原有课程的优质资源，给出这样的 prompt：

我有点懒得看视频，请你这样帮我速通：

  1. 以每一课内的每一个 section 为单位去学习，以 slides 和 notes 为核心主线，辅助我学习
  2. 上面的原话尽量是照搬翻译，你自己少添油加醋
  3. 但是，你使用 intelligent UI 画图辅助我理解，这是被鼓励的
  4. 每次学完一些知识，使用 homework 里面对应的题目，出一个 intelligent UI 搭配的问答系统给我当作练习

就这样，首先从第 17 课开始，你先试着输出一下你会将第 17 课如何划分，划分好之后，我说开始，我们再一点点开始学习。

需要读取的文件有点多，你稍微注意一点读取。

试试效果吧。

二编：效果相当好。

Lec 17 Concurrency Control Theory

为什么需要并发控制和 Recovery 恢复：

  • Lost Update Problem (Concurrency Control) 丢失更新问题（并发控制）：当两个或更多事务试图同时更新相同的数据时，我们该如何处理？
  • Durability Problem (Recovery) 持久性问题（恢复）：在发生断电时，我们如何确保数据库处于正确的状态？

事务 Transaction 的基本要求：要么完成全部步骤，要么一个步骤都不执行。

处理事务的一种简单方法：

  • 全部串行化，单个 worker 线程，每次执行一个事务。
  • 在事务开始之前，DBMS 将整个数据库复制到一个新文件，并在这个文件上进行所有修改。
  • 如果事务成功，新文件就成为当前数据库文件；如果事务失败，DBMS 就丢弃修改过的副本，不会保存该事务的任何修改。

这种方法被成为 The Strawman System 或 Shadow Paging，放弃了所有并发，效果不好。

如果需要并发执行，那么需要保证：

  • 正确性，保证执行符合需求，不出错
  • 公平性，保证所有事务不饿死

而且，事务只能约束 DBMS 的东西，假设一个事务修改了数据库并向外部邮箱发送邮件，随后事务 Abort，DBMS 是无力收回邮件的。

因此，我们需要形式化的正确性标准（Formal Correctness Criteria），来判断某种交错执行是否有效。具体如下：

形式上，一个数据库可以表示为一组固定的、具有名称的数据对象（A、B、C……）。

这些对象可以是属性（Attributes）、元组（Tuples）、页面（Pages）、表（Tables），甚至整个数据库。

我们将要讨论的算法适用于任何类型的对象，但是所有对象必须属于同一类型。

事务（Transaction）是对这些对象执行的一系列读写操作，例如 R(A)、W(B)。这是 DBMS 对用户程序的抽象视图。

事务的边界由客户端定义。

在 SQL 中，一个新事务由 BEGIN 命令开始，然后以 COMMIT 或 ABORT / ROLLBACK 结束。

对于 COMMIT，要么事务的全部修改都被保存到数据库中，要么 DBMS 覆盖这一决定，转而中止该事务。

对于 ABORT，事务的所有修改都会被撤销，使得该事务如同从未发生过一样。

事务的中止既可以由事务自身主动发起，也可以由 DBMS 引起。

正确性规范：ACID

Atomic

事务的提交的可能的结果：

  • Commit
  • Abort / Rollback

保证 Atomic 原子性的方法：

  • Logging：DBMS 按照顺序将所有操作记录在日志中，同时在磁盘和内存维护 undo logs
  • Shadow Paging：上文提过。运行时性能不如 log

两种方式的关键区别在于：

Logging： 允许修改数据，再通过记录的信息撤销修改。

Shadow Paging： 保留原始页面，在副本上修改，提交后才采用新页面。

两个并发事务互相影响，导致最终数据库状态无法与任何一种串行执行结果对应。主要违反了哪项性质？：Isolation.

Consistency

Integrity Constraints

SQL 层面的约束，比如某某字段不能为负数。

Eventual Consistency

最终一致性：一个已经提交的事务可能看到不一致的结果

比如，一个已经提交的事务，可能无法立即看到一个更早提交的事务所做的更新。

所以，最终一致性不是很好。

Isolation

Isolation of Transactions：DBMS 为事务提供一种「使之认为自己是系统里唯一运行的事务」的假象，看不到其余事务的影响。

等价于：事务串行运行。但是，不可能真的串行。所以，我们需要一种方法，使事务能够交错执行，同时看起来仍然是逐个执行的。

Concurrency Control Protocol

并发控制协议是 DBMS 在运行时决定如何正确地交错执行多个事务的操作的方法。

分为两类：

  • Pessimistic 悲观并发控制：DBMS 假设事务之间会冲突，因此开始就不允许问题的发生；
  • Optimistic 乐观并发控制：DBMS 乐观地认为事务之间很少发生冲突，故选择在冲突发生之后再处理。

Execution Schedule

DBMS 执行事务的顺序被称为执行调度。

目的：交错执行事务来最大化并发性，同时等价于某一种串行执行。

调度的形式化性质

可以认为执行前和执行后是状态迁移，整个数据库是一个状态机。

  • 串行调度：字面意思
  • 等价调度：两种调度产生的终态完全一致
  • 可串行化调度：如果某个调度与这些事务的一种串行执行等价，那么它就是可串行化调度

Conflicting Operations

定义几个概念。

如果两个操作满足以下条件，就称它们存在冲突：

  1. 它们属于不同的事务。
  2. 它们作用于同一个数据对象。
  3. 至少有一个操作是写操作。

不同类型的冲突导致不同类型的异常，如：

读写冲突导致不可重复读，即一个事务多次读取同一个数据对象，却无法得到相同的值。简单举例就是事务 T1 有两个读任务，这两个任务之间夹着一个完整的事务 T2，和 T1 存在 RW 冲突。

写读冲突导致脏读，即一个事务读取了另一个事务写入、但是尚未提交的数据。

写写冲突导致丢失更新，即一个事务覆盖了另一个尚未提交的事务写入的数据。其实就是事务 T1 先写，T2 后写覆盖了 T1 的写。

异常还有一个幻读，后面说。

区分冲突和异常：

冲突是操作之间的关系，异常是执行过程中出现的异常现象。

Conflict Serializability

两个调度冲突等价，当且仅当这两个条件都成立时：

  1. 它们包含相同事务的相同操作。
  2. 在两个调度中，每一对相互冲突的操作都具有相同的先后顺序。

如果一个调度 S 与某个串行调度冲突等价，那么 S 就是冲突可串行化的。

直观理解就是，可以通过交换不同事务之间相邻且不冲突的操作，将调度 S 转换为串行调度。

举例：

Dependency Graph

使用依赖图来验证一个调度是否冲突可串行化。

依赖图中：

  • 每个事务都是图中的一个 node
  • 当且仅当事务 $T_i$ 的操作 $O_i$ 与事务 $T_j$ 的操作 $O_j$ 冲突，且 $O_i$ 在调度中出现在 $O_j$ 之前时，存在一条 $T_i$ 到 $T_j$ 的有向边

一个调度冲突可串行化，当且仅当其依赖图无环。

理解：如果依赖图没有环，就能找到一种拓扑排序，将事务按照这种顺序串行执行，同时满足所有冲突操作之间的顺序约束。

View Serializability

视图可串行化，是一种比冲突可串行化更弱的可串行化定义。

视图可串行化难以高效地强制保证，因为 DBMS 并不知道应用程序会如何解释这些值。因此，实际系统中不采用这种方式。

所以我懒得看了，跳过。

Durability

事务持久性：已提交事务的所有修改，在系统崩溃或重启后都必须是持久的，即不允许以下两种情况的发生：

  • 不允许不完整的更新，崩溃恢复后，不能只留下某个事务的一部分修改。
  • 不保留失败事务的修改，没有成功提交的事务，其修改不能成为数据库恢复后的有效状态。

通过合适的 redo log 来实现。

一个例题：

Lec 18 Two-Phase Locking

Transaction Locks

可串行化及其相关理论有一个假设：调度时，已知所有的读写操作。

但是，实际中，需要一种运行过程中动态保持正确性的方法。

因而，DBMS 会使用锁来动态产生可串行化的事务执行调度，内部有一个锁管理器负责决定某个事务是否可以获得特定对象上的锁。

上面这句话有点绕，举个简单的例子就是，假设 Ta 和 Tb 想访问同一个对象，就会由 Lock Manager 来协调锁的请求。

Lock 与 Latch 的区别：

  • Lock：保护数据库的数据值（隔离事务），避免并发事务的冲突
  • Latch：保护 DBMS 内部的数据结构（隔离线程），避免多线程并发访问导致的错误

Locks 通常持续整个事务，而 Latches 只在较短的临界区内持有。

两种基本的锁：

  • Shared Lock 共享锁：允许多个事务同时读取同一个对象
  • Exclusive Lock 排他锁：持锁时其余事务不准对该对象持锁

其实就是读写锁吧。

Lock Manager 的工作原理：维护内部的 Lock Table，记录哪些事务持有哪些锁，以及哪些事务正在等待获取锁。

Basic Two-Phase Locking

两阶段锁：一种悲观并发控制协议，使用锁来动态决定某个事务是否允许访问数据库中的对象。

Phase 1：Growing，每个事务向 DBMS 的 Lock Manager 请求它所需要的锁。Lock Manager 批准或拒绝这些请求。

Phase 2：Shrinking，事务在第一次释放锁后，立即进入收缩阶段。在这一阶段，事务只能释放先前获得的锁，不能获取新的锁。

核心：一旦开始释放锁，就不能再获取新锁，也不能升级已有锁。

2PL 是保证冲突可串行化的，因为调度产生的依赖图不存在环。

简单解释：在 2PL 下，事务之间的冲突先后关系必须与它们的最后一次成功获取锁的时刻顺序一致，不可能产生环，因为不能重新获得锁。

2PL 存在 Cascading Abort 问题：一个事务中止后，其他事务也必须回滚，导致已经完成的计算工作被浪费。

简单举例，T1 完成写入之后进入 shrink 阶段，T2 得到锁之后结果出事故 abort 了，那么 T1 完成的也要 abort。

2PL 也可能产生脏读。

Strong Strict 2PL

定义 Strict Schedule（严格调度）：如果一个事务写入的任何值，在该事务提交之前，都不会被另一个事务读取或覆盖，那么这个调度是 Strict 的。

所以 SS2PL：是 2PL 的一种变体，事务必须结束（Commit 或 Abort）以后，才能释放锁。

优点：

  • 不发生级联中止
  • DBMS 可以通过恢复被恢复元组的依赖值，撤销一个已中止事务的修改。
  • 可以避免脏读

缺点：

  • 并发性能差
  • 不能防死锁

Strict 2PL：必须保持所有 X-Lock 直到事务结束，但允许提前释放 S-Lock（前提是仍遵守 2PL 的阶段限制）。

Deadlock

2PL 处理死锁的两种方法：检测和预防

Detection

DBMS 可以建立 Waits-for Graph，用于跟踪每个事务正在等待获取哪些锁。

图的定义如下：

  1. node 代表事务。
  2. 如果事务 $T_i$ 正在等待事务 $T_j$ 释放某个锁，则存在一条有向边 $T_i\rightarrow T_j$ （等待者 -> 持有者）
  3. 系统周期性地检查等待图中是否存在环，并决定如何打破它。

系统通常使用一个后台线程，周期性地检查 Waits-for Graph 是否存在环。如果一次检查遗漏了死锁，后续检查仍有机会发现它，所以检测的频率存在 trade-offs。

Handling

当 DBMS 检测到死锁时，会选择一个 Victim Transaction（牺牲事务），将其回滚，以打破等待环。

选择策略有很多，比如说时间、执行比例等。

Prevention

与 Detection 不同，死锁预防会在死锁发生前，阻止任何事务获得死锁。

即：当事务尝试获取另一个事务持有的锁时，DBMS 可以中止其中一个事务。

为了实现这一点，DBMS 给事务分配优先级，比如一种方案是「越老，优先级越高」。

举例，Wait-Die 就是：

  • 老事务请求新事务的锁，老事务等待
  • 新事务请求老事务的锁，老事务死

Wound-Die：

  • 老事务请求新事务的锁，新事务死
  • 新事务请求老事务的锁，新事务等待

这两种协议都保证了没有死锁，两种方案都只允许事务沿着一个方向等待锁，这样图中不可能产生环。

如果一个事务被中止后重启，DBMS 会让它继续使用原来的时间戳，而不是分配新的时间戳。

这样能避免事务不断变年轻、优先级不断降低，从而反复被中止导致 Starvation（饥饿）。

注意：这是一种避免饥饿的措施，不意味着在任何调度条件下都绝对不会饥饿。

Lock Hierarchy

其实就是区分锁的颗粒度。

trade offs：

  • Coarse-grained locks（粗粒度锁）减少锁管理开销，但限制并发；
  • Fine-grained locks（细粒度锁）提高潜在并发性，但需要管理更多锁。
Database Lock Hierarchy
层级 使用频率
Database Slightly Rare（较少）
Table Very Common（非常常见）
Page Common（常见）
Tuple Very Common（非常常见）
Attribute Rare（罕见）
Intention Locks

假设 T1 已对表 P 中某个 tuple 持互斥锁。若 T2 想要获得整张表的共享锁，那么 DBMS 须知这张表上存在更细粒度的互斥锁，否则可能错误批准请求。

不能逐 tuple 检查，开销太大。

因而引入意向锁，允许系统在不检查全部的低层次节点的情况下，判断是否可以给高层次接点授予锁。

如果一个节点被加上了意向锁，意味着某个事务正在该低层次上加锁。

这样，对于上面的例子，T1 会给表加一个 IX(TableP)，这样 S(TableP) 与 IX 互斥，就获得不了锁了。

IX(Table P) 表示事务打算在 P 的更低层级使用排他锁；它本身不等价于 X(Table P)。

三种意向锁：

  • Intention Shared 共享意向锁，表示事务正在或者准备在更低层级显式获取 S-Lock。
  • Intention-Exclusive（排他意向锁），表示事务正在或者准备在更低层级显式获取 X-Lock。
  • Shared + Intention-Exclusive（共享与排他意向组合锁），该节点为根的整个子树在共享模式下被显式锁定，同时事务还会在更低层级显式获取排他锁。（整体读，局部写）

一个容易反直觉的结论是：IX 与 IX 兼容。因为它们只是声明下层有写操作，不代表双方要修改同一个元组。真正的冲突还要在下层判断。

Hierarchical Locking

这一小节聚焦于事务如何沿着层级获取锁。

一般来说：对子节点获取 S/IS 或 X/IX/SIX，要求在父节点持有相应的锁。

因此，通常应当自顶向下获取锁，自底向上释放锁。

什么时候需要 SIX：扫描整张表，同时修改某一个 tuple。

只要锁兼容，不同事务就可以对同一个元素并发。

Lock Escalation

当一个事务持有大量低层级锁时，DBMS 可以自动转换为较粗粒度的锁，以减少 Lock Manager 需要维护和处理的锁请求数量。

显式加锁

大部分数据库支持用 SQL 显式加锁，绕开 Lock Manager。这里就不细说了。

一个简单的例子就是在大量写表之前先主动获取互斥锁，防止后面两个事务都想 upgrade 导致死锁，不得不 abort。

Lec 19 Timestamp Ordering Concurrency Control

关于为什么要引入 Timestamp Ordering (TO)，首先要回顾一下 2PL。

2PL 是一种悲观协议，体现在：要求事务访问数据库对象之前一定要获取锁。

但是如果事实上事务之间很少发生冲突，那么采用乐观协议更好。

TO 是一类乐观并发控制协议，具体：

  • DBMS 使用时间戳来确定事务的可串行化顺序
  • 每个事务 $T_i$ 都会被分配一个唯一、固定且单调递增的时间戳，记为 $TS(T_i)$
  • 如果 $TS(T_i) < TS(T_j)$，那么 DBMS 必须确保执行调度等价于 $T_i$ 在 $T_j$ 之前执行的串行调度。

时间戳分配策略：

  • 系统时钟（UNIX TIME）
  • 逻辑计数器（递增+1）

OCC Basic Protocol

OCC - Optimistic Concurrency Protocol

乐观并发控制（OCC）是一种使用时间戳来验证事务的乐观并发控制协议。

OCC 在冲突数量较少时表现最好。例如：

  1. 所有事务都是只读的。
  2. 事务访问的数据子集互不重叠。

如果数据库很大，并且工作负载没有明显倾斜，那么事务发生冲突的概率就较低，因此 OCC 是一种不错的选择。

OCC 中 DBMS 为每个事务创建一个 Private Workspace：

  • 事务的所有修改，在自己的 Workspace 中进行；
  • 写入的对象复制到 Workspace 中进行修改；
  • 如果隔离级别需要保证 Repeatable Read，读取的对象也会被复制到 Workspace。
  • 注意，其他事务无法读取某个事务在 Private Workspace 中产生的修改。
  • 事务准备提交时，DBMS 检查其 Write Set 是否与其他事务冲突。

OCC 的三个阶段：

  1. Read Phase 读取阶段：DBMS 跟踪事务的 Read Set 和 Write Set，并把事务的写入保存在 Private Workspace 中
  2. Validation Phase 验证阶段：当事务准备提交时，DBMS 为事务分配一个唯一的时间戳（TS），然后检查该事务是否与其他事务发生冲突。
  3. Write Phase 写入阶段：
    • 如果验证成功，DBMS 为 Private Workspace 中所有被修改的对象设置写时间戳（W-TS），并将修改原子地应用到全局数据库。
    • 如果验证失败，事务将 Abort 并重新执行。

Read Phase 是事务执行实际工作的阶段；Validation 和 Write Phase 共同组成 Commit Protocol。

OCC Validation

在 Validation Phase，我们如何确定要提交的事务是否会与其他事务产生冲突？无非是验证其他正在进行的事务的 Read / Write Sets，有两种方法。

  • Forward Validation：检查尚未提交的活动事务。
  • Backward Validation：检查已经提交的事务。

保证可串行化的三个条件：

假设时间戳顺序为：$TS(T_i)<TS(T_j)$，三个条件至少满足一个即可：

  • 完全串行，$T_i$ 在 $T_j$ 进入 Read Phase 前，已经完成 Write Phase。
  • 读阶段重叠，写入有序，$T_i$ 的 Write Phase 必须早于 $T_j$ 的 Write Phase，并且 $W_i\cap R_j=\varnothing$
  • 更大范围的重叠，$T_i$ 的 Read Phase 必须早于 $T_j$ 的 Read Phase 结束，并且 $W_i\cap R_j=\varnothing$ 且 $W_i\cap W_j=\varnothing$

OCC Performance and Limitations

OCC 的理想情况：

  • 所有事务都是只读事务
  • 事务访问互不重叠的数据子集

潜在问题：

  • Private Workspace 显然存在问题
  • Validation 和 Write Phase 的验证存在瓶颈
  • Abort 存在浪费
  • Timestamp Allocation Bottleneck

Abort 是比较严重的，因为是 OCC，高冲突场景下会有大量事务回滚。而且，Abort 的时机都是事务已经执行完成了，导致大量浪费。

Phantom Reads

幻读：当一个事务多次扫描某个范围，而另一个事务在两次扫描之间插入或删除了属于该范围的 Tuple，那么扫描事务可能得到不同的结果。

幻读问题产生于事务仅仅锁定已经存在的记录，而忽视其他事务正在创建的记录。

Phantom Prevention

方法 核心思想 课程中的使用情况
Lock Everything 锁住整张表或所有相关页面 常见，但粒度粗
Re-Execute Scans 提交前重新扫描谓词，检查结果是否还相同 较少使用
Predicate Locking 锁定 WHERE 谓词，如果另一个事务试图对同样的谓词获得锁且和已有的谓词锁互斥，就会产生锁冲突 较少使用
Index Locking 利用索引键锁定范围 常见

重点讲一下最后一个，事实上是 predicate locking 的一种特殊情况：借助索引中的 Key Range 来保护查询范围。

分为这四种：

类型 保护对象
Key-Value 单个 Key。为了保护尚不存在的 Key，需要引入 Virtual Keys（虚拟键）。
Gap 锁住索引键值之间的 Gap，防止其他事务向被保护的间隙插入新记录。
Key-Range 锁住从一个已有 Key 到下一个 Key 的区间，从而同时保护已有键值及相应的插入范围。
Hierarchical 允许事务以不同锁模式持有更大的 Key Range，以减少访问 Lock Manager 的开销。

Isolation Levels

前面一直在说：可串行化、冲突可串行化 etc

但是强制实行串行化，系统的并发度太低，性能差。

因而，DBMS 可能希望使用较弱的一致性级别，以改善可扩展性。

四种异常：

异常 原文释义
Dirty Read 脏读 读取了尚未提交的数据
Unrepeatable Read 不可重复读 重新读取同一数据得到不同结果
Lost Update 丢失更新 一个事务覆盖了另一个并发事务的更新
Phantom Read 幻读 插入或删除记录导致相同范围扫描得到不同结果

四个隔离级别，从强到弱依次为

  • Serializable：不允许幻读，所有读取均可重复，也不允许脏读。
  • Repeatable Read：可能出现幻读。
  • Read Committed：可能出现幻读、不可重复读和丢失更新。
  • Read Uncommitted：所有上述异常都可能发生。

其实这个名字对应的定义很好记，比如说 Read Commited 为什么不会发生脏读，就是因为脏读的定义就是「读到了未提交的数据」。而 Repeatable Read 就是说多次读取得到的数据一样，也就是解决了不可重复读和丢失更新问题。为什么解决了丢失更新？因为丢失更新也可以算是反复读取得到不一致数据。

如何实现不同的隔离级别？以 2PL 为例：

隔离级别 实现思路
Serializable Strong Strict 2PL + Phantom Protection
Repeatable Read Strong Strict 2PL，但没有 Phantom Protection
Read Committed 排他锁保持到事务结束，共享锁读完立即释放
Read Uncommitted 排他锁保持到事务结束，读取时不获取共享锁

Lec 20 MVCC

MVCC Fundamentals

Multi-Version Control System MVCC 是一个比单纯的 Concurrency Control Protocol 更加广泛的概念，涉及 DBMS 的设计与实现的方方面面。

MVCC 的核心思想：一个逻辑对象，存在多个物理版本。

MVCC 的核心收益：写事务不阻塞读事务、读事务也不阻塞写事务。

注意，MVCC 使读写可以互不阻塞，但不会自动消除写写冲突。

意味着一个事务可以修改对象，同时其他事务读取该对象的旧版本。

只读事务可以在不使用任何锁的情况下，通过访问 DBMS 提供的一致快照 Consistent Snapshots。

Snapshot Isolation

快照隔离：在事务开始时，向事务提供数据库的一个一致性快照，快照中的数据值只包括当时已提交事务产生的值。整个完整事务在这个快照内完成。

Write-Write Conflicts 的解决方案：First Writer Wins 或者 Last Writer Wins。

比如说前者，先进行的事务写但是未提交，后进行的事务写同一个对象就会被 abort。

Write Skew Anomaly

在 Snapshot Isolation 下，当两个并发事务修改不同的对象时，可能发生 Write Skew Anomaly（写偏斜异常），从而产生不可串行化的调度。

解释这个问题，可以举一个例子：

  • 假设数据库最初有两颗弹珠，一黑一白，前者为 A，后者为 B。
  • T1 将所有黑色弹珠变成白色，T2 将所有白色弹珠变成黑色。
  • 串行化结果：
    • 如果顺序是 T1 - T2，最后就全是黑色；
    • 如果顺序是 T2 - T1，最后就全是白色。
    • 这两种情况对应了串行化的唯一可能。
  • 但是如果在快照隔离下，两个事务在初始条件相同的快照上执行；
  • T1 只修改 A，T2 只修改 B
  • 因为不是写同一个对象，不发生 WW 冲突
  • 那么，最后得到结果：A 为白，B为黑，不对应任何一种串行结果。

其实本质原因就是依赖图中存在环。

严格说，这里使用了多版本串行化图中的 Read-Write Antidependency（反依赖）；不能简单地把它当作单版本调度直接套用普通冲突图。

Project 4 的 Snapshot Isolation 只需检查写写冲突，因此前面的弹珠例子可能成功提交两个事务。

但是 Task 4.4 的 Serializable Verification 还需要检查读取过的数据，判断并发事务的写入是否使这些读取失效。

例如，T1 提交时，如果发现 T2 已经提交，并且：

$$ R_1\cap W_2\ne\varnothing $$

那么就可能需要中止 T1，以避免不可串行化的执行。

Version Chains

版本存储：DBMS 使用 Tuple 中的指针字段，为每个逻辑 Tuple 创建一条 Version Chain（版本链）。本质上，它是一条按照时间戳排列的链表。事务在运行时沿着版本链遍历，直到找到对自己可见的正确版本。

Version Chain Ordering

  • Oldest-to-Newest (O2N)：
    • 新版本追加在版本链的末尾。查找时必须遍历版本链。
  • Newest-to-Oldest (N2O)：
    • 每次创建新版本，都必须更新索引指针，使其指向新的链头。
    • 读取最新版本时无需遍历版本链。
    • 这通常是更好的方法，因为大多数事务只关心最新版本。

注意 BusTub 项目中的实际做法：

BusTub 并不是把每次更新后的完整 Tuple 都追加到主表，而是采用类似 Delta Storage 的方案：当前物理数值 -> Undo Log 链条。后面部分细说。

Append-Only Storage

追加式存储 Append-Only Storage

  • 将一个逻辑 Tuple 的所有物理版本保存在同一个表空间中。
  • 不同版本会混合存储在表中。
  • 每次更新时，DBMS 只需将 Tuple 的新版本追加到表中的空闲空间，然后更新版本链。

Time-Travel Storage

其实是和 Append-Only Storage 相对的，第二种版本存储方案。具体如下：

  • DBMS 维护一张独立的表，称为 Time-Travel Table，用于存放 Tuple 的旧版本。
  • 每次执行更新时，DBMS 将旧版本复制到 Time-Travel Table，然后使用新数据覆盖 Main Table 中的 Tuple。
  • Main Table 中 Tuple 的指针指向 Time-Travel Table 里的历史版本。

仍然是指针链表的逻辑结构，只是历史版本都在 Time-Travel Table。

直接优点是，主表不必同时混合保存大量历史 Tuple。

Delta Storage

Time-Travel Storage 有这样的问题：只是改列很多的 tuple 的某一列，结果要全量记录整份历史信息。

Delta Storage 与 Time-Travel Storage 类似，但 DBMS 不再存储完整的历史 Tuple，而是仅将 Tuple 之间的差异或变化（Delta）存储在 Delta Storage Segment 中。

随后，事务可以逆序遍历这些 Delta，并应用它们来重新创建旧版本。

因此，与 Time-Travel Storage 相比，Delta Storage 的写入更快，但读取更慢。

Delta 保存的是修改之前的值，而不是修改之后的值。

注意，对于已经逻辑删除且不再被任何活跃事务需要的 Tuple，其主表中的物理记录最终也可以被回收。

也就是下文要探讨的 GC。

Tuple-Level Garbage Collection

如果满足以下任意一个条件，版本就是可以回收的：

  1. 没有任何活跃事务能够看到这个版本。
  2. 这个版本由一个已经中止（Aborted）的事务创建。

垃圾回收有两种主要实现方法：Tuple-Level GC 和 Transaction-Level GC。

关于第一点，举个例子，就是版本 A0 的时间戳是 10，但是当前所有活跃事务的时间戳都 > 10 了，而且被逻辑删除了，那么这个版本就可以被回收了。

这里重点讲一下我们所说的 Tuple-Level GC 的原理：DBMS 通过直接检查 Tuple 来发现旧版本。

两个实现方案：

  • Background Vacuuming
    • 独立的后台线程定期扫描表，寻找能够回收的版本。
    • 一种简单的优化是维护 Dirty Page Bitmap（脏页位图），记录自上次扫描以来哪些 Page 被修改。这样，后台线程就可以跳过没有发生变化的 Page。
  • Cooperative Cleaning
    • Worker Threads 在遍历版本链时，同时识别可回收的版本
    • 只适用于 Oldest-to-Newest（O2N）版本链，因为遍历顺序必须是 老 -> 新，这样才能顺便清理

Transaction-Level Garbage Collection

在事务级垃圾回收中，每个事务负责跟踪自己的旧版本，因此 DBMS 不必通过扫描 Tuple 来寻找这些版本。

  • 每个事务都维护自己的 Read Set 和 Write Set。
  • 当事务结束时，垃圾回收器可以利用这些集合，确定哪些 Tuple 能够被回收。

简单来说：维护 Old Versions 集合，判断这些 old versions 是否还被需要。

不过其实 BusTub 的实现和这个区别很大，到时候再说。

Logical vs. Physical Pointers

理解 MVCC 的索引如何定位版本链。

对于主键索引，指向版本链的头部，如果事务修改了 Tuple 的主键属性，那么这次修改会被当作一次 DELETE，随后执行 INSERT。如果采用 Time-Travel 或 Delta Storage，最新 Tuple 可能始终保存在同一个物理槽位中，此时普通列更新不一定需要修改索引指针。

更新 Tuple 的内容，不等于一定改变 Tuple 的物理地址。

对于二级索引，比较复杂。管理有两种方案：

  1. 使用 Logical Pointers 逻辑指针：
    • DBMS 为每个 Tuple 使用一个固定且不会变化的标识符。
    • 要求额外增加一个间接寻址层（Indirection Layer），用于将逻辑 ID 映射到 Tuple 的物理位置。
    • 随后，Tuple 更新只需要修改间接寻址层中的映射。
  2. Physical Pointers 物理指针
    • DBMS 直接使用版本链头部的物理地址。
    • 每当版本链头发生改变，就需要更新所有相关索引。这可能非常昂贵。

MVCC Duplicate Key Problem

MVCC 数据库中的索引通常不会将 Tuple 的版本信息与索引键一起保存。不同快照中的同一个 Key 可能指向不同的逻辑 Tuple。因此，索引需要能够支持重复的 Key。这就是 MVCC Duplicate Key Problem（重复键问题）。

提出三个要求：

  1. 索引的底层数据结构需要能够存储非唯一键。
  2. 主键索引和唯一索引需要使用额外的执行逻辑进行条件插入。必须原子地检查 Key 是否存在，再决定能否插入。
  3. Worker 可能从一次索引查询中得到多个条目，因此需要沿着指针找到正确的物理版本。

允许索引底层保存重复 Key，不等于允许数据库中出现违反唯一性约束的两条可见记录。

不过，bustub 的约束是一个索引始终指向同一个 RID，

Deleted

  • Logical Delete（逻辑删除） 表示对特定快照而言，该记录已经不存在。
  • Physical Delete（物理删除） 表示数据库实际释放该记录占用的存储空间。

逻辑删除的方法：其实 projects 里面都做过了：

  1. metadata 维护一个 is_deleted_
  2. 设置 tombstone
课程笔记 > 数据库 > bustub
#课程笔记 #数据库 #公开课
CMU 15-445 Bustub Project 4 - Concurrency Control - Note
https://blog.wendain.ing/posts/cmu-15-445-bustub-proj4/
作者
wendaining
发布于
2026年10月20日
更新于
2026年10月21日
许可协议