4 min read

CMU 15-445/645 fall2024 p4

15445 C++DataBaseMVCCConcurrency Control

在服务器内按 bustub 文档完成环境配置后，P4 主要完成了并发控制与多版本执行链路：事务时间戳分配、Undo Log 版本链、可见性重建、写写冲突处理、Serializable 校验和垃圾回收。和 P0/P1/P2/P3 一样，public 指模板仓库远程，origin 指我自己的远程仓库，日常开发在本地仓库完成。

Git 命令

git pull public master # 拉取模板更新
git push origin main   # 推送本地提交

transaction.h（事务状态与版本元数据）

transaction.h 补齐了 P4 需要的事务内数据结构与接口：

  • src/include/concurrency/transaction.h:129 的 AppendUndoLog 负责追加版本日志并返回 UndoLink。
  • src/include/concurrency/transaction.h:135 的 AppendWriteSet 记录事务写集合（后续提交/回滚使用）。
  • src/include/concurrency/transaction.h:142 的 AppendScanPredicate 记录 Serializable 下的扫描谓词。
  • src/include/concurrency/transaction.h:147 的 GetScanPredicates 为提交阶段冲突校验提供读取入口。

watermark.h / watermark.cpp（读时间戳水位线）

Watermark 负责跟踪系统内最小活跃读时间戳：

  • src/include/concurrency/watermark.h:26 定义 Watermark 结构，维护 commit_ts_、watermark_ 和活跃读集合。
  • src/include/concurrency/watermark.h:49 使用 std::map<timestamp_t, int> 维护读时间戳计数。
  • src/concurrency/watermark.cpp:19 的 AddTxn 在事务开始时登记 read_ts。
  • src/concurrency/watermark.cpp:28 的 RemoveTxn 在事务结束时移除并更新当前水位线。

execution_common.h / execution_common.cpp（MVCC 公共逻辑）

P4 的执行器与事务管理共用逻辑集中在 execution_common：

  • src/include/execution/execution_common.h:49、src/execution/execution_common.cpp:30 提供 NextBatch 兼容层。
  • src/execution/execution_common.cpp:211 的 ReconstructTuple 根据 base tuple + undo logs 重建可见版本。
  • src/execution/execution_common.cpp:252 的 CollectUndoLogs 收集对当前事务可见的版本链。
  • src/execution/execution_common.cpp:296 的 GenerateNewUndoLog 生成首次修改时的 undo 记录。
  • src/execution/execution_common.cpp:342 的 GenerateUpdatedUndoLog 合并同事务重复修改，避免冗余版本。

transaction_manager.h / transaction_manager.cpp（P4 核心）

TransactionManager 是 P4 主体：

  • src/concurrency/transaction_manager.cpp:59 的 Begin 分配事务 ID，并设置 read_ts/commit_ts。
  • src/concurrency/transaction_manager.cpp:75 的 VerifyTxn 执行 Serializable 校验（基于扫描谓词与提交后写集合）。
  • src/concurrency/transaction_manager.cpp:176 的 Commit 串行化提交，写回最终 commit_ts。
  • src/concurrency/transaction_manager.cpp:227 的 Abort 回滚当前事务的写入并恢复版本链。
  • src/concurrency/transaction_manager.cpp:267 的 GarbageCollection 执行 stop-the-world 清理。
  • src/include/concurrency/transaction_manager.h:102 的 UpdateTupleAndUndoLink 与 src/include/concurrency/transaction_manager.h:111 的 GetTupleAndUndoLink 提供原子读写辅助接口。

MVCC 执行器改造（Scan / DML）

执行器层按 MVCC 语义处理可见性和冲突：

  • src/execution/seq_scan_executor.cpp:31、src/execution/seq_scan_executor.cpp:57：顺序扫描中收集谓词并按版本链重建可见 tuple。
  • src/execution/index_scan_executor.cpp:35、src/execution/index_scan_executor.cpp:79：索引扫描回表后同样进行可见性判断。
  • src/execution/insert_executor.cpp:62：插入路径处理主键冲突、版本继承与 undo 生成。
  • src/execution/delete_executor.cpp:62：删除路径写入 tombstone 语义并维护索引一致性。
  • src/execution/update_executor.cpp:62：更新路径覆盖“原地更新”和“主键变更导致 delete+insert”两类流程。

可串行化与冲突处理

P4 的关键行为在于“能并发 + 不破坏隔离级别”：

  • src/concurrency/transaction_manager.cpp:40 的 MatchesPredicate 用于谓词命中判断。
  • src/concurrency/transaction_manager.cpp:116 开始按表逐 RID 校验读写冲突。
  • src/concurrency/transaction_manager.cpp:147 对读时间戳之后提交的版本执行冲突检测。
  • src/concurrency/transaction_manager.cpp:189 在 Commit 阶段启用 Serializable 验证，不满足则中止提交。

生成提交包

  1. 自动打包（按 CMakeLists.txt:380 的 P4_FILES，通过 CMakeLists.txt:395 的 submit-p4 目标生成）

cmake —build build —target submit-p4

  1. 生成并写入签名文件

python3 gradescope_sign.py

  1. 检查提交包内容

unzip -l project4-submission.zip