CMU 15-445/645 (fall 2023) Project 4 CONCURRENCY CONTROL

本篇为15-445 project 4 concurrency control的总结。

23 fall是BusTub第一次引入MVOCC，在这之前并发控制使用的是2PL。MVCC也是现代数据库基本都会采用的协议，BusTub也算是与时俱进了。实验手册和代码里的注释没有之前那么的project那么保姆，在开始之前建议先过一遍PPT把MVCC复习一下。

Timestamps

task1比较简单，主要是在TransactionManager的Begin()给事务赋read_ts_，Commit()处理last_commit_ts_和在这两个函数里维护watermark。watermark指的是当前运行中的事务里最小的read_ts_，因为维护比最小的read_ts_还要小的历史版本没有意义，所以知道watermark后我们就能对无用的历史版本进行GC了。在watermark的实现里可以用std::map来存current_reads_，这样就能利用map的有序性来直接获取最小的read_ts_。

Storage Format and Sequential Scan

从这里开始我们就需要弄清楚BusTub是怎样存历史数据的了。BusTub对MVCC做了简化，并不会将历史记录持久化到磁盘上，数据会存储在三个位置中：

1. Table_heap: 最新的数据总是在table_heap中；
2. TransanctionManager: 存储了table_heap中元组上一次修改的指针；
3. Transaction: 存储了该事务修改过的元组的历史版本（Undo_log）。

Tuple reconstruction比较简单，只需要根据入参对元组进行相应的拼装即可，相信这对于已经完成project 3执行算子的你来说不是难事。重写seqscan executor就复杂一点，需要清楚共有几种情况：

1. tuple.ts_ == txnId: 说明这个元组被改事务修改过，直接返回该元组；
2. tuple.ts <= txn.read_ts_: 按之前逻辑正常进行读取；
3. 不符合上述两种情况则要reconstruct tuple。

如何找到元组的undo_log呢？调用TxnManagerGetUndoLog方法根据元组的RID获得上一次修改所在的事务和undo_link，则可以顺理成章的拿到第一个undo_log了，这里注意我们要获得 >= txn.read_ts_的所有undo_log作为reconstruct的参数。这里transanction, undo_link和undo_log的关系比较复杂，看一看看测试用例是怎么写的会比较有帮助。

MVCC Executors

Insert executor比较简单，因为是刚插入的元组，所以不会有上一次的修改记录，undolink设为nullopt就行，插入完记得更新write set。Commit中我们只需要更新修改过的tuple的ts为commit_ts就行。

在开始接下来的任务前，首先应该完成TxnMgrDbg()这个辅助函数，这将很好的帮助理解每个txn是如何对un_log和undo_link操作的。注释里的样例就是测试用例的标准输出，可以通过执行测试用例来确定自己写的辅助函数是否正确。

在开始update或者delete前，我们需要先检测之前该事务是否已经修改过此元组，如果已经修改过就直接更新undo_log，如果是刚插入的元组则什么都直接更新table_heap里的元组就行。然后我们需要确定是否存在写写冲突。写写冲突有如下情况：

1. 事务 A 尝试更新 tuple 时，发现 tuple 的最新 timestamp 属于另一个 uncommitted 的事务B
2. 事务 A 尝试更新 tuple 时，发现 tuple 的最新 timestamp 属于另一个 committed 的事务B，且 B commited timestamp > A read timestamp

实验手册里写的很清楚，我就不翻译了。

Let us go through the above example. In case (1), txn10 deletes the (A, 2) tuple and has not committed yet. Txn9 can still read an old version of the tuple (A, 2) because the read timestamp is 3.In this case, if txn9 needs to update / delete the tuple, it should be aborted with a write-write conflict In case (2), if any other transactions try to update / delete this tuple, they will be aborted. In case (3), there is another transaction that updates (C, 2) to (C, 4) and the commit timestamp is set to 4. Txn9 can read an old version of the tuple (C, 2), but it should be aborted when update / delete the (C, 4) tuple, because there is a newer update that happens after the transaction read timestamp.

两者的逻辑其实大差不差，我是直接在excution_common里写了一个Modify函数共用了许多逻辑。

GC只会在没有事务进行时发生，所以就不需要考虑得很复杂。根据watermark遍历txn和undo_log把无用的数据清楚就好了。

Primary Key Index

Insert根据实验手册说的一步一步写就行。因为忙着做毕设，之后的实验我就听取实验手册的警告没有继续往后写了，前面的区域以后再来探索吧（误

总结

写BusTub确实过瘾，再次感谢CMU DB group能把制作如此精良的project开放给所有人，感恩！