BusTub MVCC
发布于 • 作者: Ethan
BusTub 中 MVCC 工作原理
CMU 的教学数据库系统 (BusTub)，实现了典型的 多版本并发控制 (MVCC) 机制。
1. 核心数据结构
1.1 UndoLink（版本链指针）
struct UndoLink {
txn_id_t prev_txn_; // 前一个版本所在的事务ID
int prev_log_idx_; // 在该事务中的日志索引
};
每个 Tuple 通过 UndoLink 指向前一个版本，形成一条版本链。
1.2 UndoLog（版本日志）
struct UndoLog {
bool is_deleted_; // 是否是删除标记
std::vector<bool> modified_fields_; // 哪些字段被修改
Tuple tuple_; // 修改后的数据
timestamp_t ts_; // 时间戳
UndoLink prev_version_; // 更早的版本链接
};
每次修改都会生成一条 UndoLog，存储在事务的 undo_logs_ 向量中。
1.3 Transaction（事务）
class Transaction {
const txn_id_t txn_id_; // 事务ID
std::atomic<timestamp_t> read_ts_; // 读时间戳
std::atomic<timestamp_t> commit_ts_; // 提交时间戳
std::vector<UndoLog> undo_logs_; // 该事务生成的所有版本
std::unordered_map<table_oid_t, std::unordered_set<RID>> write_set_; // 写集
};
2. 版本号设计
const txn_id_t TXN_START_ID = 1LL << 62; // 2^62
- 事务ID 最高位为1：用于区分未提交事务（临时ID）和已提交版本（正式时间戳）
- 读时间戳 (read_ts_) =
last_commit_ts_（事务开始时的最新提交时间） - 提交时间戳 (commit_ts_) = 递增的序列号
3. 事务生命周期
3.1 Begin（事务开始）
auto TransactionManager::Begin(IsolationLevel isolation_level) -> Transaction * {
auto txn_id = next_txn_id_++; // 生成事务ID
auto txn = std::make_unique<Transaction>(txn_id, isolation_level);
txn->read_ts_.store(last_commit_ts_); // 设置读时间戳 = 最新提交时间
running_txns_.AddTxn(txn->read_ts_); // 加入运行事务集合
return txn_ref;
}
关键点：事务开始时记录 last_commit_ts_ 作为快照起点。
3.2 Commit（事务提交）
auto TransactionManager::Commit(Transaction *txn) -> bool {
timestamp_t commit_ts = last_commit_ts_.load() + 1; // 获取提交时间戳
// Serializable 隔离级别：验证可串行化
if (txn->GetIsolationLevel() == IsolationLevel::SERIALIZABLE) {
if (!VerifyTxn(txn)) { Abort(txn); return false; }
}
txn->commit_ts_ = commit_ts; // 设置提交时间戳
CommitWriteSets(txn); // 更新所有修改元组的ts_
last_commit_ts_.fetch_add(1); // 递增全局提交时间戳
txn->state_ = TransactionState::COMMITTED;
}
3.3 Abort（事务回滚）
void TransactionManager::Abort(Transaction *txn) {
// 遍历写集中的每个Tuple
for (RID rid : rids) {
auto [base_meta, base_tuple, undo_link] = GetTupleAndUndoLink(this, table, rid);
if (!undo_link.has_value()) {
// 没有前一个版本 → 是INSERT，删除该Tuple
table->UpdateTupleMeta({txn->GetReadTs(), true}, rid);
} else {
// 有前一个版本 → 恢复旧数据
auto txn_undo_log = GetUndoLog(undo_link.value());
auto reconstructed = ReconstructTuple(schema, base_tuple, base_meta, {txn_undo_log});
table->UpdateTupleInPlace({txn->GetReadTs(), false}, reconstructed.value(), rid);
}
}
}
4. 读操作（版本选择）
当读取一个 Tuple 时，系统通过 UndoLink 遍历版本链，找到满足读时间戳的最新版本。
auto GetTupleAndUndoLink(TransactionManager *txn_mgr, TableHeap *table_heap, RID rid)
-> std::tuple<TupleMeta, Tuple, std::optional<UndoLink>> {
// 1. 获取当前最新版本（TableHeap中）
auto [meta, tuple] = page->GetTuple(rid);
// 2. 获取UndoLink（指向更早版本）
auto undo_link = txn_mgr->GetUndoLink(rid);
// 3. 在执行器层面，会通过 WalkUndoLogs 遍历版本链
// 根据 read_ts_ 找到可见的版本
return std::make_tuple(meta, tuple, undo_link);
}
版本可见性规则：
- 如果版本的
ts_< 事务的read_ts_，则可见 - 如果版本的事务ID >=
TXN_START_ID（未提交事务），需要判断是否是自己
5. 写操作与版本链更新
// 更新Tuple和UndoLink原子操作
auto UpdateTupleAndUndoLink(..., RID rid, undo_link, ...) -> bool {
// 1. 获取写锁
auto page_write_guard = table_heap->AcquireTablePageWriteLock(rid);
// 2. 检查并发冲突
if (check != nullptr && !check(base_meta, base_tuple, rid, undo_link)) {
return false; // 冲突，取消更新
}
// 3. 更新Tuple数据到TableHeap
if (meta != base_meta || !IsTupleContentEqual(tuple, base_tuple)) {
table_heap->UpdateTupleInPlaceWithLockAcquired(meta, tuple, rid, page);
}
// 4. 更新UndoLink，指向之前版本
txn_mgr->UpdateUndoLink(rid, undo_link);
return true;
}
6. 垃圾回收 (GC)
void TransactionManager::GarbageCollection() {
timestamp_t watermark = running_txns_.GetWatermark(); // 最低运行事务读时间戳
// 遍历所有表的所有Tuple
for (each tuple) {
auto undo_pairs = WalkUndoLogs(this, undo_link);
// 标记不可访问的UndoLog
MarkUnaccessibleUndoLogs(meta.ts_, watermark, undo_pairs);
}
// 删除已提交且所有UndoLog都不可访问的事务
RemoveUnusedTxns();
}
7. 隔离级别支持
enum class IsolationLevel {
READ_UNCOMMITTED, // 未使用
SNAPSHOT_ISOLATION, // 快照隔离
SERIALIZABLE // 可串行化（通过 VerifyTxn 验证）
};
- SNAPSHOT_ISOLATION: 读取时基于
read_ts_构造快照 - SERIALIZABLE: 提交前调用
VerifyTxn()验证读-写冲突
8. 整体架构图
┌─────────────────────────────────────────────────────────────┐
│ TransactionManager │
│ ┌──────────────┐ ┌──────────────┐ ┌───────────────────┐ │
│ │ txn_map_ │ │ version_info_│ │ last_commit_ts_ │ │
│ │ (所有事务) │ │ (版本链) │ │ (全局时钟) │ │
│ └──────────────┘ └──────────────┘ └───────────────────┘ │
└─────────────────────────────────────────────────────────────┘
│
┌─────────────────────┼─────────────────────┐
▼ ▼ ▼
┌──────────────┐ ┌──────────────────┐ ┌──────────────────┐
│ Transaction │ │ TableHeap │ │ version_info_ │
│ - txn_id │ │ ┌────────────┐ │ │ (page_id -> │
│ - read_ts │ │ │ TupleMeta │ │ │ PrevLink) │
│ - commit_ts │ │ │ - ts_ │ │ │ │
│ - undo_logs │ │ │ - deleted │ │ └──────────────────┘
└──────────────┘ │ ├────────────┤ │
│ │ Tuple │ │
│ └────────────┘ │
└──────────────────┘
版本链: Tuple → UndoLink(prev_txn_, idx) → Transaction.undo_logs_[idx] → ... → 旧版本
关键点总结
| 特性 | 实现方式 |
|---|---|
| 版本存储 | 每个事务维护 undo_logs_ 向量 |
| 版本链 | UndoLink 链接 (txn_id, log_idx) |
| 快照读取 | 基于 read_ts_（事务开始时的 last_commit_ts_） |
| 可见性判断 | 版本 ts_ < 事务 read_ts_ |
| 写时复制 | 更新时创建新版本，原版本入 UndoLog |
| GC 机制 | 基于 watermark（最低运行事务读时间戳） |
完整示例：MVCC 全流程演示
初始状态
数据库空 TableHeap:
[空]
系统状态:
- last_commit_ts_ = 0
- 无运行事务
场景 1: 事务 T1 插入数据
T1: BEGIN() -- 事务开始
|
| txn_id = 2^62 + 1 (临时ID)
| read_ts = last_commit_ts_ = 0
|
| INSERT INTO users (id=1, name="Alice", age=30)
|
| TableHeap: [RID(0,0)]
| TupleMeta: ts_=2^62+1 (T1临时ID), is_deleted_=false
| Tuple: (id=1, name="Alice", age=30)
|
| version_info_: (page=0, slot=0) → null (无前版本)
|
| COMMIT
| commit_ts = 1
| last_commit_ts_ = 1
| 更新 TupleMeta.ts_ = 1
|
v
结果:
TableHeap[RID(0,0)]: TupleMeta{ts_=1, deleted=false}, Tuple{id=1,name=Alice,age=30}
version_info_: (0,0) → null
场景 2: T2 和 T3 并发读取 (SNAPSHOT ISOLATION)
系统状态:
- last_commit_ts_ = 1
T2: BEGIN() T3: BEGIN()
| |
| txn_id = 2^62 + 2 | txn_id = 2^62 + 3
| read_ts = 1 | read_ts = 1
| |
| SELECT * FROM users | SELECT * FROM users
| WHERE id=1 | WHERE id=1
| |
| 检查: ts=1 < TXN_START_ID ✓ |
| ts=1 <= read_ts=1 ✓ |
| 返回: Alice | 返回: Alice
| |
v v
结果: T2 和 T3 都读到 "Alice" (可见)
场景 3: T2 更新、T3 也更新 (写-写冲突)
状态: last_commit_ts_=1
T2: BEGIN() T3: BEGIN()
| |
| read_ts=1 | read_ts=1
| |
| UPDATE users | UPDATE users
| SET name='Bob' | SET name='Charlie'
| WHERE id=1 | WHERE id=1
| |
| 1. GetTupleAndUndoLink → base_meta.ts_=1
| 2. IsWriteWriteConflict:
| ts=1 < TXN_START_ID ✓
| ts=1 > read_ts=1? → 1 > 1 = false
| → 无冲突 ✓
| |
| 3. 生成 UndoLog:
| UndoLog{is_deleted=false, ts=1, tuple=Alice}
| prev_version = null
| |
| 4. UpdateTupleAndUndoLink:
| - check(): ts=1 <= read_ts=1 ✓
| - 更新 TupleMeta: ts_=2^62+2 (T2临时)
| - 更新 Tuple: name=Bob
| - 更新 version_info_: (0,0) → UndoLink(T1,0)
| |
| 1. GetTuple → base_meta.ts_=2^62+2 (T2未提交!)
| 2. IsWriteWriteConflict:
| ts=2^62+2 >= TXN_START_ID ✓
| 2^62+2 != T3.temp_ts(2^62+3) → 冲突!
| 3. txn.SetTainted()
| 4. throw ExecutionException
| → T3 Abort
结果：
TableHeap[RID(0,0)]:
TupleMeta{ts_=2^62+2, deleted=false}, Tuple{id=1,name=Bob}
version_info_: (0,0) → UndoLink(prev_txn=2^62+1, prev_log_idx=0)
T2.undo_logs_[0]: UndoLog{ts=1, tuple=Alice, is_deleted=false}
场景 4: 读自己的写
状态: T2 已提交, last_commit_ts_=2
T4: BEGIN()
|
| read_ts = 2
|
| UPDATE users SET age=25 WHERE id=1
|
| 1. GetTuple: base_meta.ts_=2 (T2提交版本)
| 2. IsWriteWriteConflict:
| ts=2 < TXN_START_ID ✓
| ts=2 > read_ts=2? → 2 > 2 = false
| → 无冲突 ✓
|
| 3. 自己的修改？
| IsSelfModification: ts=2 != T4.temp_ts(2^62+4) ✓
| → 不是自己的修改，需要生成 UndoLog
|
| 4. 生成 UndoLog:
| UndoLog{ts=2, tuple=Bob}
|
| 5. 更新: ts_=2^62+4, name=Bob, age=25
|
| 6. SELECT age FROM users WHERE id=1
|
| 检查: base_meta.ts_=2^62+4 >= TXN_START_ID ✓
| == T4.temp_ts ✓
| → 是自己的版本，直接返回
| → 返回 age=25 (自己刚写的值)
场景 5: 版本链遍历
当前状态:
TableHeap[RID(0,0)]: TupleMeta{ts_=2^62+4, deleted=false}, Tuple{id=1,name=Bob,age=25}
version_info_(0,0): UndoLink(prev_txn=2^62+2, prev_log_idx=0)
version_info_(0,0): UndoLink(prev_txn=2^62+1, prev_log_idx=0)
事务undo_logs:
T1(2^62+1): [] (已提交)
T2(2^62+2): [UndoLog{ts=1, tuple=Alice}]
T3: Aborted (无undo_logs)
T4(2^62+4): [UndoLog{ts=2, tuple=Bob}]
版本链:
[RID(0,0)] → T4版本(ts=2^62+4) → T2版本(ts=2^62+2) → T1版本(ts=1)
T5 读取快照 (read_ts=1):
T5: BEGIN()
| read_ts=1
|
| SELECT * FROM users WHERE id=1
|
| 1. GetTuple: base_meta.ts_=2^62+4 >= TXN_START_ID
| 不是自己的 → 检查 UndoLog
|
| 2. WalkUndoLogs:
| - UndoLink(T4,0): ts=2 >= TXN_START_ID, != T5.temp_ts
| → 继续遍历
| - UndoLink(T2,0): ts=2 < TXN_START_ID, ts=2 > read_ts=1
| → 继续遍历
| - UndoLink(T1,0): ts=1 <= read_ts=1 ✓ 停止
|
| 3. ReconstructTuple:
| 应用 UndoLog[T2] → Bob → UndoLog[T1] → Alice
|
| 4. 返回 Alice (快照时的值)
场景 6: 事务提交
T4: COMMIT
|
| 1. 获取 commit_ts = 3 (last_commit_ts + 1)
| 2. Serializable验证 (如需)
| 3. CommitWriteSets:
| - 更新 TupleMeta.ts_ = 3
| 4. last_commit_ts_ = 3
| 5. state = COMMITTED
| 6. 从 running_txns_ 移除
|
v
结果:
TableHeap[RID(0,0)]: TupleMeta{ts_=3, deleted=false}, Tuple{id=1,name=Bob,age=25}
version_info_(0,0): UndoLink(T2,0) → UndoLink(T1,0)
场景 7: 事务回滚 (Abort)
当前: T6 运行中, last_commit_ts_=3
T6: BEGIN()
| read_ts=3
|
| UPDATE users SET name='David' WHERE id=1
|
| 更新: TupleMeta{ts_=2^62+6}, Tuple{name=David}
| 生成 UndoLog{ts=3, tuple=Bob}
| version_info_(0,0) → UndoLink(T6,0) → UndoLink(T2,0)
|
| 某处检测到需要 Abort (如死锁)
|
| Abort():
| 遍历 write_set 中的每个 RID
|
| GetTupleAndUndoLink(RID(0,0)):
| - base_meta.ts_=2^62+6 (T6临时)
| - undo_link = UndoLink(T6,0)
|
| GetUndoLog(UndoLink(T6,0)):
| - UndoLog{ts=3, tuple=Bob}
|
| ReconstructTuple([UndoLog{ts=3, tuple=Bob}]):
| - 返回 Bob
|
| UpdateTupleInPlace:
| - TupleMeta{ts_=read_ts=3, deleted=false}
| - Tuple{name=Bob}
|
v
结果: 回滚到 T6 之前的版本
TableHeap[RID(0,0)]: TupleMeta{ts_=3}, Tuple{name=Bob,age=25}
version_info_: 清除 T6 相关的 link
场景 8: 垃圾回收 (GC)
状态:
- last_commit_ts_ = 3
- T1, T2, T4 已提交
- T3, T6 已中止
- 运行事务: T7 (read_ts=3)
GC 触发:
1. watermark = running_txns_.GetWatermark() = 3
2. 遍历 TableHeap:
RID(0,0):
- base_meta.ts_=3 (< TXN_START_ID)
- undo_link = UndoLink(T2,0)
WalkUndoLogs:
- (T2,0): UndoLog{ts=2}
ts=2 < watermark=3 → 标记为 INVALID_TS
- (T1,0): UndoLog{ts=1}
ts=1 < watermark=3 → 标记为 INVALID_TS
3. RemoveUnusedTxns:
- T1: 所有 undo_log.ts_ == INVALID_TS → 可删除 ✓
- T2: 所有 undo_log.ts_ == INVALID_TS → 可删除 ✓
- T3: 已中止，删除 ✓
- T4: 还有有效 undo_log → 保留
结果: 清理后的版本链更短，内存释放
完整流程图
┌─────────────────────────────────────────────────────────────────────────┐
│ 时间轴 │
├─────────────────────────────────────────────────────────────────────────┤
│ 0 1 2 3 4 5 6 │
│ │ │ │ │ │ │ │ │
│ │ T1 │ T2 │ T4 │ T6 │ │ │ │
│ │ INSERT │ UPDATE │ UPDATE │ UPDATE │ │ │ │
│ │ (COM) │ (COM) │ (COM) │ (ABORT)│ │ │ │
│ │ │ │ │ │ │ │ │
│ └─────────────────────────────────────────────────────────────────────┘
版本变化:
┌─────────────────────────────────────────────────────────────────────────┐
│ T1 INSERT: [ts=1] Alice │
│ ↓ │
│ T2 UPDATE: [ts=T2_temp] Bob ←undo: [ts=1] Alice │
│ ↓ │
│ T4 UPDATE: [ts=T4_temp] Bob,age=25 ←undo: [ts=2] Bob │
│ ↓ │
│ T6 UPDATE: [ts=T6_temp] David ←undo: [ts=3] Bob,age=25 │
│ ↓ │
│ T6 ABORT: [ts=3] Bob,age=25 ← (回滚) │
└─────────────────────────────────────────────────────────────────────────┘
关键机制总结
| 场景 | 核心函数 | 关键判断 |
|---|---|---|
| 快照读取 | CollectUndoLogs |
ts <= read_ts_ |
| 写冲突检测 | IsWriteWriteConflict |
ts > read_ts_ 或其他事务临时ID |
| 读自己写 | CollectUndoLogs |
ts == txn.GetTransactionTempTs() |
| 乐观更新 | check() 函数 |
并发修改检测 |
| 提交 | CommitWriteSets |
更新 ts_ = commit_ts |
| 回滚 | ReconstructTuple |
恢复到 UndoLog 保存的版本 |
| GC | MarkUnaccessibleUndoLogs |
ts < watermark |